QCRYPT · 2019

In this tutorial we will clarify the difference between protocol and implementation security. While the framework for protocol security is well developed, the field of studying implementation security is still in flow. We will see several examples how implementations of QKD devices may be attacked via side-channel attacks. These attacks use the difference between actual implementations and the model assumptions of security proofs as a lever. Subsequently, we will discuss what can be done to mitigate the issues arising from potential side-channel attacks. Finally, we will discuss what statements we can actually make about QKD implementations.

Entanglement – the property that particles can share a single quantum state – is arguably the most counterintuitive yet potentially most powerful element in quantum theory. The non-local features of quantum theory are highlighted by the conflict between entanglement and local causality discovered by John Bell. Decades of Bell inequality tests, culminating in a series of loophole-free tests in 2015, have confirmed the non- locality of nature [1]. Future quantum networks [2] may harness these unique features of entanglement in a range of exciting applications, such as quantum computation and simulation, secure communication, enhanced metrology for astronomy and time-keeping as well as fundamental investigations. To fulfill these promises, a strong worldwide effort is ongoing to gain precise control over the full quantum dynamics of multi-particle nodes and to wire them up using quantum-photonic channels. Here I will present recent and ongoing work with the specific target of realizing the first multi-node network wired by quantum entanglement, including first primitive network experiments [3,4] using diamond-based quantum network nodes. [1] For a popular account of these experiments, see e.g. Ronald Hanson and Krister Shalm, Scientific American 319, 58-65 (2018). [2] Quantum internet: A vision for the road ahead, S Wehner, D Elkouss, R Hanson, Science 362 (6412), eaam9288 (2018). [3] N. Kalb et al., Science 356, 928 (2017). [4] P.C. Humphreys et al., Nature 558, 268 (2018).

We study a quantum switch serving a set of users. The function of the switch is to convert bipartite entanglement generated over individual links connecting each user to the switch, into bipartite or tripartite entangled states among (pairs or groups of) users at the highest possible rates at a fixed ratio. Such entanglement can then be converted to quantum-secure shared secret bits among pairs or triples of users using E91-like Quantum Key Distribution (QKD) protocols. The switch can store a certain number of qubits in a quantum memory for a certain length of time, and can make two-qubit Bell-basis measurements or three-qubit GHZ-basis projective measurements on qubits held in the memory. We model a set of randomized switching policies. Discovering that some are better than others, we present analytical results for the case where the switch stores one qubit per user at a given time step, and find that the best policies outperform a time division multiplexing (TDM) policy for sharing the switch between bipartite and tripartite entanglement generation. This performance improvement decreases as the number of users grows. The model is easily augmented to study the capacity region in the presence of qubit decoherence, obtaining similar results. Moreover, decoherence appears to have little effect on capacity. We also study a smaller class of policies when the switch can store two qubits per user. The full manuscript can be found at https://arxiv.org/abs/1901.06786.

In this work we report the first chip-to-chip multidimensional entanglement distribution. The faithful generation and transmission of the multidimensional quantum states relies on two main ingredients: silicon integrated photonics, offering a compelling platform for quantum information processing, and multicore fibres, which allows the reliable transmission of path encoded qudits.

Micius satellite was successfully launched into orbit in 2016. In the past three years, we have implemented a series of experimental works, including satellite-to-ground quantum key distribution, quantum entanglement distribution over 1000 km, ground-to-satellite quantum teleportation. The feasibility of a global quantum network has been demonstrated with ground quantum communication networks with optical fiber. In this report, we will present recent works based on Micius satellite, such as: space quantum key distribution and its application, quantum experiment based on quantum entanglement distribution, and expanded application of space quantum communication. The ongoing project in China of high orbit quantum satellite will also be introduced with results of several tests in ground.

Space-based quantum key distribution would allow, in the near future, secure communications be- tween parties over continental distances, complementing short-range fiber-based quantum networks. However, further demonstrations of daylight operations over free-space channels and the full compatibility with the telecom-based fiber infrastructure are still necessary. Here we present the prototype for daylight QKD at 1550 nm we developed as a demonstrator for application of QKD both on ground and in Space. Our QKD source, exploiting integrated silicon photonics technology, allows to reach a QBER of 1% during the field-test performed over a 145 m link, and represents a promising resource to design quantum optical payloads to be implemented in future satellite missions.

