Proving in Zero-Knowledge that a Number is the Product of Two Safe Primes

Abstract

We present the first efficient statistical zero-knowledge protocols to prove statements such as: - A committed number is a prime. - A committed (or revealed) number is the product of two safe primes, i.e., primes p and q such that (p - 1)=2 and (q - 1)=2 are prime. - A given integer has large multiplicative order modulo a composite number that consists of two safe prime factors. The main building blocks of our protocols are statistical zero-knowledge proofs of knowledge that are of independent interest. We show how to prove the correct computation of a modular addition, a modular multiplication, and a modular exponentiation, where all values including the modulus are committed to but not publicly known. Apart from the validity of the equations, no other information about the modulus (e.g., a generator whose order equals the modulus) or any other operand is exposed. Our techniques can be generalized to prove that any multivariate modular polynomial equation is satisfied, where only commitments to the variables of the polynomial and to the modulus need to be known. This improves previous results, where the modulus is publicly known. We show how these building blocks allow to prove statements such as those listed earlier.