ترفندهای رمزنگاری مشکل را کمی آسان تر می کند | مجله کوانتا

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

به گفته محققان، مدت‌هاست که آیا واقعاً چنین است یا خیر راهول ایلانگو، یک دانشجوی فارغ التحصیل در حال مطالعه نظریه پیچیدگی در موسسه فناوری ماساچوست. "می توانید بپرسید، "آیا مشکلاتی وجود دارد که حدس و بررسی برای آنها بهینه است؟"

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

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

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

تعریف سختی

نتایج جدید آخرین موردی است که برای اولین بار در اتحاد جماهیر شوروی، قبل از ظهور نظریه پیچیدگی، مورد بررسی قرار گرفت. آلندر گفت: «قبل از اینکه من در کلاس ابتدایی باشم، مردم روسیه این را تدوین می کردند.

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

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

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

در سال 1959، یک محقق برجسته به نام سرگئی یابلونسکی ادعا کرد که ثابت کرده است که جستجوی جامع واقعاً تنها راه حل مشکل حداقل اندازه مدار است. اما اثبات او خلأهایی ایجاد کرد. برخی از محققان در آن زمان متوجه نقص‌ها شدند، اما یابلونسکی به اندازه‌ای تأثیرگذار بود که بسیاری دیگر را از کار روی سؤال perebor منصرف کرد.

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

ترافیک یک طرفه

رمزنگاری مدرن از مشکلات محاسباتی سختی برای محافظت از پیام های مخفی استفاده می کند. اما سختی محاسباتی تنها زمانی مفید است که نامتقارن باشد – اگر رمزگشایی پیام‌های کدگذاری شده سخت باشد اما رمزگذاری پیام‌ها در وهله اول سخت نباشد.

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

آلندر گفت: «رمز نگاران واقعاً دوست دارند توابع یک طرفه قابل محاسبه بسیار بسیار کارآمدی داشته باشند که وارونه کردن آنها واقعاً بسیار دشوار است. به نظر می رسد بسیاری از توابع ریاضی این ویژگی را دارند و دشواری معکوس کردن این توابع از دشواری ظاهری حل مسائل محاسباتی مختلف ناشی می شود.

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

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

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

ساخت بر روی ساختارهای داده

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

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

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

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

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

پس از موفقیت پاس و لیو در سال 2020، این نتایج قدیمی ناگهان به تازگی مرتبط شدند. الگوریتم Fiat-Naor می تواند توابع دلخواه را سریعتر از جستجوی جامع معکوس کند. آیا می تواند برای مشکلات فشرده سازی نیز کار کند؟

خارج از یونیفرم

اولین محققی که این سوال را مطرح کرد نظریه پرداز پیچیدگی بود راهول سانتانام از دانشگاه آکسفورد و دانشجوی کارشناسی ارشدش هانلین رن. آنها این کار را در یک مقاله 2021 ثابت می کند که مشکلات فشرده سازی و وارونگی عملکرد حتی بیشتر از آنچه محققان تصور می کردند در هم تنیده بودند.

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

نتایج آنها پیامدهای متفاوتی برای دو دسته گسترده از الگوریتم‌هایی داشت که محققان اغلب مطالعه می‌کنند، به نام‌های الگوریتم‌های «یکنواخت» و «غیر یکنواخت». الگوریتم‌های یکنواخت برای هر ورودی از رویه یکسانی پیروی می‌کنند - برای مثال، یک برنامه یکسان برای مرتب‌سازی فهرست‌های اعداد، چه 20 ورودی در لیست یا 20,000 ورودی وجود داشته باشد، به همین ترتیب عمل می‌کند. الگوریتم های غیریکنواخت در عوض از رویه های متفاوتی برای ورودی های با طول های مختلف استفاده می کنند.

ساختارهای داده مورد استفاده توسط الگوریتم Fiat-Naor همیشه برای یک تابع خاص تنظیم می شوند. برای معکوس کردن تابعی که یک رشته 10 بیتی را درهم می‌زند، به ساختار داده‌ای متفاوت با ساختار داده‌ای نیاز دارید که برای معکوس کردن تابعی که یک رشته 20 بیتی را درهم می‌زند، متفاوت باشد، حتی اگر درهم‌سازی به روشی مشابه انجام شود. این باعث می شود که Fiat-Naor یک الگوریتم غیریکنواخت باشد.

نتایج Santhanam و Ren نشان داد که ممکن است بتوان الگوریتم Fiat-Naor را به الگوریتمی برای حل مشکلات فشرده سازی تبدیل کرد. اما تطبیق الگوریتم از یک مسئله به مشکل دیگر ساده نبود و آنها این سوال را بیشتر دنبال نکردند.

پاس یک سال بعد، پس از شنیدن سخنرانی فیات در مورد الگوریتم کلاسیک در کارگاهی که مشارکت ناور در رمزنگاری را جشن می‌گرفت، به همین ایده رسید. او گفت: «این ایده برای استفاده از وارونگی تابع از آن زمان در ذهن من بود. او بعداً با محقق دانشگاه تل آویو شروع به کار روی این مشکل کرد نوام مازور.

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

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

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

وارونگی همگرایی

اثبات جدید برای الگوریتم های غیریکنواخت یک سوال طبیعی را مطرح می کند: الگوریتم های یکنواخت چطور؟ آیا راهی برای حل مشکلات فشرده سازی سریعتر از جستجوی جامع با استفاده از آنها وجود دارد؟

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

سانتانام گفت: "من بسیار شگفت زده خواهم شد." "این به یک ایده کاملا جدید نیاز دارد."

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

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

او گفت: "من واقعا خوشحالم که این همگرایی منافع بین جوامع مختلف را می بینم." "من فکر می کنم برای علم عالی است."