A general zero-knowledge scheme (Q1364207)

An interactive proof is an interactive protocol by which one party, a prover, attempts to convince the other party, a verifier, that a given input string \(I\) is either in a given language (\textit{interactive proof of membership}), or that she 'knows' a witness \(S\) for which \((I,S)\) satisfies a given polynomial-time predicate (\textit{interactive proof of knowledge}). A proof is \textit{zero-knowledge} if its execution reveals no more than is strictly necessary. Many zero-knowledge proofs are known for various problems. In the paper so called \(3t\)-interaction type protocols are of special interest. In such protocols two parties, \(A\) and \(B\) interact in the following way: \(A\) sends a 'cover', \(B\) sends a 'query' and \(A\) answers the query. Then \(B\) checks the answer and if it is valid, the procedure is repeated; after \(t\) successful independent iterations \(B\) accepts. In the paper a general setting for \(3t\)-interaction type zero-knowledge protocols is given and it is shown that many of previously published protocols fit into this setting. First, basic notation and the general protocol are introduced. Then, conditions concerning parameters of the protocol that are necessary for the protocol to be zero-knowledge proof are given (later in the paper it is proved that these conditions are necessary). After that it is shown that a number of known zero-knowledge proofs are particular cases of the general protocol proposed in the paper. Finally, generality of the protocol is discussed and some open problems are outlined.