Top

Published in:

2018 | OriginalPaper | Chapter

The Search Successive Minima Problem Is Equivalent to Its Optimization Version

Authors : Haoyu Li, Yanbin Pan

Published in: Information Security Applications

Publisher: Springer International Publishing

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

The shortest vector problem (SVP) and the shortest independent vectors problem (SIVP) are two famous problems in lattices, which are usually used to evaluate the hardness of some computational problems related to lattices. It is well known that the search-SVP is equivalent to its optimization version. However, it seems very difficult to prove the equivalence between search-SIVP and optimization-SIVP. In this paper, we revisit the Successive Minima Problem (SMP), which is proved the equivalence relation with SIVP. Naturally we will consider its optimization version as to find all successive minima of a given lattice, and finally we will prove that it is equivalent to its search version.

Dont have a licence yet? Then find out more about our products and how to get one now:

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!

inform now

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!

inform now

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!

inform now

previous chapter Robust 3D Mesh Watermarking Scheme for an Anti-Collusion Fingerprint Code

next chapter An Improved Algorithm to Solve the Systems of Univariate Modular Equations

Ajtai, M.: Generating hard instances of lattice problems (extended abstract). In: Proceedings of the Twenty-Eighth Annual ACM Symposium on Theory of Computing, STOC 1996, pp. 99–108. ACM, New York (1996). https://doi.org/10.1145/237814.237838

Ajtai, M.: The shortest vector problem in L2 is NP-hard for randomized reductions (extended abstract). In: Proceedings of the Thirtieth Annual ACM Symposium on Theory of Computing, STOC 1998, pp. 10–19. ACM, New York (1998). https://doi.org/10.1145/276698.276705

Ajtai, M., Dwork, C.: A public-key cryptosystem with worst-case/average-case equivalence. In: Proceedings of the Twenty-Ninth Annual ACM Symposium on Theory of Computing, STOC 1997, pp. 284–293. ACM, New York (1997). https://doi.org/10.1145/258533.258604

Alkim, E., Bindel, N., Buchmann, J.A., Dagdelen, Ö., Schwabe, P.: TESLA: Tightly-Secure Efficient Signatures from Standard Lattices. IACR Cryptology ePrint Archive 2015, 755 (2015). https://eprint.iacr.org/2015/755.pdf

Blömer, J., Naewe, S.: Sampling methods for shortest vectors, closest vectors and successive minima. In: Arge, L., Cachin, C., Jurdziński, T., Tarlecki, A. (eds.) ICALP 2007. LNCS, vol. 4596, pp. 65–77. Springer, Heidelberg (2007). https://doi.org/10.1007/978-3-540-73420-8_8CrossRefMATH

Boas, P.V.E.: Another NP-complete problem and the complexity of computing short vectors in lattices. Mathematics Department Report 81-04. University of Amsterdam (1981)

Brakerski, Z., Vaikuntanathan, V.: Efficient fully homomorphic encryption from (standard) LWE. SIAM J. Comput. 43(2), 831–871 (2014). https://doi.org/10.1137/120868669MathSciNetCrossRefMATH

Cai, J.Y., Nerurkar, A.: Approximating the SVP to within a factor (1–1/dim\(^\epsilon \)) is NP-hard under randomized conditions. In: Proceedings of the Thirteenth Annual IEEE Conference on Computational Complexity (Formerly: Structure in Complexity Theory Conference) (Cat. No.98CB36247), pp. 46–55, June 1998

Ducas, L., Durmus, A., Lepoint, T., Lyubashevsky, V.: Lattice signatures and bimodal Gaussians. In: Canetti, R., Garay, J.A. (eds.) CRYPTO 2013. LNCS, vol. 8042, pp. 40–56. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-40041-4_3CrossRef

10.

Gentry, C.: Fully homomorphic encryption using ideal lattices. In: Proceedings of the Forty-First Annual ACM Symposium on Theory of Computing, STOC 2009, pp. 169–178. ACM, New York (2009). https://doi.org/10.1145/1536414.1536440

11.

