Article

On Removing Rejection Conditions in Practical Lattice-Based Signatures

Authors:

Rouzbeh Behnia,

Daniel MasnyAuthors Info & Claims

Post-Quantum Cryptography: 12th International Workshop, PQCrypto 2021, Daejeon, South Korea, July 20–22, 2021, Proceedings

Pages 380 - 398

https://doi.org/10.1007/978-3-030-81293-5_20

Published: 20 July 2021 Publication History

Abstract

Digital signatures following the methodology of “Fiat-Shamir with Aborts”, proposed by Lyubashevsky, are capable of achieving the smallest public-key and signature sizes among all the existing lattice signature schemes based on the hardness of the Ring-SIS and Ring-LWE problems. Since its introduction, several variants and optimizations have been proposed, and two of them (i.e., Dilithium and qTESLA) entered the second round of the NIST post-quantum cryptography standardization. This method of designing signatures relies on rejection sampling during the signing process. Rejection sampling is crucial for ensuring both the correctness and security of these signature schemes.

In this paper, we investigate the possibility of removing the two rejection conditions used both in Dilithium and qTESLA. First, we show that removing one of the rejection conditions is possible, and provide a variant of Lyubashevsky’s signature with comparable parameters with Dilithium and qTESLA. Second, we give evidence on the difficulty of removing the other rejection condition, by showing that two very general approaches do not yield a signature scheme with correctness or security.

References

[1]

Ajtai, M.: Generating hard instances of lattice problems (extended abstract). In: STOC, pp. 99–108 (1996)

[2]

Albrecht MR et al. Catalano D, De Prisco R, et al. Estimate all the LWE, NTRU schemes! Security and Cryptography for Networks 2018 Cham Springer 351-367

[3]

Albrecht MR, Player R, and Scott S On the concrete hardness of learning with errors J. Math. Cryptol. 2015 9 3 169-203

[4]

Alkim, E., et al.: The lattice-based digital signature scheme qtesla. IACR Cryptology ePrint Archive, vol. 85 (2019)

[5]

Bai S and Galbraith SD Benaloh J An improved compression technique for signatures based on learning with errors Topics in Cryptology – CT-RSA 2014 2014 Cham Springer 28-47

[6]

Boyd, C.: Digital multisignatures. Cryptography and Coding, pp. 241–246 (1986)

[7]

Chaum D Chaum D, Rivest RL, and Sherman AT Blind signatures for untraceable payments Advances in Cryptology 1983 Boston, MA Springer 199-203

[8]

Desmedt Y Pomerance C Society and group oriented cryptography: a new concept Advances in Cryptology — CRYPTO ’87 1988 Heidelberg Springer 120-127

[9]

Desmedt Y and Frankel Y Brassard G Threshold cryptosystems Advances in Cryptology — CRYPTO’ 89 Proceedings 1990 New York Springer 307-315

[10]

Ding J, Fluhrer S, and Rv S Susilo W and Yang G Complete attack on RLWE key exchange with reused keys, without signal leakage Information Security and Privacy 2018 Cham Springer 467-486

[11]

Ding, J., Xie, X., Lin, X.: A simple provably secure key exchange scheme based on the learning with errors problem. Cryptology ePrint Archive, Report 2012/688 (2012)

[12]

Ducas L, Durmus A, Lepoint T, and Lyubashevsky V Canetti R and Garay JA Lattice signatures and bimodal gaussians Advances in Cryptology – CRYPTO 2013 2013 Heidelberg Springer 40-56

[13]

Ducas L et al. Crystals-dilithium: a lattice-based digital signature scheme IACR Trans. Cryptogr. Hardw. Embed. Syst. 2018 2018 1 238-268

[14]

Fiat A and Shamir A Odlyzko AM How to prove yourself: practical solutions to identification and signature problems Advances in Cryptology — CRYPTO’ 86 1987 Heidelberg Springer 186-194

[15]

Fluhrer, S.R.: Cryptanalysis of ring-LWE based key exchange with key share reuse. IACR Cryptology ePrint Arch. vol. 85 (2016)

[16]

Gentry, C., Peikert, C., Vaikuntanathan, V.: Trapdoors for hard lattices and new cryptographic constructions. In: STOC, pp. 197–206 (2008)

[17]

Gentry C and Szydlo M Knudsen LR Cryptanalysis of the revised NTRU signature scheme Advances in Cryptology — EUROCRYPT 2002 2002 Heidelberg Springer 299-320

[18]

Goldreich O, Goldwasser S, and Halevi S Kaliski BS Public-key cryptosystems from lattice reduction problems Advances in Cryptology — CRYPTO ’97 1997 Heidelberg Springer 112-131

[19]

Güneysu T, Lyubashevsky V, and Pöppelmann T Prouff E and Schaumont P Practical lattice-based cryptography: a signature scheme for embedded systems Cryptographic Hardware and Embedded Systems – CHES 2012 2012 Heidelberg Springer 530-547

[20]

Guo S, Kamath P, Rosen A, and Sotiraki K Kiayias A, Kohlweiss M, Wallden P, and Zikas V Limits on the efficiency of (Ring) LWE based non-interactive key exchange Public-Key Cryptography – PKC 2020 2020 Cham Springer 374-395

[21]

