Oberseminar Kryptographie

Sommersemester 2008

Oberseminar
Dozent Zeit Raum Erstmals am
Prof. A. May donnerstags, 14:00-16:00 NA 5/64 10.04.2008

Wir Ernten was wir Sieben (und nicht umgekehrt)

Roberto Avanzi

Donnerstag, 26.06.2008

Es wird ueber die Berechnung von Diskreten Logarithmen geredet. Die Filtering-Technik des Erntens macht die Berechnung von Diskreten Logarithmen wenigstens 30% schneller, und theoretisch auch mehr. Der Witz ist, diese Verbesserung ist nur abhaengig von den Parametern fuer das Ernten an sich, und haengt nicht von der Art des Index-Calculus Algorithmus ab (ohne Primzahlen oder mit einer Primzahl).

Factoring Polynomials with the van Hoeij Algorithm

Mathias Herrmann

Donnerstag, 12.06.2008

Although a polynomial time algorithm exists, the most commonly used algorithm for factoring a univariate polynomial f with integer coefficients is the Berlekamp-Zassenhaus algorithm which has a complexity that depends exponentially on n where n is the number of modular factors of f. This exponential time complexity is due to a combinatorial problem; the problem of choosing the right subset of these n factors. In this paper we reduce this combinatorial problem to a different problem that can be solved with polynomial time algorithms such as LLL. The result is a practical algorithm that can factor large polynomials even when n is large as well.

News on Factoring with Oracles

Alexander May

Donnerstag, 05.06.2008

Faktorisieren großer Zahlen ist eines der fundamentalen Probleme der Zahlentheorie, auf dem auch die Sicherheit von RSA basiert. Daher besteht großes Interesse an guten Faktorisierungsalgorithmen. Einige Fortschritte bezüglich der Komplexität von Faktorisierungsalgorithmen wurden durch das Quadratische Sieb, die Elliptische Kurven Methode und das Zahlkörpersieb erzielt. Seitdem wurde klassische Faktorisierung hauptsächlich in eingeschränkten Modellen betrachtet, in denen der Angreifer gewisse Orakel befragen darf. Beispiele hierfür sind Orakel, die jegliche ja/nein-Fragen beantworten, oder Orakel, die einen Teil der Bits eines Faktors zurückgeben. Ein weiterer Faktorisierungsangriff mit einem Orakel wird hier vorgestellt. Dabei wird die Mächtigkeit des Orakels weiter eingeschränkt, indem nur indirekte Informationen über einzelne Faktoren gegeben werden.

Cryptanalysis

Gregor Leander

Mittwoch, 30.04.2008

We describe the cryptanalysis of a public key cryptosystem, whose security relies on the problem of finding a low-weight multiple of a given polynomial. Our attack is a chosen ciphertext attack which leads to a full key-recovery and runs in polynomial time in the security parameter of the scheme.

Lattice-Based Identification Schemes Secure Under Active Attacks (Vadim Lyubashevsky - PKC 2008)

Maike Ritzenhofen

Donnerstag, 24.04.2008

There is an inherent difficulty in building 3-move ID schemes based on combinatorial problems without much algebraic structure. A consequence of this, is that most standard ID schemes today are based on the hardness of number theory problems. Not having schemes based on alternate assumptions is a cause for concern since improved number theoretic algorithms or the realization of quantum computing would make the known schemes insecure. In this work, we examine the possibility of creating identification protocols based on the hardness of lattice problems. We construct a 3-move identification scheme whose security is based on the worst-case hardness of the shortest vector problem in all lattices, and also present a more efficient version based on the hardness of the same problem in ideal lattices.