Unconditionally-Secure and Reusable Public-Key Authentication
We present a quantum-public-key identification protocol and show that it is secure against a computationally-unbounded adversary. This demonstrates for the first time that unconditionally-secure and reusable public-key authentication is possible in princi
- PDF / 316,416 Bytes
- 22 Pages / 439.37 x 666.142 pts Page_size
- 96 Downloads / 185 Views
Institute for Quantum Computing, University of Waterloo, 200 University Avenue, Waterloo, ON N2L 3G1, Canada 2 Department of Combinatorics and Optimization, University of Waterloo, 200 University Avenue, Waterloo, ON N2L 3G1, Canada [email protected] 3 Perimeter Institute for Theoretical Physics, 31 Caroline Street North, Waterloo, ON N2L 2Y5, Canada
Abstract. We present a quantum-public-key identification protocol and show that it is secure against a computationally-unbounded adversary. This demonstrates for the first time that unconditionally-secure and reusable public-key authentication is possible in principle with (purestate) public keys.
1
Introduction
Public-key cryptography has proved to be an indispensable tool in the modern information security infrastructure. Most notably, digital signature schemes form the backbone of Internet commerce, allowing trust to be propagated across the network in an efficient fashion. In turn, public-key encryption allows the private communication of messages (or, more usually, the establishment of symmetric secret keys) among users who are authenticated via digital signatures. The security of these classical public-key cryptosystems relies on assumptions on the difficulty of certain mathematical problems [1]. Gottesman and Chuang [2] initiated the study of quantum-public-key cryptography, where the public keys are quantum systems, with the goal of obtaining the functionality and efficiency of public-key cryptosystems but with information-theoretic security. They presented a secure one-time digital signature scheme for signing classical messages, based on Lamport’s classical scheme [3]. In a public-key framework, Alice chooses a random private key, creates copies of the corresponding public key via some publicly-known algorithm, and distributes the copies in an authenticated fashion to all potential “Bobs”. In principle, this asymmetric setup allows, e.g., any Bob to send encrypted messages to Alice or to verify any signature for a message that Alice digitally signed. By eliminating the need for each Alice-Bob pair to establish a secret key (in large networks where there may be many “Alices” and “Bobs”), the framework vastly simplifies key distribution, which is often the most costly part of any cryptosystem, compared to a framework that uses only symmetric keys. D. Bacon et al. (Eds.): TQC 2011, LNCS 6745, pp. 121–142, 2014. c Springer-Verlag Berlin Heidelberg 2014 DOI: 10.1007/978-3-642-54429-3 8,
122
L. Ioannou and M. Mosca
Some remarks about the quantum-public-key framework are in order. First, we address the issue of purity of the quantum public keys. In principle, the quantum public key can be either in a pure or mixed state from Alice’s point of view (a mixed state is a fixed probabilistic distribution of pure states). Gottesman and Chuang [2] assumed pure-state public keys. For digital signature schemes, this purity is crucial; for, otherwise, Alice could cheat by sending different public keys to different “Bobs”. Purity prevents Alice’s cheating in this case because d
Data Loading...
