Movatterモバイル変換

[0]ホーム
URL:

Skip to main content

Advertisement

Springer Nature Link
Log in

Asymptotically Efficient Lattice-Based Digital Signatures

  • Conference paper

Part of the book series:Lecture Notes in Computer Science ((LNSC,volume 4948))

Included in the following conference series:

Abstract

We give a direct construction of digital signatures based on the complexity of approximating the shortest vector in ideal (e.g., cyclic) lattices. The construction is provably secure based on the worst-case hardness of approximating the shortest vector in such lattices within a polynomial factor, and it is also asymptotically efficient: 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 dimensionn of the underlying lattice. Since no sub-exponential (inn) time algorithm is known to solve lattice problems in the worst case, even when restricted to cyclic lattices, our construction gives a digital signature scheme with an essentially optimal performance/security trade-off.

Research supported in part by NSF grant CCF-0634909. Any opinions, findings, and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the National Science Foundation.

Similar content being viewed by others

Keywords

These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

References

  1. Aharonov, D., Regev, O.: Lattice problems in NP ∩ coNP. Journal of the ACM 52(5), 749–765 (2005)

    Article MathSciNet  Google Scholar 

  2. Ajtai, M.: Generating hard instances of lattice problems. Complexity of Computations and Proofs, Quaderni di Matematica 13, 1–32 (2004) (Preliminary version in STOC 1996)

    MathSciNet  Google Scholar 

  3. Ajtai, M., Kumar, R., Sivakumar, D.: A sieve algorithm for the shortest lattice vector problem. In: STOC, pp. 601–610 (2001)

    Google Scholar 

  4. Bleichenbacher, D., Maurer, U.: On the efficiency of one-time digital signatures. In: Kim, K.-c., Matsumoto, T. (eds.) ASIACRYPT 1996. LNCS, vol. 1163, pp. 145–158. Springer, Heidelberg (1996)

    Chapter  Google Scholar 

  5. Bleichenbacher, D., Maurer, U.: Optimal tree-based one-time digital signature schemes. In: Puech, C., Reischuk, R. (eds.) STACS 1996. LNCS, vol. 1046, pp. 363–374. Springer, Heidelberg (1996)

    Google Scholar 

  6. Blum, M., Micali, S.: How to generate cryptographically strong sequences of pseudo-random bits. SIAM J. Comput. 13(4), 850–864 (1984)

    Article MATH MathSciNet  Google Scholar 

  7. Bos, J., Chaum, D.: Provably unforgeable signatures. In: McCurley, K.S., Ziegler, C.D. (eds.) Advances in Cryptology 1981 - 1997. LNCS, vol. 1440, pp. 1–14. Springer, Heidelberg (1999)

    Google Scholar 

  8. Cramer, R., Shoup, V.: Signature schemes based on the strong RSA assumption. ACM Trans. Inf. Syst. Secur. 3(3), 161–185 (2000)

    Article  Google Scholar 

  9. Diffie, W., Hellman, M.: New directions in cryptography. IEEE Transactions on Information Theory IT-22(6), 644–654 (1976)

    Article MathSciNet  Google Scholar 

  10. Dinur, I.: ApproximatingSVP ∞  to within almost-polynomial factors is NP-hard. Theor. Comput. Sci. 285(1), 55–71 (2002)

    Article MATH MathSciNet  Google Scholar 

  11. Even, S., Goldreich, O., Micali, S.: On-line/off-line digital signatures. J. Cryptology 9(1), 35–67 (1996)

    Article MATH MathSciNet  Google Scholar 

  12. Gennaro, R., Gertner, Y., Katz, J., Trevisan, L.: Bounds on the efficiency of generic cryptographic constructions. SIAM Journal on Computing 35(1), 217–246 (2005)

    Article MATH MathSciNet  Google Scholar 

  13. Gennaro, R., Halevi, S., Rabin, T.: Secure hash-and-sign signatures without the random oracle. In: Stern, J. (ed.) EUROCRYPT 1999. LNCS, vol. 1592, pp. 123–139. Springer, Heidelberg (1999)

    Chapter  Google Scholar 

  14. Goldreich, O., Goldwasser, S.: On the limits of nonapproximability of lattice problems. J. Comput. Syst. Sci. 60(3) (2000)

    Google Scholar 

  15. Goldwasser, S., Micali, S., Rivest, R.: A digital signature scheme secure against adaptive chosen-message attacks. SIAM J. Comput. 17(2), 281–308 (1988)

    Article MATH MathSciNet  Google Scholar 

  16. Hevia, A., Micciancio, D.: The provable security of graph-based one-time signatures and extensions to algebraic signature schemes. In: Zheng, Y. (ed.) ASIACRYPT 2002. LNCS, vol. 2501, pp. 379–396. Springer, Heidelberg (2002)

    Chapter  Google Scholar 

  17. Kumar, R., Sivakumar, D.: On polynomial-factor approximations to the shortest lattice vector length. SIAM J. Discrete Math. 16(3), 422–425 (2003)

    Article MATH MathSciNet  Google Scholar 

  18. Lyubashevsky, V., Micciancio, D.: Generalized compact knapsacks are collision resistant. In: Bugliesi, M., Preneel, B., Sassone, V., Wegener, I. (eds.) ICALP 2006. LNCS, vol. 4052, pp. 144–155. Springer, Heidelberg (2006)

    Chapter  Google Scholar 

  19. Lyubashevsky, V., Micciancio, D., Peikert, C., Rosen, R.: Provably secure FFT hashing. Technical report, 2nd NIST Cryptographic Hash Function Workshop (2006)

    Google Scholar 

  20. Merkle, R.: A digital signature based on a conventional encryption function. In: McCurley, K.S., Ziegler, C.D. (eds.) Advances in Cryptology 1981 - 1997. LNCS, vol. 1440, pp. 369–378. Springer, Heidelberg (1999)

    Google Scholar 

  21. Merkle, R.: A certified digital signature. In: McCurley, K.S., Ziegler, C.D. (eds.) Advances in Cryptology 1981 - 1997. LNCS, vol. 1440, pp. 218–238. Springer, Heidelberg (1999)

    Google Scholar 

  22. Micciancio, D.: Generalized compact knapsacks, cyclic lattices, and efficient one-way functions. Computational Complexity (2007) (Special issue on worst-case versus average-case complexity, in print. Available on-line as doi:10.1007/s00037-007-0234-9. Preliminary version in FOCS 2002)

    Google Scholar 

  23. Naor, M., Yung, M.: Universal one-way hash functions and their cryptographic applications. In: STOC, pp. 33–43 (1989)

    Google Scholar 

  24. Pedersen, T., Pfitzmann, B.: Fail-stop signatures. SIAM J. Comput. 26(2), 291–330 (1997)

    Article MATH MathSciNet  Google Scholar 

  25. Peikert, C., Rosen, A.: Efficient collision-resistant hashing from worst-case assumptions on cyclic lattices. In: Halevi, S., Rabin, T. (eds.) TCC 2006. LNCS, vol. 3876, Springer, Heidelberg (2006)

    Google Scholar 

  26. Peikert, C., Rosen, A.: Lattices that admit logarithmic worst-case to average-case connection factors. In: STOC (2007)

    Google Scholar 

  27. Rompel, J.: One-way functions are necessary and sufficient for secure signatures. In: STOC, pp. 387–394 (1990)

    Google Scholar 

  28. Szydlo, M.: Merkle tree traversal in log space and time. In: Cachin, C., Camenisch, J.L. (eds.) EUROCRYPT 2004. LNCS, vol. 3027, pp. 541–554. Springer, Heidelberg (2004)

    Google Scholar 

  29. van Emde Boas, P.: Another NP-complete problem and the complexity of computing short vectors in a lattice. Technical Report 81-04, University of Amsterdam (1981),http://turing.wins.uva.nl/~peter/

Download references

Author information

Authors and Affiliations

  1. University of California, San Diego, La Jolla, CA 92093-0404, USA

    Vadim Lyubashevsky & Daniele Micciancio

Authors
  1. Vadim Lyubashevsky
  2. Daniele Micciancio

Editor information

Ran Canetti

Rights and permissions

Copyright information

© 2008 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Lyubashevsky, V., Micciancio, D. (2008). Asymptotically Efficient Lattice-Based Digital Signatures. In: Canetti, R. (eds) Theory of Cryptography. TCC 2008. Lecture Notes in Computer Science, vol 4948. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-78524-8_3

Download citation

Publish with us

[8]ページ先頭
©2009-2025 Movatter.jp