Вычислительное предположение Диффи – Хеллмана - Википедия - Computational Diffie–Hellman assumption

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

Определение

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

${ Displaystyle (г, г ^ {а}, г ^ {Ь}) ,}$

для произвольно выбранного генератора грамм и случайный

${ Displaystyle а, б ин {0, ldots, q-1 }, ,}$

это вычислительно трудноразрешимый вычислить значение

${ displaystyle g ^ {ab}. ,}$

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

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

Данный

${ Displaystyle (г, г ^ {а}, г ^ {Ь}), ,}$

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

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

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

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

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

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

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

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

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

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

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

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

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

Рекомендации