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

در نظریه پیچیدگی محاسباتی، فرضیه سختی محاسباتی (به انگلیسی : Computational hardness assumption )^[۱] به این معنا است که یک مسئله خاص نمی‌تواند به صورت کارآمد حل شود (که معمولاً "کارآمد" به معنای حل در زمان چندجمله‌ای است). اثبات سختی (به‌صورت غیرمشروط) برای تقریباً هیچ مسئله مفیدی تاکنون امکان‌پذیر نبوده است. در عوض، دانشمندان کامپیوتر از کاهش‌ها استفاده می‌کنند تا سختی یک مسئله جدید یا پیچیده را به یک فرضیه سختی محاسباتی در مورد مسئله‌ای که بهتر درک شده است، مرتبط کنند.^[۲]

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

فرضیه‌های سختی محاسباتی همچنین برای هدایت طراحان الگوریتم مفید هستند: بعید است که یک الگوریتم ساده بتواند فرضیه سختی محاسباتی شناخته‌شده‌ای مانند P!=NP را نقض کند.

مقایسه فرضیه‌های سختی

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

قدرت فرضیه‌های سختی

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

فرضیه‌های حالت میانگین در برابر بدترین حالت

فرضیه حالت میانگین بیان می‌کند که یک مسئله خاص در بیشتر نمونه‌ها از یک توزیع مشخص دشوار است، در حالی که فرضیه بدترین حالت تنها می‌گوید که مسئله در برخی نمونه‌ها دشوار است. برای یک مسئله خاص، سختی در حالت میانگین، سختی در بدترین حالت را نتیجه می‌دهد؛ بنابراین فرضیه سختی حالت میانگین قوی‌تر از فرضیه سختی بدترین حالت برای همان مسئله است^[۳].

با این حال، برای کاربردهای رمزنگاری، دانستن اینکه یک مسئله تنها در برخی نمونه‌ها دشوار است (یعنی سختی در بدترین حالت) مفید نیست، زیرا راهی برای تولید نمونه‌های دشوار فراهم نمی‌کند^[۴]. خوشبختانه، بسیاری از فرضیه‌های سختی حالت میانگین که در رمزنگاری استفاده می‌شوند (مانند RSA، لگاریتم گسسته و برخی مسائل مربوط به شبکه‌ها) می‌توانند از طریق کاهش‌های "بدترین حالت به حالت میانگین" اثبات شوند.^[۵]

قابلیت ابطال

یکی از ویژگی‌های مطلوب در فرضیه‌های سختی محاسباتی، قابلیت ابطال است؛ به این معنا که اگر فرضیه نادرست باشد، بتوان این نادرستی را اثبات کرد. به طور خاص، ناور (2003) مفهومی رسمی از قابلیت ابطال رمزنگاری معرفی کرد^[۶]. به طور تقریبی، یک فرضیه سختی محاسباتی زمانی ابطال‌پذیر است که بتوان آن را در قالب یک چالش بیان کرد: یک پروتکل تعاملی بین یک مهاجم و یک تأییدکننده کارآمد، به گونه‌ای که اگر و تنها اگر فرضیه نادرست باشد، مهاجم کارآمد بتواند تأییدکننده را قانع کند.

فرضیه‌های رایج سختی رمزنگاری

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

1. مسئله تجزیه اعداد صحیح

برای یک عدد مرکب n که حاصل ضرب دو عدد اول بزرگ p و q است، مسئله تجزیه اعداد صحیح یافتن p و q است (یا به طور کلی، یافتن اعداد اول p1​,…,pk​ به گونه‌ای که n=∏i​pi​). هنوز الگوریتمی که این مسئله را در زمان چندجمله‌ای حل کند پیدا نشده است. امنیت بسیاری از پروتکل‌های رمزنگاری بر این فرض استوار است که تجزیه اعداد صحیح دشوار است. نمونه‌هایی از سیستم‌های رمزنگاری که امنیت آن‌ها معادل این فرضیه است شامل سیستم رمزنگاری رابین و سیستم اوکاماتو–اوشیاما هستند. بسیاری دیگر از سیستم‌ها بر فرضیه‌های قوی‌تر مانند RSA و مسائل باقی‌مانده استوارند.

2. مسئله RSA

برای یک عدد مرکب n، توان e و عدد c=memodn، مسئله RSA یافتن m است. این مسئله دشوار فرض می‌شود، اما با داشتن تجزیه n آسان می‌شود. در سیستم رمزنگاری RSA، (n,e) کلید عمومی، c رمزگذاری پیام m، و تجزیه n کلید خصوصی برای رمزگشایی است.

3. مسائل باقی‌مانده (Residuosity Problems)

