http://iet.metastore.ingenta.com
1887

Analysing recursive preprocessing of BKZ lattice reduction algorithm

Analysing recursive preprocessing of BKZ lattice reduction algorithm

For access to this article, please select a purchase option:

Buy article PDF
£12.50
(plus tax if applicable)
Buy Knowledge Pack
10 articles for £75.00
(plus taxes if applicable)

IET members benefit from discounts to all IET publications and free access to E&T Magazine. If you are an IET member, log in to your account and the discounts will automatically be applied.

Learn more about IET membership 

Recommend to library

You must fill out fields marked with: *

Librarian details
Name:*
Email:*
Your details
Name:*
Email:*
Department:*
Why are you recommending this title?
Select reason:
 
 
 
 
 
IET Information Security — Recommend this title to your library

Thank you

Your recommendation has been sent to your librarian.

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.

References

    1. 1)
      • O. Regev .
        1. Regev, O.: ‘On lattices, learning with errors, random linear codes, and cryptography’, JACM, 2009, 56, 6, pp. 34:134:40.
        . JACM , 6 , 34:1 - 34:40
    2. 2)
      • C. Gentry .
        2. Gentry, C.: ‘Fully homomorphic encryption using ideal lattices’. STOC'09, 2009, pp. 169178.
        . STOC'09 , 169 - 178
    3. 3)
      • V. Lyubashevsky , D. Micciancio , C. Peikert .
        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. 5472.
        . Fast Software Encryption (FSE) 2008 , 54 - 72
    4. 4)
      • A.K. Lenstra , H.W. Lenstra , L. Lovász .
        4. Lenstra, A.K., Lenstra, H.W., Lovász, L.: ‘Factoring polynomials with rational coefficients’, Math. Ann., 1982, 261, (4), pp. 515534.
        . Math. Ann. , 4 , 515 - 534
    5. 5)
      • C.P. Schnorr .
        5. Schnorr, C.P.: ‘A hierarchy of polynomial time lattice basis reduction algorithms’, Theor. Comput. Sci., 1987, 53, (2–3), pp. 201224.
        . Theor. Comput. Sci. , 201 - 224
    6. 6)
      • C.P. Schnorr , M. Euchner .
        6. Schnorr, C.P., Euchner, M.: ‘Lattice basis reduction: improved practical algorithms and solving subset sum problems’, Math. Program., 1994, 66, pp. 181199.
        . Math. Program. , 181 - 199
    7. 7)
      • M. Ajtai , R. Kumar , D. Sivakumar .
        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. 601610.
        . Proc. of 33rd ACM Symp. on Theory of Computing (STOC) , 601 - 610
    8. 8)
      • Y. Chen , P.Q. Nguyen .
        8. Chen, Y., Nguyen, P.Q.: ‘BKZ 2.0: better lattice security estimate’. ASIACRYPT'11, 2011 (LNCS, 7073), pp. 120.
        . ASIACRYPT'11 , 1 - 20
    9. 9)
      • C.P. Schnorr .
        9. Schnorr, C.P.: ‘Lattice reduction by random sampling and birthday methods’. STACS'03, 2003, vol. 2607, pp. 145156.
        . STACS'03 , 145 - 156
    10. 10)
      • G. Hanrot , X. Pujol , D. Stehlé .
        10. Hanrot, G., Pujol, X., Stehlé, D.: ‘Analyzing blockwise lattice algorithms using dynamical systems’. CRYPTO'11, 2011 (LNCS, 6841), pp. 447464.
        . CRYPTO'11 , 447 - 464
    11. 11)
      • N. Gama , P.Q. Nguyen , O. Regev .
        11. Gama, N., Nguyen, P.Q., Regev, O.: ‘Lattice enumeration using extreme pruning’. EUROCRYPT, 2010, 2010, pp. 257278.
        . EUROCRYPT, 2010 , 257 - 278
    12. 12)
      • G. Hanrot , D. Stehlé .
        12. Hanrot, G., Stehlé, D.: ‘Improved analysis of Kannan's shortest lattice vector algorithm (extended abstract)’. Crypto'07, 2007, vol. 4622, pp. 170186.
        . Crypto'07 , 170 - 186
    13. 13)
      • V. Shoup .
        13. Shoup, V.: ‘NTL: A library for doing number theory’. Available at http://www.shoup.net/ntl/.
        .
    14. 14)
      • M.M. Haque .
        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
This is a required field
Please enter a valid email address