موضوع مقاله: فرضیه سختی محاسباتی | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # فرضیه سختی محاسباتی | مقدمه: اثبات سختی (به‌صورت غیرمشروط) برای تقریباً هیچ مسئله مفیدی تاکنون امکان‌پذیر نبوده است. | ## بخش 1: فرضیه سختی محاسباتی | در عوض، دانشمندان کامپیوتر از کاهش‌ها استفاده می‌کنند تا سختی یک مسئله جدید یا پیچیده را به یک فرضیه سختی محاسباتی در مورد مسئله‌ای که بهتر درک شده است، مرتبط کنند. در برخی موارد، پروتکل‌های رمزنگاری به امنیت نظری اطلاعات دست می‌یابند؛ مثال رایج این نوع امنیت، رمز یک‌بار مصرف است. با این حال، امنیت نظری اطلاعات همیشه دست‌یافتنی نیست؛ در چنین مواردی، رمزنگاران به امنیت محاسباتی روی می‌آورند. به‌طور خلاصه، این به معنای آن است که این سیستم‌ها در صورتی امن هستند که فرض شود مهاجمان از نظر محاسباتی محدود هستند، همان‌طور که در عمل همه مهاجمان محدودیت محاسباتی دارند. فرضیه‌های سختی محاسباتی همچنین برای هدایت طراحان الگوریتم مفید هستند: بعید است که یک الگوریتم ساده بتواند فرضیه سختی محاسباتی شناخته‌شده‌ای مانند P!=NP را نقض کند. مقایسه فرضیه‌های سختی دانشمندان علوم کامپیوتر روش‌های مختلفی برای ارزیابی میزان قابلیت اطمینان فرضیه‌های سختی ارائه داده‌اند. قدرت فرضیه‌های سختی فرض می‌کنیم که فرضیه A قوی‌تر از فرضیه B است، اگر A به B منجر شود (و عکس آن یا نادرست باشد یا اثبات نشده باشد). به بیان دیگر، حتی اگر A نادرست باشد، ممکن است B همچنان درست باشد و پروتکل‌های رمزنگاری مبتنی بر B قابل استفاده باقی بمانند. بنابراین، هنگام طراحی پروتکل‌های رمزنگاری، هدف آن است که امنیت با استفاده از ضعیف‌ترین فرضیات ممکن اثبات شود. فرضیه‌های حالت میانگین در برابر بدترین حالت فرضیه حالت میانگین بیان می‌کند که یک مسئله خاص در بیشتر نمونه‌ها از یک توزیع مشخص دشوار است، در حالی که فرضیه بدترین حالت تنها می‌گوید که مسئله در برخی نمونه‌ها دشوار است. برای یک مسئله خاص، سختی در حالت میانگین، سختی در بدترین حالت را نتیجه می‌دهد؛ بنابراین فرضیه سختی حالت میانگین قوی‌تر از فرضیه سختی بدترین حالت برای همان مسئله است. با این حال، برای کاربردهای رمزنگاری، دانستن اینکه یک مسئله تنها در برخی نمونه‌ها دشوار است (یعنی سختی در بدترین حالت) مفید نیست، زیرا راهی برای تولید نمونه‌های دشوار فراهم نمی‌کند. خوشبختانه، بسیاری از فرضیه‌های سختی حالت میانگین که در رمزنگاری استفاده می‌شوند (مانند RSA، لگاریتم گسسته و برخی مسائل مربوط به شبکه‌ها) می‌توانند از طریق کاهش‌های "بدترین حالت به حالت میانگین" اثبات شوند. قابلیت ابطال یکی از ویژگی‌های مطلوب در فرضیه‌های سختی محاسباتی، قابلیت ابطال است؛ به این معنا که اگر فرضیه نادرست باشد، بتوان این نادرستی را اثبات کرد. به طور تقریبی، یک فرضیه سختی محاسباتی زمانی ابطال‌پذیر است که بتوان آن را در قالب یک چالش بیان کرد: یک پروتکل تعاملی بین یک مهاجم و یک تأییدکننده کارآمد، به گونه‌ای که اگر و تنها اگر فرضیه نادرست باشد، مهاجم کارآمد بتواند تأییدکننده را قانع کند. فرضیه‌های رایج سختی رمزنگاری تعدادی فرضیه سختی رمزنگاری رایج وجود دارد که در زیر برخی از آن‌ها و پروتکل‌هایی که از آن‌ها استفاده می‌کنند، آورده شده است: 1. مسئله تجزیه اعداد صحیح برای یک عدد مرکب n که حاصل ضرب دو عدد اول بزرگ p و q است، مسئله تجزیه اعداد صحیح یافتن p و q است (یا به طور کلی، یافتن اعداد اول p1​,…,pk​ به گونه‌ای که n=∏i​pi​). امنیت بسیاری از پروتکل‌های رمزنگاری بر این فرض استوار است که تجزیه اعداد صحیح دشوار است. | ## بخش 2: فرضیه سختی محاسباتی | نمونه‌هایی از سیستم‌های رمزنگاری که امنیت آن‌ها معادل این فرضیه است شامل سیستم رمزنگاری رابین و سیستم اوکاماتو–اوشیاما هستند. بسیاری دیگر از سیستم‌ها بر فرضیه‌های قوی‌تر مانند RSA و مسائل باقی‌مانده استوارند. موارد خاص مهم شامل مسئله باقی‌مانده درجه دوم و مسئله باقی‌مانده مرکب تصمیمی هستند. برخی سیستم‌های رمزنگاری که بر سختی این مسائل استوارند عبارتند از: سیستم رمزنگاری گلدواسر–مایکالی (مسئله باقی‌مانده درجه دوم) مولد بلوم–بلوم–شاب (مسئله باقی‌مانده درجه دوم) سیستم رمزنگاری پاییه (مسئله باقی‌مانده مرکب تصمیمی) 4. مسئله لگاریتم گسسته (DLP) مقاله اصلی: لگاریتم گسسته با داشتن عناصر ‌‌ و ‌‌ از یک گروه ‌‌، مسئله لگاریتم گسسته درخواست می‌کند که عدد صحیح ‌‌ پیدا شود به‌طوری که ‌‌. مسئله لگاریتم گسسته به‌صورت مشخص با مسئله تجزیه عدد صحیح قابل مقایسه نیست، اما پیچیدگی محاسباتی آن‌ها ارتباط نزدیکی دارد. بیشتر پروتکل‌های رمزنگاری مرتبط با مسئله لگاریتم گسسته در واقع بر فرضیه قوی‌تری به نام فرضیه دیفی‌–هلمن تکیه دارند: با داشتن عناصر گروه ‌‌، که در آن ‌‌ یک مولد و ‌‌ اعداد صحیح تصادفی هستند، یافتن ‌‌ دشوار است. مثال‌هایی از پروتکل‌هایی که از این فرضیه استفاده می‌کنند شامل تبادل کلید دیفی‌–هلمن اصلی و رمزنگاری الگمال است (که بر نسخه قوی‌تر یعنی نوع تصمیمی دیفی‌–هلمن یا DDH تکیه دارد). نگاشت‌های چندخطی یک نگاشت چندخطی تابعی است به شکل ‌‌ (که در آن ‌‌ گروه‌هایی هستند) به‌طوری که برای هر ‌‌ و ‌‌ داریم: برای کاربردهای رمزنگاری، می‌خواهیم گروه‌های ‌‌ و یک نگاشت ‌‌ بسازیم به‌طوری که نگاشت و عملیات گروهی روی ‌‌ به‌طور کارآمد قابل محاسبه باشند، اما مسئله لگاریتم گسسته روی ‌‌ همچنان سخت باقی بماند. برخی کاربردها نیازمند فرضیه‌های قوی‌تری هستند، مثلاً نسخه‌های چندخطی فرضیه دیفی‌–هلمن. برای حالت خاص ‌‌، نگاشت‌های دوجمله‌ای با امنیت باورپذیر از طریق جفت‌سازی ویل و تیت ساخته شده‌اند. اما برای ‌‌، ساختارهای متعددی در سال‌های اخیر پیشنهاد شده‌اند که بسیاری از آن‌ها نیز شکسته شده‌اند، و در حال حاضر اجماع روشنی درباره یک گزینه امن وجود ندارد. برخی سیستم‌های رمزنگاری که بر سختی نگاشت‌های چندخطی متکی هستند شامل موارد زیر می‌شوند: طرح بونه‌–فرانکلین (دیفی‌–هلمن دوجمله‌ای) بونه‌–لین‌–شچام (دیفی‌–هلمن دوجمله‌ای) کاندید گارگ‌–جنتری‌–هالوی‌–رایکووا‌–ساهی‌–واترز برای رمزنگاری تابعی و مبهم‌سازی با قابلیت تمایز (پازل‌های چندخطی) مسائل شبکه مقاله اصلی: مسئله شبکه اساسی‌ترین مسئله محاسباتی روی شبکه‌ها، مسئله کوتاه‌ترین بردار (SVP) است: با داشتن یک شبکه ‌‌، کوتاه‌ترین بردار غیرصفر ‌‌ را پیدا کنید. مفیدترین فرضیه سختی شبکه در رمزنگاری، مسئله یادگیری با خطاها (LWE) است: با داشتن نمونه‌هایی به صورت ‌‌، که در آن ‌‌ برای یک تابع خطی ‌‌ است، یادگیری ‌‌ با استفاده از جبر خطی آسان است. در مسئله LWE، ورودی الگوریتم دارای خطا است، یعنی برای هر زوج ‌‌ با احتمالی کوچک. این خطاها باعث می‌شوند که مسئله (برای پارامترهای مناسب) غیرقابل حل باشد؛ به‌خصوص، تبدیل‌هایی از بدترین حالت به میانگین حالت برای نسخه‌هایی از SVP شناخته شده‌اند. برای کامپیوترهای کوانتومی، مسائل تجزیه و لگاریتم گسسته آسان هستند، اما مسائل شبکه به‌طور فرضی سخت باقی می‌مانند. این امر برخی سیستم‌های رمزنگاری مبتنی بر شبکه را به کاندیدهایی برای رمزنگاری پساکوانتومی تبدیل کرده است. | ## بخش 3: فرضیه سختی محاسباتی | برخی سیستم‌های رمزنگاری که بر سختی مسائل شبکه متکی هستند عبارتند از: NTRU (شامل NTRUEncrypt و NTRUSign) بیشتر کاندیدهای رمزنگاری کاملاً همومورفیک فرضیات سختی غیررمزنگاری علاوه بر کاربردهای رمزنگاری، فرضیات سختی برای اثبات قضایای پیچیدگی محاسباتی که به‌طور قطعی دشوار هستند، استفاده می‌شوند. در این کاربردها، نشان داده می‌شود که فرضیه سختی منجر به یک نتیجه پیچیدگی نظری مطلوب می‌شود، به جای آنکه خود نتیجه به‌طور مستقیم ثابت شود. شناخته‌شده‌ترین فرضیه از این نوع، فرضیه ‌‌ است، اما فرضیات دیگری نیز مانند فرضیه زمان نمایی، فرضیه کلیک کاشته‌شده و فرضیه بازی یکتا وجود دارند. اگر مسئله‌ ای ‌C-سخت باشد (با توجه به کاهش‌ های زمانی چندجمله‌ ای)، آنگاه نمی‌ توان آن را با یک الگوریتم زمان چندجمله‌ ای حل کرد مگر اینکه فرض سختی محاسباتی ‌P≠C اشتباه باشد. فرضیه زمان نمایی (ETH) و انواع آن مقاله اصلی: فرضیه زمان نمایی فرضیه زمان نمایی (ETH) تقویتی از فرض سختی ‌P≠NP است که بیان می‌کند نه تنها مسئله رضایت‌ بخشی بولی (SAT) فاقد الگوریتم زمان چندجمله‌ ای است، بلکه نیازمند زمان نمایی (‌2^(\u03a9(n ‌) می‌باشد. این فرضیه‌ ها و سایر فرضیات سختی محاسباتی مرتبط به دستیابی به نتایج پیچیدگی دقیق‌تر کمک می‌کنند، مانند تمایز بین زمان چندجمله‌ ای و زمان شبه‌ چندجمله‌ ای یا حتی تمایز بین ‌n^(1.99) و ‌n^2. فرضیات سختی در حالت میانگین مقاله اصلی: پیچیدگی در حالت میانگین برخی مسائل محاسباتی به‌ طور میانگین، با توجه به یک توزیع خاص از نمونه‌ ها، سخت فرض می‌شوند. به عنوان مثال، در مسئله کلیک کاشته‌ شده (Planted Clique)، ورودی یک گراف تصادفی است که با نمونه‌ گیری از گراف تصادفی اردوش‌-رنی تولید شده و سپس یک کلیک تصادفی ‌k-تایی در آن “کاشته” شده است. فرضیات سختی در حالت میانگین برای اثبات سختی در حالت میانگین در کاربردهایی مانند آمار مفید هستند. به علاوه، فرض سختی کلیک کاشته‌ شده برای تمایز بین زمان چندجمله‌ ای و شبه‌ چندجمله‌ ای در برخی مسائل دیگر نیز استفاده شده است. بازی‌ های یکتا مقاله اصلی: فرضیه بازی‌ های یکتا مسئله پوشش برچسب یکتا یک مسئله رضایت‌ بخشی محدودیت است که در آن هر محدودیت ‌C شامل دو متغیر ‌x و ‌y می‌باشد و برای هر مقدار ‌x، یک مقدار یکتا برای ‌y وجود دارد که ‌C را ارضا می‌کند. تعیین اینکه آیا همه محدودیت‌ ها قابل ارضا هستند ساده است، اما فرضیه بازی‌ های یکتا (UGC) بیان می‌کند که تعیین اینکه تقریباً همه محدودیت‌ ها 1-ε)-کسر) یا تقریباً هیچ‌ یک از آن‌ ها (ε-کسر) قابل ارضا هستند، NP-سخت است. به ویژه، با فرض UGC، یک الگوریتم برنامه‌ ریزی نیمه‌ معین وجود دارد که تضمین‌ های تقریب بهینه برای بسیاری از مسائل مهم را ارائه می‌دهد. گسترش مجموعه کوچک مقاله اصلی: فرضیه گسترش مجموعه کوچک مسئله گسترش مجموعه کوچک (SSE) که ارتباط نزدیکی با مسئله پوشش برچسب یکتا دارد، به دنبال یافتن یک مجموعه کوچک از رئوس در یک گراف ‌G = (V, E) است که گسترش یال آن حداقل باشد. بنابراین، فرضیه گسترش مجموعه کوچک که بیان می‌کند SSE سخت است، فرضی قوی‌تر (اما مرتبط) نسبت به فرضیه بازی‌ های یکتا است. فرضیه 3SUM مقاله اصلی: 3SUM در مسئله 3SUM، با یک مجموعه از n عدد روبه‌ رو هستیم و هدف این است که آیا سه عدد وجود دارند که مجموع آن‌ ها صفر شود؟ یک الگوریتم زمانی درجه دوم برای 3SUM وجود دارد و فرض شده که هیچ الگوریتمی نمی‌تواند 3SUM را در زمان “واقعاً کمتر از درجه دوم” حل کند. فرضیه 3SUM یک فرض سختی محاسباتی است که بیان می‌کند هیچ الگوریتم ‌O(n^(2-\u03b5 (برای هر مقدار ثابت ε>0) برای حل 3SUM وجود ندارد. | ## جمع‌بندی | این فرضیه برای اثبات کران‌ های پایین نزدیک به درجه دوم در مسائل مختلف، به‌ ویژه در هندسه محاسباتی، مفید است.