برای عدد مرکب n و اعداد صحیح y و d، مسئله باقی‌مانده تعیین این است که آیا xd≡y(modn) وجود دارد (یا پیدا کردن x). موارد خاص مهم شامل مسئله باقی‌مانده درجه دوم و مسئله باقی‌مانده مرکب تصمیمی هستند. برخی سیستم‌های رمزنگاری که بر سختی این مسائل استوارند عبارتند از:

• سیستم رمزنگاری گلدواسر–مایکالی (مسئله باقی‌مانده درجه دوم)
• مولد بلوم–بلوم–شاب (مسئله باقی‌مانده درجه دوم)
• سیستم رمزنگاری پاییه (مسئله باقی‌مانده مرکب تصمیمی)

4. فرضیه Phi-Hiding

برای یک عدد مرکب m، محاسبه تابع اویلر ϕ(m) به صورت کارآمد امکان‌پذیر نیست. فرضیه Phi-Hiding بیان می‌کند که محاسبه ϕ(m) یا هر یک از عوامل اول آن دشوار است. این فرضیه در پروتکل Cachin–Micali–Stadler برای جستجوی خصوصی استفاده می‌شود.

مسئله لگاریتم گسسته (DLP)

مقاله اصلی: لگاریتم گسسته

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

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

نگاشت‌های چندخطی

یک نگاشت چندخطی تابعی است به شکل ‌‌ (که در آن ‌‌ گروه‌هایی هستند) به‌طوری که برای هر ‌‌ و ‌‌ داریم:

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

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

برخی سیستم‌های رمزنگاری که بر سختی نگاشت‌های چندخطی متکی هستند شامل موارد زیر می‌شوند:

• طرح بونه‌–فرانکلین (دیفی‌–هلمن دوجمله‌ای)
• بونه‌–لین‌–شچام (دیفی‌–هلمن دوجمله‌ای)
• کاندید گارگ‌–جنتری‌–هالوی‌–رایکووا‌–ساهی‌–واترز برای رمزنگاری تابعی و مبهم‌سازی با قابلیت تمایز (پازل‌های چندخطی)^[۷]

مسائل شبکه

مقاله اصلی: مسئله شبکه

اساسی‌ترین مسئله محاسباتی روی شبکه‌ها، مسئله کوتاه‌ترین بردار (SVP) است: با داشتن یک شبکه ‌‌، کوتاه‌ترین بردار غیرصفر ‌‌ را پیدا کنید. بیشتر سیستم‌های رمزنگاری نیازمند فرضیات قوی‌تری درباره نسخه‌های SVP هستند، مانند مسئله کوتاه‌ترین بردارهای مستقل (SIVP)، GapSVP یا Unique-SVP.^[۸]

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

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

برخی سیستم‌های رمزنگاری که بر سختی مسائل شبکه متکی هستند عبارتند از:

• NTRU (شامل NTRUEncrypt و NTRUSign)
• بیشتر کاندیدهای رمزنگاری کاملاً همومورفیک

فرضیات سختی غیررمزنگاری

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

مسائل سخت کلاس ‌C

بسیاری از مسائل محاسباتی در حالت بدترین ‌حالت (worst-case) به عنوان مسائل سخت یا حتی کامل (complete) برای یک کلاس پیچیدگی ‌C شناخته شده ‌اند. به‌ طور خاص، می‌توان به مسائل NP-hardشاره کرد، اما برخی از مسائل نیز ممکن است PSPACE-hard، PPAD-hard و غیره باشند. این بدان معناست که این مسائل حداقل به سختی هر مسئله دیگری در کلاس ‌C هستند. اگر مسئله‌ ای ‌C-سخت باشد (با توجه به کاهش‌ های زمانی چندجمله‌ ای)، آنگاه نمی‌ توان آن را با یک الگوریتم زمان چندجمله‌ ای حل کرد مگر اینکه فرض سختی محاسباتی ‌P≠C اشتباه باشد.

فرضیه زمان نمایی (ETH) و انواع آن

مقاله اصلی: فرضیه زمان نمایی

فرضیه زمان نمایی (ETH) تقویتی از فرض سختی ‌P≠NP است که بیان می‌کند نه تنها مسئله رضایت‌ بخشی بولی (SAT) فاقد الگوریتم زمان چندجمله‌ ای است، بلکه نیازمند زمان نمایی (‌2^(\u03a9(n))‌) می‌باشد. فرضیه قوی‌ تر زمان نمایی (SETH) نیز بیان می‌کند که مسئله k-SAT به زمان ‌2^(1-\u03b5k)n نیاز دارد، به‌ طوری که ‌lim₋{k \u2192 \u221e} \u03b5k = 0. این فرضیه‌ ها و سایر فرضیات سختی محاسباتی مرتبط به دستیابی به نتایج پیچیدگی دقیق‌تر کمک می‌کنند، مانند تمایز بین زمان چندجمله‌ ای و زمان شبه‌ چندجمله‌ ای یا حتی تمایز بین ‌n^(1.99) و ‌n^2. چنین فرضیاتی همچنین در پیچیدگی پارامتری کاربرد دارند.^[۱۰]

