Skip to Main content Skip to Navigation
Conference papers

The Twist-AUgmented technique for key exchange

Olivier Chevassut 1 Pierre-Alain Fouque 2 Pierrick Gaudry 3, 4 David Pointcheval 2
3 SPACES - Solving problems through algebraic computation and efficient software
INRIA Lorraine, LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
4 TANC - Algorithmic number theory for cryptology
Inria Saclay - Ile de France, LIX - Laboratoire d'informatique de l'École polytechnique [Palaiseau]
Abstract : 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.
Document type :
Conference papers
Complete list of metadatas

Cited literature [25 references]  Display  Hide  Download
Contributor : Pierrick Gaudry <>
Submitted on : Wednesday, October 4, 2006 - 1:32:02 PM
Last modification on : Thursday, February 11, 2021 - 2:48:25 PM
Long-term archiving on: : Tuesday, April 6, 2010 - 6:07:06 PM


  • HAL Id : inria-00103433, version 1



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⟩



Record views


Files downloads