Предположение Диффи-Хеллмана о принятии решений

Предположение о решающей сложности Диффи–Хеллмана (DDH) — это предположение о вычислительной сложности определенной проблемы, включающей дискретные логарифмы в циклических группах . Оно используется в качестве основы для доказательства безопасности многих криптографических протоколов, в частности криптосистем Эль-Гамаля и Крамера–Шоупа .

Рассмотрим (мультипликативную) циклическую группу порядка и с генератором . Предположение DDH утверждает, что при заданных и для равномерно и независимо выбранных значение «выглядит как» случайный элемент в .${\displaystyle G}$${\displaystyle д}$ ${\displaystyle г}$${\displaystyle г^{а}}$${\displaystyle г^{б}}$${\displaystyle a,b\in \mathbb {Z} _{q}}$${\displaystyle g^{ab}}$${\displaystyle G}$

Это интуитивное понятие можно формально сформулировать, сказав, что следующие два распределения вероятностей вычислительно неразличимы (по параметру безопасности , ):${\displaystyle n=\log(q)}$

• ${\displaystyle (г^{а},г^{б},г^{аб})}$, где и выбираются случайным образом и независимо из .${\displaystyle а}$${\displaystyle б}$${\displaystyle \mathbb {Z} _{q}}$
• ${\displaystyle (g^{a},g^{b},g^{c})}$, где выбираются случайным образом и независимо из .${\displaystyle a,b,c}$${\displaystyle \mathbb {Z} _{q}}$

Тройки первого рода часто называют триплетами DDH или кортежами DDH .

Предположение DDH связано с предположением дискретного логарифма . Если бы было возможно эффективно вычислять дискретные логарифмы в , то предположение DDH не выполнялось бы в . Учитывая , можно было бы эффективно решить, сначала взяв дискретное значение , а затем сравнив с .${\displaystyle G}$${\displaystyle G}$${\displaystyle (g^{a},g^{b},z)}$${\displaystyle z=g^{ab}}$${\displaystyle \log _{g}}$${\displaystyle g^{a}}$${\displaystyle z}$${\displaystyle (g^{b})^{a}}$

DDH считается более сильным предположением, чем предположение о дискретном логарифме, поскольку существуют группы, для которых вычисление дискретных логарифмов считается сложным (и, таким образом, предположение DL считается верным), но обнаружение кортежей DDH является простым (и, таким образом, DDH является ложным). Из-за этого требование, чтобы предположение DDH выполнялось в группе, считается более строгим, чем DL.

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

Задача обнаружения кортежей DDH является случайной саморедуцируемой , что означает, грубо говоря, что если она сложна даже для небольшой доли входных данных, то она сложна почти для всех входных данных; если она проста даже для небольшой доли входных данных, то она проста почти для всех входных данных.

При использовании криптографического протокола, безопасность которого зависит от предположения DDH, важно, чтобы протокол был реализован с использованием групп, в которых предполагается соблюдение DDH:

• Подгруппа -ых вычетов по модулю простого числа , где также является большим простым числом (также называется группой Шнорра ). Для случая это соответствует группе квадратичных вычетов по модулю безопасного простого числа .${\displaystyle \mathbb {G} _{q}}$${\displaystyle k}$${\displaystyle p=kq+1}$${\displaystyle q}$${\displaystyle k=2}$
• Фактор -группа для безопасного простого числа , которая состоит из смежных классов . Эти смежные классы могут быть представлены как , что подразумевает . Поскольку и изоморфны, а изоморфизм может быть эффективно вычислен в обоих направлениях, DDH одинаково сложен в обеих группах.${\displaystyle \mathbb {Z} _{p}^{*}/\{1,-1\}}$ ${\displaystyle p=2q+1}$ ${\displaystyle \{\{1,-1\},\ldots \{q,-q\}\}}$${\displaystyle \{x,-x\}}$${\displaystyle x}$${\displaystyle \mathbb {Z} _{p}^{*}/\{1,-1\}\equiv \{1,\ldots ,q\}}$${\displaystyle \mathbb {Z} _{p}^{*}/\{1,-1\}}$${\displaystyle \mathbb {G} _{q}}$
• Эллиптическая кривая простого порядка над полем , где — простое число, при условии, что имеет большую степень вложения.${\displaystyle E}$ ${\displaystyle GF(p)}$${\displaystyle p}$${\displaystyle E}$
• Якобиан гиперэллиптической кривой над полем с простым числом приведенных делителей, где — простое число, при условии , что якобиан имеет большую степень вложения. ${\displaystyle GF(p)}$${\displaystyle p}$

Важно отметить, что предположение DDH не выполняется в мультипликативной группе , где является простым числом. Это происходит потому, что если является генератором , то символ Лежандра показывает , является ли четным или нечетным. Учитывая , и , можно таким образом эффективно вычислить и сравнить младший бит , и , соответственно, что обеспечивает вероятностный метод отличия от случайного элемента группы.${\displaystyle \mathbb {Z} _{p}^{*}}$${\displaystyle p}$${\displaystyle g}$${\displaystyle \mathbb {Z} _{p}^{*}}$${\displaystyle g^{a}}$${\displaystyle a}$${\displaystyle g^{a}}$${\displaystyle g^{b}}$${\displaystyle g^{ab}}$${\displaystyle a}$${\displaystyle b}$${\displaystyle ab}$${\displaystyle g^{ab}}$

Предположение DDH не выполняется на эллиптических кривых над с малой степенью вложения (скажем, меньше ), класс, который включает суперсингулярные эллиптические кривые . Это связано с тем, что спаривание Вейля или спаривание Тейта можно использовать для непосредственного решения задачи следующим образом: для такой кривой можно вычислить и . В силу билинейности пар эти два выражения равны тогда и только тогда, когда по модулю порядка . Если степень вложения велика (скажем, около размера ), то предположение DDH все равно будет выполняться, поскольку спаривание невозможно вычислить. Даже если степень вложения мала, существуют некоторые подгруппы кривой, в которых предположение DDH, как полагают, выполняется.${\displaystyle GF(p)}$${\displaystyle \log ^{2}(p)}$${\displaystyle P,aP,bP,cP}$${\displaystyle e(P,cP)}$${\displaystyle e(aP,bP)}$${\displaystyle ab=c}$${\displaystyle P}$${\displaystyle p}$

• Проблема Диффи–Хеллмана
• Обмен ключами Диффи-Хеллмана
• Предположения о вычислительной сложности
• предположение XDH
• Линейное предположение о принятии решений

• Боне, Дэн (1998). "Решение проблемы Диффи-Хеллмана". Труды Третьего симпозиума по алгоритмической теории чисел . Конспект лекций по информатике. Том 1423. С. 48–63. CiteSeerX  10.1.1.461.9971 . doi :10.1007/BFb0054851. ISBN 978-3-540-64657-0.