فرضیات سختی در حالت میانگین

مقاله اصلی: پیچیدگی در حالت میانگین

برخی مسائل محاسباتی به‌ طور میانگین، با توجه به یک توزیع خاص از نمونه‌ ها، سخت فرض می‌شوند. به عنوان مثال، در مسئله کلیک کاشته‌ شده (Planted Clique)، ورودی یک گراف تصادفی است که با نمونه‌ گیری از گراف تصادفی اردوش‌-رنی تولید شده و سپس یک کلیک تصادفی ‌k-تایی در آن “کاشته” شده است. هدف، یافتن این کلیک کاشته‌ شده است که با احتمال بالا منحصر به فرد است. نمونه‌ ای دیگر فرضیه فایگ (Feige’s Hypothesis) است که یک فرض سختی محاسباتی درباره نمونه‌ های تصادفی 3-SAT می‌باشد.^[۱۱] فرضیات سختی در حالت میانگین برای اثبات سختی در حالت میانگین در کاربردهایی مانند آمار مفید هستند.^[۱۲] به علاوه، فرض سختی کلیک کاشته‌ شده برای تمایز بین زمان چندجمله‌ ای و شبه‌ چندجمله‌ ای در برخی مسائل دیگر نیز استفاده شده است.^[۱۳]

بازی‌ های یکتا

مقاله اصلی: فرضیه بازی‌ های یکتا

مسئله پوشش برچسب یکتا یک مسئله رضایت‌ بخشی محدودیت است که در آن هر محدودیت ‌C شامل دو متغیر ‌x و ‌y می‌باشد و برای هر مقدار ‌x، یک مقدار یکتا برای ‌y وجود دارد که ‌C را ارضا می‌کند. تعیین اینکه آیا همه محدودیت‌ ها قابل ارضا هستند ساده است، اما فرضیه بازی‌ های یکتا (UGC) بیان می‌کند که تعیین اینکه تقریباً همه محدودیت‌ ها ((1-ε)-کسر) یا تقریباً هیچ‌ یک از آن‌ ها (ε-کسر) قابل ارضا هستند، NP-سخت است. بسیاری از مسائل تقریب‌ زنی با فرض UGC، NP-سخت شناخته می‌شوند. به ویژه، با فرض UGC، یک الگوریتم برنامه‌ ریزی نیمه‌ معین وجود دارد که تضمین‌ های تقریب بهینه برای بسیاری از مسائل مهم را ارائه می‌دهد.^[۱۴]

گسترش مجموعه کوچک

مقاله اصلی: فرضیه گسترش مجموعه کوچک

مسئله گسترش مجموعه کوچک (SSE) که ارتباط نزدیکی با مسئله پوشش برچسب یکتا دارد، به دنبال یافتن یک مجموعه کوچک از رئوس در یک گراف ‌G = (V, E) است که گسترش یال آن حداقل باشد. مشخص شده است که اگر SSE سخت باشد، مسئله پوشش برچسب یکتا نیز سخت است. بنابراین، فرضیه گسترش مجموعه کوچک که بیان می‌کند SSE سخت است، فرضی قوی‌تر (اما مرتبط) نسبت به فرضیه بازی‌ های یکتا است.^[۱۵] برخی مسائل تقریب‌ زنی به عنوان SSE-سخت شناخته می‌شوند.^[۱۶]

فرضیه 3SUM

مقاله اصلی: 3SUM

در مسئله 3SUM، با یک مجموعه از n عدد روبه‌ رو هستیم و هدف این است که آیا سه عدد وجود دارند که مجموع آن‌ ها صفر شود؟ یک الگوریتم زمانی درجه دوم برای 3SUM وجود دارد و فرض شده که هیچ الگوریتمی نمی‌تواند 3SUM را در زمان “واقعاً کمتر از درجه دوم” حل کند. فرضیه 3SUM یک فرض سختی محاسباتی است که بیان می‌کند هیچ الگوریتم ‌O(n^(2-\u03b5)) (برای هر مقدار ثابت ε>0) برای حل 3SUM وجود ندارد. این فرضیه برای اثبات کران‌ های پایین نزدیک به درجه دوم در مسائل مختلف، به‌ ویژه در هندسه محاسباتی، مفید است.^[۱۷]

