CryptoDB
Antoine Joux
Publications
Year
Venue
Title
2022
EUROCRYPT
Practical Post-Quantum Signature Schemes from Isomorphism Problems of Trilinear Forms
📺
Abstract
In this paper, we propose a practical signature scheme based on the alternating trilinear form equivalence problem. Our scheme is inspired from the Goldreich-Micali-Wigderson's zero-knowledge protocol for graph isomorphism, and can be served as an alternative candidate for the NIST's post-quantum digital signatures.
First, we present theoretical evidences to support its security, especially in the post-quantum cryptography context. The evidences are drawn from several research lines, including hidden subgroup problems, multivariate cryptography, cryptography based on group actions, the quantum random oracle model, and recent advances on isomorphism problems for algebraic structures in algorithms and complexity.
Second, we demonstrate its potential for practical uses. Based on algorithm studies, we propose concrete parameter choices, and then implement a prototype. One concrete scheme achieves 128 bit security with public key size ~4100 bytes, signature size ~6800 bytes, and running times (key generation, sign, verify) ~0.8ms on a common laptop computer.
2022
CRYPTO
Syndrome Decoding in the Head: Shorter Signatures from Zero-Knowledge Proofs
📺
Abstract
Zero-knowledge proofs of knowledge are useful tools to design signature schemes. The ongoing effort to build a quantum computer motivates the cryptography community to develop new secure cryptographic protocols based on quantum-hard cryptographic problems. One of the few directions is code-based cryptography for which the strongest problem is the syndrome decoding (SD) for random linear codes. This problem is known to be NP-hard and the cryptanalysis state of the art has been stable for many years. A zero-knowledge protocol for this problem was pioneered by Stern in 1993. Since its publication, many articles proposed optimizations, implementation, or variants.
In this paper, we introduce a new zero-knowledge proof for the syndrome decoding problem on random linear codes. Instead of using permutations like most of the existing protocols, we rely on the MPC-in-the-head paradigm in which we reduce the task of proving the low Hamming weight of the SD solution to proving some relations between specific polynomials. We propose a 5-round zero-knowledge protocol that proves the knowledge of a vector x such that y=Hx and \wt(x) <= w and which achieves a soundness error closed to 1/N for an arbitrary N.
While turning this protocol into a signature scheme, we achieve a signature size of 11-12 KB for a 128-bit security when relying on the hardness of the SD problem on binary fields. Using bigger fields (like \F_{2^8}), we can produce fast signatures of around 8 KB. This allows us to outperform Picnic3 and to be competitive with SPHINCS+, both post-quantum signature candidates in the ongoing NIST standardization effort. Moreover, our scheme outperforms all the existing code-based signature schemes for the common ``signature size + public key size'' metric.
2018
CRYPTO
A New Public-Key Cryptosystem via Mersenne Numbers
📺
Abstract
In this work, we propose a new public-key cryptosystem whose security is based on the computational intractability of the following problem: Given a Mersenne number
$$p = 2^n - 1$$
p=2n-1, where n is a prime, a positive integer h, and two n-bit integers T, R, decide whether their exist n-bit integers F, G each of Hamming weight less than h such that
$$T = F\cdot R + G$$
T=F·R+G modulo p.
2018
ASIACRYPT
How to Securely Compute with Noisy Leakage in Quasilinear Complexity
Abstract
Since their introduction in the late 90’s, side-channel attacks have been considered as a major threat against cryptographic implementations. This threat has raised the need for formal leakage models in which the security of implementations can be proved. At Eurocrypt 2013, Prouff and Rivain introduced the noisy leakage model which has been argued to soundly capture the physical reality of power and electromagnetic leakages. In their work, they also provide the first formal security proof for a masking scheme in the noisy leakage model. However their work has two important limitations: (i) the security proof relies on the existence of a leak-free component, (ii) the tolerated amount of information in the leakage (aka leakage rate) is of O(1 / n) where n is the security parameter (i.e. the number of shares in the underlying masking scheme). The first limitation was nicely tackled by Duc, Dziembowski and Faust one year later (Eurocrypt 2014). Their main contribution was to show a security reduction from the noisy leakage model to the conceptually simpler random-probing model. They were then able to prove the security of the well-known Ishai-Sahai-Wagner scheme (Crypto 2003) in the noisy leakage model. The second limitation was addressed in a paper by Andrychowicz, Dziembowski and Faust (Eurocrypt 2016) which makes use of a construction due to Ajtai (STOC 2011) to achieve security in the strong adaptive probing model with a leakage rate of $$O(1/\log n)$$. The authors argue that their result can be translated into the noisy leakage model with a leakage rate of O(1) by using secret sharing based on algebraic geometric codes. In terms of complexity, the protected program scales from |P| arithmetic instructions to $$\tilde{O}(|P| \, n^2)$$. According to the authors, this $$\tilde{O}(n^2)$$ blow-up could be reduced to $$\tilde{O}(n)$$ using packed secret sharing but no details are provided. Moreover, such an improvement would only be possible for a program of width at least linear in n. The issue of designing an explicit scheme achieving $$\tilde{O}(n)$$ complexity blow-up for any arithmetic program is hence left open.In this paper, we tackle the above issue: we show how to securely compute in the presence of noisy leakage with a leakage rate $$\tilde{O}(1)$$ and complexity blow-up $$\tilde{O}(n)$$. Namely, we introduce a transform that turns any program P composed of arithmetic instructions on some filed $$\mathbb {F}$$ into a (functionally equivalent) program $$\varPi $$ composed of $$|\varPi | = O(|P| n \log n)$$ arithmetic instructions which can tolerate some (quasi-constant) amount of noisy leakage on its internal variables (while revealing negligible information). We use a polynomial encoding allowing quasilinear multiplication based on the fast Number Theoretic Transform (NTT). We first show that our scheme is secure in the random-probing model with leakage rate $$O(1/\log n)$$. Using the reduction by Duc et al. this result can be translated in the noisy leakage model with a $$O(1/|\mathbb {F}|^2 \log n)$$ leakage rate. However, a straight application of this reduction is not satisfactory since our construction requires $$|\mathbb {F}| = O(n)$$. In order to bypass this issue (which is shared with the construction of Andrychowicz et al.), we provide a generic security reduction from the noisy leakage model at the logical-instruction level to the random-probing model at the arithmetic level. This reduction allows us to prove the security of our construction in the noisy leakage model with leakage rate $$\tilde{O}(1)$$.
2014
EUROCRYPT
2014
EUROCRYPT
2013
EUROCRYPT
2012
EUROCRYPT
2012
EUROCRYPT
2012
EUROCRYPT
2003
CRYPTO
2003
JOFC
2002
FSE
Program Committees
- Crypto 2020
- Asiacrypt 2016
- PKC 2013
- FSE 2012
- Crypto 2012
- Asiacrypt 2012
- Asiacrypt 2011
- FSE 2011 (Program chair)
- Asiacrypt 2010
- FSE 2010
- Eurocrypt 2010
- Eurocrypt 2009 (Program chair)
- FSE 2008
- Eurocrypt 2008
- Crypto 2007
- FSE 2007
- Asiacrypt 2006
- FSE 2006
- Eurocrypt 2006
- FSE 2005
- Crypto 2005
- Eurocrypt 2004
- Crypto 2003
- PKC 2002
- Eurocrypt 2002
Coauthors
- Divesh Aggarwal (1)
- Razvan Barbulescu (1)
- Aurélie Bauer (1)
- Anja Becker (2)
- Eli Biham (2)
- Dan Boneh (1)
- Patrick Carribault (1)
- Guilhem Castagnos (1)
- Florent Chabaud (1)
- Yeow Meng Chee (1)
- Rafi Chen (2)
- Philippe Chose (1)
- Jean-Sébastien Coron (3)
- Thai Duong (1)
- Jean-Charles Faugère (2)
- Thibauld Feneuil (1)
- Pierre-Alain Fouque (1)
- Pierrick Gaudry (1)
- Henri Gilbert (1)
- Dahmun Goudarzi (1)
- Louis Granboulan (2)
- Helena Handschuh (1)
- Nick Howgrave-Graham (1)
- Louise Huot (1)
- William Jalby (1)
- Éliane Jaulmes (4)
- Ilya Kizhvatov (1)
- Sébastien Kunz-Jacques (1)
- Fabien Laguillaumie (1)
- Christophe Lemuet (1)
- Reynald Lercier (2)
- Stefan Lucks (1)
- Avradip Mandal (1)
- Gwenaëlle Martinet (1)
- Chrysanthi Mavromati (1)
- Alexander May (1)
- Marcel Medwed (1)
- Alexander Meurer (1)
- Michel Mitton (1)
- Frédéric Muller (4)
- David Naccache (3)
- Kim Nguyen (1)
- Phong Q. Nguyen (2)
- Pascal Paillier (1)
- Thomas Peyrin (1)
- Cécile Pierrot (1)
- Thomas Plantard (1)
- Guillaume Poupard (1)
- Anupam Prakash (1)
- Youming Qiao (1)
- Jean-René Reinhard (1)
- Guénaël Renault (1)
- Pierre-Michel Ricordel (1)
- Matthieu Rivain (2)
- Miklos Santha (1)
- Nigel P. Smart (1)
- François-Xavier Standaert (1)
- Jacques Stern (5)
- Willy Susilo (1)
- Gang Tang (1)
- Emmanuel Thomé (2)
- Mehdi Tibouchi (1)
- Frédéric Valette (2)
- Serge Vaudenay (1)
- Frederik Vercauteren (1)
- Vanessa Vitse (2)