Cryptanalysis of a code-based one-time signature
- PDF / 524,020 Bytes
- 10 Pages / 439.37 x 666.142 pts Page_size
- 89 Downloads / 187 Views
Cryptanalysis of a code-based one-time signature Jean-Christophe Deneuville1
· Philippe Gaborit2
Received: 30 August 2019 / Revised: 22 January 2020 / Accepted: 5 February 2020 © Springer Science+Business Media, LLC, part of Springer Nature 2020
Abstract In 2012, Lyubashevsky introduced a new framework for building lattice-based signature schemes without resorting to any trapdoor [such as Gentry C, Peikert C, Vaikuntanathan V, in: Ladner and Dwork (eds) 40th ACM STOC, ACM Press, Victoria, pp. 197–206, 2008 or Hoffstein J, Pipher J, Silverman JH in: Pfitzmann (ed) EUROCRYPT 2001. LNCS, vol. 2045, pp 211–228, Springer, Heidelberg, 2001]. The idea is to sample a set of short lattice elements and construct the public key as a Short Integer Solution (SIS for short) instance. Signatures are obtained using a small subset sum of the secret key, hidden by a (large) Gaussian mask. (Information leakage is dealt with using rejection sampling.) Recently, Persichetti proposed an efficient adaptation of this framework to coding theory (Persichetti E in Cryptography 2(4):30, 2018). In this paper, we show that this adaptation cannot be secure, even for one-time signatures (OTS), due to an inherent difference between bounds in Hamming and Euclidean metrics. The attack consists in rewriting a signature as a noisy syndrome decoding problem, which can be handled efficiently using the extended bit flipping decoding algorithm. We illustrate our results by breaking Persichetti’s OTS scheme built upon this approach (Persichetti 2018): using a single signature, we recover the secret (signing) key in about the same amount of time as required for a couple of signature verifications. Keywords Post-quantum cryptography · Coding theory · Signature · Cryptanalysis Mathematics Subject Classification 94A60 · 11T71 · 14G50
The first version of this work [30] was presented in the “Eleventh International Workshop on Coding and Cryptography (WCC 2019)”. This is one of several papers published in Designs, Codes and Cryptography comprising the “Special Issue on Coding and Cryptography 2019”.
B
Jean-Christophe Deneuville [email protected] Philippe Gaborit [email protected]
1
École Nationale de l’Aviation Civile, Federal University of Toulouse, Toulouse, France
2
XLIM-MATHIS, University of Limoges, Limoges, France
123
J.-C. Deneuville, P. Gaborit
1 Introduction Building efficient and secure full-time (stateless) signature schemes from coding theory assumptions is a long standing open problem. Few years ago, Lyubashevsky [9] proposed a new method for obtaining digital signatures from lattice assumptions, that does not require the use of a trapdoor (such as GPV [7] or NTRU [8]). The construction works by sampling relatively short lattice vectors, used as the secret key. The public key is an instance of the SIS problem. To produce a digital signature, the signer commits a masking value, receives a challenge depending on the message to sign and the committed value, and computes a combination of the challenge and the secr
Data Loading...
