Posts Tagged ‘2PC
Quantum cryptography makes use of the quantum-mechanical behavior of nature for the design and analysis of cryptographic schemes. Optimally (but not always), quantum cryptography allows for the design of cryptographic schemes whose security is guaranteed solely by the laws of nature. This is in sharp contrast to standard cryptographic schemes, which can be broken in principle, i.e., when given sufficient computing power. From a theory point of view, quantum cryptography offers a beautiful interplay between the mathematics of adversarial behavior and quantum information theory. We discuss the traditional application of quantum cryptography, quantum key distribution (QKD), from a modern perspective, and we discuss some recent developments in the context of quantum two-party cooperation (2PC). QKD allows two distant parties to communicate in a provably-secure way in the presence of an outside eavesdropper, whereas 2PC is concerned with protecting information against possibly malicious insiders. We show the basic idea of constructing quantum cryptographic schemes, but we also show some connectionsto quantum information theory as needed for the rigorous security analyses, and we discuss some of the relevant quantum-information-theoretic results.
The security of most of the cryptographic schemes currently used relieson unproven computational complexity assumptions (like the assumed hardness of factoring large numbers), combined with an assumed bound on a potential attacker’s computing power. This complexity-theoretic approach of designing cryptographic schemes leads to very practical solutions but obviously has its downside: one cannot be fully certain about the security of the scheme! Indeed, the underlying computational complexity assumption might be broken from one day to another (e.g. byan efficient factoring algorithm being discovered) since complexity theory is still far from being able to prove some computational problem to be “hard” in the sense as needed. Furthermore, it is known that the standard complexity assumptions used in practice (factoring and computing discrete-logs) break down as soon as a quantum computer can be built. Finally, even if it is computationally infeasible for an attacker to extract sensitive data from the information available to him at the time the cryptographic scheme is used, the attacker can still store, say, an intercepted ciphertext and wait until computer technology has advanced enough so that he eventually can recover the data that was to be protected. This clearly poses a serious threat to long term highly-sensitive data.
Optimally, but not always, quantum cryptography allows for the design of cryptographic schemes that can be proven secure under the sole assumption that the laws of quantum mechanics are correct—or that they at least describe sufficiently well the behavior of certain particles like photons or spin-1/2 particles, which would be used to implement the quantum-cryptographic schemes. For instance, the search for a rigorous analysis of one of the first quantum cryptographic schemes led to important insights into quantum information theory, which in turn proved to be useful for the design of new quantum cryptographic schemes.
On the other hand, we also want to present quantum cryptography as an exact mathematical science that combines elements from classical cryptography, information theory and quantum mechanics. Therefore, besides the quantum-cryptographic schemes we show, we also discuss the theoretical foundations needed to rigorously understand and prove their security. These are quantum-information-theoretic results, specifically developed for the analysis of quantum-cryptographic schemes, but can be appreciated in their own right as providing interesting insight into the theory of quantum information. For instance, we show a meaningful way to measure the uncertainty that some piece of classical (meaning non-quantum) data contains when givena correlated quantum state, and we show that this measure determines the number of nearly-random-and-independent bits that can be extracted from the classical data. Also, we show a variant of the uncertainty principle that expresses the amount of uncertainty in terms of the above measure.
As of specific quantum cryptographic results, we focus in this article on the question of tackling classical (i.e. non-quantum) cryptographic tasks by quantum cryptographic means, like how to securely communicate a classical private message by using a quantum channel. Specifically, we focus on quantum-key distribution(QKD), which is the traditional application of quantum cryptography, and on recent new developments in the context of quantum two-party cooperation (2PC).
QKD allows two parties, Alice and Bob, to agree on a secret key K by public communication, i.e., even if an attacker Eve can access the complete conversation between Alice and Bob. By the laws of quantum mechanics, it is guaranteed that the agreed-upon secret key K is (close to) random-and-independent of Eve’s (quantum) view. As such, K can then be safely used for instance as encryption key for a (possibly perfectly-secure) encryption scheme to securely communicate a private message viathe public communication channel.
2PC, on the other hand, is concerned with protecting information against inside attackers. Unfortunately, quantum cryptographic 2PC schemes whose security is guaranteed by the laws of quantum mechanics alone do not exist (unless one settles for avery low level of security), but in addition, some “technological restriction” needs to be assumed about the attacker: for instance, that he cannot reliably store arbitrarily many, say, photons without affecting their polarization. While the theory of quantum physics permits to store quantum states, doing so in the form of photons, for instance, is technically very challenging and essentially impossible with current technology. Itis thus reasonable to base security upon it.