The Twist-AUgmented technique for key exchange

Olivier Chevassut (1) , Pierre-Alain Fouque (2) , Pierrick Gaudry (3, 4) , David Pointcheval (2)

1 LBNL - Lawrence Berkeley National Laboratory [Berkeley]
2 LIENS - Laboratoire d'informatique de l'école normale supérieure
3 SPACES - Solving problems through algebraic computation and efficient software
4 TANC - Algorithmic number theory for cryptology

Key derivation refers to the process by which an agreed upon large random number, often named master secret, is used to derive keys to encrypt and authenticate data. Practitioners and standardization bodies have usually used the random oracle model to get key material from a Diffie-Hellman key exchange. However, formal proofs in the standard model require randomness extractors to formally extract the entropy of the random master secret into a seed prior to deriving other keys. Whereas this is a quite simple tool, it is not easy to use in practice ­or it is easy to misuse it­. In addition, in many standards, the acronym PRF (Pseudo-Random Functions) is used for several tasks, and namely the randomness extraction. While randomness extractors and pseudo-random functions are a priori distinct tools, we first study whether such an application is correct or not. We thereafter study the case of Zp where p is a safe-prime and the case of elliptic curve since in IPSec for example, only these two groups are considered. We present very efficient and provable randomness extraction techniques for these groups under the DDH assumption. In the special case of elliptic curves, we present a new technique --the so-called 'Twist-AUgmented' technique-- which exploits specific properties of some elliptic curves, and avoids the need of any randomness extractor. We finally compare the efficiency of this method with other solutions.

Domaines: Cryptographie et sécurité [cs.CR]

Olivier Chevassut, Pierre-Alain Fouque, Pierrick Gaudry, David Pointcheval. The Twist-AUgmented technique for key exchange. 9th International Conference on Theory and Practice of Public Key Cryptology - PKC 2006, Apr 2006, New York, USA, pp.410-426. ⟨inria-00103433⟩