TU Darmstadt / ULB / tuprints

Lattice-based Signature Schemes with Additional Features

Rückert, Markus :
Lattice-based Signature Schemes with Additional Features.
TU Darmstadt
[Ph.D. Thesis], (2011)

[img]
Preview
PDF
Dissertation.pdf
Available under Creative Commons Attribution Non-commercial No Derivatives.

Download (1454Kb) | Preview
Item Type: Ph.D. Thesis
Title: Lattice-based Signature Schemes with Additional Features
Language: English
Abstract:

Building cryptographic schemes upon as many fundamentally different hard problems as possible, seems to be the best way to hedge against future threats such as quantum computers. Being mainly based on the hardness of factoring and computing discrete logarithms, the present security landscape is at risk. In contrast, problems in lattices, such as finding short non-zero vectors, seem to withstand quantum computer attacks and the best known algorithms run in exponential time. In sharp contrast to other fields of cryptography, lattices admit a worst-case to average-case reduction (Ajtai 1996). Instead of assuming that a problem is hard for randomly chosen instances, lattice-based cryptosystems merely require the existence of a single hard instance, i.e., hardness in the worst case. With such an additional "trust anchor", the resulting security guarantees are much more plausible. Quite recently, we have seen an increased interest in lattice-based cryptography with many striking results. In this thesis, we are particularly interested in signature schemes, which provide a supporting pillar for today's economy. While we have seen basic signature schemes from lattices, e.g., (Gentry, Peikert, Vaikuntanathan 2008), (Lyubashevsky, Micciancio 2008), (Lyubashevsky 2009), or (Cash, Hofheinz, Kiltz, Peikert 2009), there are hardly any results dealing with the specific needs of applications, where ordinary signatures often fall too short. In this thesis, we build upon the above results and equip them with additional features, motivated by an exemplary selection of application scenarios. Hence, we demonstrate the great versatility of lattices in cryptography. In particular, we facilitate privacy-friendly electronic elections, fair online contract signing, signature compression, secure signatures in the strongest sense, as well as identity-based primitives. As far as possible, we avoid simplifying assumptions, such as the random oracle model. We believe that our techniques can be transferred to other application scenarios as well. Independently of the these results, we discuss the practical hardness of lattice problems and provide a framework for estimating the security of essentially all modern lattice-based cryptography.

Alternative Abstract:
Alternative AbstractLanguage
Nahezu die gesamte kryptographische Landschaft basiert heute auf der Unlösbarkeit zweier Probleme --- dem Faktorisierungsproblem und dem Problem diskrete Logarithmen zu berechnen. Diese Duokultur könnte im Falle neuartiger Angriffe rasch zum Kollaps ganzer Teilbereiche der modernen Kryptographie führen. Die konkrete Bedrohung durch Quantencomputer, beispielsweise mit Shor's Faktorisierungsalgorithmus (Shor 1997), ist hierbei nur ein Grund nach Alternativen zu suchen. Mit Gitterproblemen, wie dem Problem sehr kurze Gittervektoren zu finden, steht bereits eine gut erforschte Alternative zur Verfügung. Diese Probleme zeigen sich resistent gegenüber Quantencomputern und sie widerstehen, im Gegensatz zum Faktorisierungsproblem, subexponentiellen Algorithmen. In der Gitterkryptographie kann man auf sehr milde Annahmen zurückgreifen und damit außergewöhnlich starke Sicherheitsgarantien erzielen. Ajtais Entdeckung der unterliegenden komplexitätstheoretischen "worst-case to average-case" Reduktion (Ajtai 1996) besagt, dass eine zufällige Instanz bestimmter Gitterprobleme mindestens so schwer ist wie die schwierigste Instanz eines verwandten Problems. Mit den Arbeiten (Gentry, Peikert, Vaikuntanathan 2008), (Lyubashevsky, Micciancio 2008), (Lyubashevsky 2009) und (Cash, Hofheinz, Kiltz, Peikert 2009) zu Signaturverfahren stehen solide Grundbausteine zur Verfügung. Möchte man diese in Geschäftsprozessen nutzen, greifen sie jedoch häufig zu kurz. Oft sind hier Zusatzeigenschaften notwendig, um auf Signaturen Berechnungen ausführen zu können. Die vorliegende Dissertation zeigt die Vielseitigkeit von Gittern in der Kryptographie anhand ausgewählter Anwendungsszenarien auf. Mit den vorgestellten Verfahren unterstützt sie elektronische Wahlverfahren, Vertragsunterzeichnung über das Internet sowie die Signaturkompression. Des Weiteren werden Techniken zur Erfüllung des stärksten Sicherheitsmodells für Signaturverfahren ohne vereinfachende Annahmen, wie Random Oracles, vorgestellt und diskutiert, wie sich identitätsbasierte Primitive verwirklichen lassen. Es ist zu erwarten, dass sich die vorgestellten Techniken verallgemeinern und auf andere Anwendungsbereiche übertragen lassen. Unabhängig davon wird die praktische Schwierigkeit der relevanten Gitterprobleme untersucht. Dies ermöglicht die Bewertung und Auswahl sicherer Parametersätze für die gesamte moderne Gitterkryptographie.German
Uncontrolled Keywords: Lattice-based Cryptography, Blind Signatures, Verifiably Encrypted Signatures, Cryptanalysis, Digital Signatures, Identity-based Cryptography
Alternative keywords:
Alternative keywordsLanguage
Lattice-based Cryptography, Blind Signatures, Verifiably Encrypted Signatures, Cryptanalysis, Digital Signatures, Identity-based CryptographyEnglish
Classification DDC: 000 Allgemeines, Informatik, Informationswissenschaft > 004 Informatik
500 Naturwissenschaften und Mathematik > 510 Mathematik
Divisions: Fachbereich Informatik > Theoretische Informatik - Kryptographie und Computeralgebra
Date Deposited: 17 Jan 2011 10:36
Last Modified: 07 Dec 2012 11:59
Related URLs:
URN: urn:nbn:de:tuda-tuprints-23939
License: Creative Commons: Attribution-Noncommercial-No Derivative Works 3.0
Referees: Buchmann, Prof. Dr. Johannes and Micciancio, Prof. Dr. Daniele
Refereed: 20 December 2010
URI: http://tuprints.ulb.tu-darmstadt.de/id/eprint/2393
Export:

Actions (login required)

View Item View Item