TU Darmstadt / ULB / TUprints

Quantum Security of Cryptographic Primitives

Gagliardoni, Tommaso (2017)
Quantum Security of Cryptographic Primitives.
Technische Universität Darmstadt
Ph.D. Thesis, Primary publication

[img]
Preview
Text
PhD thesis Tommaso Gagliardoni.pdf
Copyright Information: CC BY-NC-ND 4.0 International - Creative Commons, Attribution NonCommercial, NoDerivs.

Download (1MB) | Preview
Item Type: Ph.D. Thesis
Type of entry: Primary publication
Title: Quantum Security of Cryptographic Primitives
Language: English
Referees: Fischlin, Prof. Dr. Marc ; Schaffner, Prof. Dr. Christian
Date: 21 February 2017
Place of Publication: Darmstadt
Date of oral examination: 25 January 2017
Abstract:

We call quantum security the area of IT security dealing with scenarios where one or more parties have access to quantum hardware. This encompasses both the fields of post-quantum cryptography (that is, traditional cryptography engineered to be resistant against quantum adversaries), and quantum cryptography (that is, security protocols designed to be natively run on a quantum infrastructure, such as quantum key distribution). Moreover, there exist also hybrid models, where traditional cryptographic schemes are somehow `mixed' with quantum operations in certain scenarios. Even if a fully-fledged, scalable quantum computer has yet to be built, recent results and the pace of research in its realization call for attention, lest we suddenly find ourselves one day with an obsolete security infrastructure. For this reason, in the last two decades research in quantum security has experienced an exponential growth in interest and investments.

In this work, we propose the first systematic classification of quantum security scenarios, and for each of them we recall the main tools and results, as well as presenting new ones. We achieve this goal by identifying four distinct quantum security classes, or domains, each of them encompassing the security notions and constructions related to a particular scenario. We start with the class QS0, which is `classical cryptography' (meaning that no quantum scenario is considered), where we present some classical constructions and results as a preliminary step.

Regarding post-quantum cryptography, we introduce the class QS1, where we discuss in detail the problems arising when designing a classical cryptographic object meant to be resistant against adversaries with local quantum computing power, and we provide a classification of the possible quantum security reductions in this scenario when considering provable security. Moreover, we present results about the quantum security and insecurity of the Fiat-Shamir transformation (a useful tool used to turn interactive identification schemes into digital signatures), and ORAMs (protocols used to outsource a database in a private way).

In respect to hybrid classical-quantum models, in the security class QS2 we discuss in detail the possible scenarios where these scenarios arise, and what a correct formalization should be in terms of quantum oracle access. We also provide a novel framework for the quantum security (both in terms of indistinguishability and semantic security) of secret-key encryption schemes, and we give explicit secure constructions, as well as impossibility results.

Finally, in the class QS3 we consider all those cryptographic constructions designed to run natively on quantum hardware. We give constructions for quantum encryption schemes (both in the secret- and public-key scenario), and we introduce transformations for obtaining such schemes by conceptually simpler schemes from the class QS2. Moreover, we introduce a quantum version of ORAM, called quantum ORAM (QORAM), aimed at outsourcing in a private way a database composed of quantum data. In proposing a suitable security model and an explicit construction for QORAMs, we also introduce a technique of independent interest which models a quantum adversary able to extract information from a quantum system without disturbing it `too much'.

We believe that the framework we introduce in this work will be a valuable tool for the scientific community in addressing the challenges arising when formalizing sound constructions and notions of security in the quantum world.

Alternative Abstract:
Alternative AbstractLanguage

In dieser Arbeit bezeichnen wir mit der Terminologie Quantensicherheit den Bereich der IT-Sicherheit welcher sich mit dem Anwendungsfall beschäftigt, in dem einer oder mehrere Teilnehmer Zugriff auf Quanten-Hardware haben. Dies umfasst sowohl den Bereich der Post-Quanten Kryptographie (d.h. klassische Kryptographie, welche resistent gegen Quantenangreifern ist), als auch die Quantenkryptographie (dies sind Sicherheitsprotokolle, welche so gestaltet sind, dass sie nativ auf Quanteninfrastrukturen operieren, z.B. Quantenschlüsselverteilung). Weiterhin werden sogenannte Hybridmodelle erfasst, in welchen traditionelle kryptographische Verfahren zu einem gewissen Grade mit Quantenoperationen `gemischt’ sind. Obwohl ein voll ausgereifter, skalierbarer Quantencomputer noch gebaut werden muss, zeigen aktuelle Resultate und das rasante Bestreben nach dessen Realisierung, dass man auf den Ernstfall vorbereitet sein sollte, um zu vermeiden sich eines Tages in einer überholten Sicherheitsinfrastruktur wiederzufinden. Dies begründet auch das in den letzten zwei Jahrzehnten exponentiell gestiegene Interesse und Investment in Forschung zum Thema Quantensicherheit.

