Problema CDH e problema Square-DH

Question

Problema CDH e problema Square-DH

#1 da (6 voti)
#2 da (2 voti)

9

Il problema CDH dice approssimativamente che scegliere $ U = g ^ u, V = g ^ v $ uniformemente a caso dal gruppo ciclico $ G $, è difficile calcolare $ CDH (U, V) = g ^ {uv} $ .

Il problema di Square-DH dice approssimativamente di scegliere $ U = g ^ u $ in modo uniforme a caso dal gruppo ciclico $ G $, è difficile calcolare $ Z = g ^ {u ^ 2} $

Se riesco a risolvere il problema del CDH, allora è molto chiaro che il problema di Square-DH può anche essere risolto facilmente ($ CDH (U, U) = g ^ {u ^ 2} $). Mentre, se il problema di Square-DH può essere risolto, allora possiamo risolvere il problema CDH di $ UV $: $$ g ^ {{(u + v) ^ 2}} = g ^ {u ^ 2 + v ^ 2 + 2uv} = g ^ {u ^ 2} {g ^ v ^ 2} CDH (U, V) ^ 2 $$, mentre il problema di Square-DH di $ U $ e $ V $ può essere risolto. quindi dividendo $ g ^ {u ^ 2} $ e $ g ^ {v ^ 2} $, otteniamo $ CDH (U, V) ^ 2 $, e infine calcoliamo la radice quadrata di $ CDH (U, V) ^ 2 $, otteniamo $ CDH (U, V) $

Quindi, posso dire che sono uguali tra loro?

diffie-hellman provable-security

posta T.B 25.12.2013 - 09:18

fonte

2 risposte

Leggi altre domande sui tag diffie-hellman provable-security

Gestione delle eccezioni nelle applicazioni multilivello La crittografia dei file di Microsoft Office garantisce l'integrità?

score 6 · Answer 1

Per lo più.

I due problemi sono in realtà più strettamente equivalenti in un modello di gap rispetto a un modello non-gap.

Square-DH si riduce chiaramente a CDH in entrambi i casi, ma CDH riduce a due chiamate a Square-DH (hai 3, ma puoi usare $ (u-v) ^ 2 $ per renderlo 2). Questo va bene se l'avversario di Square-DH ha sempre ragione, ma forse l'avversario risolve solo il problema di Square-DH con probabilità $ \ epsilon $. La riduzione non sa se l'avversario è riuscito, quindi risolve CDH con probabilità solo $ \ epsilon ^ 2 $.

Se devi provare molte volte per risolvere CDH, devi far girare $ O (2 / \ epsilon) $ Square avversario avversario e fare $ O (\ epsilon ^ 2) $ ipotesi, che è un po ' sciolto ... a meno che tu non abbia un oracolo DDH, come nel modello gap. In tal caso, puoi filtrare i tentativi Square-DH sbagliati. La riduzione non è ancora perfettamente stretta, però. Può risolvere il problema CDH in tempo $ t $ chiamate Square-DH con una probabilità che è di primo ordine $ t ^ 2 \ epsilon ^ 2/2 $ quando $ t < 1 / \ epsilon $. Quindi se il tuo avversario è impreciso e non hai molto tempo, è comunque una riduzione allentata, ma se hai $ \ approx 1 / \ epsilon $ time, diventa di nuovo stretto.

score 2 · Answer 2

2

Sì , hai dimostrato che questi due problemi sono equivalenti mostrando riduzioni nelle entrambe indicazioni (che è il modo di risolvere tali problemi). Btw., Questo risultato è ben noto che detiene l'ordine di $ G $ è primo.

risposta data 25.12.2013 - 12:30

fonte