Gentry, C., Peikert, C., Vaikuntanathan, V.: Trapdoors for hard lattices and new cryptographic constructions. In: Proceedings of the Fortieth Annual ACM Symposium on Theory of Computing, STOC 2008, pp. 197–206. ACM, New York (2008). https://doi.org/10.1145/1374376.1374407

12.

Goldreich, O., Micciancio, D., Safra, S., Seifert, J.P.: Approximating shortest lattice vectors is not harder than approximating closest lattice vectors 71, 55–61 (1999). http://www.sciencedirect.com/science/article/pii/S0020019099000836

13.

Hoffstein, J., Howgrave-Graham, N., Pipher, J., Silverman, J.H., Whyte, W.: NTRUSign: digital signatures using the NTRU lattice. In: Joye, M. (ed.) CT-RSA 2003. LNCS, vol. 2612, pp. 122–140. Springer, Heidelberg (2003). https://doi.org/10.1007/3-540-36563-X_9CrossRef

14.

Hoffstein, J., Pipher, J., Silverman, J.H.: NTRU: a ring-based public key cryptosystem. In: Buhler, J.P. (ed.) ANTS 1998. LNCS, vol. 1423, pp. 267–288. Springer, Heidelberg (1998). https://doi.org/10.1007/BFb0054868CrossRef

15.

Horn, R.A., Johnson, C.R.: Matrix Analysis. Cambridge University Press, Cambridge (2012)CrossRef

16.

Hu, G., Pan, Y.: Improvements on reductions among different variants of SVP and CVP. In: Kim, Y., Lee, H., Perrig, A. (eds.) WISA 2013. LNCS, vol. 8267, pp. 39–51. Springer, Cham (2014). https://doi.org/10.1007/978-3-319-05149-9_3CrossRef

17.

Ipsen, I.C.F., Rehman, R.: Perturbation bounds for determinants and characteristic polynomials. SIAM J. Matrix Anal. Appl. 30(2), 762–776 (2008). https://doi.org/10.1137/070704770MathSciNetCrossRefMATH

18.

Kannan, R.: Minkowski’s convex body theorem and integer programming. Math. Oper. Res. 12(3), 415–440 (1987). https://doi.org/10.1287/moor.12.3.415MathSciNetCrossRefMATH

19.

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). https://doi.org/10.1007/11787006_13CrossRef

20.

Lyubashevsky, V., Micciancio, D., Peikert, C., Rosen, A.: SWIFFT: a modest proposal for FFT hashing. In: Nyberg, K. (ed.) FSE 2008. LNCS, vol. 5086, pp. 54–72. Springer, Heidelberg (2008). https://doi.org/10.1007/978-3-540-71039-4_4CrossRef

21.

Micciancio, D.: Efficient reductions among lattice problems. In: Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2008, pp. 84–93. Society for Industrial and Applied Mathematics, Philadelphia (2008). http://dl.acm.org/citation.cfm?id=1347082.1347092

22.

Micciancio, D., Goldwasser, S.: Complexity of Lattice Problems: A Cryptographic Perspective. The Kluwer International Series in Engineering and Computer Science, vol. 671. Kluwer Academic Publishers, Boston (2002)CrossRef

23.

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, pp. 145–166. Springer, Heidelberg (2006). https://doi.org/10.1007/11681878_8CrossRef

24.

Piazza, G., Politi, T.: An upper bound for the condition number of a matrix in spectral norm. J. Comput. Appl. Math. 143(1), 141–144 (2002). http://www.sciencedirect.com/science/article/pii/S0377042702003965MathSciNetCrossRef

25.

Regev, O.: On lattices, learning with errors, random linear codes, and cryptography. In: Proceedings of the Thirty-Seventh Annual ACM Symposium on Theory of Computing, STOC 2005, pp. 84–93. ACM, New York (2005). https://doi.org/10.1145/1060590.1060603

Title: The Search Successive Minima Problem Is Equivalent to Its Optimization Version
Authors: Haoyu Li
Yanbin Pan
Publisher: Springer International Publishing
Book: Information Security Applications
Print ISBN: 978-3-319-93562-1

Electronic ISBN: 978-3-319-93563-8

Copyright Year: 2018
DOI: https://doi.org/10.1007/978-3-319-93563-8_4

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner