[HGI-News-de] HGI Kolloquium Do. 06.08.: "Finding Small Roots of Multivariate Polynomial Equations" von A. Bauer

[Newsletter des Horst Görtz Instituts]

Hallo,

im Rahmen des HGI Kolloquiums "Aktuelle Themen der IT-Sicherheit" wird
am kommenden *Donnerstag* der folgende Vortrag angeboten:

Aurelie Bauer (ENS Paris):
*Toward a Rigorous Generalization of Coppersmith's Methods for Finding
Small Roots of Multivariate Polynomial Equations*

Termin:
Donnerstag, der 06. August um  11.00 Uhr (*s.t.*)
Raum: IC 4/161

Interessierte sind herzlich eingeladen!


==============================================================
Abstract:

In 1996, Coppersmith introduced two lattice-based techniques for finding
small roots of polynomial equations. The first one works for the
univariate modular case, the other one for the bivariate case over the
integers. Since then, these techniques have been widely used for
cryptanalytic applications. As some of these applications use a bigger
number of variables, generalizations of Coppersmith's methods have even
been proposed. Unfortunately, these extensions are only heuristic as
they rely on a well-known assumption concerning algebraic independence
between polynomials.

In this talk, we focus on multivariate generalizations of Coppersmith's
methods and especially on the validity of the assumption concerning
algebraic independence. Usually, this assumption is not considered as a
problem because it is often satisfied in practice. In this presentation,
we first study the limits of using this type of assumption by
highlighting a real cryptographic counterexample. This result emphasizes
the necessity of finding rigorous methods. In this purpose, we propose a
new construction which guarantees the algebraic independence between
polynomials and that uses Gröbner bases computations. By applying this
new technique on real cryptographic schemes, we obtain some promising
results. In particular, we manage to prove how to make fully rigorous
the attack initially proposed by Boneh and Durfee on the RSA equation
for a small private key.
==============================================================

Informationen über die nächsten geplanten Vorträge im Rahmen des
HGI Kolloquiums sind auch im Web zu finden:
http://www.hgi.rub.de/hgi/hgi-seminar/aktuelles

Gruß,
Mathias Herrmann