Решающее предположение Диффи-Хеллмана

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

Определение

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

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

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

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

Связь с другими предположениями

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

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

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

Другие объекты недвижимости

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

Группы, для которых предполагается наличие DDH

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

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

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

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

См. также

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

Ссылки

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