Введение

Проблема Диффи — Хеллмана (DHP) — это математическая задача, впервые предложенная Уитфилдом Диффи и Мартином Хеллманом в области криптографии, которая является теоретической основой протокола обмена ключами Диффи — Хеллмана и его производных. Эта задача возникла из-за того, что многие системы безопасности используют односторонние функции: математические операции, которые легко вычислить, но сложно обратить. Например, они позволяют зашифровать сообщение, но расшифровать его — затруднительно. Если бы задача DHP была легко разрешима, эти системы были бы легко взломаны.

Комплексность вычислений

В криптографии для определенных групп предполагается, что задача Диффи — Хеллмана (DHP) является сложной, и это часто называют предположением Диффи — Хеллмана. Эта задача выдерживала проверку на протяжении нескольких десятилетий, и до сих пор не было опубликовано "легкого" решения. По состоянию на 2006 год наиболее эффективным известным способом решения DHP является решение задачи дискретного логарифмирования (DLP), то есть нахождение x по заданным g и gx. Фактически, значительный прогресс (достигнутый den Boer, Maurer, Wolf, Boneh и Lipton) был сделан в направлении доказательства того, что для многих групп DHP почти так же сложна, как и DLP. На сегодняшний день не существует доказательств того, что DHP или DLP являются сложными задачами, за исключением общих групп (по работам Нечаева и Шоупа). Доказательство сложности любой из этих задач подразумевает, что P ≠ NP.

Другие варианты

Рассматривалось множество вариантов проблемы Диффи — Хеллмана. Наиболее важным вариантом является проблема принятия решения Диффи — Хеллмана (DDHP), заключающаяся в том, чтобы отличить gxy от случайного элемента группы, зная g, gx и gy. Иногда проблему Диффи — Хеллмана (DHP) называют вычислительной проблемой Диффи — Хеллмана (CDHP) для более четкого разграничения с DDHP. В последнее время получили распространение группы с сопряжениями, и в этих группах DDHP решается легко, однако DHP по-прежнему считается сложной задачей. Подробности о менее значимых вариантах DHP можно найти в указанных ссылках.