Search

Quantum cryptography exploits principles of quantum physics for the secure processing of information. A prominent example is secure communication, i.e., the task of transmitting confidential messages from one location to another. The cryptographic requirement here is that the transmitted messages remain inaccessible to anyone other than the designated recipients, even if the communication channel is untrusted. In classical cryptography, this can usually only be guaranteed under computational hardness assumptions, e.g., that factoring large integers is infeasible. In contrast, the security of quantum cryptography relies entirely on the laws of quantum mechanics. Here we review this physical notion of security, focusing on quantum key distribution and secure communication., Comment: 63 pages, 34 figures. In submission to RMP. Partly based on arXiv:1409.3525. v2: new references and minor edits

Recent research in quantum cryptography has led to the development of schemes that encrypt and authenticate quantum messages with computational security. The security definitions used so far in the literature are asymptotic, game-based, and not known to be composable. We show how to define finite, composable, computational security for secure quantum message transmission. The new definitions do not involve any games or oracles, they are directly operational: a scheme is secure if it transforms an insecure channel and a shared key into an ideal secure channel from Alice to Bob, i.e., one which only allows Eve to block messages and learn their size, but not change them or read them. By modifying the ideal channel to provide Eve with more or less capabilities, one gets an array of different security notions. By design these transformations are composable, resulting in composable security. Crucially, the new definitions are finite. Security does not rely on the asymptotic hardness of a computational problem. Instead, one proves a finite reduction: if an adversary can distinguish the constructed (real) channel from the ideal one (for some fixed security parameters), then she can solve a finite instance of some computational problem. Such a finite statement is needed to make security claims about concrete implementations. We then prove that (slightly modified versions of) protocols proposed in the literature satisfy these composable definitions. And finally, we study the relations between some game-based definitions and our composable ones. In particular, we look at notions of quantum authenticated encryption and QCCA2, and show that they suffer from the same issues as their classical counterparts: they exclude certain protocols which are arguably secure., Comment: 43+11 pages, 18 figures, v2: minor changes, extended version of the published paper

Relativistic protocols have been proposed to overcome some impossibility results in classical and quantum cryptography. In such a setting, one takes the location of honest players into account, and uses the fact that information cannot travel faster than the speed of light to limit the abilities of dishonest agents. For example, various relativistic bit commitment protocols have been proposed. Although it has been shown that bit commitment is sufficient to construct oblivious transfer and thus multiparty computation, composing specific relativistic protocols in this way is known to be insecure. A composable framework is required to perform such a modular security analysis of construction schemes, but no known frameworks can handle models of computation in Minkowski space. By instantiating the systems model from the Abstract Cryptography framework with Causal Boxes, we obtain such a composable framework, in which messages are assigned a location in Minkowski space (or superpositions thereof). This allows us to analyse relativistic protocols and to derive novel possibility and impossibility results. We show that (1) coin flipping can be constructed from the primitive channel with delay, (2) biased coin flipping, bit commitment and channel with delay are all impossible without further assumptions, and (3) it is impossible to improve a channel with delay. Note that the impossibility results also hold in the computational and bounded storage settings. This implies in particular non-composability of all proposed relativistic bit commitment protocols, of bit commitment in the bounded storage model, and of biased coin flipping., Comment: Clarified definitions and formulations, clarified how causal boxes are instantiated, strengthened results

We model (interactive) resources that provide Alice with a string $X$ and a guarantee that any Eve interacting with her interface of the resource obtains a (quantum) system $E$ such that the conditional (smooth) min-entropy of $X$ given $E$ is lower bounded by some $k$. This (abstract) resource specification encompasses any setting that results in the honest players holding such a string (or aborting). For example, it could be constructed from, e.g., noisy channels, quantum key distribution (QKD), or a violation of Bell inequalities, which all may be used to derive bounds on the min-entropy of $X$. As a first application, we use this min-entropy resource to modularize key distribution (KD) schemes by dividing them in two parts, which may be analyzed separately. In the first part, a KD protocol constructs a min-entropy resource given the (physical) resources available in the specific setting considered. In the second, it distills secret key from the min-entropy resource---i.e., it constructs a secret key resource. We prove security for a generic key distillation protocol that may use any min-entropy resource. Since the notion of resource construction is composable---security of a composed protocol follows from the security of its parts--- this reduces proving security of a KD protocol (e.g., QKD) to proving that it constructs a min-entropy resource. As a second application, we provide a composable security proof for the recent Fehr-Salvail protocol [EUROCRYPT 2017] that authenticates classical messages with a quantum message authentication code (Q-MAC), and recycles all the key upon successfully verifying the authenticity of the message. This protocol uses (and recycles) a non-uniform key, which we model as consuming and constructing a min-entropy resource., Comment: 39+18 pages, 11 figures

