Решающее предположение Диффи – Хеллмана - Decisional Diffie–Hellman assumption

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

Определение

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

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

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

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

Отношение к другим предположениям

Предположение DDH связано с дискретное логарифмическое предположение. Если бы можно было эффективно вычислять дискретные журналы в ${\displaystyle G}$, то предположение DDH не будет выполняться в ${\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). Если бы можно было эффективно вычислить ${\displaystyle g^{ab}}$ из ${\displaystyle (g^{a},g^{b})}$, то можно легко различить два приведенных выше распределения вероятностей. Как и выше, DDH считается более сильным предположением, чем CDH.

Другие свойства

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

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

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

• Подгруппа ${\displaystyle k}$th остатки по простому модулю ${\displaystyle p}$, куда ${\displaystyle (p-1)/k}$ также является большим простым числом (также называемым Группа Шнорра ). В случае ${\displaystyle k=2}$, это соответствует группе квадратичные вычеты по модулю а безопасный прайм.
• Простой порядок эллиптическая кривая ${\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 не выполняется для эллиптических кривых над ${\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}$), то предположение DDH все еще будет выполняться, потому что спаривание не может быть вычислено. Даже если степень вложения невелика, есть некоторые подгруппы кривой, в которых предположение DDH выполняется.

Смотрите также

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

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

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