Starting in 1974, Ralph Merkle proposed the first unclassified systems for secure communications over insecure channels. When legitimate communicating parties are willing to spend an amount of computational effort proportional to some parameter N, an eavesdropper cannot break into their communication without spending a time in the order ofN2, which is quadratically more than the legitimate effort. We investigate quantum analogues to this technique. First, we show that Merkle's systems are completely insecure if the legitimate parties are classical but the eavesdropper uses quantum computation. Then, we describe simple modifications on Merkle's proposals, in which the legitimate parties still use classical communication but benefit from local quantum computation to agree on a common key. We show that the optimal quantum eavesdropping strategy against our protocols requires a time in the order o/7V3/2. We conjecture these Quantum Merkle Puzzles to be optimal in the classical communication model, in which case quantum mechanics does more harm than good for the purpose of secure communications over insecure classical channels. This is in sharp contrast with Quantum Key Distribution, which ensures unconditionally secure communications over quantum channels.
Starting in 1974, Ralph Merkle proposed the first unclassified systems for secure communications over insecure channels. When legitimate communicating parties are willing to spend an amount of computational effort proportional to some parameter N, an eavesdropper cannot break into their communication without spending a time in the order ofN2, which is quadratically more than the legitimate effort. We investigate quantum analogues to this technique. First, we show that Merkle's systems are completely insecure if the legitimate parties are classical but the eavesdropper uses quantum computation. Then, we describe simple modifications on Merkle's proposals, in which the legitimate parties still use classical communication but benefit from local quantum computation to agree on a common key. We show that the optimal quantum eavesdropping strategy against our protocols requires a time in the order o/7V3/2. We conjecture these Quantum Merkle Puzzles to be optimal in the classical communication model, in which case quantum mechanics does more harm than good for the purpose of secure communications over insecure classical channels. This is in sharp contrast with Quantum Key Distribution, which ensures unconditionally secure communications over quantum channels.
In 1974, Ralph Merkle proposed the first unclassified protocol for secure communications over insecure channels. When legitimate communicating parties are willing to spend an amount of computational effort proportional to some parameter N, an eavesdropper cannot break into their communication without spending a time proportional to N2 , which is quadratically more than the legitimate effort. In a quantum world, however, Merkle’s protocol is immediately broken by Grover’s algorithm, but it is easily repaired if we are satisfied with a quantum protocol against which a quantum adversary needs to spend a time proportional to N3/2 in order to break it. Can we do better? We give two new key establishment protocols in the spirit of Merkle’s. The first one, which requires the legitimate parties to have access to a quantum computer, resists any quantum adversary who is not willing to make an effort at least proportional to N5/3 , except with vanishing probability. Our second protocol is purely classical, yet it requires any quantum adversary to work asymptotically harder than the legitimate parties, again except with vanishing probability. In either case, security is proved for a typical run of the protocols: the probabilities are taken over the random (or quantum) choices made by the legitimate participants in order to establish their key as well as over the random (or quantum) choices made by the adversary who is trying to be privy to it.
Key agreement is a cryptographic scenario between two legitimate parties, who need to establish a common secret key over a public authenticated channel, and an eavesdropper who intercepts all their messages in order to learn the secret. We consider query complexity in which we count only the number of evaluations (queries) of a given black-box function, and classical communication channels. Ralph Merkle provided the first unclassified scheme for secure communications over insecure channels. When legitimate parties are willing to ask O(N) queries for some parameter N, any classical eavesdropper needs Omega(N^2) queries before being able to learn their secret, which is is optimal. However, a quantum eavesdropper can break this scheme in O(N) queries. Furthermore, it was conjectured that any scheme, in which legitimate parties are classical, could be broken in O(N) quantum queries. In this thesis, we introduce protocols à la Merkle that fall into two categories. When legitimate parties are restricted to use classical computers, we offer the first secure classical scheme. It requires Omega(N^{13/12}) queries of a quantum eavesdropper to learn the secret. We give another protocol having security of Omega(N^{7/6}) queries. Furthermore, for any k>= 2, we introduce a classical protocol in which legitimate parties establish a secret in O(N) queries while the optimal quantum eavesdropping strategy requires Theta(N^{1/2+k/{k+1}}) queries, approaching Theta(N^{3/2}) when k increases. When legitimate parties are provided with quantum computers, we present two quantum protocols improving on the best known scheme before this work. Furthermore, for any k>= 2, we give a quantum protocol in which legitimate parties establish a secret in O(N) queries while the optimal quantum eavesdropping strategy requires Theta(N^{1+{k}/{k+1}})} queries, approaching Theta(N^{2}) when k increases.
At Crypto 2011, some of us had proposed a family of cryptographic protocols for key establishment capable of protecting quantum and classical legitimate parties unconditionally against a quantum eavesdropper in the query complexity model. Unfortunately, our security proofs were unsatisfactory from a cryptographically meaningful perspective because they were sound only in a worst-case scenario. Here, we extend our results and prove that for any \eps > 0, there is a classical protocol that allows the legitimate parties to establish a common key after O(N) expected queries to a random oracle, yet any quantum eavesdropper will have a vanishing probability of learning their key after O(N^(1.5-\eps)) queries to the same oracle. The vanishing probability applies to a typical run of the protocol. If we allow the legitimate parties to use a quantum computer as well, their advantage over the quantum eavesdropper becomes arbitrarily close to the quadratic advantage that classical legitimate parties enjoyed over classical eavesdroppers in the seminal 1974 work of Ralph Merkle. Along the way, we develop new tools to give lower bounds on the number of quantum queries required to distinguish two probability distributions. This method in itself could have multiple applications in cryptography. We use it here to study average-case quantum query complexity, for which we develop a new composition theorem of independent interest.
Assuming an insecure quantum channel and an authenticated classical channel, we propose an unconditionally secure scheme for encrypting classical messages under a shared key, where attempts to eavesdrop the ciphertext can be detected. If no eavesdropping is detected, we can securely re-use the entire key for encrypting new messages. If eavesdropping is detected, we must discard a number of key bits corresponding to the length of the message, but can re-use almost all of the rest. We show this is essentially optimal. Thus, provided the adversary does not interfere (too much) with the quantum channel, we can securely send an arbitrary number of message bits, independently of the length of the initial key. Moreover, the key-recycling mechanism only requires one-bit feedback. While ordinary quantum key distribution with a classical one time pad could be used instead to obtain a similar functionality, this would need more rounds of interaction and more communication.
Quantum key distribution allows two parties, traditionally known as Alice and Bob, to establish a secure random cryptographic key if, firstly, they have access to a quantum communication channel, and secondly, they can exchange classical public messages which can be monitored but not altered by an eavesdropper, Eve. Quantum key distribution provides perfect security because, unlike its classical counterpart, it relies on the laws of physics rather than on ensuring that successful eavesdropping would require excessive computational effort. However, security proofs of quantum key distribution are not trivial and are usually restricted in their applicability to specific protocols. In contrast, we present a general and conceptually simple proof which can be applied to a number of different protocols. It relies on the fact that a cryptographic procedure called privacy amplification is equally secure when an adversary's memory for data storage is quantum rather than classical.
It seems that quantum key distribution (QKD) may be completely insecure when the message sender Alice always encodes her key bits in a fixed basis. In this paper, we present a QKD protocol with classical Alice, i.e. Alice always encodes her key bit in the {|0〉,|1〉} basis (we call it classical {0,1} basis) and the eavesdropper Eve knows this fact. We prove that our protocol is completely robust against any eavesdropping attack and present the amount of tolerable noise against Eve's individual attack. Next, we present a QKD protocol to demonstrate that secure key bits can be distributed even if neither Alice nor Bob has quantum capacities, and extend this idea to a QKD network protocol with numerous parties who have only classical capacities. Finally, we discuss that quantum is necessary in QKD for security reasons, but both Alice and Bob may be classical.