امنیت اثبات‌پذیر و کاهش‌ها

امنیت اثبات‌پذیر نشان می‌دهد که شکستن یک طرح رمزنگاری حداقل به همان اندازه دشوار است که حل یک مسئله که حل‌ناپذیر فرض می‌شود، با ارائه یک کاهش صریح از مسئله فرض‌شده-دشوار به هر حمله‌ای به طرح.

Definition

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

Scope

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

Core questions

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

Key concepts

• کاهش امنیتی
• اثبات‌های مبتنی بر بازی
• اثبات‌های مبتنی بر شبیه‌سازی
• کاهش‌های محکم در مقابل سست
• امنیت مشخص
• مدل اوراکل تصادفی
• مدل استاندارد
• مزیت ناچیز
• فرض سختی

Key theories

روش‌شناسی اثبات کاهشی

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

مدل اوراکل تصادفی

بسیاری از طرح‌های کارآمد با ایده‌آل‌سازی یک تابع هش به عنوان یک اوراکل واقعاً تصادفی، امن اثبات می‌شوند؛ این مدل اثبات‌هایی را برای ساختارهای عملی ممکن می‌سازد اما اکتشافی است، زیرا هیچ تابع واقعی یک اوراکل تصادفی نیست.

Mechanisms

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

Clinical relevance

امنیت اثبات‌پذیر استانداردی است که طرح‌های رمزنگاری از طریق آن اعتماد و استانداردسازی کسب می‌کنند: فرآیندهای AES، SHA-3 و پساکوانتوم NIST به شدت اثبات‌های امنیتی را مورد توجه قرار دادند، و پروتکل‌هایی مانند TLS 1.3 با تحلیل‌های کاهشی و بررسی‌شده توسط ماشین همراه بودند. درک کاهش‌ها به متخصصان اجازه می‌دهد تا قضاوت کنند که یک ادعای امنیتی چه چیزی را تضمین می‌کند و چه چیزی را تضمین نمی‌کند، و پارامترهایی را انتخاب کنند که استحکام کاهش را در نظر بگیرند.

Evidence & guidelines

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

History

روش‌شناسی کاهشی با انقلاب تعریفی اوایل دهه ۱۹۸۰ پدیدار شد و در طول دهه ۱۹۹۰ سیستماتیک شد. بلار و روگاوی مدل اوراکل تصادفی (۱۹۹۳) را برای اثبات امنیت طرح‌های عملی معرفی کردند، و بعدها تحلیل «امنیت مشخص» را برای کمی‌سازی تضمین‌ها. نتیجه سال ۱۹۹۸ کانتی، گلدریچ و هالوی که طرح‌ها را در مدل اوراکل تصادفی امن نشان می‌داد اما هنگام نمونه‌سازی ناامن بودند، بحث بر سر مدل‌های ایده‌آل را تشدید کرد.

Key figures

• Mihir Bellare
• Phillip Rogaway
• Oded Goldreich
• Shafi Goldwasser
• Silvio Micali

Seminal works

• bellare1993
• katz2020
• goldreich2001

Frequently asked questions

آیا اثبات امنیتی به این معنی است که یک طرح هرگز نمی‌تواند شکسته شود؟

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

چرا مدل اوراکل تصادفی بحث‌برانگیز تلقی می‌شود؟

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