1. "Computational hardness assumption". Wikipedia (به انگلیسی). 2023-12-20.
2. "Computational hardness assumption". Wikipedia (به انگلیسی). 2023-12-20.
3. Braverman, Mark; Ko, Young Kun; Weinstein, Omri (2015-10). "Approximating the best Nash Equilibrium in n o (log n ) -time breaks the Exponential Time Hypothesis" (به انگلیسی). Society for Industrial and Applied Mathematics: 970–982. doi:10.1137/1.9781611973730.66. ISBN 978-1-61197-374-7. {{cite journal}}: ; Check date values in: |date= (help)
4. J. Katz and Y. Lindell, Introduction to Modern Cryptography (Chapman and Hall/CRC Cryptography and Network Security Series), Chapman and Hall/CRC, 2007.
5. Goldwasser, Shafi; Kalai, Yael Tauman (2016). "Cryptographic Assumptions: A Position Paper". Theory of Cryptography Conference (TCC) 2016. Springer. pp. 505–522. doi:10.1007/978-3-662-49096-9_21.
6. Naor, Moni (2003). "On cryptographic assumptions and challenges". In Boneh, Dan (ed.). Advances in Cryptology – CRYPTO 2003: 23rd Annual International Cryptology Conference, Santa Barbara, California, USA, August 17-21, 2003, Proceedings. Lecture Notes in Computer Science. Vol. 2729. Berlin: Springer. pp. 96–109. doi:10.1007/978-3-540-45146-4_6. MR 2093188.
7. Garg, Sanjam; Gentry, Craig; Halevi, Shai; Raykova, Mariana; Sahai, Amit; Waters, Brent (2016-01). "Candidate Indistinguishability Obfuscation and Functional Encryption for All Circuits". SIAM Journal on Computing (به انگلیسی). 45 (3): 882–929. doi:10.1137/14095772X. ISSN 0097-5397. {{cite journal}}: Check date values in: |date= (help)
8. Ajtai, Miklós; Dwork, Cynthia (1997). "A public-key cryptosystem with worst-case/average-case equivalence" (به انگلیسی). ACM Press: 284–293. doi:10.1145/258533.258604. ISBN 978-0-89791-888-6.
9. Fortnow, Lance (2009-09). "The status of the P versus NP problem". Communications of the ACM (به انگلیسی). 52 (9): 78–86. doi:10.1145/1562164.1562186. ISSN 0001-0782. {{cite journal}}: Check date values in: |date= (help)
10. Lokshtanov, Daniel; Marx, Daniel; Saurabh, Saket (2011). "Lower bounds based on the Exponential Time Hypothesis". Bulletin of the EATCS. 105: 41–72.
11. Feige, Uriel (2002-05-19). "Relations between average case complexity and approximation complexity" (به انگلیسی). ACM: 534–543. doi:10.1145/509907.509985. ISBN 978-1-58113-495-7.
12. Berthet, Quentin; Rigollet, Philippe (2013-08-01). "Optimal detection of sparse principal components in high dimension". The Annals of Statistics. 41 (4). doi:10.1214/13-aos1127. ISSN 0090-5364.
13. Hazan, Elad; Krauthgamer, Robert (2011-01). "How Hard Is It to Approximate the Best Nash Equilibrium?". SIAM Journal on Computing (به انگلیسی). 40 (1): 79–91. doi:10.1137/090766991. ISSN 0097-5397. {{cite journal}}: Check date values in: |date= (help)
14. Raghavendra, Prasad (2008-05-17). "Optimal algorithms and inapproximability results for every CSP?" (به انگلیسی). ACM: 245–254. doi:10.1145/1374376.1374414. ISBN 978-1-60558-047-0.
15. Raghavendra, Prasad; Steurer, David (2010-06-05). "Graph expansion and the unique games conjecture" (به انگلیسی). ACM: 755–764. doi:10.1145/1806689.1806792. ISBN 978-1-4503-0050-6.
16. Wu, Y.; Austrin, P.; Pitassi, T.; Liu, D. (2014-04-06). "Inapproximability of Treewidth and Related Problems". Journal of Artificial Intelligence Research. 49: 569–600. doi:10.1613/jair.4030. ISSN 1076-9757.
17. WILLIAMS, VIRGINIA VASSILEVSKA (2019-05). "ON SOME FINE-GRAINED QUESTIONS IN ALGORITHMS AND COMPLEXITY". Proceedings of the International Congress of Mathematicians (ICM 2018). WORLD SCIENTIFIC. doi:10.1142/9789813272880_0188. {{cite journal}}: Check date values in: |date= (help)