We show that a family of quantum authentication protocols introduced in [Barnum et al., FOCS 2002] can be used to construct a secure quantum channel and additionally recycle all of the secret key if the message is successfully authenticated, and recycle part of the key if tampering is detected. We give a full security proof that constructs the secure channel given only insecure noisy channels and a shared secret key. We also prove that the number of recycled key bits is optimal for this family of protocols, i.e., there exists an adversarial strategy to obtain all non-recycled bits. Previous works recycled less key and only gave partial security proofs, since they did not consider all possible distinguishers (environments) that may be used to distinguish the real setting from the ideal secure quantum channel and secret key resource., Comment: 38+17 pages, 13 figures. v2: constructed ideal secure channel and secret key resource have been slightly redefined; also added a proof in the appendix for quantum authentication without key recycling that has better parameters and only requires weak purity testing codes

We propose the concept of a system algebra with a parallel composition operation and an interface connection operation, and formalize composition-order invariance, which postulates that the order of composing and connecting systems is irrelevant, a generalized form of associativity. Composition-order invariance explicitly captures a common property that is implicit in any context where one can draw a figure (hiding the drawing order) of several connected systems, which appears in many scientific contexts. This abstract algebra captures settings where one is interested in the behavior of a composed system in an environment and wants to abstract away anything internal not relevant for the behavior. This may include physical systems, electronic circuits, or interacting distributed systems. One specific such setting, of special interest in computer science, are functional system algebras, which capture, in the most general sense, any type of system that takes inputs and produces outputs depending on the inputs, and where the output of a system can be the input to another system. The behavior of such a system is uniquely determined by the function mapping inputs to outputs. We consider several instantiations of this very general concept. In particular, we show that Kahn networks form a functional system algebra and prove their composition-order invariance. Moreover, we define a functional system algebra of causal systems, characterized by the property that inputs can only influence future outputs, where an abstract partial order relation captures the notion of "later". This system algebra is also shown to be composition-order invariant and appropriate instantiations thereof allow to model and analyze systems that depend on time.

Complex information-processing systems, for example quantum circuits, cryptographic protocols, or multi-player games, are naturally described as networks composed of more basic information-processing systems. A modular analysis of such systems requires a mathematical model of systems that is closed under composition, i.e., a network of these objects is again an object of the same type. We propose such a model and call the corresponding systems causal boxes. Causal boxes capture superpositions of causal structures, e.g., messages sent by a causal box A can be in a superposition of different orders or in a superposition of being sent to box B and box C. Furthermore, causal boxes can model systems whose behavior depends on time. By instantiating the Abstract Cryptography framework with causal boxes, we obtain the first composable security framework that can handle arbitrary quantum protocols and relativistic protocols., Comment: 44+24 pages, 16 figures. v3: minor edits based on referee comments, matches published version up to layout. v2: definition of causality weakened, new references

Randomness extractors, widely used in classical and quantum cryptography and other fields of computer science, e.g., derandomization, are functions which generate almost uniform randomness from weak sources of randomness. In the quantum setting one must take into account the quantum side information held by an adversary which might be used to break the security of the extractor. In the case of seeded extractors the presence of quantum side information has been extensively studied. For multi-source extractors one can easily see that high conditional min-entropy is not sufficient to guarantee security against arbitrary side information, even in the classical case. Hence, the interesting question is under which models of (both quantum and classical) side information multi-source extractors remain secure. In this work we suggest a natural model of side information, which we call the Markov model, and prove that any multi-source extractor remains secure in the presence of quantum side information of this type (albeit with weaker parameters). This improves on previous results in which more restricted models were considered and the security of only some types of extractors was shown., Comment: 21 pages + appendix. v2: Improved comparison to previous work. Comments are welcome!

This work is intended as an introduction to cryptographic security and a motivation for the widely used Quantum Key Distribution (QKD) security definition. We review the notion of security necessary for a protocol to be usable in a larger cryptographic context, i.e., for it to remain secure when composed with other secure protocols. We then derive the corresponding security criterion for QKD. We provide several examples of QKD composed in sequence and parallel with different cryptographic schemes to illustrate how the error of a composed protocol is the sum of the errors of the individual protocols. We also discuss the operational interpretations of the distance metric used to quantify these errors., Comment: 31+23 pages. 28 figures. Comments and questions welcome

We present a 625 MHz clocked coherent one-way quantum key distribution (QKD) system which continuously distributes secret keys over an optical fibre link. To support high secret key rates, we implemented a fast hardware key distillation engine which allows for key distillation rates up to 4 Mbps in real time. The system employs wavelength multiplexing in order to run over only a single optical fibre and is compactly integrated in 19-inch 2U racks. We optimized the system considering a security analysis that respects finite-key-size effects, authentication costs, and system errors. Using fast gated InGaAs single photon detectors, we reliably distribute secret keys with rates up to 140 kbps and over 25 km of optical fibre, for a security parameter of 4E-9.

