Ticket #3232 (closed enhancement: fixed)

Opened 5 months ago

Last modified 3 months ago

[with patch, positive review] wrap NTL's BKZ

Reported by: malb Assigned to: was
Priority: major Milestone: sage-3.0.6
Component: linear algebra Keywords: editor_malb
Cc:

Description

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.

Attachments

ntru_2_47.sage (27.2 kB) - added by rpw on 07/07/2008 04:12:17 PM.
NTRU derived lattice, n=47
bkz.patch (49.3 kB) - added by malb on 07/08/2008 04:54:57 AM.
addresses rpw's review

Change History

05/25/2008 01:22:19 PM changed by malb

  • summary changed from wrap NTL's BKZ to [with patch, needs review] wrap NTL's BKZ.

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.

06/15/2008 02:45:43 PM changed by craigcitro

  • keywords set to editor_malb.

06/15/2008 08:32:05 PM changed by malb

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.

06/22/2008 10:59:56 AM changed by malb

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

06/25/2008 04:17:09 AM changed by malb

  • summary changed from [with patch, needs review] wrap NTL's BKZ to [with patch, under review by rpw] wrap NTL's BKZ.

state of affairs for editorial meeting 26/06/08

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

07/07/2008 04:12:17 PM changed by rpw

  • attachment ntru_2_47.sage added.

NTRU derived lattice, n=47

07/07/2008 04:13:12 PM changed by rpw

  • summary changed from [with patch, under review by rpw] wrap NTL's BKZ to [with patch, positive review] wrap NTL's BKZ.

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

07/08/2008 01:32:30 AM changed by malb

  • summary changed from [with patch, positive review] wrap NTL's BKZ to [with patch, positive review pending typos] wrap NTL's BKZ.

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

07/08/2008 04:53:44 AM changed by malb

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

07/08/2008 04:54:57 AM changed by malb

  • attachment bkz.patch added.

addresses rpw's review

07/08/2008 04:55:28 AM changed by malb

  • summary changed from [with patch, positive review pending typos] wrap NTL's BKZ to [with patch, positive review] wrap NTL's BKZ.

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

07/14/2008 08:24:46 PM changed by mabshoff

  • status changed from new to closed.
  • resolution set to fixed.

Merged bkz.patch in Sage 3.0.6.alpha0