Measurement-device-independent quantum key distribution (MDI-QKD) offers a method of distributing shared randomness for use in symmetric key cryptography, while integrated optics provides a promising platform for ubiquitous quantum communication. This work experimentally demonstrates the use of indium phosphide (InP) devices for MDI-QKD. We generate 100 ps pulses for 2 GHz clocked, time-bin encoded BB84 states with random phases through a novel gain switching technique. By interfering two independent InP devices, we achieve 50 bps at 100 km and pre-empt the availability of integrated receivers which will increase rates through inherent scalability.

We show joint propagation of CV-QKD with successful secret key generation over 24 hours with 100 state-of-the-art EDFA amplified coherent WDM channels amounting to a total classical bitrate of 18.3~Tbit/s.

Measurement-device-independent quantum key distribution (MDI-QKD) is the only known QKD scheme that can completely overcome the problem of detection side-channel attacks. Yet, despite its practical importance, there is no standard approach towards proving the security of MDI-QKD. Here, we present a simple numerical method that can efficiently compute almost-tight security bounds for any discretely modulated MDI-QKD protocol. To demonstrate the broad utility of our method, we use it to analyze the security of coherent-state MDI-QKD, decoy-state MDI-QKD with leaky sources, and a variant of twin-field QKD called phase-matching QKD. In all of the numerical simulations (using realistic detection models) we find that our method gives significantly higher secret key rates than those obtained with current security proof techniques. Interestingly, we also find that phase-matching QKD using only two coherent test states is enough to overcome the fundamental rate-distance limit of QKD. Taken together, these findings suggest that our security proof method enables a versatile, fast, and possibly optimal approach towards the security validation of practical MDI-QKD systems.

We introduce the idea of temporarily trusted quantum nodes. We introduce a new primitive in that model, erasable bit commitment, which is a variant on standard two-party bit commitment. We show how to implement this primitive in our new model with temporarily trusted nodes. The erasable property allows Alice, in the case that the trust period is about to expire, to ask the trusted nodes to erase her commitment in such a way that a future coalition, after the trust period, of all trusted nodes together with Bob cannot extract any information about the commitment. This is impossible classically. A caveat is that after such an erasure, Alice is not committed to a classical value anymore. We provide a robust protocol which requires a constant number of trusted nodes and which can handle a small fraction of dishonest trusted nodes as well as implementation errors. Our approach lends itself to actual optical implementations, and requires memory during the trust period.

While quantum computers will bring immense computing capability that cannot be achieved with any feasible amount of regular computing power, they also break some of the mostly widely used codes that we depend on to protect our digital systems. For the advent of a quantum computer to be a positive milestone in human history, we must first fix these fundamental building blocks of cyber security. Come hear how this threat is actually a great opportunity to make our digital infrastructures more secure than they otherwise would be. And learn about the exciting science that underpins new tools for making our world more safe and secure, including quantum satellite communications.

Device-independent cryptography goes beyond conventional quantum cryptography by providing security that holds independently of the quality of the physical devices used to implement the cryptographic protocols. In this tutorial we will present existing device-independent quantum key distribution protocols and discuss the ideas underlying their security proofs. In particular, the tutorial will cover the best practices for using known techniques to prove security of device-independent protocols. Lastly, we will present several open questions whose solutions have the potential of bringing the quantum cryptography community closer to an experimental realization of device-independent quantum key distribution.

Conditional mutual information-based measures such as intrinsic information and squashed entanglement have been important theoretical tools to obtain upper bounds on distillable secret-key rates, with the latter playing an important role for device-dependent quantum key distribution protocols. Inspired by this line of work, we propose an information-theoretic quantifier for Bell non-locality called intrinsic non-locality. It uses conditional mutual information to measure the deviation of a given bipartite correlation from one having a local-hidden-variable model. We prove that it satisfies certain desirable properties such as faithfulness, convexity, and monotonicity under local operations and shared randomness. Most especially, we then prove that intrinsic non-locality is an upper bound on the secret-key-agreement capacity of a large class of device-independent protocols conducted using a device characterized by a bipartite correlation. In other words, given a device characterized by such a bipartite correlation, the secret-key rate that can be extracted from this device with a device-independent protocol is bounded from above by intrinsic non-locality. Finally, we evaluate intrinsic non-locality to obtain an explicit bound on the secret-key rate that can be obtained from a specific bipartite correlation studied extensively in the device-independent literature.

