seminario - IME-USP

On the Unpredictability of Bits of the Elliptic
Curve Diffie-Hellman Scheme
Dan Boneh e Igor E. Shparlinski
Mestrando: Dionathan Nakamura
Orientador: Routo Terada
Resumo
Resumo (em outras palavras)


Se existir um algoritmo para calcular o LSB,
então existe um algoritmo para decifrar o DH
Equivalente: calcular o LSB é tão difícil quanto
calcular toda a chave secreta do DH.
Diffie-Hellman




Seja g o gerador de um grupo cíclico de ordem p
Seja X = gx mod p e Y = gy mod p as chaves
públicas
A chave combinada é K = gxy mod p
Mesmo dados g, gx, gy é difícil recuperar gxy
Diffie-Hellman sobre CE



Seja G um ponto de ordem prima q pertencente a
curva
Seja a, b inteiros em [1, q-1]
O problema análogo em CE é:
Curvas elípticas considedas


Sendo p primo e Fp um campo finito de
tamanho p
Consideramos as curvas com equações de
Weierstrass, da forma:
Isomorfismo

Temos o seguinte isomorfismo:

Verificamos que:

De fato um isomorfismo:
DH em famílias de curvas

O resultado de trabalho se baseia nas classes
de isomorfismo de uma curva, pois:
Vantagem

No trabalho vamos supor que existe um
algoritmo A que possui uma vantagem em
predizer o LSB das coordenadas da chave do
DH conforme:
Nosso resultado principal
Nosso resultado principal
Ou ainda, computar o LSB não é mais fácil que
computar todo o DH.
HPN-CM


Apresentamos o Hidden Number ProblemChosen Multiplier :
Achar a em tempo polinomial (lg p e 1/e)
list HPN-CM

Achar os a para o qual a probabilidade se
mantém.
Theorema 2

W. Alexi, B. Chor, O. Goldreich, and C. Schnorr. 'RSA and
Rabin functions: Certain parts are as hard as the whole', SIAM
J. Computing, 17(1988), 194-209, Nov. 1988.
Teorema 3: HPN-CM
d
Vamos provar

Seja a função

Alegamos que
Verificando a alegação
Lema 1
Prova
Lema 2
Vamos provar
Teorema 4


V. Shoup, 'Lower bounds for discrete logarithms and
related problems', In Proc. Eurocrypt '97, Lect. Notes in
Comp. Sci., Springer-Verlag, Berlin, 1233 (1997), 256-266.
Enfim, prova do Teorema 1
continuação
Conclusão

Nós mostramos que não se pode existir um
algoritmo que prediz o LSB das coordenadas X
e Y do segredo do DH-CE numa fração não
negligenciável das classes de isomorfismo –
assumindo que o problema do DH é difícil em
alguma curva da classe.