Self-Dual BKZ on NTRU: Dimension-Onset, Fatigue, and a Cross-Engine Reference-Free DSD Observable

The Root Hermite Factor (RHF) is the standard one-number summary of lattice-reduction quality; the companion paper found BKZ and self-dual BKZ (SD-BKZ) RHF-equal on LWE-Kannan lattices. This report shows that on circulant NTRU near the fatigue point they differ, on identical bases, in where reduction first finds the dense secret sublattice. At β=20, n=89–113, BKZ needs a modulus 20–29% larger than SD-BKZ to recover the exact key (19–28% scored by a reference-free dense-sublattice flag; the 29% is 21% under a monotone onset fit). At β=40 the G6K sieve and fplll enumeration agree: the gap narrows to at most 9%, and SD-BKZ leads per key at n=89 and 113 on both engines, unresolved at n=101. Below fatigue the advantage is not smooth in dimension: tied for n≤67, it spikes at n≈71–73 and settles to a plateau for n=79–89. At n=157–185, in preliminary cells, the β=40 recovery wall moves with blocksize and tours, and SD-BKZ leads per seed but not per core-hour on fplll. The threat model is an adversary free to pick SD-BKZ over BKZ at fixed blocksize and tours; the instances are toy-size (n≤185, β≤60) and no deployed parameter set is evaluated. All experiments are reproducible via a containerised, determinism-gated benchmark.

Authors

Publication Details

Journal
Zenodo (CERN European Organization for Nuclear Research)
Published
2026-11-20
DOI
https://doi.org/10.5281/zenodo.24393193
Primary Topic
Cryptography and Data Security
Type
preprint
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
NOV
preprint

Self-Dual BKZ on NTRU: Dimension-Onset, Fatigue, and a Cross-Engine Reference-Free DSD Observable

Brendan Chambers-Bourgeois
1 links
Zenodo (CERN European Organization for Nuclear Research)
Cryptography and Data Security
preprint

Self-Dual BKZ on NTRU: Dimension-Onset, Fatigue, and a Cross-Engine Reference-Free DSD Observable

Brendan Chambers-Bourgeois
preprint en

Abstract

The Root Hermite Factor (RHF) is the standard one-number summary of lattice-reduction quality; the companion paper found BKZ and self-dual BKZ (SD-BKZ) RHF-equal on LWE-Kannan lattices. This report shows that on circulant NTRU near the fatigue point they differ, on identical bases, in where reduction first finds the dense secret sublattice. At β=20, n=89–113, BKZ needs a modulus 20–29% larger than SD-BKZ to recover the exact key (19–28% scored by a reference-free dense-sublattice flag; the 29% is 21% under a monotone onset fit). At β=40 the G6K sieve and fplll enumeration agree: the gap narrows to at most 9%, and SD-BKZ leads per key at n=89 and 113 on both engines, unresolved at n=101. Below fatigue the advantage is not smooth in dimension: tied for n≤67, it spikes at n≈71–73 and settles to a plateau for n=79–89. At n=157–185, in preliminary cells, the β=40 recovery wall moves with blocksize and tours, and SD-BKZ leads per seed but not per core-hour on fplll. The threat model is an adversary free to pick SD-BKZ over BKZ at fixed blocksize and tours; the instances are toy-size (n≤185, β≤60) and no deployed parameter set is evaluated. All experiments are reproducible via a containerised, determinism-gated benchmark.

Zenodo (CERN European Organization for Nuclear Research)
Cryptography and Data Security
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.

Laika access coming soon