In this QCRYPT submission, we present a numerical toolbox that is capable of producing non-trivial lower bounds on the asymptotic secret key rate of any device-independent quantum key distribution (DIQKD) protocol. The main mechanism of our toolbox is a new method for estimating the entropy production of a quantum channel, giving rise to bounds that can be computed using the family of semidefinite programs (SDPs) known as the Navascues-Pironio-Acin (NPA) hierarchy.

The importance of being able to verify quantum computation delegated to remote servers increases with recent development of quantum technologies. In some of the proposed protocols for this task, a client delegates her quantum computation to non-communicating servers in multiple rounds of communication. In this work, we propose the first protocol where the client delegates her quantum computation to two servers in one-round of communication. Another advantage of our protocol is that it is conceptually simpler than previous protocols. The parameters of our protocol also make it possible to prove security even if the servers are allowed to communicate, but respecting the plausible assumption that information cannot be propagated faster than speed of light, making it the first relativistic protocol for quantum computation.

Sources producing high amounts of entanglement are essential for quantum cryptography. Given an uncharacterized source, manufactured by a possibly untrusted entity, how can we certify that it produces a lot of entanglement? We initiate the study of operational device-independent entanglement certification by presenting a device-independent protocol that lower-bounds the one-shot distillable entanglement of the remaining quantum state after the execution of the protocol. By this, the protocol certifies the amount of “useful entanglement” available for proceeding applications. Importantly, our protocol does not abort, with high probability, when testing realistically noisy sources.

Zero-knowledge proof systems have played a fundamental role in complexity theory and cryptography since its invention. I will introduce the basic definitions and constructions of zero-knowledge proof systems, and discuss the new questions that arise in a quantum setting. This includes making classical ZK proofs secure against quantum adversaries as well as making quantum interactive proof systems zero-knowledge.

Fully homomorphic encryption schemes (FHE) allow to apply arbitrary efficient computation to encrypted data without decrypting it first. This allows a client to delegate computation to a computationally powerful server without compromising the privacy of the input. This notion was proposed by Rivest, Adleman and Dertouzos in 1978, but a first candidate was only proposed 30 years later by Gentry. Broadbent and Jeffery (2015) asked whether it is possible to construct a *quantum* analog, which will allow to apply an arbitrary quantumly efficient computation to (classical or quantum) encrypted data. The ultimate notion of Quantum FHE (QFHE) scheme will allow even to a classical client privately delegate computation to a quantum server. The talk will survey the exciting recent advancement on this question, through the first “ultimate” candidate proposed by Mahadev (2018) and beyond. Connections to other quantum-cryptographic primitives and open questions will also be discussed.

We show that every language in QMA admits a classical-verifier, quantum-prover zero-knowledge argument system which is sound against quantum polynomial-time provers and zero-knowledge for classical (and quantum) polynomial-time verifiers. The protocol builds upon two recent results: a computational zero-knowledge proof system for languages in QMA, with a quantum verifier, introduced by Broadbent et al. (FOCS 2016), and an argument system for languages in QMA, with a classical verifier, introduced by Mahadev (FOCS 2018).

