The hardness of the lattice isomorphism problem (LIP) is a new lattice-based assumption used in asymmetric cryptography.However, there is yet to be a standard-model IND-CCA2secure public-key encryption scheme based on LIP.One promising candidate for such a scheme is the combination of an existing LIP-based IND-CPA-secure key encapsulation mechanism (KEM) by Ducas and van Woerden with the 𝑘-repetition framework by Rosen and Segev to construct an IND-CCA2-secure KEM.In this thesis, we provide strong evidence for our claim that this combination cannot be securely realized due to inherent qualities of LIP that prevent correlation across multiple ciphertexts of the KEM with independent public keys.We dub the sum of these qualities the Lattice Incompatibility Problem.Our analysis is extensive and provides insight into several fundamental properties of average-case LIP instances and their coefficient vectors.Additionally, we establish formal requirements for any other combination of an IND-CPA-secure asymmetric encryption scheme with 𝑘-repetition and demonstrate that this combination cannot be black-box for arbitrary IND-CPA-secure schemes.As part of our empirical evaluations, we also present a description, proof of correctness, and implementation of a sampling algorithm for the discrete Gaussian distribution on arbitrary quadratic forms that avoids taking the Cholesky decomposition for improved numerical stability.i Zusammenfassung Die Schwierigkeit des Gitterisomorphismusproblems (LIP) wird als neue gitterbasierte Annahme zur Konstruktion von asymmetrischer Kryptographie genutzt.Jedoch gibt es bis jetzt noch kein gegen adaptive aktive Angreifer sicheres asymmetrisches Verschlüsselungsverfahren, das auf der Schwierigkeit von LIP beruht.Ein möglicher Kandidat für ein solches Verfahren entsteht durch die Kombination aus einem existierenden LIP-basierten Schlüsselenkapsulierungsmechanismus (KEM) von Ducas und Woerden zusammen mit dem 𝑘-Wiederholungs-Rahmenwerk von Rosen und Segev, die zu einem entsprechend gegen solche Angreifer sicherem KEM führen könnte.In dieser Arbeit präsentieren wir starke Argumente dafür, dass diese Kombination durch inhärente Merkmale von LIP, die eine Korrelation über mehrere Chiffrate des KEMs mit unabhängigen öffentlichen Schlüsseln verhindern, nicht auf sichere Art realisierbar ist.Wir bezeichnen die Summe dieser Eigenschaften als das Gitterinkompatibilitätsproblem.Unsere Analyse ist umfänglich und zeigt einige grundlegende Eigenschaften durchschnittlicher LIP-Instanzen und ihrer Koeffizientenvektoren auf.Zusätzlich geben wir formale Anforderungen an, die für jede Kombination eines gegen passive Angreifer sicheren asymmetrischen Verschlüsselungsverfahrens mit der 𝑘-Wiederholung erforderlich sind.Wir demonstrieren zudem, dass diese Kombination nicht generisch für beliebige Verfahren umgesetzt werden kann.Weiter stellen wir als Teil unserer empirischen Evaluationen einen Algorithmus samt Beschreibung, Korrektheitsbeweis und Implementierung vor, der Stichproben der diskreten Gauß-Verteilung über beliebigen quadratischen Formen zieht, ohne dabei die Cholesky-Zerlegung der Form zu ermitteln, was zu verbesserter numerischer Stabilität führt.
The hardness of the lattice isomorphism problem (LIP) is a new lattice-based assumption used in asymmetric cryptography.However, there is yet to be a standard-model IND-CCA2secure public-key encryption scheme based on LIP.One promising candidate for such a scheme is the combination of an existing LIP-based IND-CPA-secure key encapsulation mechanism (KEM) by Ducas and van Woerden with the 𝑘-repetition framework by Rosen and Segev to construct an IND-CCA2-secure KEM.In this thesis, we provide strong evidence for our claim that this combination cannot be securely realized due to inherent qualities of LIP that prevent correlation across multiple ciphertexts of the KEM with independent public keys.We dub the sum of these qualities the Lattice Incompatibility Problem.Our analysis is extensive and provides insight into several fundamental properties of average-case LIP instances and their coefficient vectors.Additionally, we establish formal requirements for any other combination of an IND-CPA-secure asymmetric encryption scheme with 𝑘-repetition and demonstrate that this combination cannot be black-box for arbitrary IND-CPA-secure schemes.As part of our empirical evaluations, we also present a description, proof of correctness, and implementation of a sampling algorithm for the discrete Gaussian distribution on arbitrary quadratic forms that avoids taking the Cholesky decomposition for improved numerical stability.i Zusammenfassung Die Schwierigkeit des Gitterisomorphismusproblems (LIP) wird als neue gitterbasierte Annahme zur Konstruktion von asymmetrischer Kryptographie genutzt.Jedoch gibt es bis jetzt noch kein gegen adaptive aktive Angreifer sicheres asymmetrisches Verschlüsselungsverfahren, das auf der Schwierigkeit von LIP beruht.Ein möglicher Kandidat für ein solches Verfahren entsteht durch die Kombination aus einem existierenden LIP-basierten Schlüsselenkapsulierungsmechanismus (KEM) von Ducas und Woerden zusammen mit dem 𝑘-Wiederholungs-Rahmenwerk von Rosen und Segev, die zu einem entsprechend gegen solche Angreifer sicherem KEM führen könnte.In dieser Arbeit präsentieren wir starke Argumente dafür, dass diese Kombination durch inhärente Merkmale von LIP, die eine Korrelation über mehrere Chiffrate des KEMs mit unabhängigen öffentlichen Schlüsseln verhindern, nicht auf sichere Art realisierbar ist.Wir bezeichnen die Summe dieser Eigenschaften als das Gitterinkompatibilitätsproblem.Unsere Analyse ist umfänglich und zeigt einige grundlegende Eigenschaften durchschnittlicher LIP-Instanzen und ihrer Koeffizientenvektoren auf.Zusätzlich geben wir formale Anforderungen an, die für jede Kombination eines gegen passive Angreifer sicheren asymmetrischen Verschlüsselungsverfahrens mit der 𝑘-Wiederholung erforderlich sind.Wir demonstrieren zudem, dass diese Kombination nicht generisch für beliebige Verfahren umgesetzt werden kann.Weiter stellen wir als Teil unserer empirischen Evaluationen einen Algorithmus samt Beschreibung, Korrektheitsbeweis und Implementierung vor, der Stichproben der diskreten Gauß-Verteilung über beliebigen quadratischen Formen zieht, ohne dabei die Cholesky-Zerlegung der Form zu ermitteln, was zu verbesserter numerischer Stabilität führt.
In dieser Arbeit präsentieren wir einen Ansatz, mit dem die Sicherheit von Protokollen für multi-party-computations (MPC) verbessert werden kann. Dafür gehen wir davon aus, dass Protokollteilnehmer aus mehreren Geräten mit unterschiedlicher Zusammensetzung von Hardware, Software und Betriebssystemen bestehen. Dies wird als diverse Redundanz bezeichnet. Dazu wird die Annahme getroffen, dass redundante Geräte aufgrund ihres unterschiedlichen Aufbaus nicht alle gleichzeitig korrumpiert werden können. Auf dieser Basis konstruieren wir ein MPC Protokoll, das sicher bleibt, selbst wenn die letzte ehrlich Partei teilweise korrumpiert wird. Um die Annahme formal zu beschreiben, schlagen wir ein Korruptionsmodell vor, das zwei unterschiedliche Typen von Korruptionen vorsieht. Um Angriffe über physikalischen Zugriff auf Geräte zu beschreiben, wird der übliche aktive Angriff benutzt. Angriffe über das Netzwerk werden jedoch eingeschränkt, um zu modellieren, dass solche Angriffe auf vorhandene Sicherheitslücken angewiesen sind. Wenn Systeme in diverser Redundanz vorliegen, ist es unwahrscheinlich, dass sie alle zur selben Zeit Sicherheitslücken aufweisen. Dieser Ansatz wird in der praktischen IT-Sicherheit bereits eingesetzt, wurde, so weit wir wissen, aber noch nicht verwendet, um formale Sicherheitsgarantien zu geben. Viele kryptographische Protokolle machen (implizit) die Annahme, dass jede Partei aus nur einem physikalischen Gerät besteht. Deshalb wird eine Partei dann entweder vollständig korrumpiert oder bleibt komplett ehrlich. Deshalb ist es für unsere Zwecke notwendig, Parteien in mehrere Geräte aufzuteilen. Diese Geräte führen dann ein Protokoll aus, mit dem eine ganze Partei realisiert wird. Um wichtige Stellen zu schützen, an denen die ganze Partei auf einmal korrumpiert werden könnte, setzen wir das MPC Protokoll SPDZ [Dam+13] ein. Hier nutzen wir aus, dass SPDZ nur innerhalb einer Partei eingesetzt wird. Hier vertrauen sich die Geräte, zumindest zu Beginn, bevor Korruptionen stattfinden können. Dieses initiale Vertrauen erlaubt es, den aufwändigsten Teil von SPDZ, die Vorverarbeitungsphase, zu überspringen. Dieser Ansatz verursacht linearen zusätzlichen Aufwand im Vergleich zu herkömmlichen Protokollen. Dafür wird sichergestellt, dass Parteien, die bis zu einem Viertel ihrer Geräte aufgrund von Korruptionen verlieren, weiter als ehrliche Parteien am Protokoll teilnehmen können. Außerdem bleibt ihre Ein- und Ausgabe geheim.
Recent developments have been made in the construction of cryptosystems with security based on the hardness of the lattice isomorphism problem (LIP). Due to lattice conjectures, one may expect in the future that breaking such schemes is computationally harder than most current lattice-based cryptosystems. To the best of our knowledge, there have not been any attempts to concretely instantiate a key encapsulation mechanism (KEM) based on LIP. In this work, we propose the first instance of such a KEM, following the framework of Ducas and van Woerden (EUROCRYPT 2022), using simple lattices. We present a randomness extractor derived from a hash function based on the short integer solution problem; define a concrete set of parameters for instantiating the scheme; provide a rigorous security estimation of an attacker trying to decode an encapsulated key through reductions to hard lattice problems; and use well-known methods to convert the IND-CPA secure KEM into an IND-CCA2 secure KEM, comparing the latter with other modern lattice-based KEMs. The resulting security is estimated under the assumption that an adversary cannot efficiently solve related instances of LIP, which is a consequence of the lack of cryptanalysis towards identifying isomorphism between lattices.
The Lattice Isomorphism Problem (LIP) is an emerging foundation for post-quantum cryptography thanks to the pioneering work of Ducas and van Woerden (EUROCRYPT '22). That work lays the foundation for LIP in cryptography with a zero-knowledge proof of knowledge (ZKPoK), a key-encapsulation mechanism, and a digital signature scheme which is further developed into the efficient signature Hawk (ASIACRYPT '22) using structured lattices. However, as compared to the development of lattice-based cryptography from the Short Integer Solution (SIS) and Learning with Errors (LWE) problems, LIP-based cryptography is yet to cover a rich variety of functionalities beyond the two basic ones: encrypting and digitally signing messages. This work is an effort to extend the landscape of LIP-based cryptography from the above basic primitives to more advanced ones by adapting techniques used in SIS-based and LWE-based primitives to LIP. We provide a public-key encryption (PKE) which encrypts plaintexts of integral vectors, and it comes with a zero-knowledge proof of plaintext knowledge. We use this PKE as a commitment scheme in the construction of a ZKPoK for quadratic relations, so this ZKPoK has a straightline extractor naturally. Using the same ZKPoK in non-interactive mode by Fiat-Shamir transformation, we introduce the first LIP-based blind signature scheme which is the blinded version of the digital signatures of Ducas and van Woerden. The security of our scheme stems from a new one-more Close Vector Problem (omCVP) assumption. This assumption is arguably an analogue of the one-more-SIS assumption by Agrawal et al. (CCS '22) and the one-more Short Vector Problem in Hawk signatures. To ensure confidence in omCVP, we provide a cryptanalysis attempt and convince that our parameter choice is in the safe zone.
Privatsphärebewahrende authentifizierte Schlüsselaustauschverfahren (PPAKE, von engl. Privacy Preserving Authenticated Key Exchange) sind AKE (engl. Authenticated Key Exchange) Protkolle, die so konzipiert werden, dass sie die Identität der beiden Kommunikationspartner vor Dritten geheim halten. PPAKE Protokolle wurden bereits in der Vergangenheit betrachtet. In diesem Werk möchten wir die bestehenden formalen Privatsphäreeigenschaften solcher Protokolle stärken. Der wichtigste Zusatz ist, dass wir auch Angreifer betrachten, die den Protokollablauf nicht korrekt beenden (z.B. weil sie sich nicht authentifizieren können). Auch derartige Angriffe sind relevant, da es dem Angreifer möglicherweise egal ist, ob der Protkollablauf abgebrochen wird, nachdem er die Identität seines Zieles herausgefunden hat. Zusätzlich präsentieren wir ein formales Modell das diese Eigenschaften abbildet und mehrere Protkolle, die unterschiedlich starke Privatsphärebewahrungseigenschaften erfüllen. Eines davon ist eine genersiche Konstruktion aus generischen kryptografischen Grundbausteinen und kann daher auf eine Art instanziiert werden, von der angenommen wird dass sie selbst gegen zukünftige Quantencomputer sicher ist. Zudem präsentieren wir formale Beweise aller Protokolle in dem von uns eingeführten Modell. Der zweite Teil dieser Masterarbeit behandelt die automatische Verifikation der Privatsphäreeigenschaften des wichtigsten Protokolls aus dem ersten Teil. Automatische Verifikation wird verwendet, um entweder einen Angriff gegen ein Protokoll zu finden, oder festzustellen dass die angegebenen Eigenschaften tatsächlich erüllt sind. Dadurch wird die Wahrscheinlichkeit, in den von Menschenhand geschriebenen Beweisen einen Fehler gemacht zu haben, minimiert. Als erstes untersuchten wir die automatische Verifikationssoftware “Tamarin Prover”, die jedoch, bevor der zugeteilte Arbeitsspeicher von ca. 60 GB aufgebraucht war, zu keinem Ergebnis führte (weder einem Beweis noch einem Angriff). Daher nutzten wir stattdessen die Verifikationssoftware ProVerif und konnten die gewünschten Eigenschaften erfolgreich beweisen. In diesem Werk präsentieren wir sowohl unsere Tamarin- als auch unsere ProVerif-Formulierung.
Identity-based encryption with equality test (IBEET) is a variant of identity-based encryption (IBE), in which any user with trapdoors can check whether two ciphertexts are encryption of the same plaintext. Although several lattice-based IBEET schemes have been proposed, they have drawbacks in either security or efficiency. Specifically, most IBEET schemes only satisfy selective security, while public keys of adaptively secure schemes in the standard model consist of matrices whose numbers are linear in the security parameter. In other words, known lattice-based IBEET schemes perform poorly compared to the state-of-the-art lattice-based IBE schemes (without equality test). In this paper, we propose a semi-generic construction of CCA-secure lattice-based IBEET from a certain class of lattice-based IBE schemes. As a result, we obtain the first lattice-based IBEET schemes with adaptive security and CCA security in the standard model without sacrificing efficiency. This is because, our semi-generic construction can use several state-of-the-art lattice-based IBE schemes as underlying schemes, e.g. Yamada's IBE scheme (CRYPTO'17).
Moderne Kryptographie erlaubt nicht nur, personenbezogene Daten im Internet zu schützen oder sich für bestimmte Dienste zu authentifizieren, sondern ermöglicht auch das Auswerten einer Funktion auf geheimen Eingaben mehrerer Parteien, ohne dass dabei etwas über diese Eingaben gelernt werden kann (mit der Ausnahme von Informationen, die aus der Ausgabe und eigenen Eingaben effizient abgeleitet werden können). Kryptographische Protokolle dieser Art werden sichere Mehrparteienberechnung genannt und eignen sich für ein breites Anwendungsspektrum, wie z.B. geheime Abstimmungen und Auktionen. Um die Sicherheit solcher Protokolle zu beweisen, werden Annahmen benötigt, die oft komplexitätstheoretischer Natur sind, beispielsweise, dass es schwierig ist, hinreichend große Zahlen zu faktorisieren. Sicherheitsannahmen, die auf physikalischen Prinzipien basieren, bieten im Gegensatz zu komplexitätstheoretischen Annahmen jedoch einige Vorteile: die Protokolle sind meist konzeptionell einfacher, die Sicherheit ist unabhängig von den Berechnungskapazitäten des Angreifers, und die Funktionsweise und Sicherheit ist oft für den Menschen leichter nachvollziehbar. (Zum Beispiel forderte das Bundesverfassungsgericht: „Beim Einsatz elektronischer Wahlgeräte müssen die wesentlichen Schritte der Wahlhandlung und der Ergebnisermittlung vom Bürger zuverlässig und ohne besondere Sachkenntnis überprüft werden können.“ (BVerfG, Urteil des Zweiten Senats vom 03. März 2009)). Beispiele für solche Annahmen sind physikalisch getrennte oder unkorrumpierbare Hardware-Komponenten (vgl. Broadnax et al., 2018), Write-Only-Geräte für Logging, oder frei zu rubbelnde Felder, wie man sie von PIN-Briefen kennt. Auch die aus der Quantentheorie folgende Nicht-Duplizierbarkeit von Quantenzuständen ist eine physikalische Sicherheitsannahme, die z.B. verwendet wird, um nicht-klonbares „Quantengeld“ zu realisieren. In der vorliegenden Dissertation geht es neben Protokollen, die die Sicherheit und Isolation bestimmter einfacher Hardware-Komponenten als Vertrauensanker verwenden, im Besonderen um kryptographischen Protokolle für die sichere Mehrparteienberechnung, die mit Hilfe physikalischer Spielkarten durchgeführt werden. Die Sicherheitsannahme besteht darin, dass die Karten ununterscheidbare Rückseiten haben und, dass bestimmte Mischoperationen sicher durchgeführt werden können. Eine Anwendung dieser Protokolle liegt also in der Veranschaulichung von Kryptographie und in der Ermöglichung sicherer Mehrparteienberechnungen, die gänzlich ohne Computer ausgeführt werden können. Ein Ziel in diesem Bereich der Kryptographie ist es, Protokolle anzugeben, die möglichst wenige Karten benötigen – und sie als optimal in diesem Sinne zu beweisen. Abhängig von Anforderungen an das Laufzeitverhalten (endliche vs. lediglich im Erwartungswert endliche Laufzeit) und an die Praktikabilität der eingesetzten Mischoperationen, ergeben sich unterschiedliche untere Schranken für die mindestens benötigte Kartenanzahl. Im Rahmen der Arbeit wird für jede Kombination dieser Anforderungen ein UND-Protokoll – ein logisches UND zweier in Karten codierter Bits; dieses ist zusammen mit der Negation und dem Kopieren von Bits hinreichend für die Realisierung allgemeiner Schaltkreise – konstruiert oder in der Literatur identifiziert, das mit der minimalen Anzahl an Karten auskommt, und dies auch als Karten-minimal bewiesen. Insgesamt ist UND mit vier (für erwartet endliche Laufzeit (Koch, Walzer und Härtel, 2015; Koch, 2018)), fünf (für praktikable Mischoperationen oder endliche Laufzeit (Koch, Walzer und Härtel, 2015; Koch, 2018)) oder sechs Karten (für endliche Laufzeit und gleichzeitig praktikable Mischoperationen (Kastner et al., 2017)) möglich und optimal. Für die notwendigen Struktureinsichten wurden so-genannte „Zustandsdiagramme“ mit zugehörigen Kalkülregeln entwickelt, die eine graphenbasierte Darstellung aller möglichen Protokolldurchläufe darstellen und an denen Korrektheit und Sicherheit der Protokolle direkt ablesbar sind (Koch, Walzer und Härtel, 2015; Kastner et al., 2017). Dieser Kalkül hat seitdem eine breite Verwendung in der bereichsrelevanten Literatur gefunden. (Beweise für untere Schranken bzgl. der Kartenanzahl werden durch den Kalkül zu Beweisen, die zeigen, dass bestimmte Protokollzustände in einer bestimmten kombinatorischen Graphenstruktur nicht erreichbar sind.) Mit Hilfe des Kalküls wurden Begriffe der Spielkartenkryptographie als C-Programm formalisiert und (unter bestimmten Einschränkungen) mit einem „Software Bounded Model Checking“-Ansatz die Längenminimalität eines kartenminimalen UND-Protokolls bewiesen (Koch, Schrempp und Kirsten, 2019). Darüber hinaus werden konzeptionell einfache Protokolle für den Fall einer sicheren Mehrparteienberechnung angegeben, bei der sogar zusätzlich die zu berechnende Funktion geheim bleiben soll (Koch und Walzer, 2018), und zwar für jedes der folgenden Berechnungsmodelle: (universelle) Schaltkreise, binäre Entscheidungsdiagramme, Turingmaschinen und RAM-Maschinen. Es wird zudem untersucht, wie Karten-basierte Protokolle so ausgeführt werden können, dass die einzige Interaktion darin besteht, dass andere Parteien die korrekte Ausführung überwachen. Dies ermöglicht eine (schwach interaktive) Programm-Obfuszierung, bei der eine Partei ein durch Karten codiertes Programm auf eigenen Eingaben ausführen kann, ohne etwas über dessen interne Funktionsweise zu lernen, das über das Ein-/Ausgabeverhalten hinaus geht. Dies ist ohne derartige physikalische Annahmen i.A. nicht möglich. Zusätzlich wird eine Sicherheit gegen Angreifer, die auch vom Protokoll abweichen dürfen, formalisiert und es wird eine Methode angegeben um unter möglichst schwachen Sicherheitsannahmen ein passiv sicheres Protokoll mechanisch in ein aktiv sicheres zu transformieren (Koch und Walzer, 2017). Eine weitere, in der Dissertation untersuchte physikalische Sicherheitsannahme, ist die Annahme primitiver, unkorrumpierbarer Hardware-Bausteine, wie z.B. einen TAN-Generator. Dies ermöglicht z.B. eine sichere Authentifikation des menschlichen Nutzers über ein korrumpiertes Terminal, ohne dass der Nutzer selbst kryptographische Berechnungen durchführen muss (z.B. große Primzahlen zu multiplizieren). Dies wird am Beispiel des Geldabhebens an einem korrumpierten Geldautomaten mit Hilfe eines als sicher angenommenen zweiten Geräts (Achenbach et al., 2019) und mit möglichst schwachen Anforderungen an die vorhandenen Kommunikationskanäle gelöst. Da das angegebene Protokoll auch sicher ist, wenn es beliebig mit anderen gleichzeitig laufenden Protokollen ausgeführt wird (also sogenannte Universelle Komponierbarkeit aufweist), es modular entworfen wurde, und die Sicherheitsannahme glaubwürdig ist, ist die Funktionsweise für den Menschen transparent und nachvollziehbar. Insgesamt bildet die Arbeit durch die verschiedenen Karten-basierten Protokolle, Kalküle und systematisierten Beweise für untere Schranken bzgl. der Kartenanzahl, sowie durch Ergebnisse zur sicheren Verwendung eines nicht-vertrauenswürdigen Terminals, und einer Einordnung dieser in eine systematische Darstellung der verschiedenen, in der Kryptographie verwendeten physikalischen Annahmen, einen wesentlichen Beitrag zur physikalisch-basierten Kryptographie.