Ivan Damgård, Jakob Funder, Jesper Buus Nielsen, Louis Salvail
Attacks on classical cryptographic protocols are usually modeled by allowing an adversary to ask queries from an oracle. Security is then defined by requiring that as long as the queries satisfy some constraint, there is some problem the adversary cannot solve, such as compute a certain piece of information. In this paper, we introduce a fundamentally new model of quantum attacks on classical cryptographic protocols, where the adversary is allowed to ask several classical queries in quantum superposition. This is a strictly stronger attack than the standard one, and we consider the security of several primitives in this model. We show that a secret-sharing scheme that is secure with threshold $t$ in the standard model is secure against superposition attacks if and only if the threshold is lowered to $t/2$. We use this result to give zero-knowledge proofs for all of NP in the common reference string model. While our protocol is classical, it is sound against a cheating unbounded quantum prover and computational zero-knowledge even if the verifier is allowed a superposition attack. Finally, we consider multiparty computation and show that for the most general type of attack, simulation based security is not possible. However, putting a natural constraint on the adversary, we show a non-trivial example of a protocol that can indeed be simulated.
The SOLID concept is to develop small solid-state hybrid systems with 3-8 qubits capable of performing elementary processing and communication of quantum information. This involves design, fabrication and investigation of combinations of qubits, oscillators, cavities, and transmission lines, creating hybrid devices interfacing different types of qubits for quantum data storage, qubit interconversion, and communication. The agenda is to provide proofs of concept, to identify roadblocks, and to stake out roads that seem particularly promising, including practical applications of quantum technologies.
We motivate, define and construct quantum proofs of knowledge, proofs of knowledge secure against quantum adversaries. Our constructions are based on a new quantum rewinding technique that allows us to extract witnesses in many classical proofs of knowledge. We give criteria under which a classical proof of knowledge is a quantum proof of knowledge. Combining our results with Watrous’ results on quantum zeroknowledge, we show that there are zero-knowledge quantum proofs of knowledge for all languages in NP.
Rahul Jain, Alexandra Kolla, Gatis Midrijānis, Ben W. Reichardt
Let $L$ be a language decided by a constant-round quantum Arthur-Merlin ($\QAM$) protocol with negligible soundness error and all but possibly the last message being classical. We prove that if this protocol is zero knowledge with a black-box, quantum simulator $\cS$, then $L \in \BQP$. Our result also applies to any language having a three-round quantum interactive proof ($\QIP$), with all but possibly the last message being classical, with negligible soundness error and a black-box quantum simulator. These results in particular make it unlikely that certain protocols can be composed in parallel in order to reduce soundness error, while maintaining zero knowledge with a black-box quantum simulator. They generalize analogous classical results of Goldreich and Krawczyk (1990). Our proof goes via a reduction to quantum black-box search. We show that the existence of a black-box quantum simulator for such protocols when $L \notin \BQP$ would imply an impossibly-good quantum search algorithm.
In this paper, we prove classical coin-flipping secure in the presence of quantum adversaries. The proof uses a recent result of Watrous [Wat09] that allows quantum rewinding for protocols of a certain form. We then discuss two applications. First, the combination of coin-flipping with any non-interactive zero-knowledge protocol leads to an easy transformation from non-interactive zero-knowledge to interactive quantum zero-knowledge. Second, we discuss how our protocol can be applied to a recently proposed method for improving the security of quantum protocols [DFL+09], resulting in an implementation without set-up assumptions. Finally, we sketch how to achieve efficient simulation for an extended construction in the common-reference-string model.
In this paper, we prove classical coin-flipping secure in the presence of quantum adversaries. The proof uses a recent result of Watrous [Wat09] that allows quantum rewinding for protocols of a certain form. We then discuss two applications. First, the combination of coin-flipping with any non-interactive zero-knowledge protocol leads to an easy transformation from non-interactive zero-knowledge to interactive quantum zero-knowledge. Second, we discuss how our protocol can be applied to a recently proposed method for improving the security of quantum protocols [DFL+09], resulting in an implementation without set-up assumptions. Finally, we sketch how to achieve efficient simulation for an extended construction in the common-reference-string model.
Wang Yu-wu, You-Bang Zhan, (1)淮阴师范学院计算机科学系,淮安 223300; (2)淮阴师范学院物理系,淮安 223300
A theoretical scheme for zero-knowledge proof quantum identity authentication is proposed by the absolutely impartial third party CA， which has been realized based on remote state preparation and assisted cloning controlled means. In the process of identification， only CA knows the information of quantum identity card and the first party Alice and the second party Bob can accomplish the quantum identity authentication without knowing it. We discuss the probability of accomplishing this job. The security of this scheme is unconditional and it is guaranteed by quantum mechanism.
We define quantum expanders in a natural way. We give two constructions of quantum expanders, both based on classical expander constructions. The first construction is algebraic, and is based on the construction of Cayley Ramanujan graphs over the group PGL(2, q) given by Lubotzky et al. (1988). The second construction is combinatorial, and is based on a quantum variant of the Zig-Zag product introduced by Reingold et al. (2000). Both constructions are of constant degree, and the second one is explicit. Using quantum expanders, we characterize the complexity of comparing and estimating quantum entropies. Specifically, we consider the following task: given two mixed states, each given by a quantum circuit generating it, decide which mixed state has more entropy. We show that this problem is QSZK-complete (where QSZK is the class of languages having a zero-knowledge quantum interactive protocol). This problem is very well motivated from a physical point of view. Our proof resembles the classical proof that the entropy difference problem is SZK-complete, but crucially depends on the use of quantum expanders.
Jan Bouda, Paulo Mateus, Nikola Paunković, João Rasga
We show how quantum tamper-proof devices (QTPD's) can be used to attack and to develop security protocols. On one hand, we prove that it is possible to transfer proofs of zero-knowledge protocols using QTPD's. This attack can be extended to other security schemes where privacy is important. On the other hand, we present a fair contract signing protocol using QTPD's where there is no communication with Judge during the exchange phase (which is impossible classically). In the latter case, we make use of decoherence in the quantum state of the QTPD to implement a global clock over the asynchronous network. QTPD's seem to be possible to implement with existing quantum hardware, due to the fact that it is hard to isolate quantum memory from interference. These theoretical results contribute to justify the implementation of QTPD's.
Zero-knowledge proof system is an important protocol that can be used as a basic block for construction of other more complex cryptographic protocols. Quantum zero-knowledge protocols have been proposed but, since their implementation requires advanced quantum technology devices, experimental implementation of zero-knowledge protocols have not being reported. In this work, we present a quantum zero-knowledge protocol based on a quantum bit commitment protocol that can be implemented with today technology. Hence, our quantum zero-knowledge protocol can be readily implemented.
Public-key cryptography is a key technology for making the Internet and other IT infrastructures secure. The security of the established public-key cryptosystems relies on the difficulty of factoring large composite integers or computing discrete logarithms. However, it is unclear whether these computational problems remain intractable in the future. For example, Shor showed in 1994 that quantum computers can be used to factor integers and to compute discrete logarithms in polynomial time. It is therefore necessary to develop alternative public-key cryptosystems which do not rely on the difficulty of factoring or computing discrete logarithms and which are secure even against quantum computer attacks. We call such cryptosystems quantum-immune. To prove the security of these quantum-immune cryptosystems, appropriate security models have to be used. Since quantum computers are able to solve problems in polynomial time which are supposed to be intractable for classical computers, the existing security models are inadequate in the presence of quantum adversaries. Therefore, new security models have to be developed to capture quantum adversaries. Properties of these new security models have to be investigated. On a more practical level, the quantum-immune cryptosystems have to be implemented in a way that they can seamlessly replace established cryptosystems. The implementations have to be efficient and suitable for resource-constrained devices. They must easily integrate into existing public-key infrastructures. This thesis contributes to both the theory and practice of quantum-immune cryptography, addressing the above-mentioned challenges. In the theoretical part, we concentrate on the quantum zero-knowledge property of interactive proof systems. We show for the first time that the quantum statistical, perfect, and computational zero-knowledge properties are preserved under sequential composition of interactive proof systems. In the practical part, we provide implementations of the most important quantum-immune cryptosystems. We present efficiency improvements of some of the alternative cryptosystems. The implementations are very efficient and easily integrate into existing public-key infrastructures. We present comprehensive timings that show that the alternative cryptosystems are competitive or even superior compared to established cryptosystems. Finally, we present a new cryptographic API that is particularly well-suited for resource-constrained devices like mobile phones and PDAs. With this API, the alternative cryptosystems can also be used with these devices.
Zero knowledge protocol is a basic method of cryptography,which means that the certifier owns a secret,and it doesn′t reveal any other useful information about the secret to verifier when authenticated.The advantage is to keep its identity recognized without being substituted and useful information not revealed.However,the presently known typical zero knowledge proof is based on computing complexity.According to the basic thought of classical zero knowledge protocol,a scheme for quantum zero knowledge protocol in a group using a mode of quantum secure communication is designed.
In quantum zero knowledge, the assumption was made that the verifier is only using unitary operations. Under this assumption, many nice properties have been shown about quantum zero knowledge, including the fact that Honest-Verifier Quantum Statistical Zero Knowledge ($HVQSZK$) is equal to Cheating-Verifier Quantum Statistical Zero Knowledge ($QSZK$) (see ~\cite{Wat02,Wat06}). In this paper, we study what happens when we allow an honest verifier to flip some coins in addition to using unitary operations. Flipping a coin is a non-unitary operation but doesn\'t seem at first to enhance the cheating possibilities of the verifier since a classical honest verifier can flip coins. In this setting, we show an unexpected result: any classical Interactive Proof has an Honest-Verifier Quantum Statistical Zero Knowledge proof with coins. Note that in the classical case, honest verifier $SZK$ is no more powerful than $SZK$ and hence it is not believed to contain even $NP$. On the other hand, in the case of cheating verifiers, we show that Quantum Statistical Zero Knowledge where the verifier applies any non-unitary operation is equal to Quantum Zero-Knowledge where the verifier uses only unitaries. One can think of our results in two complementary ways. If we would like to use the honest verifier model as a means to study the general model by taking advantage of their equivalence, then it is imperative to use the unitary definition without coins, since with the general one this equivalence is most probably not true. On the other hand, if we would like to use quantum zero knowledge protocols in a cryptographic scenario where the honest-but-curious model is sufficient, then adding the unitary constraint severely decreases the power of quantum zero knowledge protocols.
This paper studies the complexity classes QZK and HVQZK of problems having a quantum computational zero-knowledge proof system and an honest-verifier quantum computational zero-knowledge proof system, respectively. The results proved in this paper include: (a) HVQZK = QZK, (b) any problem in QZK has a public-coin quantum computational zero-knowledge proof system, (c) any problem in QZK has a quantum computational zero-knowledge proof system of perfect completeness, and (d) any problem in QZK has a three-message public-coin quantum computational zero-knowledge proof system of perfect completeness with arbitrarily small constant error in soundness. All the results above are unconditional and do not rely any computational assumptions. For the classes QPZK, HVQPZK, and QSZK of problems having a quantum perfect zero-knowledge proof system, an honest-verifier quantum perfect zero-knowledge proof system, and a quantum statistical zero-knowledge proof system, respectively, the following new properties are proved: (e) HVQPZK = QPZK, (f) any problem in QPZK has a public-coin quantum perfect zero-knowledge proof system, (g) any problem in QSZK has a quantum statistical zero-knowledge proof system of perfect completeness, and (h) any problem in QSZK has a three-message public-coin quantum statistical zero-knowledge proof system of perfect completeness with arbitrarily small constant error in soundness. It is stressed that our proofs are direct and do not use complete promise problems or those equivalents. This gives a unified framework that works well for all of quantum perfect, statistical, and computational zero-knowledge proofs, and enables us to prove properties even on the computational and perfect zero-knowledge proofs for which no complete promise problems are known.
Zero-knowledge proof system is an important protocol that can be used as a basic block for construction of other more complex cryptographic protocols. An intrinsic characteristic of a zero-knowledge systems is the assumption that is impossible for the verifier to show to a third part that he has interacted with the prover. However, it has been shown that using quantum correlations the impossibility of transferring proofs can be successfully attacked. In this work we show two new protocols for proof transference, being the first one based on teleportation and the second one without using entangled states.
Rahul Jain, Alexandra Kolla, Gatis Midrijānis, Ben W. Reichardt
Let L be a language decided by a constant-round quantum Arthur-Merlin (QAM)\nprotocol with negligible soundness error and all but possibly the last message\nbeing classical. We prove that if this protocol is zero knowledge with a\nblack-box, quantum simulator S, then L in BQP. Our result also applies to any\nlanguage having a three-round quantum interactive proof (QIP), with all but\npossibly the last message being classical, with negligible soundness error and\na black-box quantum simulator.\n These results in particular make it unlikely that certain protocols can be\ncomposed in parallel in order to reduce soundness error, while maintaining zero\nknowledge with a black-box quantum simulator. They generalize analogous\nclassical results of Goldreich and Krawczyk (1990).\n Our proof goes via a reduction to quantum black-box search. We show that the\nexistence of a black-box quantum simulator for such protocols when L notin BQP\nwould imply an impossibly-good quantum search algorithm.\n
H. Imai, Kirill Morozov, Anderson C. A. Nascimento, Andreas Winter
Bit commitment is an important tool for constructing zero-knowledge proofs and multi-party computation. Unconditionally secure bit commitment can be based, in particular, on noisy channel or correlation where noise considered a valuable resource. Recently, Winter, Nascimento and Imai introduced the concept of commitment capacity, the maximal ratio between the length of a string which the sender commits to and the number of times the noisy channel/correlation is used. They also proved that for any discrete memoryless channel there exists a secure protocol achieving its commitment capacity however, no particular construction was given. Solving their open question, we provide an efficient protocol for achieving the commitment capacity of discrete memoryless systems (noisy channels and correlations).
Watrous had presented the first proof of zero-knowledge property of a proof system against a quantum verifier. The key of the proof is the construction of a quantum simulator. In the construction, the 'failure state' is rotated to the 'success' state by a tricky operation which is initially developped for the amplification of QMA proof systems. This manuscript presents a new and simpler construction of a simulator. In the construction, we simply amplify the success probability of a classical simulator using Grover's amplification.
The cut polytope of a graph arises in many fields. Although much is known about facets of the cut polytope of the complete graph, very little is known for general graphs. The study of Bell inequalities in quantum information science requires knowledge of the facets of the cut polytope of the complete bipartite graph or, more generally, the complete k-partite graph. Lifting is a central tool to prove certain inequalities are facet inducing for the cut polytope. In this paper we introduce a lifting operation, named triangular elimination, applicable to the cut polytope of a wide range of graphs. Triangular elimination is a specific combination of zero-lifting and Fourier-Motzkin elimination using the triangle inequality. We prove sufficient conditions for the triangular elimination of facet inducing inequalities to be facet inducing. The proof is based on a variation of the lifting lemma adapted to general graphs. The result can be used to derive facet inducing inequalities of the cut polytope of various graphs from those of the complete graph. We also investigate the symmetry of facet inducing inequalities of the cut polytope of the complete bipartite graph derived by triangular elimination.
This paper proves that several interactive proof systems are zero-knowledge against general quantum attacks. This includes the well-known Goldreich–Micali–Wigderson classical zero-knowledge protocols for graph isomorphism and graph 3-coloring (assuming the existence of quantum computationally concealing commitment schemes in the second case). Also included is a quantum interactive proof system for a complete problem for the complexity class of problems having honest verifier quantum statistical zero-knowledge proofs, which therefore establishes that honest verifier and general quantum statistical zero-knowledge are equal: $\mathrm{QSZK}= \mathrm{QSZK}_{\mathrm{HV}}$. Previously no nontrivial interactive proof systems were known to be zero-knowledge against quantum attacks, except in restricted settings such as the honest verifier and common reference string models. This paper therefore establishes for the first time that true zero-knowledge is indeed possible in the presence of quantum information and computation.
We study two group theoretic problems, GROUP INTERSECTION and DOUBLE COSET MEMBERSHIP, in the setting of black-box groups, where DOUBLE COSET MEMBERSHIP generalizes a set of problems, including GROUP MEMBERSHIP, GROUP FACTORIZATION, and COSET INTERSECTION. No polynomial-time classical algorithms are known for these problems. We show that for solvable groups, there exist efficient quantum algorithms for GROUP INTERSECTION if one of the underlying solvable groups has a smoothly solvable commutator subgroup, and for DOUBLE COSET MEMBERSHIP if one of the underlying solvable groups is smoothly solvable. We also study the decision versions of STABILIZER and ORBIT COSET, which generalizes GROUP INTERSECTION and DOUBLE COSET MEMBERSHIP, respectively. We show that they reduce to ORBIT COSET under certain conditions. Finally, we show that DOUBLE COSET MEMBERSHIP and DOUBLE COSET NONMEMBERSHIP have zero knowledge proof systems.
In this paper we propose a definition for (honest verifier) quantum statistical zero-knowledge interactive proof systems and study the resulting complexity class, which we denote QSZK/sub HV/. We prove several facts regarding this class, including: the following problem is a complete promise problem for QSZKHV: given instructions for preparing two mixed quantum states, are the states close together or far apart in the trace norm metric? This problem is a quantum generalization of the complete promise problem of Sahai and Vadhan (1997) for (classical) statistical zero-knowledge; QSZK/sub HV/ is closed under complement; QSZK/sub HV//spl sube/PSPACE. (At present it is not known if arbitrary quantum interactive proof systems can be simulated in PSPACE even for one-round proof systems); any polynomial-round honest verifier quantum statistical zero-knowledge proof system can be simulated by a two-message (i.e., one-round) honest verifier quantum statistical zero-knowledge proof system. Similarly, any polynomial-round honest verifier quantum statistical zero-knowledge proof system can be simulated by a three-message public-coin honest verifier quantum statistical zero-knowledge proof system. These facts establish close connections between classical statistical zero-knowledge and our definition for quantum statistical zero-knowledge, and give some insight regarding the effect of this zero-knowledge restriction on quantum interactive proof systems. The relationship between our definition and possible definitions of general (i.e., not necessarily honest) quantum statistical zero-knowledge are also discussed.