In this work we consider the interplay between multiprover interactive proofs, quantum entanglement, and zero knowledge proofs — notions that are central pillars of complexity theory, cryptography, and quantum information. In particular, we study the relationship between the complexity class MIP∗, the set of languages decidable by multiprover interactive proofs with quantumly entangled provers, and the class PZK-MIP∗, which is the set of languages decidable by MIP∗ protocols that furthermore possess the perfect zero knowledge property. Our main result is that the two classes are equal, i.e., MIP∗ = PZK-MIP∗ . This result provides a quantum analogue of the celebrated result of Ben-Or, Goldwasser, Kilian, and Wigderson (STOC 1988) who show that MIP = PZK-MIP (in other words, all classical multiprover interactive protocols can be made zero knowledge). We prove our result by showing that every MIP∗ protocol can be efficiently transformed into an equivalent zero knowledge MIP∗ protocol in a manner that preserves the completeness-soundness gap. Combining our transformation with previous results by Slofstra (Forum of Mathematics, Pi 2019) and Fitzsimons, Ji, Vidick and Yuen (STOC 2019) yields the corollary that all co-recursively enumerable languages (which include undecidable problems and every decidable problem) have zero knowledge MIP∗ protocols withvanishing promise gap.

Secure delegated computing is a key task for both classical and quantum networks. There exist both classical and quantum protocols for performing secure (quantum) computations in networks. In this talk, I will first give an overview of secure delegated quantum computing. Here, a client with no quantum-computational power can delegate a quantum computation to a fully fledged quantum server. I will particularly focus on experiments and vulnerabilities in the implementations. Further, I will focus on the interplay of classical and quantum approaches for delegated computing. I will demonstrate a way to perform classical (multiparty) computing amongst parties with limited computational resources. Our method harnesses quantum resources to increase the computational power of the individual parties. As particular examples, I will show how a client restricted to XOR gates can perform universal classical computation using single qubits. Further, I will demonstrate how a set of clients restricted to linear classical processing are able to jointly compute a non-linear multivariable function that lies beyond their individual capabilities. Finally, I will show proof-of-concept implementations using photonic qubits. Thus, this work highlights how minimal quantum and classical resources can be combined and exploited for classical computing.

Quantum key distribution (QKD) with conventional optics tools is limited to a linear scaling of the repeaterless bound. Recently, twin field (TF) QKD was conjectured to beat the limit by using an untrusted central station conducting a single-photon interference detection. So far, the effort to prove the conjecture was confined to the infinite key limit which neglected the time and cost for monitoring an adversary’s act. Here we propose a variant of TF-type QKD protocol equipped with a novel monitoring scheme and provide a finite-size-key security proof. We show that the protocol beats the linear bound in a reasonable running time of sending 10^12 pulses, which positively solves the conjecture.

We demonstrate the first experimental overcoming of the repeaterless secret key capacity (PLOB) bound through the implementation of the Twin Field Quantum Key Distribution (TF-QKD) protocol. We distribute secret keys at record channel losses (> 90 dB). We assess the prospects for real-world implementation of TF-QKD.

The twin-field (TF) quantum key distribution (QKD) protocol and its variants are highly attractive because they can beat the well-known fundamental limit of secret key rate for point-to-point (point-to-point bound) QKD without quantum repeaters. In this paper, we perform a proof-of-principle experimental demonstration of TF-QKD based on the protocol proposed by Curty et al., which removes the need for post-selection on the matching of a global phase from the original TF-QKD. Furthermore, we employ a Sagnac loop structure to overcome the major difficulty in the practical implementation of TF-QKD, namely, the need to stabilize the phase of the quantum state over kilometers of fiber. The experimental results show that the secret key rate of TF-QKD at high loss region can surpass the point-to-point bound of QKD with current technology.

Channel loss is one of the most severe limitation to extend the transmission distance of quan- tum key distribution in practice. The twin-field quantum key distribution can achieve a much longer transmission distance with improving the key rate from the linear scale of channel loss in the traditional decoy-state method to the square root scale of the channel transmittance. Here we demonstrate the real-optical-fibre experimental results of twin-field quantum key distribution through the sending-or-not-sending protocol, which is fault tolerant to large misalignment error. The phase locking technology developed in the frequency transfer field is adopted to ensure Alice’s and Bob’s source wavelengths are locked to each other. Phase reference pulses are used to monitor the phase difference between the channel. Further with a high performance single photon detector, we obtain the positive key rates for different distances, specifically, the obtained secure key rate at 150 km is higher than that of the measurement device independent QKD.

