Efficient non-interactive statistical zero-knowledge proof system for quasi-safe prime products

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 trap-door 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 keys of a certain format.