Practic zero-knowledge proofs: Giving hints and using deficiencies (Q1180509)

The paper presents a practical zero-knowledge proof for a special case of primitivity. The protocol, which shows that an element of the multiplicative group module a prime \(p\) is a generator, only requires that the prover be probabilistic polynomial time, though he must know the complete factorization of \(p-1\). Other known protocols for this proof make use of the computation of discrete logarithms. Here the authors get round this problem by having the verifier giving the prover ``hints'' which will help the last one to find the discrete logarithms in question. Unfortunately, the part of the protocol which shows that an element is a primitive fails in some cases if \(p-1\) has large square factors. However, this failure is so well-defined that the authors can use it in a zero- knowledge proof that a number \(n\) is not square, free. However, this proof is zero-knowledge only under a certain reasonable intractability assumption and is thus only computational zero-knowledge rather than perfect or statistical zero-knowledge. The protocol does not, however, involve any bit encryptions (blobs). Those ``blobs'' have been used before in all previous ``natura'' zero-knowledge proofs for this problem.