Zero Knowledge Protocol
Zero knowledge (ZK) proofs are probabilistic and interactive protocols that enable one party to prove to another that an assertion is true without conveying anything other than the veracity of the assertion. ZK proofs have applications in complexity theory and cryptography, and they have had a dramatic effect on cryptographic protocol design. ZK arguments are ZK proofs in which the prover is restricted to polynomial time and is given a witness to the validity of the assertion to be proved.
Zero-Knowledge Protocols Research
A classical question in the theory of zero knowledge is whether there exist 3-round, negligible-error zero-knowledge proofs or arguments for NP. Hada and Tanaka provided a positive answer. They demonstrated the existence of such arguments based on a pair of non-standard assumptions. We showed that one of their assumptions is false. This rendered their results vacuous. We recovered these results, however, under a suitably-modified new assumption. What We find most interesting about this work is that it shows that it is possible to falsify an assumption which, due to its nature and quantifier-structure, does not seem to be "efficiently falsifiable."
Another problem We are interested in is the construction of zero-knowledge sets. ZK sets allow a polynomial-time prover to commit to a finite set of strings S so that, later on, it can prove for any string x whether x is in S or x is not in S, without revealing any knowledge beyond the veracity of these membership assertions. All of the constructions proposed to date are based on the common-reference-string model and they are noninteractive, i.e., both the initial commitment and the proofs require a single message from the prover to the verifier. In a multi-party setting, a party that receives a commitment and a non-interactive proof of an assertion can do something that it could not do before interacting with the prover, namely it can send the same commitment and proof to a third party. In some applications, however, the transcript of an interaction between parties must not yield any evidence of the interaction. To address this issue, We have defined deniable zero-knowledge sets. These allow a prover to commit to a set and then prove membership assertions, without transferring the ability to prove such assertions or providing any other evidence of an interaction. We show how to transform any zero-knowledge set into a deniable zero-knowledge set. Unfortunately, the transformation is not efficient. We are currently searching for more efficient constructions.