فرض دیفی-هیلمن

مسئلهٔ دیفی-هیلمن

مسئلهٔ دیفی-هیلمن (DHP) یک مسئله ریاضی است که اولین بار توسط دو دانشمند رمزشناس به نام‌های ویتفیلد دیفی و مارتین هلمن در زمینه رمزنگاری پیشنهاد شد. انگیزه این مسئله این است که بسیاری از سیستم‌های امنیتی از عملیات ریاضی که محاسبهٔ آنها سریع است، اما عملیات معکوس آنها سخت است، استفاده می‌کنند. برای مثال، آنها می‌توانند یک پیام را رمزگذاری کنند، اما معکوس رمزگذاری (رمزگشایی) سخت است. اگر حل مسئله دیفی-هیلمن آسان باشد، این سیستم به آسانی شکسته می‌شود.

تشریح مسئله

مسئلهٔ دیفی-هیلمن به‌طور شهودی به صورت زیر است:الگو:سخ برای عنصر $g$ داده شده و مقادیر $g^x$ و $g^y$، مقدار $g^{xy}$ چیست؟الگو:سخ به‌طوری که $g$ مولد یک گروه است (معمولاً گروه ضربی یک میدان یا گروه منحنی بیضوی) و $x$ و $y$ اعداد صحیحی هستند که به تصادف انتخاب شده‌اند.الگو:سخ برای مثال، در پروتکل تبادل کلید دیفی-هلمن، مهاجم $g^x$ و $g^y$ را، بعنوان بخشی از پروتکل ردوبدل شده، مشاهده می‌کند و هر دوطرف می‌توانند کلید مشترک $g^{xy}$ را محاسبه می‌کنند. حل سریع مسئلهٔ دیفی-هیلمن به مهاجم اجازه می‌دهد که امنیت پروتکل تبادل کلید دیفی-هیلمن و بسیاری از انواع آن، از جمله رمزنگاری الجمل، را نقض می‌کند.

پیچیدگی محاسباتی

در رمزنگاری، برای بعضی گروه‌های خاص، فرض می‌شود که مسئلهٔ دیفی-هیلمن سخت است و اغلب فرض دیفی-هیلمن نامیده می‌شود. برای چند دهه بررسی دقیق این مسئله باقی مانده بود و هنوز هیچ راه حل «آسان» برای آن ارائه نشده بود.الگو:سخ در سال ۲۰۰۶ کارامدترین ابزار شناخته شده برای حل مسئلهٔ دیفی-هیلمن حل مسئلهٔ لگاریتم گسسته (DLP)، که پیداکردن $x$ از روی $g^x$ است، بود. در حقیقت پیشرفت قابل توجهی (بوسیلهٔ Wolf، Boneh، den Boer، Maurer و Lipton) در جهت نشان دادن اینکه در بسیاری از گروهها سخت بودن مسئلهٔ دیفی-هیلمن مانند سخت بودن مسئلهٔ لگاریتم گسسته است، شد. تا به امروز هیچ مدرکی وجود ندارد که مسئلهٔ دیفی-هیلمن (یا لگاریتم گسسته) مسئلهٔ سخت است، بجز در گروه‌های عمومی (Nechaev و Shoup).

منابع

• الگو:یادکرد ویکی