فرضیات سختی محاسباتی

فرضیات سختی محاسباتی، حدس‌های اثبات‌نشده اما به‌خوبی مطالعه‌شده‌ای هستند — مانند دشواری فاکتورگیری، لگاریتم‌های گسسته، و مسائل شبکه‌ای — که امنیت طرح‌های رمزنگاری نهایتاً بر آن‌ها استوار است.

Definition

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

Scope

این موضوع فرضیاتی را پوشش می‌دهد که رمزنگاری بر آن‌ها تکیه دارد: وجود توابع یک‌طرفه، مسائل نظریه اعداد (فاکتورگیری، RSA، لگاریتم گسسته)، و مسائل شبکه‌ای و کدی که در رمزنگاری پساکوانتومی استفاده می‌شوند. این موضوع به سلسله‌مراتب بین فرضیات، تمایز بین سختی بدترین حالت و حالت متوسط، و نحوه تأیید فرضیات می‌پردازد. این موضوع شامل مکانیزم‌های کاهش که فرضیات را به طرح‌ها و تعاریف امنیتی مرتبط می‌کنند، نمی‌شود که در موضوعات مرتبط دیگر بررسی شده‌اند.

Core questions

• چرا امنیت رمزنگاری باید بر فرضیات سختی اثبات‌نشده استوار باشد؟
• فرضیات اصلی (توابع یک‌طرفه، فاکتورگیری، لگاریتم گسسته، شبکه‌ها) کدامند؟
• فرضیات از نظر قدرت چگونه با یکدیگر مرتبط هستند؟
• تفاوت بین سختی بدترین حالت و حالت متوسط چیست؟
• مسائل سخت کاندید چگونه بررسی می‌شوند و چه اتفاقی می‌افتد اگر یکی از آن‌ها نقض شود؟

Key concepts

• تابع یک‌طرفه
• تابع تله‌دری
• فرضیه فاکتورگیری عدد صحیح
• فرضیه لگاریتم گسسته
• فرضیات RSA و دیفی-هلمن
• یادگیری با خطا (LWE)
• سختی بدترین حالت در مقابل سختی حالت متوسط
• P در مقابل NP
• سلسله‌مراتب فرضیات

Key theories

توابع یک‌طرفه به عنوان یک فرضیه حداقلی

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

فرضیات نظریه اعداد و شبکه‌ای

رمزنگاری کلید عمومی بر مسائل ساختاریافته — فاکتورگیری عدد صحیح، مسئله RSA، و لگاریتم‌های گسسته (به‌طور کلاسیک)، و مسائل یادگیری با خطا و کوتاه‌ترین بردار در شبکه‌ها (پساکوانتوم) — استوار است که هر یک توسط دهه‌ها بررسی رمزنگاری تحلیلی پشتیبانی می‌شوند.

Mechanisms

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

Clinical relevance

فرضیات سختی تعیین می‌کنند که چه چیزی برای استقرار ایمن است و چه چیزی نیست. کشف اینکه رایانه‌های کوانتومی فاکتورگیری و لگاریتم‌های گسسته را (از طریق الگوریتم شور) نقض می‌کنند، فرضیات پشت RSA و رمزنگاری منحنی بیضوی را در برابر مهاجمان کوانتومی بی‌اعتبار کرد و مستقیماً منجر به حرکت به سمت استانداردهای پساکوانتومی مبتنی بر شبکه شد. انتخاب طرح‌های مبتنی بر فرضیات به‌خوبی مطالعه‌شده و پیگیری وضعیت آن‌ها، برای امنیت بلندمدت ضروری است.

Evidence & guidelines

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

History

اتکا به سختی با رمزنگاری کلید عمومی در سال ۱۹۷۶ پدیدار شد، زمانی که دیفی و هلمن امنیت را به لگاریتم گسسته و RSA را به فاکتورگیری گره زدند. دهه ۱۹۸۰ توابع یک‌طرفه و تمایز بدترین حالت/حالت متوسط را رسمی کرد. کاهش‌های آژتای از بدترین حالت به حالت متوسط (۱۹۹۶) و مسئله یادگیری با خطا (LWE) رگف (۲۰۰۵) فرضیات شبکه‌ای را تثبیت کردند، که به عنوان پایه‌های مقاوم در برابر کوانتوم برجسته شدند و استانداردهای جدید پساکوانتومی را پشتیبانی می‌کنند.

Key figures

• Whitfield Diffie
• Martin Hellman
• Oded Goldreich
• Oded Regev
• Andrew Yao

Seminal works

• diffie1976
• goldreich2001
• katz2020

Frequently asked questions

چرا نمی‌توانیم به سادگی اثبات کنیم که این مسائل دشوار هستند؟

اثبات اینکه یک مسئله به زمان فوق‌چندجمله‌ای نیاز دارد، سؤالات عمیق و حل‌نشده‌ای را در نظریه پیچیدگی (به ویژه P در مقابل NP) حل می‌کند. بنابراین رمزنگاری بر فرضیاتی تکیه دارد که اعتبار آن‌ها از دهه‌ها تلاش ناموفق برای حل کارآمد آن‌ها ناشی می‌شود.

اگر یک فرضیه سختی نقض شود چه اتفاقی می‌افتد؟

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