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

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

مسئلهٔ دیفی-هیلمن (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).

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

فهرست

تشریح مسئله

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

منابع

پیوند به بیرون