Movatterモバイル変換

[0]ホーム
URL:

Skip to main content

Advertisement

Springer Nature Link
Log in

Lossy Codes and a New Variant of the Learning-With-Errors Problem

  • Conference paper

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

  • 7346Accesses

  • 34Citations

Abstract

The hardness of the Learning-With-Errors (LWE) Problem has become one of the most useful assumptions in cryptography. It exhibits a worst-to-average-case reduction making the LWE assumption very plausible. This worst-to-average-case reduction is based on a Fourier argument and the errors for current applications of LWE must be chosen from a gaussian distribution. However, sampling from gaussian distributions is cumbersome.

In this work we present the first worst-to-average case reduction for LWE with uniformly distributed errors, which can be sampled very efficiently. This new worst-to-average-case connection comes with a slight drawback and we need to use a bounded variant of the LWE problem, where the number of samples is fixed in advance. Most applications of LWE can be based on the bounded variant. The proof is based on a new tool calledlossy codes, which might be of interest in the context other lattice/coding-based hardness assumptions.

Similar content being viewed by others

Keywords

References

  1. Agrawal, S., Boneh, D., Boyen, X.: Lattice Basis Delegation in Fixed Dimension and Shorter-Ciphertext Hierarchical IBE. In: Rabin, T. (ed.) CRYPTO 2010. LNCS, vol. 6223, pp. 98–115. Springer, Heidelberg (2010)

    Chapter  Google Scholar 

  2. Applebaum, B., Cash, D., Peikert, C., Sahai, A.: Fast Cryptographic Primitives and Circular-Secure Encryption Based on Hard Learning Problems. In: Halevi, S. (ed.) CRYPTO 2009. LNCS, vol. 5677, pp. 595–618. Springer, Heidelberg (2009)

    Chapter  Google Scholar 

  3. Applebaum, B., Ishai, Y., Kushilevitz, E.: How to garble arithmetic circuits. In: FOCS, pp. 120–129 (2011)

    Google Scholar 

  4. Brakerski, Z., Gentry, C., Vaikuntanathan, V.: (Leveled) fully homomorphic encryption without bootstrapping. In: ITCS, pp. 309–325 (2012)

    Google Scholar 

  5. Bellare, M., Kiltz, E., Peikert, C., Waters, B.: Identity-based (Lossy) trapdoor functions and applications. In: Pointcheval, D., Johansson, T. (eds.) EUROCRYPT 2012. LNCS, vol. 7237, pp. 228–245. Springer, Heidelberg (2012)

    Chapter  Google Scholar 

  6. Banerjee, A., Peikert, C., Rosen, A.: Pseudorandom Functions and Lattices. In: Pointcheval, D., Johansson, T. (eds.) EUROCRYPT 2012. LNCS, vol. 7237, pp. 719–737. Springer, Heidelberg (2012)

    Chapter  Google Scholar 

  7. Brakerski, Z.: Fully Homomorphic Encryption without Modulus Switching from Classical GapSVP. In: Safavi-Naini, R. (ed.) CRYPTO 2012. LNCS, vol. 7417, pp. 868–886. Springer, Heidelberg (2012)

    Google Scholar 

  8. Brakerski, Z., Vaikuntanathan, V.: Efficient Fully Homomorphic Encryption from (Standard) LWE. In: FOCS, pp. 97–106 (2011)

    Google Scholar 

  9. Cash, D., Hofheinz, D., Kiltz, E., Peikert, C.: Bonsai Trees, or How to Delegate a Lattice Basis. In: Gilbert, H. (ed.) EUROCRYPT 2010. LNCS, vol. 6110, pp. 523–552. Springer, Heidelberg (2010)

    Chapter  Google Scholar 

  10. Dodis, Y., Ostrovsky, R., Reyzin, L., Smith, A.: Fuzzy Extractors: How to Generate Strong Keys from Biometrics and Other Noisy Data. SIAM J. Comput. 38(1), 97–139 (2008)

    Article MathSciNet MATH  Google Scholar 

  11. Goldwasser, S., Kalai, Y.T., Peikert, C., Vaikuntanathan, V.: Robustness of the Learning with Errors Assumption. In: ICS, pp. 230–240 (2010)

    Google Scholar 

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

    Google Scholar 

  13. Lyubashevsky, V., Peikert, C., Regev, O.: On Ideal Lattices and Learning with Errors over Rings. In: Gilbert, H. (ed.) EUROCRYPT 2010. LNCS, vol. 6110, pp. 1–23. Springer, Heidelberg (2010)

    Chapter  Google Scholar 

  14. Micciancio, D., Mol, P.: Pseudorandom Knapsacks and the Sample Complexity of LWE Search-to-Decision Reductions. In: Rogaway, P. (ed.) CRYPTO 2011. LNCS, vol. 6841, pp. 465–484. Springer, Heidelberg (2011)

    Chapter  Google Scholar 

  15. Micciancio, D., Mol, P.: Pseudorandom Knapsacks and the Sample Complexity of LWE Search-to-Decision Reductions. IACR Cryptology ePrint Archive, 2011:521 (2011)

    Google Scholar 

  16. Micciancio, D., Peikert, C.: Trapdoors for Lattices: Simpler, Tighter, Faster, Smaller. In: Pointcheval, D., Johansson, T. (eds.) EUROCRYPT 2012. LNCS, vol. 7237, pp. 700–718. Springer, Heidelberg (2012)

    Chapter  Google Scholar 

  17. Micciancio, D., Peikert, C.: Hardness of SIS and LWE with Small Parameters. IACR Cryptology ePrint Archive, 2013:069 (2013)

    Google Scholar 

  18. Peikert, C.: Public-key cryptosystems from the worst-case shortest vector problem: extended abstract. In: STOC, pp. 333–342 (2009)

    Google Scholar 

  19. Pietrzak, K.: Subspace LWE. In: Cramer, R. (ed.) TCC 2012. LNCS, vol. 7194, pp. 548–563. Springer, Heidelberg (2012)

    Chapter  Google Scholar 

  20. Peikert, C., Waters, B.: Lossy trapdoor functions and their applications. In: STOC, pp. 187–196 (2008)

    Google Scholar 

  21. Regev, O.: On lattices, learning with errors, random linear codes, and cryptography. In: STOC, pp. 84–93 (2005)

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Karlsruhe Institute of Technology, Karlsruhe, Germany

    Nico Döttling & Jörn Müller-Quade

Authors
  1. Nico Döttling
  2. Jörn Müller-Quade

Editor information

Editors and Affiliations

  1. Dept. of Electrical and Information Technology, Lund University, P.O. Box 118, 221 00, Lund, Sweden

    Thomas Johansson

  2. Départment d’informatique, Ecole normale supérieure, 45, rue d’Ulm, 75230, Paris Cedex 05, France

    Phong Q. Nguyen

Rights and permissions

Copyright information

© 2013 International Association for Cryptologic Research

About this paper

Cite this paper

Döttling, N., Müller-Quade, J. (2013). Lossy Codes and a New Variant of the Learning-With-Errors Problem. In: Johansson, T., Nguyen, P.Q. (eds) Advances in Cryptology – EUROCRYPT 2013. EUROCRYPT 2013. Lecture Notes in Computer Science, vol 7881. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-38348-9_2

Download citation

Publish with us

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