Delegating difficult computations to remote large computation facilities, with appropriate security guarantees, is a possible solution for the ever-growing needs of personal computing power. For delegated computation protocols to be usable in a larger context---or simply to securely run two protocols in parallel---the security definitions need to be composable. Here, we define composable security for delegated quantum computation. We distinguish between protocols which provide only blindness---the computation is hidden from the server---and those that are also verifiable---the client can check that it has received the correct result. We show that the composable security definition capturing both these notions can be reduced to a combination of several distinct "trace-distance-type" criteria---which are, individually, non-composable security definitions. Additionally, we study the security of some known delegated quantum computation protocols, including Broadbent, Fitzsimons and Kashefi's Universal Blind Quantum Computation protocol. Even though these protocols were originally proposed with insufficient security criteria, they turn out to still be secure given the stronger composable definitions., Comment: 37+9 pages, 13 figures. v3: minor changes, new references. v2: extended the reduction between composable and local security to include entangled inputs, substantially rewritten the introduction to the Abstract Cryptography (AC) framework

Informally, an extractor delivers perfect randomness from a source that may be far away from the uniform distribution, yet contains some randomness. This task is a crucial ingredient of any attempt to produce perfectly random numbers---required, for instance, by cryptographic protocols, numerical simulations, or randomised computations. Trevisan's extractor raised considerable theoretical interest not only because of its data parsimony compared to other constructions, but particularly because it is secure against quantum adversaries, making it applicable to quantum key distribution. We discuss a modular, extensible and high-performance implementation of the construction based on various building blocks that can be flexibly combined to satisfy the requirements of a wide range of scenarios. Besides quantitatively analysing the properties of many combinations in practical settings, we improve previous theoretical proofs, and give explicit results for non-asymptotic cases. The self-contained description does not assume familiarity with extractors., Comment: 21 pages, 15 figures. Source code is available under GPLv2+. Comments welcome

Device-independent quantum key distribution (DIQKD) in its current design requires a violation of Bell's inequality between two honest parties, Alice and Bob, who are connected by a quantum channel. However, in reality, quantum channels are lossy, and this can be exploited for attacks based on the detection loophole. Here, we propose a novel approach to DIQKD that overcomes this limitation. In particular, based on a combination between an entropic uncertainty relation and the Clauser-Horne-Shimony-Holt (CHSH) test, we design a DIQKD protocol where the CHSH test is carried out entirely in Alice's laboratory. Thus the loophole caused by channel losses is avoided., Comment: 11 pages, 2 figures

In their seminal work on authentication, Wegman and Carter propose that to authenticate multiple messages, it is sufficient to reuse the same hash function as long as each tag is encrypted with a one-time pad. They argue that because the one-time pad is perfectly hiding, the hash function used remains completely unknown to the adversary. Since their proof is not composable, we revisit it using a composable security framework. It turns out that the above argument is insufficient: if the adversary learns whether a corrupted message was accepted or rejected, information about the hash function is leaked, and after a bounded finite amount of rounds it is completely known. We show however that this leak is very small: Wegman and Carter's protocol is still $\epsilon$-secure, if $\epsilon$-almost strongly universal$_2$ hash functions are used. This implies that the secret key corresponding to the choice of hash function can be reused in the next round of authentication without any additional error than this $\epsilon$. We also show that if the players have a mild form of synchronization, namely that the receiver knows when a message should be received, the key can be recycled for any arbitrary task, not only new rounds of authentication., Comment: 17+3 pages. 11 figures. v3: Rewritten with AC instead of UC. Extended the main result to both synchronous and asynchronous networks. Matches published version up to layout and updated references. v2: updated introduction and references

Randomness extraction involves the processing of purely classical information and is therefore usually studied in the framework of classical probability theory. However, such a classical treatment is generally too restrictive for applications, where side information about the values taken by classical random variables may be represented by the state of a quantum system. This is particularly relevant in the context of cryptography, where an adversary may make use of quantum devices. Here, we show that the well known construction paradigm for extractors proposed by Trevisan is sound in the presence of quantum side information. We exploit the modularity of this paradigm to give several concrete extractor constructions, which, e.g, extract all the conditional (smooth) min-entropy of the source using a seed of length poly-logarithmic in the input, or only require the seed to be weakly random., Comment: 20+10 pages; v2: extract more min-entropy, use weakly random seed; v3: extended introduction, matches published version with sections somewhat reordered

The standard definition of quantum state randomization, which is the quantum analog of the classical one-time pad, consists in applying some transformation to the quantum message conditioned on a classical secret key $k$. We investigate encryption schemes in which this transformation is conditioned on a quantum encryption key state $\rho_k$ instead of a classical string, and extend this symmetric-key scheme to an asymmetric-key model in which copies of the same encryption key $\rho_k$ may be held by several different people, but maintaining information-theoretical security. We find bounds on the message size and the number of copies of the encryption key which can be safely created in these two models in terms of the entropy of the decryption key, and show that the optimal bound can be asymptotically reached by a scheme using classical encryption keys. This means that the use of quantum states as encryption keys does not allow more of these to be created and shared, nor encrypt larger messages, than if these keys are purely classical., Comment: 17 pages, 1 figure