Вычислительное предположение Диффи – Хеллмана

Вычислительное предположение Диффи-Хеллмана (CDH) представляет собой вычислительной сложности предположение о задачи Диффи-Хеллмана . Предположение CDH включает в себя проблему вычисления дискретного логарифма в циклических группах . Проблема CDH иллюстрирует атаку перехватчика при обмене ключами Диффи-Хеллмана. протокол для получения обмененного секретного ключа.

Определение

Рассмотрим циклическую группу G порядка q . Предположение CDH гласит, что, учитывая

$(g,g^{a},g^{b})\,$

для случайно выбранного генератора g и случайного

$a,b\in \{0,\ldots ,q-1\},\,$

вычислить вычислительно сложно значение

$g^{ab}.\,$

Связь с дискретными логарифмами

Предположение CDH тесно связано с предположением о дискретном логарифме . Если бы вычисление дискретного логарифма (по основанию g ) в G было простым, то проблему CDH можно было бы легко решить:

Данный

$(g,g^{a},g^{b}),\,$

можно было бы эффективно вычислить $g^{ab}$ следующим образом:

• вычислить $a$ взяв дискретный журнал $g^{a}$ базировать $g$;
• вычислить $g^{ab}$ по возведению в степень: $g^{ab}=(g^{b})^{a}$;

Вычисление дискретного логарифма — единственный известный метод решения проблемы CDH. Но нет никаких доказательств того, что это фактически единственный метод. Вопрос о том, эквивалентно ли предположение о дискретном журнале допущению о CDH, остается открытой, хотя в некоторых особых случаях можно показать, что это именно так.

Связь с решающим предположением Диффи-Хеллмана

Предположение CDH является более слабым предположением, чем решающее предположение Диффи-Хеллмана (предположение DDH). Если вычислить $g^{ab}$ от $(g,g^{a},g^{b})$ было легко (проблема CDH), то можно было тривиально решить проблему DDH.

Многие криптографические схемы, построенные на основе проблемы CDH, фактически полагаются на сложность проблемы DDH. Семантическая безопасность обмена ключами Диффи-Хеллмана, а также безопасность шифрования Эль-Гамаля зависят от сложности проблемы DDH.

Существуют конкретные конструкции групп, в которых более сильное предположение DDH не выполняется, но более слабое предположение CDH все еще кажется разумной гипотезой.

Вариации вычислительного предположения Диффи – Хеллмана

Следующие варианты проблемы CDH были изучены и оказались эквивалентными проблеме CDH:

• Квадратная вычислительная задача Диффи – Хеллмана (SCDH): на входе $g,g^{x}$, вычислить $g^{x^{2}}$;
• Обратная вычислительная задача Диффи – Хеллмана (InvCDH): на входе $g,g^{x}$, вычислить $g^{x^{-1}}$;
• Делимые вычисления Задача Диффи – Хеллмана (DCDH): на входе $g,g^{x},g^{y}$, вычислить $g^{y/x}$;

Вариации вычислительного предположения Диффи–Хеллмана в группах продуктов

Позволять $G_{1}$ и $G_{2}$ две циклические группы.

• Ковычислительная задача Диффи–Хеллмана (co-CDH): дано $g,g^{a}\in G_{1}$ и $h\in G_{2}$, вычислить $h^{a}\in G_{2}$;