**Authors:** Rosario Gennaro, Daniele Micciancio and Tal
Rabin

5th ACM Conference on Computer and Communication Security, CCS 1998, pages 67--72, San Francisco, California, November 1998. ACM, ACM Press.

**Abstract:** We present efficient zero-knowledge proof
systems for quasi-safe prime products and other related languages. Quasi-safe
primes are a relaxation of safe primes, a class of prime numbers useful in
many cryptographic applications. More specifically we present the first
simple and efficient zero-knowledge proof that an alleged RSA modulus is of
the correct form, i.e. the product of two primes. All previously known proof
enforced only that the modulus was the product of two prime powers. We then
present a zero-knowledge proof that the primes composing the RSA modulus are
quasi-safe. Our proof systems achieve higher security and better efficiency
than all previously known ones. In particular, all our proof systems are
perfect or statistical zero-knowledge, meaning that even a computationally
unbounded adversary cannot extract any information from the proofs. Moreover,
our proof systems are extremely efficient because they do not use general
reductions to NP-complete problems, can be easily parallelized preserving
zero-knowledge, and are non-interactive for computationally unbounded
provers. The prover can also be efficiently implemented given some trapdoor
information and using very little interaction. We demonstrate the
applicability of quasi-safe primes by showing how they can be effectively
used in the context of RSA based undeniable signatures to enforce the use of
``good'' public keys, i.e., keys such that if a signer can convince a
recipient of the validity of a signature, then he won't be able to
subsequently deny the same signature in case of a dispute.