Quantum information is well-known to achieve cryptographic feats that are unattainable using classical information alone. Here, we add to this repertoire by introducing a new cryptographic functionality called uncloneable encryption. This functionality allows the encryption of a classical message such that two collaborating but isolated adversaries are prevented from simultaneously recovering the message, even when the encryption key is revealed. Clearly, such functionality is unattainable using classical information alone. We formally define uncloneable encryption, and show how to achieve it using Wiesner’s conjugate coding, combined with a quantum-secure pseudorandom function (qPRF). Modelling the qPRF as a quantum oracle, we show security by adapting techniques from the quantum one-way-to-hiding lemma, as well as using bounds from quantum monogamy-of-entanglement games.

One-time programs, computer programs which self-destruct after being run only once, are a powerful building block in cryptography and would allow for new forms of secure software distribution. However, ideal one-time programs have been proved to be unachievable using either classical or quantum resources. Here we relax the definition of one-time programs to allow some probability of error in the output and show that quantum mechanics offers security advantages over purely classical resources. We introduce a scheme for encoding probabilistic one-time programs as quantum states with prescribed measurement settings, explore their security, and experimentally demonstrate various one-time programs using measurements on single-photon states. These include classical logic gates, a program to solve Yao’s millionaires problem, and a one-time delegation of a digital signature. By combining quantum and classical technology, we demonstrate that quantum techniques can enhance computing capabilities even before full-scale quantum computers are available.

Physical Unclonable Functions (PUFs) are physical devices that have unique behaviour which is hard to clone. These hardware structures are considered as an effective and feasible security primitive. The application of a wide variety of PUF structures for different security purposes such as identification and key generation has been widely studied in the context of Classical PUFs. In addition, the quantum-readout PUF (QR-PUF) has been studied as a proposition for a quantum version of classical PUFs. In this paper, we do a comprehensive study on Quantum Physical Unclonable Functions with quantum cryptographic tools. We use a quantum game-based security framework for our analysis and we define a new class of quantum attacks, called General Quantum Emulation Attack (GQEA), applicable on current quantum-readout and hybrid quantum-classical PUFs. This class of attacks are based on using a database of inputs and outputs to emulate the action of an unknown quantum transformation on a new input. We define a concrete attack based on an existing emulation algorithm and use it to show the vulnerability of the current schemes under this attack. Furthermore, we formally define a QPUF for the first time and discuss the security of Unitary QPUFs (UQPUFs) by formally defining the unforgeability property of UQPUFs. We prove any UQPUF provides selective unforgeability property while they cannot provide unconditional and existential unforgeabilities.

QKD is attracting more and more interest. In order to introduce QKD into networks, several aspects have to be considered. In the talk I will present BSI’s view on QKD, focussing mainly on security aspects. These security aspects include certification and approval requirements, evaluation criteria, the combination of QKD with “traditional” cryptography and the role of random number generation. I will argue that at the moment QKD is a technology that should only be used in hybrid modes, e.g. one should combine the Quantum Key-Agreement with a quantum-safe key-agreement in order to generate keys for symmetric encryption algorithms. It is well known that existing QKD devices are vulnerable to sidechannel atttacks. Therefore performance standards and evaluation criteria are needed, where evaluation should be performed according to internationally accepted criteria, e.g. the Common Criteria (CC). I will report on the status of a project that aims at developing a Protection Profile (PP) for QKD devices.

The quantum random oracle model (QROM) has become the standard model in which to prove the post-quantum security of random-oracle-based constructions. Unfortunately, none of the known proof techniques allow the reduction to record information about the adversary’s queries, a crucial feature of many classical ROM proofs. In this work, we give a new QROM proof technique that overcomes this “recording barrier”, allowing for efficient on-the-fly simulation of random oracles, roughly analogous to the usual classical simulation. We then use this new technique to give the first proof of indifferentiability for domain extension, as well as other applications.

