Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Bücher
Zeitschriften
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
MTZ-Fachkongress

Antriebe und Energiesysteme von morgen


Austausch von Automobil- und Energiewirtschaft

Am 14./15. Mai geht es in Chemnitz um die Mobilitätswende durch Elektro- und Wasserstofffahrzeuge.
Erweiterte Suche
Anmelden
nach oben
Journal of Cryptology
Erschienen in: Journal of Cryptology 3/2018

30.10.2017

Asymptotically Efficient Lattice-Based Digital Signatures

verfasst von: Vadim Lyubashevsky, Daniele Micciancio

Erschienen in: Journal of Cryptology | Ausgabe 3/2018

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

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.
Vorheriger Artikel On the Feasibility of Extending Oblivious Transfer
Nächster Artikel Fast Garbling of Circuits Under Standard Assumptions

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

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!

Jetzt informieren

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!

Jetzt informieren

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!

Jetzt informieren
Fußnoten
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.
 
Literatur
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.
R. Impagliazzo and M. Naor. Efficient cryptographic schemes provably as secure as subset sum. J. Cryptology, 9(4):199–216, 1996.MathSciNetCrossRefMATH
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.
Metadaten
Titel
Asymptotically Efficient Lattice-Based Digital Signatures
verfasst von
Vadim Lyubashevsky
Daniele Micciancio
Publikationsdatum
30.10.2017
Verlag
Springer US
Erschienen in
Journal of Cryptology / Ausgabe 3/2018
Print ISSN: 0933-2790
Elektronische ISSN: 1432-1378
DOI
https://doi.org/10.1007/s00145-017-9270-z

Weitere Artikel der Ausgabe 3/2018

Journal of Cryptology 3/2018 Zur Ausgabe

OriginalPaper

On Constructing One-Way Permutations from Indistinguishability Obfuscation

OriginalPaper

On the Feasibility of Extending Oblivious Transfer

OriginalPaper

Completeness for Symmetric Two-Party Functionalities: Revisited

OriginalPaper

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

OriginalPaper

Efficient Slide Attacks

OriginalPaper

Key-Recovery Attacks on ASASA

Premium Partner

    Bildnachweise