TU Darmstadt / ULB / TUprints

Selecting and Reducing Key Sizes for Multivariate Cryptography

Petzoldt, Albrecht :
Selecting and Reducing Key Sizes for Multivariate Cryptography.
tuprints, Darmstadt
[Ph.D. Thesis], (2013)

[img]
Preview
Text
thesis.pdf
Available under Creative Commons Attribution Non-commercial No Derivatives, 2.5.

Download (1MB) | Preview
[img] Archive
CD.zip
Available under Creative Commons Attribution Non-commercial No Derivatives, 2.5.

Download (13MB)
Item Type: Ph.D. Thesis
Title: Selecting and Reducing Key Sizes for Multivariate Cryptography
Language: English
Abstract:

Cryptographic techniques are essential for the security of communication in modern society. As more and more business processes are performed via the Internet, the need for efficient cryptographic solutions will further increase in the future. Today, nearly all cryptographic schemes used in practice are based on the two problems of factoring large integers and solving discrete logarithms. However, schemes based on these problems will become insecure when large enough quantum computers are built. The reason for this is Shor's algorithm, which solves number theoretic problems such as integer factorization and discrete logarithms in polynomial time on a quantum computer. Therefore one needs alternatives to those classical public key schemes. Besides lattice, code and hash based cryptosystems, multivariate cryptography seems to be a candidate for this. Additional to their (believed) resistance against quantum computer attacks, multivariate schemes are very fast and require only modest computational resources, which makes them attractive for the use on low cost devices such as RFID chips and smart cards. However, there remain some open problems to be solved, such as the unclear parameter choice of multivariate schemes, the large key sizes and the lack of more advanced multivariate schemes like signatures with special properties and key exchange protocols. In this dissertation we address two of these open questions in the area of multivariate cryptography. In the first part we consider the question of the parameter choice of multivariate schemes. We start with the security model of Lenstra and Verheul, which, on the basis of certain assumptions like the development of the computing environment and the budget of an attacker, proposes security levels for now and the near future. Based on this model we study the known attacks against multivariate schemes in general and the Rainbow signature scheme in particular and use this analysis to propose secure parameter sets for these schemes for the years 2012 - 2050. In the second part of this dissertation we present an approach to reduce the public key size of certain multivariate signature schemes such as UOV and Rainbow. We achieve the reduction by inserting a structured matrix into the coefficient matrix of the public key, which enables us to store the public key in an efficient way. We propose several improved versions of UOV and Rainbow which reduce the size of the public key by factors of 8 and 3 respectively. Using the results of the first part, we show that using structured public keys does not weaken the security of the underlying schemes against known attacks. Furthermore we show how the structure of the public key can be used to speed up the verification process of the schemes. Hereby we get a speed up of factors of 6 for UOV and 2 for Rainbow. Finally we show how to apply our techniques to the QUAD stream cipher. By doing so we can increase the data throughput of QUAD by a factor of 7.

Alternative Abstract:
Alternative AbstractLanguage
Kryptographische Techniken sind für die Sicherheit der Kommunikation in der modernen Gesellschaft unverzichtbar. Da der Anteil der im Internet durchgeführten Geschäftsprozesse weiter zunimmt, wird der Bedarf nach effizienten Lösungen auf diesem Gebiet noch weiter steigen. Nahezu alle heutzutage benutzten kryptographischen Verfahren beruhen entweder auf dem Problem des Faktorisierens großer Zahlen oder dem Lösen diskreter Logarithmen. Jedoch werden derartige Verfahren unsicher, sobald Quantencomputer entsprechender Größe zur Verfügung stehen. Der Grund dafür ist Shor's Algorithmus, mit dessen Hilfe zahlentheoretische Probleme wie das Faktorisieren ganzer Zahlen und das Lösen diskreter Logarithmen auf einem Quantencomputer in polynomieller Zeit durchgeführt werden können. Aufgrund dessen werden Alternativen zu diesen klassischen public-key-Verfahren benötigt. Neben gitter-, code- und hashbasierten Verfahren ist die multivariate Kryptographie ein möglicher Kandidat dafür. Zusätzlich zu der (vermuteten) Resistenz gegenüber Angriffen mit Quantencomputern sind multivariate Verfahren sehr schnell und benötigen lediglich moderate Rechenkapazitäten, was diese Verfahren für den Einsatz auf RFID chips und smart cards attraktiv macht. Jedoch bleiben noch einige offene Probleme zu lösen, wie die Parameterwahl multivariater Verfahren, das Problem großer Schlüssel sowie der Mangel an fortgeschrittenen multivariaten Verfahren wie Signaturverfahren mit speziellen Eigenschaften und key-exchange Protokollen. In dieser Dissertation befassen wir uns mit zwei dieser offenen Fragen auf dem Gebiet der multivariaten Kryptographie. Im ersten Teil beschäftigen wir uns mit der Parameterwahl multivariater Verfahren. Wir beginnen mit dem Sicherheitsmodell von Lenstra und Verheul, das, auf der Basis einiger Annahmen wie der Entwicklung von Rechenkapazitäten und dem Budget eines Angreifers, Sicherheitslevel für die Gegenwart und die nahe Zukunft vorschlägt. Von diesem Modell ausgehend analysieren wir bekannte Angriffe gegen multivariate Systeme im Allgemeinen und das Rainbow Signaturverfahren im Besonderen, um für diese Verfahren sichere Parametersätze für die Zeit bis 2050 herzuleiten. Im zweiten Teil der Dissertation stellen wir eine Strategie zur Verkleinerung des öffentlichen Schlüssels bestimmter multivariater Signaturverfahren wie UOV und Rainbow vor. Wir erzielen unsere Ergebnisse, indem wir eine strukturierte Matrix in die Koeffizientenmatrix des öffentlichen Schlüssels übertragen. Dies ermöglicht es uns, den öffentlichen Schlüssel auf effiziente Weise zu speichern. Wir beschreiben mehrere dieser verbesserten Varianten von UOV und Rainbow, die die Größe des öffentlichen Schlüssels um das 8-fache (UOV) bzw. das 3-fache (Rainbow) verringern. Darüber hinaus zeigen wir, wie sich die Struktur des öffentlichen Schlüssels dazu verwenden lässt, den Verifikationsprozess der beiden Signaturverfahren zu beschleunigen. Hierbei erzielen wir Beschleunigungen um das 6-fache (UOV) bzw. das 2-fache (Rainbow). Mit Hilfe der Ergebnisse des ersten Teils zeigen wir, dass durch unsere Maßnahmen die Sicherheit der Verfahren nicht beeinträchtigt wird. Im letzten Abschnitt zeigen wir, wie sich unsere Techniken auf die multivariate Stromchiffre QUAD anwenden lassen. Dadurch lässt sich der Datendurchsatz von QUAD um das 7-fache erhöhen. German
Place of Publication: Darmstadt
Publisher: tuprints
Classification DDC: 000 Allgemeines, Informatik, Informationswissenschaft > 004 Informatik
Divisions: 20 Department of Computer Science > Theoretical Computer Science - Cryptography and Computer Algebra
Date Deposited: 08 Aug 2013 10:19
Last Modified: 08 Aug 2013 10:19
URN: urn:nbn:de:tuda-tuprints-35230
Referees: Buchmann, Prof. Dr. Johannes and Ding, Prof. Dr, Jintai
Refereed: 15 July 2013
URI: http://tuprints.ulb.tu-darmstadt.de/id/eprint/3523
Export:
Actions (login required)
View Item View Item

Downloads

Downloads per month over past year