id: 00025946
dt: j
an: 00025946
au: Boyar, Joan; Friedl, Katalin; Lund, Carsten
ti: Practic zero-knowledge proofs: Giving hints and using deficiencies.
so: J. Cryptology 4, No.3, 185-206 (1991).
py: 1991
pu: Springer-Verlag, New York, NY
la: EN
cc: 
ut: efficiency; number-theoretic problems; zero-knowledge proof
ci: 
li: doi:10.1007/BF00196727
ab: 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.
rv: M.De Soete (Brussels)