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
Bücher
Zeitschriften
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
SLX-Digitalkonferenz: Zukunftswerkstatt 2024

Mehr Umsatz mit Top-Kontakten

Am 7. Mai erfahren Sie, wie Vertriebsteams Leadgenerierung, Leadnurturing und Leadstrategien effizient steuern können.
Erweiterte Suche
Anmelden
nach oben
Designs, Codes and Cryptography

01.06.2015

Worst-case to average-case reductions for module lattices

Erschienen in: Designs, Codes and Cryptography | Ausgabe 3/2015

Einloggen, um Zugang zu erhalten

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

search-config
loading …

Abstract

Most lattice-based cryptographic schemes are built upon the assumed hardness of the Short Integer Solution (SIS) and Learning With Errors (LWE) problems. Their efficiencies can be drastically improved by switching the hardness assumptions to the more compact Ring-SIS and Ring-LWE problems. However, this change of hardness assumptions comes along with a possible security weakening: SIS and LWE are known to be at least as hard as standard (worst-case) problems on euclidean lattices, whereas Ring-SIS and Ring-LWE are only known to be as hard as their restrictions to special classes of ideal lattices, corresponding to ideals of some polynomial rings. In this work, we define the Module-SIS and Module-LWE problems, which bridge SIS with Ring-SIS, and LWE with Ring-LWE, respectively. We prove that these average-case problems are at least as hard as standard lattice problems restricted to module lattices (which themselves bridge arbitrary and ideal lattices). As these new problems enlarge the toolbox of the lattice-based cryptographer, they could prove useful for designing new schemes. Importantly, the worst-case to average-case reductions for the module problems are (qualitatively) sharp, in the sense that there exist converse reductions. This property is not known to hold in the context of Ring-SIS/Ring-LWE: Ideal lattice problems could reveal easy without impacting the hardness of Ring-SIS/Ring-LWE.
Fußnoten
1
With the exception of the recent result of Micciancio and Peikert [26] on the hardness of SIS and LWE with small parameters.
 
