CryptoExperts’ staff has three accepted papers to the Eurocrypt 2013 conference and one accepted paper to the FSE 2013 workshop.
Eurocrypt is a major conference in cryptography sponsored by the International Association for Cryptologic Research (IACR) to be hold this year in Athens in May 26-30, 2013. The following papers were accepted for presentation and publication in the conference proceedings:
- Faster index calculus for the medium prime case. Application to 1175-bit and 1425-bit finite fields. written by Antoine Joux (CryptoExperts / UVSQ). This paper describes a new algorithmic technique for index calculus called PinPointing that produces new records on discrete logarithm computations.
- Batch Fully Homomorphic Encryption over the Integers written by Jung Hee Cheon (SNU), Jean-Sébastien Coron (Tranef), Jinsu Kim (SNU), Moon Sung Lee (SNU), Tancrède Lepoint (CryptoExperts and ENS), Mehdi Tibouchi (NTT), and Aaram Yun (UNIST). This paper generalizes a fully homomorphic scheme based on integers to add a batching capability (i.e. packing \(\ell\) plaintext into a single ciphertext) and describes a homomorphic evaluation of a full-fledged AES circuit in several minutes.
- Masking against Side Channel Attacks: a Formal Security Proof written by Emmanuel Prouff (ANSSI) and Matthieu Rivain (CryptoExperts). This paper provides an information theoretic security proof for implementations using masking to protect their intermediate variables in the presence of noisy side-channel leakage.
FSE (Fast Software Encryption) is a major workshop on fast software encryption sponsored by the International Association for Cryptologic Research (IACR) to be hold this year in Singapore in March 11-13, 2013. The following paper was accepted for presentation and publication in the conference proceedings:
- Higher-Order Side Channel Security and Mask Refreshing written by Jean-Sébastien Coron (Tranef), Emmanuel Prouff (ANSSI), Matthieu Rivain (CryptoExperts) and Thomas Roche (ANSSI). This paper shows how some mask refreshing procedure introduces a security flaw in previous higher-order masking schemes (in the probing security model) and propose a new method to avoid this issue.
Antoine Joux, from CryptoExperts, has recently announced new records for the computation of discrete logarithms in finite fields. This is of interest to cryptographers, because the discrete logarithm problem is the core problem which underlies Diffie-Hellman key agreement protocol.
This protocol was originally introduced with a restricted form of finite fields, namely prime fields. In other words, the system is given by three parameters, a prime \(p\), a divisor \(q\) of \((p-1)\) and an element \(g\) of order \(q\) modulo \(p\). This means that the numbers \(g^x \bmod p\) are all distinct for \(x\) in \([0,q-1]\).
Given these parameters, in order to create a common key, two users Alice and Bob, proceed as follows:
1) Alice chooses a secret number \(A\) in \([0,q-1]\) and Bob a number \(B\)
2) The users compute and announce \(g^A \bmod p\) and \(g^B \bmod B\)
3) Alice computes \((g^B)^A \bmod p\) and Bob \((g^A)^B \bmod p\). These numbers are equal and can serve as a common key.
Note that in this form, the protocol is unauthenticated and suffers from Man-in-the-Middle attacks.
Later on, the Diffie-Hellman protocol was generalized to other groups. First, the multiplicative group of an arbitrary finite field, then elliptic curves over finite fields.
The use of different finite fields (esp. fields of the form \(GF(2^n)\)) allows to improve the efficiency of the underlying arithmetic computations compared to \(GF(p)\).
An essential property for the security of the Diffie-Hellman protocol is that the discrete logarithm problem in the considered group should be difficult. Otherwise, it is possible to recover \(A\) from the publicly visible value \(g^A\), which breaks the security of the key exchange.
As a consequence, in order to securely use cryptographic protocols based on Diffie-Hellman, it is essential to understand the computational hardness of computing discrete logarithms. The recent records announced by CryptoExperts are based on a new algorithmic technique called PinPointing which will be described in a reseach paper Faster index calculus for the medium prime case to appear at the Eurocrypt 2013 conference.
This technique is currently applicable to finite field of the form \(GF(q^k)\), where \(q\) is a moderate size (typically in the 16—32 bit range) and \(k\) is large enough to obtain a large finite field. Until recently, it was known that these fields were slightly less secure than prime fields, however, the situation was not critical and the previous record involved a field of size \(923\) bits. With the recent records, it has been shown that a \(1400+\) bitsize is easily attackable. As a consequence, we recommend to all cryptographic users to stop using medium prime fields.
CryptoExperts pursues its evaluation effort on the security of discrete logarithms, in order to assess more precisely the limits of applicability of Pinpointing.
Antoine Joux is a former PhD student of Jacques Stern, on Lattice Reduction and Cryptography. From 1993 to 1998, he was a cryptographer for the French defense procurement agency (DGA). In 1998, he joined the French national security agency (ANSSI), where he became head of the scientific division. From 2004 to 2012, he returned to DGA and joined the division in charge of interfacing with scientific research (DGA/MRIS)
In parallel, since september 2004, Antoine is a part-time professor at the University of Versailles Saint-Quentin-en-Yvelines and an active member of the academic community in cryptology. He was an elected director of the International Association for Cryptologic Research (IACR) from 2006 to 2011 and has been program chair of Eurocrypt’2009 and FSE’2011. Since 2009, he is an associate editor for the Journal of Cryptology.
His research interests include several topics such as hash functions, pairings, stream ciphers, modes of operation, computation of discrete logarithms, ... Many of his contributions concern cryptanalysis and are reflected in his book Algorithmic Cryptanalysis. A list of his publications can be found on DBLP.
Antoine has been an invited speaker in several research venues such as ANTS’2002, NIST Hash Workshop 2005, ECC’2008, Africacrypt’2009, SSTIC’09, Eurocrypt’2012, WMC’2012. He is also “Chevalier de l’Ordre National du Mérite” and “Chevalier dans l’Ordre des Palmes Académiques”.
From Nov. 6 to Nov. 8, CryptoExperts exhibits at CARTES 2012! Come and visit our booth where you will know more about our service offers. Take some time to discover our new encryption technology for secure content distribution, the industry’s first efficient cryptographic solution that enables CAS vendors and content providers to remotely revoke compromised smart cards used by control word servers and thereby efficiently thwart pirate activities. Meet our expert developers of CC-ready embedded cryptographic libraries for smart cards and get all your questions answered.
Meet us there: Hall 4, Aisle J, Stand 121. We would love to hear from you!
On October 2nd 2012, the NIST announced Keccak as the winner of the SHA-3 Cryptographic Hash Algorithm Competition. CryptoExperts congratulates the designers of Keccak for winning this competition.
The SHA-3 competition was launched in 2007, and counted 64 submissions. CryptoExperts members were involved in three different submissions (Pascal Paillier in Shabal, Matthieu Finiasz in FSB and Louis Goubin in Crunch). The designs of these three hash functions were very different from each other, reflecting the multidisciplinary of CryptoExperts members in advanced cryptographic research.
Keccak was finally chosen for several reasons, in particular its elegant new (3D) design, its good general performance and its flexibility. Keccak was not the fastest candidate among the finalists (benchmarks) but a key-argument was its complementarity to the existing SHA-2 family of hash algorithms. Indeed, the huge difference between their inner-design makes it very unlikely that a cryptanalytic attack against one scheme could be applied to the other scheme.
As pointed out by the NIST, the selection of the SHA-3 does not make the SHA-2 family obsolete and there is no need for a rapid transition from SHA-2 to SHA-3. However, it is probably a good idea to start including implementations of SHA-3 in new products. If you are in need of a secure implementation of Keccak for your smartcard cryptographic libraries, you can always contact us!
Matthieu Finiasz did his PhD in the project team SECRET at INRIA from 2001 to 2004 and was a postdoctoral researcher at EPFL in the LASEC team from 2004 to 2007. After 5 years as a research scientist at ENSTA he joins CryptoExperts today. His research interests are the design of efficient code-based cryptosystems and, more generally, applications of coding theory to symmetric and asymmetric cryptography. Matthieu has a thorough research experience and numerous scientific publications in the field of code-based cryptographic systems. Among other achievements, Matthieu is one of the designers of the CFS signature scheme (2001), the first signature scheme with a tight security reduction to the syndrome decoding problem (the central NP-complete problem in code-based cryptography). He also designed other cryptographic primitives with similar security reductions, like the provably secure hash function FSB submitted to the NIST SHA-3 competition (2008).
Matthieu Finiasz’s web page.