Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Journal of Cryptology
Published in: Journal of Cryptology 3/2018

30-10-2017

Asymptotically Efficient Lattice-Based Digital Signatures

Authors: Vadim Lyubashevsky, Daniele Micciancio

Published in: Journal of Cryptology | Issue 3/2018

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

We present a general framework that converts certain types of linear collision-resistant hash functions into one-time signatures. Our generic construction can be instantiated based on both general and ideal (e.g., cyclic) lattices, and the resulting signature schemes are provably secure based on the worst-case hardness of approximating the shortest vector (and other standard lattice problems) in the corresponding class of lattices to within a polynomial factor. When instantiated with ideal lattices, the time complexity of the signing and verification algorithms, as well as key and signature size, is almost linear (up to poly-logarithmic factors) in the dimension n of the underlying lattice. Since no sub-exponential (in n) time algorithm is known to solve lattice problems in the worst case, even when restricted to ideal lattices, our construction gives a digital signature scheme with an essentially optimal performance/security trade-off.
previous article On the Feasibility of Extending Oblivious Transfer
next article Fast Garbling of Circuits Under Standard Assumptions

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

inform now
Footnotes
1
To make sure that someone does not choose \(\mathbf {H}\) with a planted trapdoor, it could be demanded that \(\mathbf {H}=\text {XOF}(x)\) where XOF is some extendable output function (e.g., SHAKE [32]) and x is a public seed.
 
2
Notice that the following equality holds true also when \(b=1\), because \(\tilde{\mathbf {K}}\mathbf {m}=\mathbf {K}\mathbf {m}\) for all \(\tilde{\mathbf {K}} \in \mathcal {D}_\mathbf {H}(\mathbf {K},\mathbf {m})\). But this is not used in this step of the proof.
 
3
All the signature schemes are proved secure in the random oracle model.
 
4
We are just using the notation from this paper as an analogy. The actual keys in the full-fledged signature are constructed a little differently. In particular, the (secret and public) keys in this work actually comprise both the (secret and public) keys and the “commit” step of the \(\varSigma \)-protocols underlying the full signature schemes. We refer readers to [23] for a more in-depth discussion about the relationship of collision-resistant hash functions, one-time signatures, \(\varSigma \)-protocols, and full signatures.
 
