Anzeige
Erschienen in:
2010 | OriginalPaper | Buchkapitel
Smallest Reduction Matrix of Binary Quadratic Forms
And Cryptographic Applications
verfasst von : Aurore Bernard, Nicolas Gama
Erschienen in: Algorithmic Number Theory
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
We present a variant of the Lagrange-Gauss reduction of quadratic forms designed to minimize the norm of the reduction matrix within a quadratic complexity. The matrix computed by our algorithm on the input
f
has norm
$O(\parallel f \parallel^{1/2}/\Delta_{f}^{1/4})$
, which is the square root of the best previously known bounds using classical algorithms. This new bound allows us to fully prove the heuristic lattice based attack against NICE Cryptosystems, which consists in factoring a particular subclass of integers of the form
pq
2
. In the process, we set up a homogeneous variant of Boneh-Durfee-HowgraveGraham’s algorithm which finds small rational roots of a polynomial modulo unknown divisors. Such algorithm can also be used to speed-up factorization of
pq
r
for large
r
.