A Study Of Zero-Knowledge Interactive Quantum Proof

Since quantum computation and quantum communication are possible in principle and may be physically realized one day (now we have already realized it partly, especially in secure quantum communication), it would be very interesting to see how quantumness can change our lives. In particular, it would be intriguing to see what security quantumness may provide us, which is becoming more and more important in our everyday life. As it is well-known, classical cryptography sometimes is insecure under quantum attack, this also drives us to consider quan-tum cryptography:can we use quantum mechanism to counter against the attack that may also come from quantum mechanism?Among others, zero-knowledge proof is a basic notion in classical cryptogra-phy, which can be used to construct many useful cryptographic protocols, e.g. identification scheme. Thus, it would be interesting to generalize zero-knowledge proof to quantum case, that is, consider zero-knowledge quantum proof. The theme of this thesis is to carry out a complexity-theoretic study of zero-knowledge quantum interactive proof. Here by "complexity-theoretic method" we mean we identify languages (or promise problems) possessing zero-knowledge quantum in-teractive proof as a complexity class, and study it using various ideas and methods developed in computational complexity.Specifically, we first fully discuss the formal definition of zero-knowledge quantum proof, explaining how it generalizes from its classical counterpart and captures our intuition. As far as we known, similar systematical discussion of zero-knowledge quantum proof can be found nowhere before us.We next study perfect zero-knowledge quantum proof, constructing a first complete problem for the corresponding complexity class. We remark that this result heavily relies on quantum property, thus does not have classical counterpart. It turns out that our complete problem finds many applications in the study of perfect zero-knowledge quantum proof.Manipulating trace distance serves as a basic tool in deriving complete prob-lems for statistical and perfect zero-knowledge quantum proof. In this thesis, we discover an interesting way of reversing trace distance. In particular, this way has two intriguing features:first, our construction makes use of quantum entangle-ment; its underlying idea is similar to a common quantum phenomenon known as decoherence. Second, our construction has a non-black-box sense.