Journal title
عنوان نشریه
Quarterly Journal of Science Kharazmi University
Literature & Humanities
http://jsci.khu.ac.ir
1
admin
doi
fa
jalali
1393
4
1
gregorian
2014
7
1
14
2
online
1
fulltext
fa
بررسی و تعیین پیچیدگی بهینه ساختارهای دسترسی دوبخشی
Determining the Optimal Complexity of Bipartite Access Structures
علوم پایه
Science
علمی پژوهشی بنیادی
S
در یک طرح تقسیم راز دوبخشی، مجموعه سهام¬داران را به دو قسمت چنان تقسیم می¬کنند که همه سهام¬داران درون یک بخش، نقش یکسانی را بازی کنند. پادرو و سائز ساختارهای دسترسی ایده¬آل دو بخشی را به طور کامل دسته بندی کرده¬اند اما اینکه کدام ساختارهای دسترسی غیرایده¬آل پیچیدگی بهینه دارند همچنان نامعلوم است. از طرفی مشخص کردن پیچیدگی ساختارهای دسترسی در حالت کلی، یکی از بزرگترین مسائل حل نشده در بحث تقسیم راز است. به این منظور و در راستای بررسی پیچیدگی، ما خودمان را به ساختارهای دسترسی دو بخشی محدود می¬کنیم تا روش جدیدی برای محاسبه کران¬هایی روی پیچیدگی بهینه این گونه ساختارها بدست آوریم. در این مقاله با استفاده از ارتباط طرح¬های تقسیم راز و پلی¬ماتریدها، برای پیچیدگی هر ساختار دسترسی دوبخشی، از یک مساله برنامه¬ریزی خطی استفاده می¬کنیم تا یک کران پایین روی پیچیدگی هر ساختار دسترسی ارائه دهیم. ساختارهای دسترسی که ما در این مقاله بررسی کرده¬ایم محدودیتی در تعداد سهام¬داران شرکت کننده در طرح ندارند. به علاوه در این مقاله نشان خواهیم داد که برخی از کران¬های پایین ارائه شده بر روی پیچیدگی این ساختارهای دسترسی دقیق هستند. در آخر طرح¬های بهینه جدیدی را بر روی ساختارهای دسترسی دوبخشی خاص ارائه خواهیم داد.
Determining the Optimal Complexity of Bipartite Access Structures<br><br>Abbas Cneraghi <br><br>Abstract<br><br>Keywords: Complexity, Secret Sharing Scheme, Access structure.<br><br><br><br>In a bipartite secret sharing scheme, the set of participants is divided into two parts, and all participants in each part play an equivalent role. The ideal bipartite access structures were characterized by Padro and Saez, but it is not known which is the optimal information rate of non ideal bipartite access structures. Determining the optimal complexity of general access structures is one of the major problems in secret sharing. We study this open problem restricted to the bipartite access structures, obtaining a new method to compute bounds on the optimal complexity. Namely, by using the connection between secret sharing schemes and polymatroids, we show a linear programming problem that determines, for each access structure, a lower bound on the complexity. Moreover, we show new optimal constructions for certain bipartite access structures.
پیچیدگی , طرح تقسیم راز , ساختار دسترسی ,
Complexity , Secret Sharing Scheme , Access structure ,
97
114
http://jsci.khu.ac.ir/browse.php?a_code=A-10-837-1&slc_lang=fa&sid=1
Abbas
Cheraghi
عباس
چراغی
acheraghi78@yahoo.com
1003194753284600113
1003194753284600113
Yes
Assistant professor
هیات علمی استادیار