Proving in Zero-Knowledge that a Number is the Product of Two Safe
Primes
Jan Camenisch November 1998 |

## Abstract:This paper presents the first efficient statistical zero-knowledge protocols to prove statements such as: - A committed number is a pseudo-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 primes as well. - A given value is of large order modulo a composite number that consists of two safe prime factors.
The main building blocks of our protocols are
statistical zero-knowledge proofs that are of independent interest. Mainly,
we show how to prove the correct computation of a modular addition, a modular
multiplication, or a modular exponentiation, where all values including the
modulus are committed but We show how a prover can use these building blocks to convince a verifier that a committed number is prime. This finally leads to efficient protocols for proving that a committed (or revealed) number is the product of two safe primes. As a consequence, it can be shown that a given value is of large order modulo a given number that is a product of two safe primes.
Available as |

Last modified: 2003-06-08 by webmaster.