This paper summarizes the current knowledge in the field of two-party cryptographic protocols devised from quantum systems. We introduce the reader to the notion of cryptographic protocols and describe a number of simple building blocks to achieve them. We also give pointers for the reader who is interested to the quantum implementation of these building blocks. 1 Introduction Since the 1970's the science of secret writing, cryptography, has changed substantially due to the introduction of "public key cryptosystems" [26, 41]. The many properties of certain instances of these systems have open the door to several new applications (consult [42, 25, 29, 44, 34, 28, 7, 30, 36, 32, 11, 19, 33] for instance, to mention just a few). The initial goal of cryptography, to provide secure communications, has evolved into a variety of tasks involving secret data. The scenario in which such tasks take place involves two participants (say Alice and Bob) who wish to perform some computation involving ...
This paper summarizes the current knowledge in the field of two-party cryptographic protocols devised from quantum systems. We introduce the reader to the notion of cryptographic protocols and describe a number of simple building blocks to achieve them. We also give pointers for the reader who is interested to the quantum implementation of these building blocks. 1 Introduction Since the 1970's the science of secret writing, cryptography, has changed substantially due to the introduction of "public key cryptosystems" [26, 41]. The many properties of certain instances of these systems have open the door to several new applications (consult [42, 25, 29, 44, 34, 28, 7, 30, 36, 32, 11, 19, 33] for instance, to mention just a few). The initial goal of cryptography, to provide secure communications, has evolved into a variety of tasks involving secret data. The scenario in which such tasks take place involves two participants (say Alice and Bob) who wish to perform some computation involving ...
Broadly speaking, cryptography is the problem of doing communication or computation involving two or more parties who may not trust one another. The best known cryptographic problem is the transmission of secret messages. Suppose wish to communicate in secret. For example, you may wish to give your credit card number to a merchant in exchange for goods, hopefully without any malevolent third party intercepting your credit card number. The way this is done is to use a cryptographic protocol. The most important distinction is between private key cryptosystems and public key cryptosystems.
Quantum cryptography lies at the intersection of information theory and quantum mechanics. Cryptosystems come in two major classes depending on whether the key is shared in public or in secret. Public key cryptosystems are special in that they allow two people, who have not yet met, to communicate securely by looking-up encryption methods in a public directory. In quantum cryptography, the sender and receiver have two types of communication channels: a classical public channel and a quantum channel. The best application of cryptography is to allow a secure communication. In the near future, quantum cryptography may be used in top-secret applications in the military, for example, as the basis of communication links. The first protocol for quantum cryptography was proposed in 1984 by C. H. Bennett and G. Brassard. Some of the basic quantum cryptographic systems are: four-states protocol, two-states protocol, 4+2 protocol and multi-photon and multi-stage protocol.
Quantum cryptography provides an ensemble of protocols, such as quantum key distribution [1-3], quantum random number generation [4], closed group digital signatures [5], long-term secure data storage [6] and multi-party secure computation [7], which are robust against future algorithmic and computational advances, including the emergence of quantum computers. This is because its security is information-theoretic, i.e., it can be proven based only on models of the local devices operated by legitimate users and does not require any assumptions on the resources available to an adversary [8-12]. Information-theoretic security will be important for data confidentiality in the future when we expect more powerful computers and new algorithms to be at the fingertips of our digital foes. Of particular concern is the advent of quantum computers that can be used to launch efficient attacks on conventional techniques, such as the widely-used forms of public key cryptography. Well before more powerful conventional and quantum computers become available, quantum cryptography will be important to protect against a generic vulnerability inherent to current cryptographic techniques based on computational complexity: encrypted data can be stored today and decrypted in the future, when suitable technology becomes available. This leads to the possibility of retrospectively breaking encryption keys established with computational techniques, such as the Diffie-Hellman key exchange algorithm. This becomes a serious threat if data confidentiality must be maintained for several years, especially as it is now feasible to store large volumes of information.Although the quantum cryptographic protocolsare information-theoretic secure, real systemsmay still possess side channels, i.e. security vulnerabilities, if their implementation deviates significantly from the idealised models used in the security analysis [12-15]. This is a common threat to any cryptosystem, irrespective of whether it is based on quantum theory [16-23] or computational complexity [24-28]. For example, timing attacks can threaten implementations of both quantum [16] and non-quantum [24] systems. Therefore, the security analysis of a cryptosystem’s implementation, for simplicity called “implementation security”, is anatural and important development in the evolution of all cryptographic technologies, including quantum cryptography.Since the security of quantum cryptography depends only on the legitimate users’ local equipment, the fundamental task in quantum cryptography implementation security is to estimate how much information such equipment leaks to a potential adversary. When this information leakage can be bounded below a certain value, security can be restored [29, 30] using a technique called privacy amplification[31, 32, 33]. This compresses a partially secret bit sequence into a highly secure key, with the amount of compression depending upon the estimated information leakage. Thus, by adequately characterising a real system, it is possible to restore the security promise of the theoretical protocol against technology available at the time that secret key is being created. It is a specific feature of quantum cryptography that this security statement does not change with future technological advances.Privacyamplification is not the only resource available to enforce the implementation security of quantum cryptography. Modifications to hardware and protocols can dramatically reduce the information leakage and the potential occurrence of side-channels and active attacks [34-38]. Moreover, quantum correlations can be used to test the hardware of a real system [39-40]. Such tests can be quite demanding to implement but have the advantage of immunity against a large class of implementation issues. The importance of analysing the implementation security of quantum cryptography is widely recognised and is a very active area of research. National metrology institutes, government organisations, universities and private companies fully acknowledge the importance of thissubject and are supporting its effective development. ETSI has established an Industry Specification Group (ISG) to coordinate these efforts and to set forward-looking standards in quantum cryptography implementation security [41]. These will guide security evaluation by qualified third parties, as part of a security certification of quantum cryptographic products.
This book offers an accessible and engaging introduction to quantum cryptography, assuming no prior knowledge in quantum computing. Essential background theory and mathematical techniques are introduced and applied in the analysis and design of quantum cryptographic protocols. The title explores several important applications such as quantum key distribution, quantum money, and delegated quantum computation, while also serving as a self-contained introduction to the field of quantum computing. With frequent illustrations and simple examples relevant to quantum cryptography, this title focuses on building intuition and challenges readers to understand the basis of cryptographic security. Frequent worked examples and mid-chapter exercises allow readers to extend their understanding, and in-text quizzes, end-of-chapter homework problems, and recommended further reading reinforce and broaden understanding. Online resources available to instructors include interactive computational problems in Julia, videos, lecture slides, and a fully worked solutions manual.
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.
This book offers an accessible and engaging introduction to quantum cryptography, assuming no prior knowledge in quantum computing. Essential background theory and mathematical techniques are introduced and applied in the analysis and design of quantum cryptographic protocols. The title explores several important applications such as quantum key distribution, quantum money, and delegated quantum computation, while also serving as a self-contained introduction to the field of quantum computing. With frequent illustrations and simple examples relevant to quantum cryptography, this title focuses on building intuition and challenges readers to understand the basis of cryptographic security. Frequent worked examples and mid-chapter exercises allow readers to extend their understanding, and in-text quizzes, end-of-chapter homework problems, and recommended further reading reinforce and broaden understanding. Online resources available to instructors include interactive computational problems in Julia, videos, lecture slides, and a fully worked solutions manual.