Detailansicht
A quantum-resistant zero-knowledge protocol for NP-complete
Rebecca Hofer
Art der Arbeit
Masterarbeit
Universität
Universität Wien
Fakultät
Fakultät für Physik
Studiumsbezeichnung bzw. Universitätlehrgang (ULG)
Masterstudium Physics
Betreuer*in
Philip Walther
Mitbetreuer*in
Mathieu Bozzio
DOI
10.25365/thesis.74497
URN
urn:nbn:at:at-ubw:1-14086.05466.269842-8
Link zu u:search
(Print-Exemplar eventuell in Bibliothek verfügbar)
Abstracts
Abstract
(Deutsch)
In den letzten Jahren wurden erhebliche Fortschritte auf dem Gebiet der Quantenkryptographie erzielt. So wurden Protokolle wie Quantum key distribution (QKD), Quantum money, oder Quantum coin flipping entwickelt und verbessert und ebenso in praktische Anwendungen umgesetzt. Klassische Kryptographie stüzt ihre Sicherheit in der Regel auf Annahmen zur schweren Lösbarkeit von mathematischen Problemen. Hier liegt auch der grundlegende Unterschied zu Quantenkryptografischen Protokollen: solche unbewiesenen mathematischen Annahmen sind nicht notwendig um die Sicherheit von Protokollen zu argumentieren, da diese auf Quantenmechanischen Prinzipien beruhen. Das BB84 Protokoll war eines der ersten das zeigen konnte, wie mit Quantenprinzipien informationstheoretische Sicherheit erreicht werden kann. Es ist jedoch auch allgemein bekannt, dass Quantenkryptographie ihre Grenzen hat. So wurde gezeigt dass es, ebenso wie bei den klassischen Gegenstücken, unmöglich ist, eine perfektes Quantum bit-commtiment Protokoll oder ein perfektes Quantum weak coin flipping Protokoll zu erstellen. Ein häufig alternativ gewählter Ansatz um trotzdem informationstheoretische Sicherheit erreichen zu können besteht darin, relativistische Einschränkungen in die Protokolle einzuführen, die zwar bestimmte No-Go-Theoreme umgehen, jedoch im Gegenzug erfordern, dass Sicherheit und Vertrauen in andere Aspekte oder Parteien im Protokoll angenommen werden. In dieser Arbeit werde ich ein Zero-Knowledge-Protokoll vorstellen, das weder relativistische Raum-Zeit-Einschränkungen noch Annahmen zur Berechnungsschwierigkeit von mathematischen Problemen erfordert. Stattdessen basiert das Protokoll auf einem commitment scheme das informations-theoretisch binding und quantum computationally hiding ist. Dies wird durch die Methode conjugate coding erreicht - ein häufig verwendetes Prinzip in der Quantenkryptographie, welche auch ein Kernbestandteil des BB84-Protokolls ist. Basierend auf dem commitment scheme ermöglicht unser Protokoll ein quantum-computationally secure zero-knowledge proof Protokoll für NP-complete Probleme. Während bereits erhebliche Forschung zu klassischen und quantenbasierten Zero-Knowledge-Beweisen durchgeführt wurde, war das primäre Ziel dieser Arbeit die Entwicklung eines sicheren, und vorallem praktisch umsetzbaren Protokolls, dass resilient ist gegenüber Angriffen von klassichen und Quantencomputern.
Abstract
(Englisch)
In recent years, considerable progress has been made in the quantum cryptography field in developing and enhancing protocols such as quantum key distribution, quantum money, or quantum coin flipping and in bringing these concepts into practical applications. In contrast to classical cryptography, where security is commonly argued based on computational hardness assumptions, these protocols aim to elevate security through quantum means. Quantum key distribution, in particular, is a foundational cornerstone in this field, illustrating how quantum principles can achieve information-theoretic security. However, it is well-recognized that quantum cryptography does have its limitations. Equally, achieving perfect bit commitment or weak coin flipping remains impossible, akin to their classical counterparts. A common alternative approach is introducing relativistic constraints into the protocols, which, while bypassing certain no-go theorems, necessitates establishing or assuming security and trust in other aspects or parties involved in the protocol. This thesis will outline a quantum version of a zero-knowledge proof protocol that does not rely on such relativistic constraints or classical computational hardness assumptions. Instead, it offers an information-theoretic secure binding and quantum-computationally hiding commitment scheme, achieved utilizing the method of conjugate coding — a core element of many quantum cryptographic protocols, such as the BB84 quantum key distribution protocol. Building on this quantum commitment scheme, our protocol provides a quantum-computationally secure zero-knowledge proof for NP-complete problems. While considerable research has already been conducted on classical and quantum zero-knowledge proofs, this work distinguishes itself by focusing on developing a theoretically sound, practically implementable, and robust protocol against classical and quantum attacks.
Schlagwörter
Schlagwörter
(Deutsch)
Null-Wissen-Beweis
Schlagwörter
(Englisch)
Zero-knowledge proof
Autor*innen
Rebecca Hofer
Haupttitel (Englisch)
A quantum-resistant zero-knowledge protocol for NP-complete
Paralleltitel (Deutsch)
Ein Quanten-resistentes Null-Wissen Protokoll für NP-complete
Publikationsjahr
2023
Umfangsangabe
viii, 65 Seiten
Sprache
Englisch
Beurteiler*in
Philip Walther
Klassifikation
33 Physik > 33.23 Quantenphysik
AC Nummer
AC16970377
Utheses ID
68626
Studienkennzahl
UA | 066 | 876 | |