Anzeige
Erschienen in:
2006 | OriginalPaper | Buchkapitel
Practical Lattice Basis Sampling Reduction
verfasst von : Johannes Buchmann, Christoph Ludwig
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 propose Simple Sampling Reduction (
SSR
) that makes Schnorr’s Random Sampling Reduction (
RSR
) practical. We also introduce generalizations of
SSR
that yield bases with several short basis vectors and that, in combination, generate shorter basis vectors than
SSR
alone. Furthermore, we give a formula for Pr[||
v
||
2
≤
x
] provided
v
is randomly sampled from
SSR
’s search space. We describe two algorithms that estimate the probability that a further
SSR
iteration will find an even shorter vector, one algorithm based on our formula for Pr[||
v
||
2
≤
x
], the other based on the approach of Schnorr’s
RSR
analysis. Finally, we report on some cryptographic applications.