Anzeige
Erschienen in:
2010 | OriginalPaper | Buchkapitel
Solving Generalized Small Inverse Problems
verfasst von : Noboru Kunihiro
Erschienen in: Information Security and Privacy
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 introduce a “generalized small inverse problem (GSIP)” and present an algorithm for solving this problem. GSIP is formulated as finding small solutions of
$f(x_0, x_1, \ldots , x_n)=x_0 h(x_1, \ldots , x_n)+C=0 (\bmod \; M)$
for an
n
-variate polynomial
h
, non-zero integers
C
and
M
. Our algorithm is based on lattice-based Coppersmith technique. We provide a strategy for construction of a lattice basis for solving
f
= 0, which are systematically transformed from a lattice basis for solving
h
= 0. Then, we derive an upper bound such that the target problem can be solved in polynomial time in log
M
in an explicit form. Since GSIPs include some RSA-related problems, our algorithm is applicable to them. For example, the small key attacks by Boneh and Durfee are re-found automatically.