Applications of randomness such as private key generation and public randomness beacons require small blocks of certified random bits on demand. Device-independent quantum random number generators can produce such random bits, but existing quantum-proof protocols and loophole-free implementations suffer from high latency, requiring many hours to produce any random bits. Here we develop a broadly applicable framework, quantum probability estimation, for yielding efficient quantum-proof protocols. The framework is general and encompasses methods from previous works [Miller and Shi, SIAM Journal on Computing 46, 1304 (2017); Arnon-Friedman et al., Nature Communications 9, 459 (2018)]. Quantum probability estimation can adapt to changing experimental conditions, allows stopping the experiment as soon as the prespecified randomness goal is achieved, and can tolerate imperfect knowledge of the input distribution. Moreover, we demonstrate device-independent quantum randomness generation from a loophole-free Bell test with quantum probability estimation, obtaining multiple blocks of 512 random bits with an average experiment time of less than 5 minutes per block and with certified error bounded by $2^{-64}\approx 5.42\times 10^{-20}$.

**merged with** Thomas Van Himbeeck and Stefano Pironio. Correlations and Randomness Generation based on an Energy Constraint In a previous paper, we introduced a semi-device-independent scheme consisting of an untrusted source sending quantum states to an untrusted measuring device, with the sole assumption that the average energy of the states emitted by the source is bounded. Given this energy constraint, we showed that certain correlations between the source and the measuring device can only occur if the outcomes of the measurement are non-deterministic, i.e., these correlations certify the presence of randomness. In the present paper, we go further and show how to quantify the randomness as a function of the correlations and prove the soundness of a QRNG protocol exploiting this relation. For this purpose, we introduce (1) a semidefinite characterization of the set of quantum correlations, (2) an algorithm to lower-bound the Shannon entropy as a function of the correlations and (3) a proof of soundness using finite trials compatible with our energy assumption.

I will start this talk with a review of various technological advances that have enabled the first 10 Mb/s quantum key distribution (QKD) system. I will then introduce our latest developments on photonic integration and implementation security of QKD optics.

Cryptography with quantum states exhibits a number of surprising and counterintuitive features. In an intriguing 2002 paper, Barnum et al. argued that these strange features imply that digital signatures for quantum states are impossible. In this work, we thoroughly explore this question from a theoretical crypto perspective. We expand on the work of Barnum et al. and show that even very weak forms of signing quantum states are impossible; essentially, if a signature scheme is secure, then it is classical. We then show a positive result: it is possible to sign quantum states, provided that they are also encrypted with the public key of the intended recipient. Following classical nomenclature, we call this notion quantum signcryption. Classically, signcryption is only interesting if it provides superior efficiency to simultaneous encryption and signing. Our results imply that, quantumly, it is far more interesting: by the laws of quantum mechanics, it is the only signing method available. We develop security definitions for quantum signcryption, ranging from a simple one-time two-user setting, to a chosen-ciphertext-secure many-time multi-user setting. We also give secure constructions based on post-quantum public-key primitives. (Joint work with Tommaso Gagliardoni and Christian Majenz.)

The famous Fiat-Shamir transformation turns any public-coin three-round interactive proof, i.e., any so-called sigma-protocol, into a non-interactive proof in the random-oracle model. We study this transformation in the setting of a quantum adversary that in particular may query the random oracle in quantum superposition. Our main result is a generic reduction that transforms any quantum dishonest prover attacking the Fiat-Shamir transformation in the quantum random-oracle model into a similarly successful quantum dishonest prover attacking the underlying sigma-protocol (in the standard model). Applied to the standard soundness and proof-of-knowledge definitions, our reduction implies that both these security properties, in both the computational and the statistical variant, are preserved under the Fiat-Shamir transformation even when allowing quantum attacks. Our result improves and completes the partial results that have been known so far, but it also proves wrong certain claims made in the literature. In the context of post-quantum secure signature schemes, our results imply that for any sigma-protocol that is a proof-of-knowledge against quantum dishonest provers (and that satisfies some additional natural properties), the corresponding Fiat-Shamir signature scheme is secure in the quantum random-oracle model. For example, we can conclude that the non-optimized version of Fish, which is the bare Fiat-Shamir variant of the NIST candidate Picnic, is secure in the quantum random-oracle model.

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.

