چکیده:
تسهیم راز، یعنی به اشتراک گذاشتن داده محرمانه میان تعدادی شرکتکننده، بهطوریکه زیرمجموعههای مشخصی (مجاز) از آنها قادر به بازیابی آن داده، باشند ولی زیرمجموعههای غیرمجاز قادر به بازیابی اطلاعات مرتبط با آن نباشند. روشهای متعدد برای تسهیم راز ارائه شده است. از جمله این روشها، تسهیم راز مبتنیبر مجموعه احاطهگر و احاطهگر یالی است. در روش مبتنی بر احاطهگر یالی، نیاز است که تمام مجموعههای احاطهگر یالی برای گراف بهدست آید. یافتن تمام مجموعههای احاطهگر یالی برای گراف یک مسئله NP-کامل است. بهسادگی میتوان تمام مجموعههای احاطهگر یالی یک گراف داده شده را با استفاده از تجزیه درختی گراف آن و الگوریتم برنامهنویسی پویا بهدست آورد. ساخت تجزیه درختی یک گراف با عرض درختی محدود، از زمان چندجملهای است. اما در حالت کلی محاسبه عرض درختی و ساختن تجزیه درختی با حداقل عرض، یک مسئله NP-کامل است. هدف ما در این مقاله، استفاده از الگوریتم رقابت استعماری برای ساخت تجزیه درختی گرافها است که میتواند بهصورت موازی پیادهسازی شود. بنابراین، روش پیشنهادی علاوهبر این که روش نوینی برای پیادهسازی طرح تسهیم راز است، میتواند زمان اجرارا در حالت موازی تا 5% کاهش دهد.
Secret sharing refers to methods of distributing a secret amongst a group of participants, each of whom is assigned with a share of the secret. The secret can be reconstructed only when a sufficient number, of possibly different types of shares are combined together. Different secret sharing methods have been presented, such as secret sharing schemes based on dominating set and edge dominating set. In edge dominating set method, it is required that all of the edge dominating sets are obtained for the graph, which is a NP-complete problem. All of the edge dominating sets can be easily obtained, using tree decomposition of the graph and dynamic programming. Although generating tree decomposition of a graph with finite treewidth can be solved in polynomial time, but it is shown to be NP-complete for general graphs. In this paper, to generate tree decompositions of general graphs, we use the notion of Imperialist Competitive Algorithm (ICA) which can be applied in parallel. Therefore, the proposed method, in addition to being a new method for implementation of the secret sharing scheme, can reduce runtime by up to five percent in parallel.
خلاصه ماشینی:
هدف ما در این مقاله، استفاده از الگوریتم رقابت استعماري برای ساخت تجزیه درختی گرافها است که میتواند بهصورت موازی پیادهسازی شود.
كليدواژهها: 1- مقدمه تسهیم راز، مجموعه احاطهگر یالی، تجزیه درختی و الگوریتم رقابت استعماري دانش رمزنگاری با امنیت اطلاعات در ارتباط است.
تحقیقات نشان داده است براي حل مسئلههايNP-کامل روي گرافهایی با عرض درختی ثابت، الگوریتم زمان چندجملهاي وجود دارد.
در این روش نیاز است ابتدا یک تجزیه درختی برای گراف ورودی ایجاد شود و سپس براي هر یک از گرههاي تجزیه درختی یک جواب جزئی بهدست میآید و با پیمایش پایین به بالاي تجزیه درختی، جواب نهایی در ریشه یافت خواهد شد [10].
ابتدا با استفاده از الگوریتم رقابت استعماري یک تجزیه درختی برای گراف ورودی ایجاد میشود.
در مرحله دوم، با استفاده از الگوریتم تولید مجموعه احاطهگر مخلوط در [4] و با در نظر گرفتن فقط پوشش یالی در مراحل اجرای الگوریتم،مجموعه احاطهگریالی متناظر با تجزیه درختی داده شده در زمان چندجملهای محاسبه میکنیم.
(رجوع شود به تصوير صفحه) الگوریتم 1: الگوریتم تسهیم راز مبتنیبر احاطهگر یالی با استفاده از الگوریتم رقابت استعماري 3-1- امنیت و مزیت طرح امنیت این ساختار مبتنی بر امنیت تسهیم راز آل- سیدی است که بر اساس نرخ اطلاعات تعیین میگردد.
این الگوریتم از رقابت بین امپراتوريها برايتصاحب مستعمرهها الهام گرفته شده است.
از اینرو، در این پژوهش با استفاده از الگوریتم رقابت استعماری روشی جهت بهدست آوردن عرض درختی گراف مفروض ارائه گردیده است که یک پیشپردازش جهت ساخت سیستم تسهیم راز است.
Bodlaender, “A linear-time algorithm for finding tree-decompositions of small treewidth,” SIAM Journal on computing, vol.