بخشی از مقاله
چکیده
در این مقاله دو الگوریتم کارا بر اساس پایه گروبنر برای به اشتراک گذاری اطلاعات مهم مورد بررسی قرار می گیرند . هدف آن است که هر الگوریتمی که باعث کاهش فضای ذخیره سازی می شود ، مورد استفاده قرار گیرد . در این الگوریتم ها از طرح آستانه ای تسهیم راز استفاده می شود .
-1 معرفی
طرح تسهیم راز از ابتدا توسط شامیر[1] و بلکلی[2] پیشنهاد شد . آنها در 1979 با ارائه ی این طرح پاسخ عملی به پرسش لیو دادند . فرض کنید 11 دانشمند بر روی یک پروژه محرمانه مشغول به کار هستند و می خواهند نتایج تحقیقات خود را در یک مکان امن نگهداری کنند به طوری که درب این مکان تنها با حضور حداقل 6 نفر از آن ها باز شود . کمترین تعداد قفل های مورد نیاز چقدر است ؟ کمترین تعداد کلیدهای لازم برای هر یک از نویسنگان چقدر است ؟
می توان نشان داد که حداقل قفل های مورد نیاز 462 و حداقل تعداد کلید ها نیز برای هریک از دانشمندان 252 عدد است . کاملا مشخص است که نگهداری این تعداد قفل و کلید برای دانشمندان غیر عملی است به ویژه وقتی تعداد دانشمندان زیاد شود عملا تعداد قفل ها و کلیدها نیز بسیار زیاد خواهد شد . تسهیم راز به زبان ساده یعنی به اشتراک گذاشتن مقداری تحت عنوان راز - اطلاعات محرمانه - در میان افرادی به نام سهامدار به نحوی که هرگاه زیرمجموعه های معینی از آنها جمع شده و سهم خود را به اشتراک می گذارند قادر به یافتن راز باشند اما سایر زیرمجموعه ها این توانایی را نداشته باشند . حال مدل سازی ریاضی آن را می نویسیم.
فرض کنید n} i {Pi : 1 P مجموعه ای متشکل از n سهامدار، S فضای راز - مجموعه تمام رازهای ممکن - و S i فضای سهم - مجموعه ای از تمام سهم های ممکن - سهامدار Pi باشد. یک طرح تسهیم راز عبارت است از عبارت است از روشی جهت به اشتراک گذاشتن مقدار محرمانه - راز - S i si در میان اعضای مجموعه ی . P در این روش هر سهامدار Pi P یک سهم S i si را از شخصی به عنوان مقسم که خود عضو مجموعه P نیست به صورت محرمانه دریافت می کند به نحوی که تنها زیرمجموعه های معینی از سهامداران که زیرمجموعه های مجاز یا مجموعه های دسترسی نامیده می شوند ، قادر باشند با به اشتراک گذاشتن سهم های خصوصی خود راز s را بازیابی کنند .
حال اگر k تعداد اعضای زیرمجموعه ی مجاز یا مجموعه ی دسترسی بدانیم آنگاه . k n یعنی اگر k عضو از مجموعه ی مجاز سهم های خود را به اشتراک بگذارند قادر به بازیابی راز خواهند بود و هر L k نمی تواند هرگز راز را بازیابی کند. به این طرح ، تسهیم راز - - k , n گویند. در این مقاله دو روش مربوط به تسهیم راز با استفاده از پایه گروبنر مورد بررسی قرار گرفته می شوند. در طرح پیشنهادی وانگ سهم ها با n 1 چند جمله ای دو متغیره توزیع می شوند. اما می توان چندجمله ای ها را به n کاهش داد تا فضای حافظه ی کمتری مورد استفاده قرار گیرد. هر دو طرح در ادامه ارائه می شوند. در قسمت بعد مقدمات پایه گروبنر توضیح داده می شود.