In dieser Arbeit präsentieren wir die erste systematische Klassifikation von Quantensicherheitsszenarien. Für jede Klasse werden die wichtigsten Resultate und Techniken studiert und durch neue Resultate und Techniken ergänzt. Die Klassifizierung erfolgt durch die Identifikation von vier unterschiedlichen Quantensicherheitsklassen oder Domänen, wobei sich jeder Klasse eigene Sicherheitsmodelle und Konstruktionen für ein bestimmtes Szenario zuordnen lassen. Die Klassifizierung beginnt mit der Klasse QS0, welcher klassische kryptographische Szenarien zugeordnet werden und insbesondere keine Quantenszenarien enthalten sind. Für diese Klasse werden einleitend einige klassische Konstruktionen und Resultate präsentiert.

Für Post-Quanten Kryptographie werden natürliche Probleme betrachtet die entstehen, wenn ein klassisches kryptographisches Objekt resistent gegen einen Angreifer sein soll, welcher mit der Fähigkeit eines Quantencomputers ausgestattet ist. Solche Probleme werden durch die Klasse QS1 klassifiziert. Weiter klassifizieren wir an dieser Stelle mögliche Quantensicherheitsreduktionen im Kontext der Sicherheitsanalyse bei Problemen aus dieser Klasse. Zudem werden auch die Quantensicherheit und -unsicherheit der Fiat-Shamir Transformation (diese ist ein hilfreiches Verfahren um interaktive Identifikationsverfahren in digitale Signaturen zu transformieren) betrachtet, sowie ORAMs (welches ein Protokoll ist um private Daten einer Datenbank auszulagern).

Die Klasse QS2 beinhaltet Szenarien, welche dem Hybridmodel zuzuordnen sind. Wir diskutieren im Detail sowohl welche konkreten Szenarien diesem Modell zugeordnet werden können, als auch deren Formalisierung bezüglich eines Quanten-Orakel Zugriffs. Weiter wird ein neues Rahmenmodell für Quantensicherheit von symmetrischen Verschlüsselungsverfahren (sowohl im Sinne von semantischer Sicherheit als auch Ununterscheidbarkeit) eingeführt. Es werden sowohl konkrete sichere Konstruktionen als auch Unmöglichkeitsresultate präsentiert.

Letztlich benennen wir die Klasse QS3, welche kryptographische Konstruktionen umfasst, die in natürlicher Weise auf Quantenhardware laufen. Einerseits werden Konstruktionen für Quantenverschlüsselungsverfahren (sowohl ein symmetrisches als auch asymmetrisches Verfahren) präsentiert, andererseits auch Transformationen um solche Verfahren aus konzeptionell einfacheren Verfahren der Hybridklasse QS2 zu konstruieren. Des Weiteren wird eine quantenbasierte Version von ORAM, genannt Quanten-ORAM (oder, QORAM), eingeführt, welches es erlaubt private Datensätze einer Datenbank bestehend aus Quantendaten auszulagern. Im Zuge der Formalisierung eines geeigneten Sicherheitsmodells und einer expliziten Konstruktion für QORAMs werden eigenständige Techniken entwickelt, die es erlauben einen Quantenangreifer zu formalisieren welcher Informationen aus dem Quantensystem extrahieren kann ohne es `zu viel’ zu stören.

Wir glauben, dass die in dieser Arbeit eingeführten Formalisierungen und Klassifikation wertvolle und brauchbare Werkzeuge für die Wissenschaftsgemeinschaft bieten, um zukünftige Konstruktionen und Quantensicherheitsmodelle zu formalisieren.

German
URN: urn:nbn:de:tuda-tuprints-60195
Classification DDC: 000 Generalities, computers, information > 004 Computer science
500 Science and mathematics > 510 Mathematics
500 Science and mathematics > 530 Physics
Divisions: 20 Department of Computer Science > Cryptography and Complexity Theory
Date Deposited: 23 Feb 2017 13:46
Last Modified: 23 Feb 2017 13:46
URI: https://tuprints.ulb.tu-darmstadt.de/id/eprint/6019
PPN: 399963537
Export:
Actions (login required)
View Item View Item