Hoffstein J, Howgrave-Graham N, Pipher J, Silverman JH, and Whyte W Joye M NTRUSign: digital signatures using the NTRU lattice Topics in Cryptology — CT-RSA 2003 2003 Heidelberg Springer 122-140

[22]

Kiltz E, Lyubashevsky V, and Schaffner C Nielsen JB and Rijmen V A concrete treatment of Fiat-Shamir signatures in the quantum random-oracle model Advances in Cryptology – EUROCRYPT 2018 2018 Cham Springer 552-586

[23]

Lyubashevsky V Matsui M Fiat-Shamir with aborts: applications to lattice and factoring-based signatures Advances in Cryptology – ASIACRYPT 2009 2009 Heidelberg Springer 598-616

[24]

Lyubashevsky V Pointcheval D and Johansson T Lattice signatures without trapdoors Advances in Cryptology – EUROCRYPT 2012 2012 Heidelberg Springer 738-755

[25]

Migliore, V., Benoît Gérard, Tibouchi, M., Fouque, P.-A.: Masking dilithium - efficient implementation and side-channel evaluation. In: Applied Cryptography and Network Security - 17th International Conference, ACNS 2019, Bogota, Colombia, 5–7 June 2019, Proceedings, pp. 344–362 (2019)

[26]

Nguyen PQ and Regev O Vaudenay S Learning a parallelepiped: cryptanalysis of GGH and NTRU signatures Advances in Cryptology - EUROCRYPT 2006 2006 Heidelberg Springer 271-288

[27]

Peikert C Mosca M Lattice cryptography for the internet Post-Quantum Cryptography 2014 Cham Springer 197-219

[28]

Regev, O.: On lattices, learning with errors, random linear codes, and cryptography. J. ACM 56(6), 40 (2009)

[29]

Schnorr CP Brassard G Efficient identification and signatures for smart cards Advances in Cryptology — CRYPTO’ 89 Proceedings 1990 New York Springer 239-252

[30]

Unruh D Takagi T and Peyrin T Post-quantum security of Fiat-Shamir Advances in Cryptology – ASIACRYPT 2017 2017 Cham Springer 65-95

Cited By

Devevey JPasselègue AStehlé D(2023)G+G: A Fiat-Shamir Lattice Signature Based on Convolved GaussiansAdvances in Cryptology – ASIACRYPT 202310.1007/978-981-99-8739-9_2(37-64)Online publication date: 4-Dec-2023
https://dl.acm.org/doi/10.1007/978-981-99-8739-9_2
Arnal XCano AFinogina THerranz J(2022)How to Avoid Repetitions in Lattice-Based Deniable Zero-Knowledge ProofsSecure IT Systems10.1007/978-3-031-22295-5_14(253-269)Online publication date: 30-Nov-2022
https://dl.acm.org/doi/10.1007/978-3-031-22295-5_14

Index Terms

On Removing Rejection Conditions in Practical Lattice-Based Signatures
1. Security and privacy
  1. Cryptography
    1. Public key (asymmetric) techniques
      1. Public key encryption
2. Theory of computation
  1. Computational complexity and cryptography

Index terms have been assigned to the content through auto-classification.

Recommendations

Lattice-based deniable ring signatures

In cryptography, a ring signature is anonymous as it hides the signer's identity among other users. When generating the signature, the users are arranged as a ring. Compared with group signatures, a ring signature scheme needs no group manager or ...
Towards Practical Lattice-Based One-Time Linkable Ring Signatures
Information and Communications Security
Abstract
Ring signatures, as introduced by Rivest, Shamir, and Tauman (Asiacrypt ’01), allow to generate a signature for a message on behalf of an ad-hoc set of parties. To sign a message, only the public keys must be known and these can be generated ...
Practical verifiably encrypted signature based on Waters signatures

Waters proposed the first efficient signature scheme that is known to be existentially unforgeable based on the standard computational Diffie‐Hellman assumption without random oracles. Lu et al. then proposed the first verifiably encrypted signature (VES) ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Guide Proceedings

Post-Quantum Cryptography: 12th International Workshop, PQCrypto 2021, Daejeon, South Korea, July 20–22, 2021, Proceedings

Jul 2021

501 pages

ISBN:978-3-030-81292-8

DOI:10.1007/978-3-030-81293-5

Editors:
Jung Hee Cheon
Seoul National University, Seoul, Korea (Republic of)
,
Jean-Pierre Tillich
Inria, Paris, France

© Springer Nature Switzerland AG 2021.

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 20 July 2021

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

2
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 02 Oct 2024

Other Metrics

View Author Metrics

Citations

Cited By

Devevey JPasselègue AStehlé D(2023)G+G: A Fiat-Shamir Lattice Signature Based on Convolved GaussiansAdvances in Cryptology – ASIACRYPT 202310.1007/978-981-99-8739-9_2(37-64)Online publication date: 4-Dec-2023
https://dl.acm.org/doi/10.1007/978-981-99-8739-9_2
Arnal XCano AFinogina THerranz J(2022)How to Avoid Repetitions in Lattice-Based Deniable Zero-Knowledge ProofsSecure IT Systems10.1007/978-3-031-22295-5_14(253-269)Online publication date: 30-Nov-2022
https://dl.acm.org/doi/10.1007/978-3-031-22295-5_14

View Options

View options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Table of Contents