Literature
1.
M. Ajtai. Generating hard instances of lattice problems (extended abstract). In STOC, pages 99–108, 1996.
2.
J.N. Bos and D. Chaum. Provably unforgeable signatures. In CRYPTO, pages 1–14, 1992.
3.
S. Bai and S.D. Galbraith. An improved compression technique for signatures based on learning with errors. In CT-RSA, pages 28–47, 2014.
4.
A. Blum, A. Kalai, and H. Wasserman. Noise-tolerant learning, the parity problem, and the statistical query model. J. ACM, 50(4):506–519, 2003. Prelim. version in STOC 2000.
5.
M. Blum and S. Micali. How to generate cryptographically strong sequences of pseudo-random bits. SIAM J. Comput., 13(4):850–864, 1984. Prelim. version in FOCS 1982.
6.
D. Bleichenbacher and U.M. Maurer. On the efficiency of one-time digital signatures. In ASIACRYPT, pages 145–158, 1996.
7.
N. Courtois, M. Finiasz, and N. Sendrier. How to achieve a McEliece-based digital signature scheme. In ASIACRYPT, pages 157–174, 2001.
8.
L. Ducas, A. Durmus, T. Lepoint, and V. Lyubashevsky. Lattice signatures and bimodal gaussians. In CRYPTO (1), pages 40–56, 2013.
9.
10.
11.
S. Even, O. Goldreich, and S. Micali. On-line/off-line digital signatures. J. Cryptology, 9(1):35–67, 1996. Prelim. version in CRYPTO 1989.
12.
R. Gennaro, Y. Gertner, J. Katz, and L. Trevisan. Bounds on the efficiency of generic cryptographic constructions. SIAM J. Comput., 35(1):217–246, 2005. Prelim. versions in FOCS 2000 and STOC 2003.
13.
S. Goldwasser, S. Micali, and R.L. Rivest. A digital signature scheme secure against adaptive chosen-message attacks. SIAM J. Comput., 17(2):281–308, 1988.MathSciNetCrossRefMATH
14.
C. Gentry, C. Peikert, and V. Vaikuntanathan. Trapdoors for hard lattices and new cryptographic constructions. In STOC, pages 197–206, 2008.
15.
A. Hevia and D. Micciancio. The provable security of graph-based one-time signatures and extensions to algebraic signature schemes. In ASIACRYPT, pages 379–396, 2002.
16.
17.
V. Lyubashevsky and D. Micciancio. Generalized compact knapsacks are collision resistant. In ICALP (2), pages 144–155, 2006.MathSciNetMATH
18.
V. Lyubashevsky and D. Micciancio. Asymptotically efficient lattice-based digital signatures. In TCC, pages 37–54, 2008.
19.
V. Lyubashevsky, C. Peikert, and O. Regev. On ideal lattices and learning with errors over rings. J. ACM, 60(6):43:1–43:35, 2013. Prelim. version in Eurocrypt 2010.
20.
V. Lyubashevsky, C. Peikert, and O. Regev. A toolkit for Ring-LWE cryptography. In EUROCRYPT, pages 35–54, 2013.
21.
V. Lyubashevsky. The parity problem in the presence of noise, decoding random linear codes, and the subset sum problem. In APPROX-RANDOM, pages 378–389, 2005.
22.
V. Lyubashevsky. Lattice-based identification schemes secure under active attacks. In Public Key Cryptography, pages 162–179, 2008.
23.
V. Lyubashevsky. Fiat-Shamir with aborts: Applications to lattice and factoring-based signatures. In ASIACRYPT, pages 598–616, 2009.
24.
V. Lyubashevsky. Lattice signatures without trapdoors. In EUROCRYPT, pages 738–755, 2012.
25.
V. Lyubashevsky. Digital signatures based on the hardness of ideal lattice problems in all rings. In ASIACRYPT, pages 196–214, 2016.
26.
C.A. Melchor, S. Bettaieb, X. Boyen, L. Fousse, and P. Gaborit. Adapting Lyubashevsky’s signature schemes to the ring signature setting. In AFRICACRYPT, pages 1–25, 2013.
27.
R.C. Merkle. A digital signature based on a conventional encryption function. In CRYPTO, pages 369–378, 1987.
28.
R.C. Merkle. A certified digital signature. In CRYPTO, pages 218–238, 1989.
29.
D. Micciancio. Generalized compact knapsacks, cyclic lattices, and efficient one-way functions. Computational Complexity, 16(4):365–411, 2007. Prelim. version in FOCS 2002.
30.
D. Micciancio and C. Peikert. Hardness of SIS and LWE with small parameters. In CRYPTO (1), pages 21–39, 2013.
31.
D. Micciancio and O. Regev. Worst-case to average-case reductions based on gaussian measures. SIAM J. Comput., 37(1):267–302, 2007. Prelim. version in FOCS 2004.
32.
33.
M. Naor and M. Yung. Universal one-way hash functions and their cryptographic applications. In STOC, pages 33–43, 1989.
34.
C. Peikert and A. Rosen. Efficient collision-resistant hashing from worst-case assumptions on cyclic lattices. In TCC, pages 145–166, 2006.
35.
C. Peikert and A. Rosen. Lattices that admit logarithmic worst-case to average-case connection factors. In STOC, pages 478–487, 2007.
36.
J. Rompel. One-way functions are necessary and sufficient for secure signatures. In STOC, pages 387–394, 1990.
37.
M. Rückert. Lattice-based blind signatures. In ASIACRYPT, pages 413–430, 2010.
38.
M. Szydlo. Merkle tree traversal in log space and time. In EUROCRYPT, pages 541–554, 2004.
39.
D. Wagner. A generalized birthday problem. In CRYPTO, volume 2442 of Lecture Notes in Computer Science, pages 288–303. Springer, 2002.
Metadata
Title
Asymptotically Efficient Lattice-Based Digital Signatures
Authors
Vadim Lyubashevsky
Daniele Micciancio
Publication date
30-10-2017
Publisher
Springer US
Published in
Journal of Cryptology / Issue 3/2018
Print ISSN: 0933-2790
Electronic ISSN: 1432-1378
DOI
https://doi.org/10.1007/s00145-017-9270-z

Other articles of this Issue 3/2018

Journal of Cryptology 3/2018 Go to the issue

OriginalPaper

Efficient Slide Attacks

OriginalPaper

Stream Ciphers: A Practical Solution for Efficient Homomorphic-Ciphertext Compression

OriginalPaper

On Constructing One-Way Permutations from Indistinguishability Obfuscation

OriginalPaper

Completeness for Symmetric Two-Party Functionalities: Revisited

OriginalPaper

Key-Recovery Attacks on ASASA

OriginalPaper

On the Feasibility of Extending Oblivious Transfer

Premium Partner

    Image Credits