Oberseminar WS 07/08
| Zeit | Raum |
|---|---|
| donnerstags, 16:00-18:00 | NA 5/64 |
Nächster Vortrag: Donnerstag, 17.01.2008
Zur Polynomauswahl im GNFS
Andrey Timofeev
Im GNFS spielt die Wahl der Polynomen eine signifikante Rolle. Zur Zeit findet der Algorithmus von Thorsten Kleinjung beste Polynome.
Wir versuchen etwa bessere Polynome zu finden wie folgt: Zu einer gegebenen Nullstelle $m$ wird mithilfe des LLL-Algorithmus ein gutes Polynompaar mit dieser gemeinsamen Nullstelle modulo $N$ konstruiert. Wir untersuchen zwei Varianten dieser Konstruktion, wobei wir versuchen, ein Untergitter zu finden, dessen Polynome viele lokale Bedingungen erfüllen. Dabei analysieren wir, wie die Eigenschaft "viele lokale Bedingungen" die Qualität eines ermittelten Polynompaar beeinflusst. Hierdurch können wir den lokalen Teil α des Murphy-Wertes $Q_3$ bereits mittels LLL verbessern. Möglicherweise könnte man durch diese Methode etwa bessere Polynompaare erhalten.
Vorträge
| Termin | Vortragender | Titel |
|---|---|---|
| 25.10.07 | Dr. Gregor Leander | Numerical Results on Boolean Functions with Applications in Cryptography |
| 08.11.07 | Prof. Dr. Alexander May | Using LLL-Reduction for Solving RSA and Factorization Problems: A survey |
| 15.11.07 | Maike Ritzenhofen | On the impossibility of efficiently combining collision resistant hash functions |
| 22.11.07 | Mathias Herrmann | Visualization of the Lattice Basis Selection using Newton Polytopes |
| 29.11.07 | Prof. Dr. Roberto Avanzi | Arithmetic in binary fields with applications to elliptic curve cryptography |
| 06.12.07 | Jan Aumann | Darstellung ganzer Zahlen in Zahlringen mit kryptographischen Anwendungen |
| 20.12.07 | Tim Kornau, David Oswald | Generierung optimierter Routinen für Arithmetik über binären endlichen Körpern |
| 10.01.08 | Thomas Dullien | Spezialisierte Algebraische Methoden für GF(2) |
| 17.01.08 | Andrey Timofeev | Zur Polynomauswahl im GNFS |
Numerical Results on Boolean Functions with Applications in Cryptography
In this talk we will give a survey about recent results on (vectorial)-Boolean functions with good cryptographic properties. We will focus on results that are partially derived using computer algorithms. It is demonstrated that the use of numerical results is often the key to progress in the study of highly non-linear Boolean functions. Exemplarily, we will deal with the following topics:
- Infinite families of APN functions inequivalent to power functions.
- A classification of APN mappings in dimension 5.
- A conjecture on AB exponents
References:
[1] Marcus Brinkman and Gregor Leander. On the classification of apn functions up to dimension five. International Workshop on Coding and Cryptography (WCC), 2007.
[2] Y. Edel, G. Kyureghyan, and A. Pott. A new apn function which is not equivalent to a power mapping. IEEE Transactions on Information Theory, 52(2):744–747, 2006.
[3] Philippe Langevin and Gregor Leander. On a conjecture by Dobbertin. Symposium on Algebraic Geometry and its Applications (SAGA), 2007.
Using LLL-Reduction for Solving RSA and Factorization Problems - A survey
The talk addresses the problem of inverting the RSA function and the problem of factorizing integers. We relax these problems in several ways and show that the relaxations lead to polynomial time solvable problems. In this approach, we model the relaxed problems as polynomial equations which have roots of small size. The roots are then found by a method originally introduced by D. Coppersmith in 1996, which in turn is based on the famous LLL lattice reduction algorithm.
We also present a novel application for RSA with so-called small CRT exponents. Namely, we show that the factorization of an RSA modulus N=pq can be found in polynomial time provided that RSA is used with a secret exponent d such that both d (mod p-1) and d (mod q-1) are smaller than N^0.073. The existence of such a polynomial time attack answers a long-standing open problem by Wiener.
On the impossibility of efficiently combining collision resistant hash functions
In kryptographischen Anwendungen wie zum Beispiel Digitalen Signaturen oder MACs werden Hashfunktionen verwendet. Die Sicherheit dieser Anwendungen hängt oft von der Kollisionsresistenz der zu Grunde liegenden Hashfunktion ab.
In den letzten Jahren sind Kollisionen für Standard-Hashfunktionen gefunden worden (zum Beispiel für MD5 und SHA-1).
Daher ist neben der Entwicklung neuer Konstruktionen für Hashfunktionen auch die Frage von Interesse, ob man Hashfunktionen H_1, ..., H_k so zu einer Hashfunktion H kombinieren kann, dass H kollisionsresistent ist, solange eines der H_i diese Eigenschaft hat.
Das Finden einer Kollision für eine der Hashfunktionen soll also die Sicherheit der kombinierten Hashfunktion nicht beeinträchtigen.
D. Boneh und X. Boyen betrachten diese Fragestellung in einem eingeschränkten Modell, in dem in der Auswertung von H jede Funktion H_i nur einmal aufgerufen werden darf. Hierfür zeigen sie, dass die gesuchte Funktion H eine Ausgabelänge haben muss, die der Ausgabelänge bei Konkatenation der H_i entspricht. Eine effiziente Black-Box-Kombination von Hashfunktionen existiert unter diesen Voraussetzungen also nicht.
Visualization of the Lattice Basis Selection using Newton Polytopes
In modern cryptography a major task is to find roots of modular polynomials or polynomials over the integers. In 1996 Coppersmith presented an approach based on lattice theory, that allows to find small roots in polynomial time.
Exemplary applications include factoring with known bits, partial key exposure in RSA or RSA with small private exponent $d$. The key to those results is a careful choice of the basis vectors of the corresponding lattice. There is however no general method known to select basis vectors in order to obtain optimal bounds up to which one may find the roots.
This talk will focus on the connection between the basis vectors and the {\em Newton Polytope} of the underlying polynomial. We will try to visualize the selection process and give ideas which lead to improved bounds in special cases.
Arithmetic in binary fields with applications to elliptic curve cryptography
In the first part of the talk we describe an implementation of binary field arithmetic written in the C programming language. In this implementation of field arithmetic the curve representing field multiplication performance closely resembles the theoretical quadratic bit-complexity that can be expected for small inputs.
This has important practical consequences: For instance, it will allow us to compare the performance of the arithmetic on curves of different genera and defined over fields of different sizes without worrying about penalties introduced by field arithmetic and concentrating on the curve arithmetic itself. Moreover, the cost of field inversion is very low, making the use of affine coordinates in curve arithmetic more interesting. These applications will be mentioned.
In the second part of the talk we discuss irreducible polynomials that can be used to speed up square root extraction in fields of characteristic two by representing the involved fields in a particularly convenient way. The obvious applications are to point halving methods for elliptic curves and divisor halving methods for hyperelliptic curves.
Irreducible polynomials $P(X)$ such that the square root $\zeta$ of a zero $x$ of $P(X)$ is a sparse polynomial are considered and those for which $\zeta$ has minimal degree are characterized. We reveal a surprising connection between the minimality of this degree and the extremality of the the number of trace one elements in the polynomial base associated to $P(X)$.
We also show how to improve the speed of solving quadratic equations and that the increase in the time required to perform modular reduction is marginal and does not affect performance adversely. Experimental results confirm that the new polynomials mantain their promises. Point halving gets a speed-up of $20\%$ and the performance of scalar multiplication based on point halving is improved by at least $11\%$.
Darstellung ganzer Zahlen in Zahlringen mit kryptographischen Anwendungen
Im Vortrag wollen wir für die Skalarmultiplikation auf elliptischen Kurven eine Rekodierung vorstellen, die mithilfe des Frobenius Homomorphismus sowie Fenstern arbeitet. Dabei werden wir genauer eine syntaktische Ziffernmenge $\mathcal{D}_w$ benutzen, um beliebige Elemente aus der Ordnung $\mathbb{Z}[\tau]$ zu rekodieren, wobei $\tau$ eine komplexe Nullstelle eines quadratischen Polynoms ist. Die Syntax der Ziffernmenge ist hierbei eine auf der NAF (Non-adjacent-Form) Bedingung basierende Regel nach der alle Ziffern von $\mathcal{D}_w$ erzeugt werden können und wodurch $\mathcal{D}_w$ zu einem NADS (Non-adjacent-digit-set) wird.
Wir erhalten die Möglichkeit die Skalarmultiplikation für eine große Klasse von elliptischen Kurven zu beschleunigen und für die Anwendung in kryptographischen Protokollen fruchtbar zu machen.
Generierung optimierter Routinen für Arithmetik über binären endlichen Körpern
Mit der zunehmenden Verbreitung von auf Elliptischen Kurven basierenden Krypto-Systemen entsteht die zunehmende Notwendigkeit, über effiziente und flexible Implementierungen der Arithmetik des zugrundeliegenden Körpers (GF(2^m) oder Z_p) zu verfügen.
Dieser Vortrag befasst sich mit der automatisierten Erzeugung von C-Code für die Grundoperationen über binären endlichen Körpern beliebiger Länge. Das Tool 'FFFactory' geht dabei einen Mittelweg zwischen vollständig per Hand erstellten Routinen und generischen Implementierungen (z.B. NTL). Einerseits bleibt so die Flexibilität allgemein gehaltener Bibliotheken erhalten, andererseits verringert sich der Performance-Nachteil gegenüber aufwändig manuell programmierten Funktionen.
Spezialisierte Algebraische Methoden für GF(2)
Algebraische Kryptanalyse(n) basieren darauf, für eine gegebene Verschlüsselungsfunktion eine polynomielle Darstellung (mit den Schlüsselbits als unbekannten) über einem endlichen Körper anzugeben, und im Anschluss daran mittels Methoden aus der kommutativen Algebra (Gröbnerbasen) oder der linearen Algebra (Relinearisierung) diese Gleichungssysteme zu lösen.
Die bisher angewandten Methoden zum Lösen der entstehenden Gleichungssysteme funktionieren über beliebigen Basiskörpern. Eine offensichtliche Frage ist, ob man Algorithmen konstruieren kann, die die spezifischen Eigenschaften des Basiskörpers bzw. Polynomringes ausnutzen, um effizienter als 'allgemeine' Algorithmen zu sein.
Der Vortrag betrachtet den Ring der boolschen Funktionen: GF(2)[ x1, ..., xn ] / < x1^2-x1, ..., xn^2-xn > Einige Überraschende Eigenschaften werden diskutiert - dieser Ring ist z.B. ein Hauptidealring, und es gibt einen dem euklidischen Algorithmus ähnlichen Algorithmus, um den Erzeuger eines Ideals aus einem Erzeugendensystem eines Ideals zu berechnen. Der von Raddum und Semaev vorgeschlagene Algorithmus zur Lösung von Gleichungssystemen wird in einen algebraisch-geometrischen Kontext gerückt, und einige Versuche werden diskutiert, einen für die Kryptographie nützlichen Begriff der "Approximation" von boolschen Funktionen zu definieren.
Zur Polynomauswahl im GNFS
Im GNFS spielt die Wahl der Polynomen eine signifikante Rolle. Zur Zeit findet der Algorithmus von Thorsten Kleinjung beste Polynome.
Wir versuchen etwa bessere Polynome zu finden wie folgt: Zu einer gegebenen Nullstelle $m$ wird mithilfe des LLL-Algorithmus ein gutes Polynompaar mit dieser gemeinsamen Nullstelle modulo $N$ konstruiert. Wir untersuchen zwei Varianten dieser Konstruktion, wobei wir versuchen, ein Untergitter zu finden, dessen Polynome viele lokale Bedingungen erfüllen. Dabei analysieren wir, wie die Eigenschaft "viele lokale Bedingungen" die Qualität eines ermittelten Polynompaar beeinflusst. Hierdurch können wir den lokalen Teil α des Murphy-Wertes $Q_3$ bereits mittels LLL verbessern. Möglicherweise könnte man durch diese Methode etwa bessere Polynompaare erhalten.