TU Darmstadt / ULB / TUbiblio

Lattice-based Signature Schemes with Additional Features

Rückert, Markus (2011)
Lattice-based Signature Schemes with Additional Features.
Technische Universität Darmstadt
Dissertation, Erstveröffentlichung

Kurzbeschreibung (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.

Typ des Eintrags: Dissertation
Erschienen: 2011
Autor(en): Rückert, Markus
Art des Eintrags: Erstveröffentlichung
Titel: Lattice-based Signature Schemes with Additional Features
Sprache: Englisch
Referenten: Buchmann, Prof. Dr. Johannes ; Micciancio, Prof. Dr. Daniele
Publikationsjahr: 13 Januar 2011
Datum der mündlichen Prüfung: 20 Dezember 2010
URL / URN: urn:nbn:de:tuda-tuprints-23939
Zugehörige Links:
Kurzbeschreibung (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.

Alternatives oder übersetztes Abstract:
Alternatives AbstractSprache

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.

Deutsch
Freie Schlagworte: Lattice-based Cryptography, Blind Signatures, Verifiably Encrypted Signatures, Cryptanalysis, Digital Signatures, Identity-based Cryptography
Sachgruppe der Dewey Dezimalklassifikatin (DDC): 000 Allgemeines, Informatik, Informationswissenschaft > 004 Informatik
500 Naturwissenschaften und Mathematik > 510 Mathematik
Fachbereich(e)/-gebiet(e): 20 Fachbereich Informatik > Theoretische Informatik - Kryptographie und Computeralgebra
20 Fachbereich Informatik
Hinterlegungsdatum: 17 Jan 2011 10:36
Letzte Änderung: 05 Mär 2013 09:44
PPN:
Referenten: Buchmann, Prof. Dr. Johannes ; Micciancio, Prof. Dr. Daniele
Datum der mündlichen Prüfung / Verteidigung / mdl. Prüfung: 20 Dezember 2010
Zugehörige Links:
Export:
Suche nach Titel in: TUfind oder in Google
Frage zum Eintrag Frage zum Eintrag

Optionen (nur für Redakteure)
Redaktionelle Details anzeigen Redaktionelle Details anzeigen