Literatur
1.
Ajtai M.: Generating hard instances of lattice problems (extended abstract). In: Proceedings of STOC, pp. 99–108. ACM, New York (1996).
2.
Alperin-Sheriff J., Peikert C.: Circular and KDM security for identity-based encryption. In: Proceedings of PKC. LNCS, vol. 7293, pp. 334–352. Springer, Berlin (2012).
3.
Applebaum B., Cash D., Peikert C., Sahai A.: Fast cryptographic primitives and circular-secure encryption based on hard learning problems. In: Proceedings of CRYPTO. LNCS, vol. 5677, pp. 595–618. Springer, Berlin (2009).
4.
Blömer J., Seifert J.-P.: On the complexity of computing short linearly independent vectors and short bases in a lattice. In: Proceedings of STOC, pp. 711–720. ACM, New York (1999).
5.
Boneh D., Freeman D.M.: Linearly homomorphic signatures over binary fields and new tools for lattice-based signatures. In: Proceedings of PKC. LNCS, vol. 6571, pp. 1–16. Springer, Berlin (2011).
6.
Bosma W., Pohst M.: Computations with finitely generated modules over Dedekind rings. In: Proceedings of ISSAC, pp. 151–156 (1991).
7.
Brakerski Z., Gentry G., Vaikuntanathan V.: Fully homomorphic encryption without bootstrapping. Electronic Colloquium on Computational Complexity (ECCC), vol. 18, p. 111 (2011).
8.
Brakerski Z., Langlois A., Peikert C., Regev O., Stehlé D.: Classical hardness of learning with errors. In: Proceedings of STOC, pp. 575–584. ACM, New York (2013).
9.
Cohen H.: Advanced Topics in Computational Number Theory. Springer, Heidelberg (2000).
10.
Fieker C., Pohst M.E.: Lattices over number fields. In: Proceedings ANTS-II. LNCS, vol. 1122, pp. 147–157. Springer, Heidelberg (1996).
11.
Fieker C., Stehlé D.: Short bases of lattices over number fields. In: Proceedings of ANTS-IX. LNCS, vol. 6197, pp. 157–173. Springer, Heidelberg (2010).
12.
Gan Y.H., Ling C., Mow W.H.: Complex lattice reduction algorithm for low-complexity full-diversity MIMO detection. IEEE Trans. Signal Process. 57, 2701–2710 (2009).
13.
Gentry C., Peikert C., Vaikuntanathan V.: Trapdoors for hard lattices and new cryptographic constructions. In: Proceedings of STOC, pp. 197–206. ACM, New York (2008).
14.
Gordon S.D., Katz J., Vaikuntanathan V.: A group signature scheme from lattice assumptions. In: Proceedings of ASIACRYPT. LNCS, vol. 6477, pp. 395–412. Springer, Heidelberg (2010).
15.
Hoffstein J., Pipher J., Silverman J.H.: NTRU: a ring-based public key cryptosystem. In: Proceedings of ANTS-III. LNCS, vol. 1423, pp. 267–288. Springer, Heidelberg (1998).
16.
Kiltz E., Pietrzak K., Cash D., Jain A., Venturi D.: Efficient authentication from hard learning problems. In: Proceedings of EUROCRYPT. LNCS, vol. 6632, pp. 7–26. Springer, Heidelberg (2011).
17.
López-Alt A., Tromer E., Vaikuntanathan V.: On-the-fly multiparty computation on the cloud via multikey fully homomorphic encryption. In: Proceedings of STOC, pp. 1219–1234. ACM, New York (2012).
18.
Lyubashevsky V., Micciancio D.: Generalized compact knapsacks are collision resistant. In: Proceedings of ICALP (2). LNCS, vol. 4052, pp. 144–155. Springer, Heidelberg (2006).
19.
Lyubashevsky V., Peikert C., Regev O., On ideal lattices and learning with errors over rings. In: Proceedings of EUROCRYPT, LNCS, pp. 1–23. Springer, Heidelberg (2010). All result numberings used in the present article correspond to those of the draft of the full version, available at http://​eprint.​iacr.​org/​2012/​230.​pdf.
20.
Lyubashevsky V., Peikert C., Regev O.: A toolkit for Ring-LWE cryptography. In: Proceedings of EUROCRYPT. LNCS, vol. 7881, pp. 35–54. Springer, Heidelberg (2013).
21.
Micciancio D.: Generalized compact knapsacks, cyclic lattices, and efficient one-way functions from worst-case complexity assumptions. In: Proceedings of FOCS, pp. 356–365. IEEE (2002). Conference version of [23].
22.
Micciancio D.: Almost perfect lattices, the covering radius problem, and applications to Ajtai’s connection factor. SIAM J. Comput. textbf34(1):118–169 (2004). Preliminary version in STOC (2002).
23.
Micciancio D.: Generalized compact knapsacks, cyclic lattices, and efficient one-way functions. Comput. Complex. 16(4):365–411 (2007). Full version of [21].
24.
Micciancio D., Goldwasser S.: Complexity of lattice problems : a cryptographic perspective. Kluwer Academic Press, Dordrecht (2002)
25.
Micciancio D., Peikert C.: Trapdoors for lattices: Simpler, tighter, faster, smaller. In: Proceedings of EUROCRYPT. LNCS, vol. 7237, pp. 700–718. Springer, Heidelberg (2012).
26.
Micciancio D., Peikert C.: Hardness of SIS and LWE with small parameters. In: CRYPTO (1). LNCS, vol. 8042, pp. 21–39. Springer, Heidelberg (2013).
27.
Micciancio D., Regev O.: Worst-case to average-case reductions based on Gaussian measure. In: Proceedings of FOCS, pp. 371–381. IEEE (2004). Conference version of [28].
28.
Micciancio D., Regev O.: Worst-case to average-case reductions based on Gaussian measures. SIAM J. Comput. 37(1):267–302 (2007). Full version of [27].
29.
Micciancio D., Regev O.: Lattice-based cryptography. In: Bernstein D.J., Buchmann J., Dahmen E. (eds.) Post Quantum Cryptography, pp. 147–191. Springer, Heidelberg (2009).
30.
Mollin, R.A.: Algebraic Number Theory. Chapman and Hall/CRC Press, Boca Raton (1999).
31.
Napias, H.: A generalization of the LLL-algorithm over Euclidean rings or orders. J. Théorie des nombres de Bordeaux 2, 387–396 (1996)CrossRefMathSciNet
32.
O’Neill A., Peikert C., Waters B.: Bi-deniable public-key encryption. In: Proceedings of CRYPTO. LNCS, vol. 6841, pp. 525–542. Springer, Heidelberg (2011).
33.
Peikert, C.: Limits on the hardness of lattice problems in \(\ell _p\) norms. Comput. Complex. 2(17), 300–351 (2008).
34.
Peikert C.: Public-key cryptosystems from the worst-case shortest vector problem. In: Proceedings of STOC, pp. 333–342. ACM, New York (2009).
35.
Peikert, C.: An efficient and parallel gaussian sampler for lattices. In: Proceedings of CRYPTO. LNCS, vol. 6223, pp. 80–97. Springer, Heidelberg (2010).
36.
Peikert, C., Rosen, A.: Efficient collision-resistant hashing from worst-case assumptions on cyclic lattices. In: Proceedings of TCC. LNCS, vol. 3876, pp. 145–166. Springer, Heidelberg (2006).
37.
Peikert C., Rosen A.: Lattices that admit logarithmic worst-case to average-case connection factors. In: Proceedings of STOC, pp. 478–487. ACM, New York (2007).
38.
Pietrzak K.: Subspace LWE. In: Proceedings of TCC. LNCS, vol. 7194, pp. 548–563. Springer, Heidelberg (2012).
39.
40.
Regev O.: On lattices, learning with errors, random linear codes, and cryptography. In: Proceedings of STOC, pp. 84–93. ACM, New York (2005).
41.
Regev O.: On lattices, learning with errors, random linear codes, and cryptography. J. ACM 56(6) (2009). Full version of [40].
42.
Stehlé D., Steinfeld R.: Making NTRU as secure as worst-case problems over ideal. lattices. In: Proceedings of EUROCRYPT. LNCS, vol. 6632, pp. 27–47. Springer, Heidelberg (2011).
43.
Stehlé D., Steinfeld R.: Making NTRUEncrypt and NTRUSign as secure as standard worst-case problems over ideal lattices. Cryptology ePrint Archive, Report 2013/004, 2013. Full version of [42].
44.
Stehlé D., Steinfeld R., Tanaka K., Xagawa K.: Efficient public key encryption based on ideal lattices. In: Proceedings of ASIACRYPT. LNCS, vol. 5912, pp. 617–635. Springer, Heidelberg (2009).
Metadaten
Titel
Worst-case to average-case reductions for module lattices
Publikationsdatum
01.06.2015
Erschienen in
Designs, Codes and Cryptography / Ausgabe 3/2015
Print ISSN: 0925-1022
Elektronische ISSN: 1573-7586
DOI
https://doi.org/10.1007/s10623-014-9938-4