Регистрация Войти
Рейтинг:2
Rory avatar Crypto

Нарушение CDH также нарушает DHI

флаг mp
Rory

Я пытаюсь показать, что, нарушая Вычислительное предположение Диффи-Хеллмана (CDH) один тоже ломает Обратное предположение Диффи-Хеллмана. К сожалению, я немного застрял и не знаю, куда идти. Я подозреваю, что свойство билинейности из группы спаривания, заданной $PGGen$ виноват, но я не совсем уверен, как подойти к проблеме дальше. Определения приведены ниже.

С вычислительным алгоритмом Диффи-Хеллмана (CDH), определяемым противоборством PPT A, где: $Adv^{cdh}_{PGGen,A}(n)$ пренебрежимо мало и:

$Adv^{cdh}_{PGGen,A}(n):= Pr[Z = g^{xy} \mid PG \stackrel{$}{\gets} PGGen(1^n); х, у \stackrel{$}{\gets} \mathbb{Z}_p ; Z \stackrel{$}{\gets} A(PG, g^x, g^y)]$

и обратное предположение Диффи-Хеллмана (DHI), определяемое противником PPT A, где: $Adv^{q-dhi}_{PGGen,A}(n)$ пренебрежимо мало и:

$Adv^{q-dhi}_{PGGen,A}(n):= Pr[Z = g^{1/x} \mid PG \stackrel{$}{\gets} PGGen(1^n); х, у \stackrel{$}{\gets} \mathbb{Z}_p ; Z \stackrel{$}{\gets} A(PG, g^x)]$

Любая помощь будет принята с благодарностью.

83
0 + 0
Рейтинг:3
Ievgeni avatar Crypto
флаг cn
Ievgeni

Если вы можете сломать CDH, это означает, что вы можете эффективно создавать все $ г ^ {х ^ и} $ для всех $я$ положительных результатов, комбинируя быстрое возведение в степень с оракулом CDH.

$$g^{1/x} = \begin{случаи} EXP(G',u) = g & \text{if } u=0 \ EXP(CDH(G'),u/2) & \text{если } u \text{ четно}\ CDH(G', EXP(G',u-1)) & \text{если} u \text{нечетно}\ \end{случаи}$$

Тогда мы можем вычислить $ g ^ {x ^ {p-2}} = g ^ {x ^ {p-2} \ mod p} = g ^ {x ^ {p-2}} = g ^ {\ frac {1} {x } \мод п}$. Затем вы можете сломать DHI.

0 + 0
kelalaka avatar
флаг in
kelalaka
Я думаю, что проще всего показать, что DHI эквивалентен Square DH...
0
Ответить
poncho avatar
флаг my
poncho
@kelalaka: тем не менее, хорошая вещь с подходом $g^{x^{q-2}}$ заключается в том, что он работает чисто, даже если ваш Oracle привязан к определенному $g$
0
Ответить
флаг Moldova
Admin
Этот вопрос на других языках:

Ответить или комментировать

Большинство людей не понимают, что склонность к познанию нового открывает путь к обучению и улучшает межличностные связи. В исследованиях Элисон, например, хотя люди могли точно вспомнить, сколько вопросов было задано в их разговорах, они не чувствовали интуитивно связи между вопросами и симпатиями. В четырех исследованиях, в которых участники сами участвовали в разговорах или читали стенограммы чужих разговоров, люди, как правило, не осознавали, что задаваемый вопрос повлияет — или повлиял — на уровень дружбы между собеседниками.