Your browser does not support JavaScript!
http://iet.metastore.ingenta.com
1887

access icon free Analysing recursive preprocessing of BKZ lattice reduction algorithm

  • Author(s): Md. Mokammel Haque 1  and  Josef Pieprzyk 2, 3
    • View affiliations
    • Affiliations: 1: Department of Computer Science and Engineering, Chittagong University of Engineering and Technology, Chittagong 4349, Bangladesh ;
      2: Institute of Computer Science, Polish Academy of Sciences, Warsaw, Poland ;
      3: School of Electrical Engineering and Computer Science, Queensland University of Technology, Brisbane, QLD 4000, Australia
  • Source: Volume 11, Issue 2, March 2017, p. 114 – 120
    DOI:  10.1049/iet-ifs.2016.0049 , Print ISSN 1751-8709, Online ISSN 1751-8717
© The Institution of Engineering and Technology
Received 30/01/2016, Accepted 09/06/2016, Revised 10/05/2016, Published 13/06/2016

Lattice problems are considered as the key elements in many areas of computer science as well as in cryptography; the most important of which is the shortest vector problem and its approximate variants. Algorithms for this problem are known as lattice reduction algorithms. Currently, the most practical lattice reduction algorithm for such problems is the block Korkine–Zolotarev (BKZ) algorithm and its variants. The authors optimise both the pruning and the preprocessing parameters of the recursive (aborted, extreme pruned) preprocessing of the BKZ lattice reduction algorithm and improve the results from Asiacrypt'11 by Chen and Nguyen. The authors derive approximate closed-form complexity formulas (based on the sandpile model assumption model by Hanrot et al.) for the enumeration time which allow a simple estimation of complexity without running the simulation algorithm (by Chen and Nguyen) and asymptotically suggests a modified extreme pruning bounding profiles with different parameters. Hence, the authors’ contributions are in optimising and improving the analysis of the complexity upper bound estimates presented by Chen and Nguyen, based on the same recursive-BKZ preprocessing model.

Inspec keywords: cryptography; sandpile models; vectors; approximation theory; computational complexity

Other keywords: shortest vector problem; sandpile model; preprocessing parameter optimisation; enumeration time; recursive-BKZ preprocessing model; lattice problems; block Korkine-Zolotarev algorithm; cryptography; pruning parameter optimisation; BKZ lattice reduction algorithm; extreme pruning bounding profiles; approximate closed-form complexity formulas; complexity upper bound estimate analysis; approximate variants

Subjects: Cryptography theory; Linear algebra (numerical analysis); Interpolation and function approximation (numerical analysis); Interpolation and function approximation (numerical analysis); Linear algebra (numerical analysis); Computational complexity; Cryptography

References

    1. 1)
      • 11. Gama, N., Nguyen, P.Q., Regev, O.: ‘Lattice enumeration using extreme pruning’. EUROCRYPT, 2010, 2010, pp. 257–278.
    2. 2)
      • 8. Chen, Y., Nguyen, P.Q.: ‘BKZ 2.0: better lattice security estimate’. ASIACRYPT'11, 2011 (LNCS, 7073), pp. 1–20.
    3. 3)
      • 13. Shoup, V.: ‘NTL: A library for doing number theory’. Available at http://www.shoup.net/ntl/.
    4. 4)
      • 10. Hanrot, G., Pujol, X., Stehlé, D.: ‘Analyzing blockwise lattice algorithms using dynamical systems’. CRYPTO'11, 2011 (LNCS, 6841), pp. 447–464.
    5. 5)
      • 9. Schnorr, C.P.: ‘Lattice reduction by random sampling and birthday methods’. STACS'03, 2003, vol. 2607, pp. 145–156.
    6. 6)
      • 2. Gentry, C.: ‘Fully homomorphic encryption using ideal lattices’. STOC'09, 2009, pp. 169–178.
    7. 7)
      • 12. Hanrot, G., Stehlé, D.: ‘Improved analysis of Kannan's shortest lattice vector algorithm (extended abstract)’. Crypto'07, 2007, vol. 4622, pp. 170–186.
    8. 8)
      • 5. Schnorr, C.P.: ‘A hierarchy of polynomial time lattice basis reduction algorithms’, Theor. Comput. Sci., 1987, 53, (2–3), pp. 201–224.
    9. 9)
      • 6. Schnorr, C.P., Euchner, M.: ‘Lattice basis reduction: improved practical algorithms and solving subset sum problems’, Math. Program., 1994, 66, pp. 181–199.
    10. 10)
      • 4. Lenstra, A.K., Lenstra, H.W., Lovász, L.: ‘Factoring polynomials with rational coefficients’, Math. Ann., 1982, 261, (4), pp. 515–534.
    11. 11)
      • 1. Regev, O.: ‘On lattices, learning with errors, random linear codes, and cryptography’, JACM, 2009, 56, 6, pp. 34:1–34:40.
    12. 12)
      • 3. Lyubashevsky, V., Micciancio, D., Peikert, C., et al: ‘SWIFFT: a modest proposal for FFT hashing’. Fast Software Encryption (FSE) 2008, 2008 (LNCS), 5086, pp. 54–72.
    13. 13)
      • 7. Ajtai, M., Kumar, R., Sivakumar, D.: ‘A sieve algorithm for the shortest lattice vector problem’. Proc. of 33rd ACM Symp. on Theory of Computing (STOC), 2001, pp. 601–610.
    14. 14)
      • 14. Haque, M.M.: ‘Lattice-based cryptanalysis for secure cryptosystems’. PhD thesis, Macquarie University, 2013.
http://iet.metastore.ingenta.com/content/journals/10.1049/iet-ifs.2016.0049
Loading

Related content

content/journals/10.1049/iet-ifs.2016.0049
pub_keyword,iet_inspecKeyword,pub_concept
6
6
Loading
Print this page
This is a required field
Please enter a valid email address