Game-playing proofs constitute a powerful framework for classical cryptographic security arguments, most notably applied in the context of indifferentiability. An essential ingredient in such proofs is lazy sampling of random primitives. We develop a quantum game-playing proof framework by generalizing two recently developed proof techniques. First, we describe how Zhandry’s compressed quantum oracles~\cite{zhandry2018record} can be used to do quantum lazy sampling from non-uniform function distributions. Second, we observe how Unruh’s one-way-to-hiding lemma~\cite{unruh2015revocable} can also be applied to compressed oracles, providing a quantum counterpart to the fundamental lemma of game-playing. Subsequently, we use our game-playing framework to prove quantum indifferentiability of the sponge construction, assuming a random internal function or a random permutation. Our results upgrade post-quantum security of SHA-3 to the same level that is proven against classical adversaries.

We introduce a protocol between a classical polynomial-time verifier and a quantum polynomial-time prover that allows the verifier to securely delegate to the prover the preparation of certain single-qubit quantum states. The protocol realizes the following functionality, with computational security: the verifier chooses one of the observables Z, X, Y, (X+Y)/sqrt(2), (X-Y)/sqrt(2); the prover receives a uniformly random eigenstate of the observable chosen by the verifier; the verifier receives a classical description of that state. The prover is unaware of which state he received and moreover, the verifier can check with high confidence whether the preparation was successful. The delegated preparation of single-qubit states is an elementary building block in many quantum cryptographic protocols. We expect our implementation of “random remote state preparation with verification”, a functionality first defined in (Dunjko and Kashefi 2014), to be useful for removing the need for quantum communication in such protocols while keeping functionality. The main application that we detail is to a protocol for blind and verifiable delegated quantum computation (DQC) that builds on the work of (Fitzsimons and Kashefi 2018), who provided such a protocol with quantum communication. Recently, both blind an verifiable DQC were shown to be possible, under computational assumptions, with a classical polynomial-time client (Mahadev 2017, Mahadev 2018). Compared to the work of Mahadev, our protocol is more modular, applies to the measurement-based model of computation (instead of the Hamiltonian model) and is composable. Our proof of security builds on ideas introduced in (Brakerski et al. 2018).

We present a definition for non-malleability in the setting of public-key quantum cryptography. Overcoming the notorious “recording barrier” known from generalizing other integrity-like security notions to quantum encryption, we generalize one of the equivalent classical definitions, comparison-based non-malleability, and show how it can be fulfilled. In addition, we further explore one-time non-malleability notions for symmetric-key quantum encryption known from the literature by defining plaintext and ciphertext variants and characterizing their relation. To show satisfiability of our presented definition, we use these refined one-time notions, as well as a post-quantum CNM scheme, to construct a hybrid scheme.

The goal of demonstrating a quantum advantage with currently available experimental systems is of utmost importance in quantum information science. While this remains elusive for quantum computation, the field of communication complexity offers the possibility to already explore and showcase this advantage for useful tasks. Here, we define such a task, the Sampling Matching problem, which is inspired by the Hidden Matching problem and features an exponential gap between quantum and classical protocols in the one-way communication model. Our problem allows by its conception a proof-of-principle photonic implementation based on encoding in the phase of coherent states of light, the use of a fixed size linear optic circuit, and single-photon detection. This enables us to demonstrate experimentally an advantage in the transmitted information resource beyond a threshold input size, which would have been impossible to reach for the original Hidden Matching problem. Our demonstration has implications in various communication and cryptographic settings. Specifically we have used it to introduce a robust practical quantum money-scheme. Our scheme involves an honest Bank who prepares the note by independently and uniformly selecting multiple n-bit binary secret strings which are encoded into the single photon states. The note is then distributed among untrusted holders. To carry out the transaction, the note holder sends the note to the honest local verifiers of the Bank. The verifier runs the Sampling Matching scheme on some randomly selected copies of the note and forwards the classical measurement outcome to the Bank. The Bank then declares the validity of the note. Our private-key money scheme includes multiple features such as single round classical interaction of the local verifier with the Bank, optimal note re-usability (linear in the size of Bank note), linear verification circuit size, and an unconditional security against any adversary trying to forge the Bank note while tolerating the noise of up to 21.4%. The simplistic nature of our verification scheme using Sampling Matching allows for the ability to reach a maximal theoretical noise tolerance of 25%, as conjectured by Amiri et al [Phys Rev A 95, 062334].