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

---

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

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

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

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

Предположение CDH является более слабым предположением, чем предположение Диффи-Хеллмана, принятое для принятия решений (предположение DDH). Если бы вычисление из было простым (проблема CDH), то проблему DDH можно было бы решить тривиально. ${\ Displaystyle г ^ {аб}}$${\ Displaystyle (г, г ^ {а}, г ^ {б})}$

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

---