الگوریتم رمزنگاری مشهور ارتقا پیدا می کند | مجله کوانتا

در زندگی دیجیتالی ما، امنیت به رمزنگاری بستگی دارد. یک پیام خصوصی بفرستید یا صورتحساب را به صورت آنلاین پرداخت کنید، و شما به الگوریتم هایی که برای مخفی نگه داشتن داده های خود طراحی شده اند تکیه می کنید. به طور طبیعی، برخی از مردم می‌خواهند این اسرار را فاش کنند - بنابراین محققان تلاش می‌کنند تا قدرت این سیستم‌ها را آزمایش کنند تا مطمئن شوند که به دست یک مهاجم باهوش از بین نمی‌روند.

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

در طول سال‌ها، محققان انواع LLL را برای عملی‌تر کردن این رویکرد - اما فقط تا حدی، تقویت کرده‌اند. اکنون، یک جفت رمزنگار الگوریتم جدیدی به سبک LLL ساخته اند که کارایی آن را افزایش می دهد. تکنیک جدید، که برنده شد جایزه بهترین مقاله در کنفرانس بین المللی رمز شناسی 2023، دامنه سناریوهایی را گسترش می دهد که در آن دانشمندان کامپیوتر و ریاضیدانان می توانند به طور عملی از رویکردهای LLL مانند استفاده کنند.

گفت: "این واقعا هیجان انگیز بود." کریس پیکرت، یک رمزنگار در دانشگاه میشیگان که در این مقاله دخالتی نداشت. او گفت که این ابزار برای دهه ها کانون مطالعه بوده است. "همیشه خوب است که هدفی که برای مدت طولانی روی آن کار شده است ... نشان می دهد که هنوز شگفتی هایی وجود دارد."

الگوریتم‌های نوع LLL در دنیای شبکه‌ها عمل می‌کنند: مجموعه‌ای بی‌نهایت از نقاط با فاصله منظم. به عنوان یکی از راه‌های تجسم این موضوع، تصور کنید که در حال کاشی کاری کف هستید. می توانید آن را با کاشی های مربعی بپوشانید و گوشه های آن کاشی ها یک شبکه را تشکیل می دهند. از طرف دیگر، می توانید شکل کاشی متفاوتی را انتخاب کنید - مثلاً یک متوازی الاضلاع طولانی - برای ایجاد یک شبکه متفاوت.

یک شبکه را می توان با استفاده از "پایه" آن توصیف کرد. این مجموعه ای از بردارها (در اصل، لیست اعداد) است که می توانید آنها را به روش های مختلف ترکیب کنید تا هر نقطه از شبکه را بدست آورید. بیایید یک شبکه با پایه متشکل از دو بردار را تصور کنیم: [3، 2] و [1، 4]. شبکه فقط تمام نقاطی است که می توانید با جمع و تفریق کپی هایی از آن بردارها به آن برسید.

آن جفت بردار تنها مبنای شبکه نیست. هر شبکه با حداقل دو بعد، بی نهایت پایه های ممکن دارد. اما همه پایه ها یکسان ایجاد نمی شوند. پایه‌ای که بردارهای آن کوتاه‌تر و به زوایای قائم‌تر با یکدیگر نزدیک‌تر هستند، معمولاً کار با آن‌ها آسان‌تر و برای حل برخی مسائل محاسباتی مفیدتر است، بنابراین محققان آن پایه‌ها را «خوب» می‌نامند. یک مثال از این جفت بردار آبی در شکل زیر است. پایه های متشکل از بردارهای بلندتر و کمتر متعامد - مانند بردارهای قرمز - را می توان "بد" در نظر گرفت.

این یک کار برای LLL است: به آن (یا برادرانش) مبنایی از یک شبکه چند بعدی بدهید، و شبکه بهتری را بیرون می دهد. این فرآیند به عنوان کاهش پایه شبکه شناخته می شود.

