تحلیل الگوریتم BKZ در حملات علیه رمزنگاری های مبتنی بر مشبکه و ارائه یک روش جدید

با گسترش رایانش کوانتومی، رمزنگاری مبتنی بر مشبکه به یکی از مهم ترین گزینه های رمزنگاری پساکوانتومی تبدیل شده است. امنیت بسیاری از این سامانه ها بر مسئله یادگیری با خطا (LWE) استوار است که تحلیل امنیت آن ها عمدتا از طریق حملات Primal و کاهش پایه مشبکه انجام می شود. الگوریتم BKZ به عنوان روش استاندارد کاهش پایه، در ابعاد بالا با افزایش چشمگیر زمان اجرا و هزینه محاسباتی مواجه است. در این مقاله، الگوریتم OL-BKZ به منظور بهبود کارایی BKZ ارائه می شود. در روش پیشنهادی، کاهش پایه به صورت محلی و در پنجره های هم پوشان انجام شده و برای افزایش پایداری عددی، الگوریتم LLL بین پنجره ها و در پایان فرآیند اعمال می شود. الگوریتم پیشنهادی بر روی مجموعه ای از نمونه های LWE با پارامترهای مختلف پیاده سازی و با BKZ کلاسیک مقایسه شده است. نتایج تجربی نشان می دهد که OL-BKZ ضمن حفظ کیفیت قابل قبول کاهش پایه، زمان اجرا را به طور قابل توجهی کاهش می دهد؛ به طوری که در یکی از آزمایش ها زمان اجرا از ۱.۰۵ ثانیه به ۰.۲۲ ثانیه کاهش یافته است. این نتایج نشان می دهد که OL-BKZ روشی کارآمد و مقیاس پذیر برای تحلیل امنیت رمزنگاری های مبتنی بر مشبکه، به ویژه در ابعاد بالا، است.

کلیدواژه ها:

رمزنگاری مبتنی بر مشبکه ، مسئله یادگیری با خطا ، کاهش پایه مشبکه (LWE) ، الگوریتم BKZ