Ticket #3232 (closed enhancement: fixed)
[with patch, positive review] wrap NTL's BKZ
| Reported by: | malb | Owned by: | was |
|---|---|---|---|
| Priority: | major | Milestone: | sage-3.0.6 |
| Component: | linear algebra | Keywords: | editor_malb |
| Cc: | Work issues: | ||
| Report Upstream: | Reviewers: | ||
| Authors: | Merged in: | ||
| Dependencies: | Stopgaps: |
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
Change History
comment:1 Changed 5 years ago by malb
- Summary changed from wrap NTL's BKZ to [with patch, needs review] wrap NTL's BKZ
comment:3 Changed 5 years ago 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.
comment:4 Changed 5 years ago by malb
Ralf, can you review the patch without the forwarding which now seems pointless?
comment:5 Changed 5 years ago 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.
comment:6 Changed 5 years ago 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
comment:7 Changed 5 years ago 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.
comment:8 Changed 5 years ago 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
comment:9 Changed 5 years ago 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.
comment:10 Changed 5 years ago by mabshoff
- Status changed from new to closed
- Resolution set to fixed
Merged bkz.patch in Sage 3.0.6.alpha0


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.