همه اینها چه ربطی به رمزنگاری دارد؟ به نظر می رسد که وظیفه شکستن یک سیستم رمزنگاری می تواند، در برخی موارد، به عنوان یک مشکل دیگر بازنگری شود: پیدا کردن یک بردار نسبتا کوتاه در یک شبکه. و گاهی اوقات، آن بردار را می توان از پایه کاهش یافته تولید شده توسط یک الگوریتم سبک LLL برداشت. این استراتژی به محققان کمک کرده است تا سیستم‌هایی را که در سطح ظاهراً ارتباط چندانی با شبکه‌ها ندارند، سرنگون کنند.

از لحاظ نظری، الگوریتم LLL اصلی به سرعت اجرا می‌شود: زمان اجرا به صورت نمایی با اندازه ورودی مقیاس نمی‌شود - یعنی ابعاد شبکه و اندازه (به بیت) اعداد در بردارهای پایه اما به عنوان یک تابع چند جمله‌ای افزایش می‌یابد، و گفت: «اگر واقعاً بخواهید این کار را انجام دهید، زمان چندجمله‌ای همیشه چندان امکان‌پذیر نیست». لئو دوکاس، رمزنگار در موسسه ملی تحقیقاتی CWI در هلند.

در عمل، این بدان معنی است که الگوریتم LLL اصلی نمی تواند ورودی های خیلی بزرگ را مدیریت کند. گفت: «ریاضی‌دانان و رمزنگاران توانایی انجام کارهای بیشتری را می‌خواستند کیگان رایان، دانشجوی دکترا در دانشگاه کالیفرنیا، سن دیگو. محققان برای بهینه‌سازی الگوریتم‌های سبک LLL تلاش کردند تا ورودی‌های بزرگ‌تر را در خود جای دهند و اغلب به عملکرد خوبی دست می‌یابند. با این حال، برخی از وظایف سرسختانه دور از دسترس باقی مانده اند.

مقاله جدید که توسط رایان و مشاورش نوشته شده است، نادیا هنینگر، چندین استراتژی را برای بهبود کارایی الگوریتم سبک LLL خود ترکیب می کند. برای یک چیز، این تکنیک از یک ساختار بازگشتی استفاده می کند که کار را به قطعات کوچکتر تقسیم می کند. برای دیگری، الگوریتم به دقت دقت اعداد درگیر را مدیریت می کند و تعادلی بین سرعت و نتیجه صحیح پیدا می کند. کار جدید این امکان را برای محققان فراهم می‌کند که پایه‌های شبکه‌هایی با هزاران ابعاد را کاهش دهند.

کار گذشته از رویکرد مشابهی پیروی کرده است: الف مقاله 2021 همچنین مدیریت بازگشتی و دقیق را برای کار سریع شبکه های بزرگ ترکیب می کند، اما فقط برای انواع خاصی از شبکه ها کار می کند و نه همه مواردی که در رمزنگاری مهم هستند. الگوریتم جدید در محدوده بسیار وسیع تری به خوبی رفتار می کند. گفت: "من واقعا خوشحالم که کسی این کار را انجام داد." توماس اسپیتو، محقق رمزنگاری در شرکت PQShield و نویسنده نسخه 2021. او گفت که کار تیم او "اثباتی از مفهوم" را ارائه کرد. نتیجه جدید نشان می دهد که "شما می توانید کاهش شبکه بسیار سریع را به روشی صحیح انجام دهید."

تکنیک جدید در حال حاضر شروع به کارکردن کرده است. اورل پیجریاضیدان مؤسسه تحقیقاتی ملی فرانسه اینریا گفت که او و تیمش اقتباسی از الگوریتم را برای کار روی برخی از وظایف تئوری اعداد محاسباتی قرار داده‌اند.

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

کوانتوم در حال انجام یک سری نظرسنجی برای ارائه خدمات بهتر به مخاطبانمان است. ما را بگیر نظرسنجی خواننده علوم کامپیوتر و شما برای برنده شدن رایگان وارد خواهید شد کوانتوم کالا