wrap NTL's BKZ

[malb]

The BKZ algorithm is a lattice reduction algorithm AFAIK only implemented in NTL.

  -- BKZ: Block Korkin-Zolotarev reduction.
     This is slower, but yields a higher-quality basis,
     i.e., one with shorter vectors.
     See the Schnorr-Euchner paper for a description of this.
     This basically generalizes the LLL reduction condition
     from blocks of size 2 to blocks of larger size.

It enjoys more widespread use in cryptography these days and possibly other areas. Since Sage has Damien Stehle's fast fpLLL library and NTL's BKZ this would make Sage a very nice tool for people who care about these algorithms.

Component: linear algebra

Keywords: editor_malb

Issue created by migration from https://trac.sagemath.org/ticket/3232

[malb]

comment:1

The attached patch wraps the appropriate NTL functions. It has doctests for all new methods. However, someone more familiar with BKZ might want to add an example (possibly #long) which showcases the difference between LLL and BKZ.

[craigcitro]

Changed keywords from none to editor_malb

[malb]

comment:3

Ralf forwarded the review request to a colleague of his. I'll ping him again by the end of the week to see what happened.

[malb]

comment:4

Ralf, can you review the patch without the forwarding which now seems pointless?

[malb]

comment:5

state of affairs for editorial meeting 26/06/08

I didn't hear back from rpw yet. Maybe another referee could jump in.

[sagetrac-rpw]

Attachment: ntru_2_47.sage.gz

NTRU derived lattice, n=47

[sagetrac-rpw]

comment:6

Patch applied against SAGE 3.0.3. Works fine, doctests OK. Successfully tested on some cryptographically relevant toy sample lattices (NTRU derived, one is attached, provided by Markus Rückert).

Two typos found in documentation:

• permuation -> permutation
• Gramm-Schmidt -> Gram-Schmidt

[malb]

comment:7

w00t, I'll fix the typos today-ish.

[malb]

comment:8

To highlight BKZ's features here is a Sage session for the NTRU example rpw provided:

sage: M = eval(open("ntru_2_47.sage").read()[4:])
sage: M
94 x 94 dense matrix over Integer Ring

sage: %time M_BKZ = M.BKZ()
CPU times: user 17.64 s, sys: 0.03 s, total: 17.67 s
Wall time: 17.98 s

sage: %time M_LLL = M.LLL()
CPU times: user 0.30 s, sys: 0.00 s, total: 0.30 s
Wall time: 0.30 s

sage: %time M_LLL_NTL = M.LLL(algorithm="NTL:LLL")
CPU times: user 0.11 s, sys: 0.01 s, total: 0.12 s
Wall time: 0.16 s

sage: sqrt(sum([ a^2 for a in M_BKZ[0] ])).n()
10.1488915650922

sage: sqrt(sum([ a^2 for a in M_LLL[0] ])).n()
23.0000000000000

sage: sqrt(sum([ a^2 for a in M_LLL_NTL[0] ])).n()
23.0000000000000

sage: sqrt(sum([ a^2 for a in M_BKZ[93] ])).n()
20.7364413533277

sage: sqrt(sum([ a^2 for a in M_LLL[93] ])).n()
43.0116263352131

sage: sqrt(sum([ a^2 for a in M_LLL_NTL[93] ])).n()
47.6340214552582

[malb]

addresses rpw's review

[malb]

comment:9

Attachment: bkz.patch.gz

Typos fixed in updated patch, apply bkz.patch only.

[sagetrac-mabshoff]

comment:10

Merged bkz.patch in Sage 3.0.6.alpha0