TU Darmstadt / ULB / TUprints

Contributions to Provable Security and Efficient Cryptography

Schmidt-Samoa, Katja (2006)
Contributions to Provable Security and Efficient Cryptography.
Technische Universität
Ph.D. Thesis, Primary publication

[img]
Preview
PDF
Diss.Schmidt-Samoa.pdf
Copyright Information: In Copyright.

Download (1MB) | Preview
Item Type: Ph.D. Thesis
Type of entry: Primary publication
Title: Contributions to Provable Security and Efficient Cryptography
Language: English
Referees: Takagi, Prof. Dr. Tsuyoshi ; Buchmann, Prof.Dr. Johannes
Advisors: Takagi, Prof. Dr. Tsuyoshi
Date: 27 June 2006
Place of Publication: Darmstadt
Date of oral examination: 5 January 2006
Abstract:

This thesis deals with two main matters of modern public key cryptography: provable security and efficient implementation. Indubitably, security is the most important property of any cryptographic scheme. Nevertheless, cryptographic algorithms have often been designed on a trial-and-error basis, i.e., a system has been regarded as secure as long as it withstood cryptanalytic attacks. In contrast, the provable security approach provides rigorous mathematical proofs within well-defined models. Nowadays, provable security is a key requirement for many applications. The main contribution of the first part of this thesis is the development and analysis of new provably secure trapdoor one-way permutations. (Trapdoor) one-way functions are the cardinal primitives in public key cryptography, as they are utilized as building blocks for numerous kinds of cryptographic protocols. For this reason, and because of the small number of promising candidates known today, the invention of new trapdoor one-way functions is of interest on its own. However, to prove the practical relevance of our proposal, we additionally invent several provably secure applications in the range of homomorphic encryption, fail-stop signature schemes, hybrid encryption, and trapdoor commitments. In the second part of this work, we will turn our attention to the efficient implementation of public key algorithms. Besides security, efficiency is the main criterion when evaluating cryptographic schemes because inefficient cryptosystems are of little practical value. In widely-used hand-held devices with scarce resources, cryptosystems based on elliptic curve point groups are the first choice today. Consequently, it is an active area of research to enhance the efficiency of elliptic curve scalar multiplication, which is the most common operation in these cryptosystems. Our contribution here is located in the field of multiplication methods with low memory requirements. We will introduce an algorithm which is as efficient as the state-of-the-art solution, but which significantly reduces the consumption of working memory. Moreover, we will develop a highly flexible variant which can be adapted to the exact amount of available storage. Therefore, the algorithms presented here are especially useful in connection with limited-constraint devices such as smart-cards.

Alternative Abstract:
Alternative AbstractLanguage

Diese Dissertation befasst sich mit zwei der wichtigsten Aspekte beim Entwurf von Public-Key Kryptosystemen: Beweisbare Sicherheit und Effizienz. Es steht außer Frage, dass Sicherheit eine unverzichtbare Eigenschaft jeder kryptographischen Anwendung ist. Nichtsdestotrotz vertrauten die Entwickler kryptographischer Verfahren lange Zeit der Methode von Versuch-und-Irrtum, d.h. ein Verfahren galt so lange als sicher, bis erfolgreiche Kryptanalyse eine Schwäche offenbarte. Im Gegensatz dazu bedient sich der Ansatz beweisbarer Sicherheit strenger mathematischer Beweise in wohldefinierten Sicherheitsmodellen. Heutzutage gilt beweisbare Sicherheit in vielen Bereichen als eine Standardforderung an ein Kryptosystem. Den Hauptbeitrag des ersten Teils dieser Arbeit bildet die Entwicklung und Analyse von neuen beweisbar sicheren Falltür-Einweg-Permutationen. (Falltür-)Einweg-Funktionen sind das wichtigste Primitiv in der Public-Key-Kryptographie, denn sie bilden den Hauptbaustein für zahlreiche kryptographische Anwendungen. Aus diesem Grunde, und nicht zuletzt weil nur äußerst wenige geeignete Kandidaten bekannt sind, ist die Entwicklung neuer (Falltür-)Einweg-Funktionen bereits für sich genommen von größtem Interesse. Um jedoch auch den praktischen Nutzen der vorgeschlagenen Konstruktionen unter Beweis zu stellen, werden beweisbar sichere Anwendungen aus den Bereichen homomorphe Verschlüsselung, Fail-Stop Signaturen, hybride Verschlüsselung und Falltür-Hinterlegungsverfahren vorgestellt und analysiert. Der zweite Teil dieser Arbeit widmet sich der effizienten Implementierung von Algorithmen der Public-Key-Kryptographie. Neben der Sicherheit ist die Effizienz das Hauptbewertungsmerkmal kryptographischer Verfahren, denn ineffiziente Algorithmen sind unbrauchbar für praktische Anwendungen. In den heute weit verbreiteten mobilen Endgeräten mit beschränktem Speicherplatz sind Elliptische-Kurven-Kryptosysteme aufgrund ihrer moderaten Schlüssellängen die erste Wahl. Die häufigste Operation dieser Kryptosysteme ist die Skalarmultiplikation, daher ist die Entwicklung von Verfahren zu deren Beschleunigung ein vielbeachtetes Forschungsgebiet. Die vorliegende Arbeit beschäftigt sich speziell mit Multiplikations-Algorithmen, die geringe Anforderungen an den Speicherplatz stellen. Es wird ein neuer Algorithms entworfen, der ebenso effizient ist wie die "state-of-the-art" Lösung, allerdings bei signifikant geringerem Speicherbedarf. Desweiteren wird eine Variante dieses Algorithmus entwickelt, die exakt an den zur Verfügung stehenden Speicherplatz angepasst werden kann, so dass keine wertvollen Ressourcen verschwendet werden müssen. Die vorgestellten Verfahren erweisen sich also als besonders nützlich für die Implementierung auf speicherbeschränkten Medien wie Smart-Cards.

German
Uncontrolled Keywords: trapdoor permutation, elliptic curve scalar multiplication
Alternative keywords:
Alternative keywordsLanguage
trapdoor permutation, elliptic curve scalar multiplicationEnglish
URN: urn:nbn:de:tuda-tuprints-7085
Classification DDC: 000 Generalities, computers, information > 004 Computer science
Divisions: 20 Department of Computer Science
Date Deposited: 17 Oct 2008 09:22
Last Modified: 07 Dec 2012 11:52
URI: https://tuprints.ulb.tu-darmstadt.de/id/eprint/708
PPN:
Export:
Actions (login required)
View Item View Item