SHORTER HASH-AND-SIGN LATTICE-BASED SIGNATURES
Autor: | Thomas Espitau, Mehdi Tibouchi, Alexandre Wallet, Yang Yu |
---|---|
Přispěvatelé: | Network Service Systems Laboratories (NTT), NTT Corporation, Applied Cryptography and Implementation Security (CAPSULE), SYSTÈMES LARGE ÉCHELLE (IRISA-D1), Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA), Université de Rennes (UR)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-Institut National de Recherche en Informatique et en Automatique (Inria)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-IMT Atlantique (IMT Atlantique), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT)-Université de Rennes (UR)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT)-Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT), ANR-21-ASTR-0016,AMIRAL,AMélioration des sIgnatures reposant sur les Réseaux et Applications aux fonctionnaLités cryptographiques avancées(2021), ANR-22-PETQ-0008,PQ-TLS,Post-quantum padlock for web browser(2022) |
Jazyk: | angličtina |
Rok vydání: | 2022 |
Předmět: | |
Zdroj: | Advances in Cryptology – CRYPTO 2022 Advances in Cryptology – CRYPTO 2022, Aug 2022, Santa Barbara, United States. pp.245-275, ⟨10.1007/978-3-031-15979-4_9⟩ Advances in Cryptology – CRYPTO 2022 ISBN: 9783031159787 |
DOI: | 10.1007/978-3-031-15979-4_9⟩ |
Popis: | International audience; Lattice-based digital signature schemes following the hash-and-signdesign paradigm of Gentry, Peikert and Vaikuntanathan (GPV) tend to offer anattractive level of efficiency, particularly when instantiated withstructured compact trapdoors. In particular, NIST postquantum finalistFalcon~is both quite fast for signing and verification and quite compact:NIST notes that it has the smallest bandwidth (as measured in combinedsize of public key and signature) of all round 2 digital signaturecandidates. Nevertheless, while Falcon-512, for instance, comparesfavorably to ECDSA-384 in terms of speed, its signatures are well over10 times larger. For applications that store large number of signatures,or that require signatures to fit in prescribed packet sizes, this can bea critical limitation.In this paper, we explore several approaches to further improve the sizeof hash-and-sign lattice-based signatures, particularly instantiated overNTRU lattices like Falcon and its recent variant Mitaka. In particular,while GPV signatures are usually obtained by sampling lattice pointsaccording to some \emph{spherical} discrete Gaussian distribution, weshow that it can be beneficial to sample instead according to a suitablychosen ellipsoidal discrete Gaussian: this is because only half ofthe sampled Gaussian vector is actually output as the signature, whilethe other half is recovered during verification. Making the half thatactually occurs in signatures shorter reduces signature size atessentially no security loss (in a suitable range of parameters).Similarly, we show that reducing the modulus $ with respect to whichsignatures are computed can improve signature size as well asverification key size almost ``for free''; this isparticularly true for constructions like Falcon and Mitaka that do notmake substantial use of NTT-based multiplication (and rely instead ontranscendental FFT). Finally, we show that the Gaussian vectors insignatures can be represented in a more compact way with appropriatecoding-theoretic techniques, improving signature size by an additional7 to 14%. All in all, we manage to reduce the size of, e.g., Falconsignatures by 30-40% at the cost of only 4--6 bits of Core-SVPsecurity. |
Databáze: | OpenAIRE |
Externí odkaz: |
načítá se...