یک طرح تسهیم راز مقاوم در برابر تقلب مبتنی بر گراف

طرح تسهیم راز آستانه­ای امکان تسهیم یک راز را در میان تعدادی از اعضا، به­نام شرکت­کنندگان، با ارائه سهم­هایی به آنان فراهم می­­سازد. بازیابی راز تنها به کمک تعداد مشخص از سهم­ها امکان­پذیر است. بازیابی درست راز در این طرح­ها منوط به رفتار درست شرکت­کنندکان است. اما در دنیای واقعی ممکن است برخی از شرکت­کنندگان تلاش کنند سهم­های نادرستی ارائه دهند، که تقلب نام دارد. یک طرح تسهیم راز مقاوم این امکان را فراهم می­کند که با حضور تعدادی متقلب هم­چنان راز به­درستی بازیابی شود. در این مقاله طرح تسهیم راز مقاومی ارائه می­شود که با وجود تعداد بیشینه ممکن از شرکت­کنندگان متقلب، راز به درستی بازیابی شود. در این طرح برای متقلب­ها توانایی­های زیادی در نظر می­گیریم. آنان می­توانند سهم­های خود را متناسب با سهم­های سایرین تغییر دهند و با یکدیگر ارتباط داشته باشند تا بهترین شیوه­ را برای تقلب به­کارگیرند. این طرح امکان شناسایی و حذف متقلب­ها را به کمک یک گراف جهت­دار فراهم می­سازد و نسبت به طرح­های پیشین از پیچیدگی کمتری برای بازیابی راز برخوردار است. در عین حال دارای طول سهم­ کمتری نسبت به طرح­های موجود است، که به کاهش سربار مخابراتی طرح می­انجامد. به این ترتیب، طرح تسهیم راز پیشنهادی از دو جنبه پیچیدگی بازیابی راز و طول سهم از کارآیی بیشتری نسب به طرح­های موجود برخوردار است.