On the Bits of Elliptic Curve Diffie-Hellman Keys

We study the security of elliptic curve Diffie-Hellman secret keys in the presence of oracles that provide partial information on the value of the key. Unlike the corresponding problem for finite fields, little is known about this problem, and in the case

  • PDF / 443,306 Bytes
  • 15 Pages / 430 x 660 pts Page_size
  • 25 Downloads / 176 Views

DOWNLOAD

REPORT


2

University of Waterloo, Waterloo ON N2L3G1, Canada [email protected] Dept. of Mathematics, University of California at Berkeley, Berkeley, CA 94720 [email protected] 3 Microsoft Research India Private Limited, ”Scientia”, No:196/36, 2nd Main Road, Sadashivnagar, Bangalore – 560080, India 4 Microsoft Research, 1 Microsoft Way, Redmond WA 98052 [email protected]

Abstract. We study the security of elliptic curve Diffie-Hellman secret keys in the presence of oracles that provide partial information on the value of the key. Unlike the corresponding problem for finite fields, little is known about this problem, and in the case of elliptic curves the difficulty of representing large point multiplications in an algebraic manner leads to new obstacles that are not present in the case of finite fields. To circumvent this obstruction, we introduce a small multiplier version of the hidden number problem, and we use its properties to analyze the security of certain Diffie-Hellman bits. We suggest new character sum conjectures that guarantee the uniqueness of solutions to the hidden number problem, and provide some evidence in support of the conjectures by showing that they hold on average in certain cases. We also present a Gr¨ obner basis algorithm for solving the hidden number problem and recovering the Diffie-Hellman secret key when the elliptic curve is defined over a constant degree extension field and the oracle is a coordinate function in the polynomial basis.

1

Introduction

The Diffie-Hellman scheme is a fundamental protocol for public key exchange between two parties. Its original definition over finite fields is based on the hardness of computing the map g, g a , g b → g ab for g ∈ F∗p , while its elliptic curve analogue depends on the difficulty of computing P, aP, bP → abP for points P on an elliptic curve. A natural question in this context is whether an adversary can compute some partial information about g ab (resp. abP ) for the finite field (resp. the elliptic curve) case. In studying this problem for the finite field case, Boneh and Venkatesan [4] formulated the hidden number problem (HNP) and showed that a solution to the HNP allows one to reduce the question of computing partial information to the question of computing the key itself (see also [24,15]). For example, using these techniques one can show that computing MSBk (g ab ) is tantamount to K. Srinathan, C. Pandu Rangan, M. Yung (Eds.): Indocrypt 2007, LNCS 4859, pp. 33–47, 2007. c Springer-Verlag Berlin Heidelberg 2007 

34

D. Jao, D. Jetchev, and R. Venkatesan

√ computing g ab itself for k ≥ 5 log p. In addition, the hidden number problem has turned out to be of cryptanalytic interest in its own right. For attacks on cryptosystems using partial information, see [20,23,21,16,24,17,22]. Thus an important motivation for the problem we consider is to find elliptic curve analogues of these attacks. It is natural to ask the analogous question for elliptic curve Diffie-Hellman bits, namely, can we prove that partial information about elliptic curve DiffieHellma