Worst-case to average-case reductions for module lattices
Tóm tắt
Từ khóa
Tài liệu tham khảo
Ajtai M.: Generating hard instances of lattice problems (extended abstract). In: Proceedings of STOC, pp. 99–108. ACM, New York (1996).
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).
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).
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).
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).
Bosma W., Pohst M.: Computations with finitely generated modules over Dedekind rings. In: Proceedings of ISSAC, pp. 151–156 (1991).
Brakerski Z., Gentry G., Vaikuntanathan V.: Fully homomorphic encryption without bootstrapping. Electronic Colloquium on Computational Complexity (ECCC), vol. 18, p. 111 (2011).
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).
Fieker C., Pohst M.E.: Lattices over number fields. In: Proceedings ANTS-II. LNCS, vol. 1122, pp. 147–157. Springer, Heidelberg (1996).
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).
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).
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).
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).
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).
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).
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).
Lyubashevsky V., Micciancio D.: Generalized compact knapsacks are collision resistant. In: Proceedings of ICALP (2). LNCS, vol. 4052, pp. 144–155. Springer, Heidelberg (2006).
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 .
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).
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].
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).
Micciancio D.: Generalized compact knapsacks, cyclic lattices, and efficient one-way functions. Comput. Complex. 16(4):365–411 (2007). Full version of [21].
Micciancio D., Goldwasser S.: Complexity of lattice problems : a cryptographic perspective. Kluwer Academic Press, Dordrecht (2002)
Micciancio D., Peikert C.: Trapdoors for lattices: Simpler, tighter, faster, smaller. In: Proceedings of EUROCRYPT. LNCS, vol. 7237, pp. 700–718. Springer, Heidelberg (2012).
Micciancio D., Peikert C.: Hardness of SIS and LWE with small parameters. In: CRYPTO (1). LNCS, vol. 8042, pp. 21–39. Springer, Heidelberg (2013).
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].
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].
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).
Mollin, R.A.: Algebraic Number Theory. Chapman and Hall/CRC Press, Boca Raton (1999).
Napias, H.: A generalization of the LLL-algorithm over Euclidean rings or orders. J. Théorie des nombres de Bordeaux 2, 387–396 (1996)
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).
Peikert, C.: Limits on the hardness of lattice problems in $$\ell _p$$ ℓ p norms. Comput. Complex. 2(17), 300–351 (2008).
Peikert C.: Public-key cryptosystems from the worst-case shortest vector problem. In: Proceedings of STOC, pp. 333–342. ACM, New York (2009).
Peikert, C.: An efficient and parallel gaussian sampler for lattices. In: Proceedings of CRYPTO. LNCS, vol. 6223, pp. 80–97. Springer, Heidelberg (2010).
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).
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).
Pietrzak K.: Subspace LWE. In: Proceedings of TCC. LNCS, vol. 7194, pp. 548–563. Springer, Heidelberg (2012).
Regev O.: Lecture notes of lattices in computer science, taught at the Computer Science Tel Aviv University. Available at http://www.cims.nyu.edu/regev/teaching/lattices_fall_2009/index.html .
Regev O.: On lattices, learning with errors, random linear codes, and cryptography. In: Proceedings of STOC, pp. 84–93. ACM, New York (2005).
Regev O.: On lattices, learning with errors, random linear codes, and cryptography. J. ACM 56(6) (2009). Full version of [40].
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).
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].
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).