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

By Jan Camenisch, Markus Michels. 1998

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.

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

Citations in the corpus

Privacy-Preserving Ridge Regression on Hundreds of Millions of Records (2013, methodology): “The commitment scheme we use is based on Pedersen commitments [18] and we use standard zero-knowledge protocols to prove modular arithmetic relations between the committed values [19], [20] as well as conjunctions of such arithmetic relations [21].”
Modern Cryptography: Theory and Practice (2003, background): “, van de Graaf and Peralta [291], Camenisch and Michels [63], Gennaro, Miccianicio and Rabin [120].”
Floating Car Data from Smartphones : What Google and Waze Know About You and How Hackers Can Control Traffic (2013, background): “The provider proves in zero-knowledge that n is a special RSA modulus, and that the generators of the RSA group are quadratic residues modulo n [7].”
A Certifying Compiler for Zero-Knowledge Proofs of Knowledge Based on Sigma-Protocols (2010, background): “Examples include voting schemes [3], biometric authentication [4], group signatures [5], interactive verifiable computation [6], e-cash [7], and secure multiparty computation [8].”
Evaluating 2-DNF Formulas on Ciphertexts (2005, background): “(a) Bob proves to Alice in zero knowledge that n is a product of two primes [3, 35, 16, 7].”
A Signature Scheme with Efficient Protocols (2002, methodology): “– Proof that a committed value is the product of two other committed values [8].”
1-out-of-n Signatures from a Variety of Keys (2002, methodology): “[7, 6], but they are less efficient than the Schnorr or the GQ signatures both in computation and storage.”
An Accumulator Based on Bilinear Maps and Efficient Revocation for Anonymous Credentials (2009, methodology): “In the common parameters model, we use several previously known results for proving statements about discrete logarithms, such as (1) proof of knowledge of a discrete logarithm modulo a prime [26], (2) proof of knowledge of equality of some elements in different representation [27], (3) proof that a”
An Efficient System for Non-transferable Anonymous Credentials with Optional Anonymity Revocation (2001, background): “entity that verifies, through a zero-knowledge protocol with Oi, that nOi is the product of two safe primes (see [ 13 ] for how this can be done efficiently)and that the elements aOi ,b Oi ,d Oi ,g Oi ,h Oi are indeed in QRnOi (see, for example, Goldwasser et al. [31]).”
Distributed Differentially Private Averaging with Improved Utility and Robustness to Malicious Parties (2020, methodology): “We denote this proof as This proof is inspired by the more general proof of modular sum proposed in [20].”
Anonymous credentials light (2013, background): “It is also important to note that there are efficient zero-knowledge proof protocols for proving that a commitment C is to a particular set of values; or to a set of values that satisfy a rich class of relations [7, 14, 19].”
Cryptϵ: Crypto-Assisted Differential Privacy on Untrusted Servers (2019, unknown): “ollects all the ciphertexts and proofs from the data owners and computes c = P 1(D˜ 1,···,D˜ m). Additionally, it constructs a ZKP that c is indeed the output of executing P 1 on D˜ = {D˜ 1,···,D˜ m} [24]. Formally, the proof statement is c = P 1(D˜ 1,···,D˜ m)∧∀i Open(Com i)= MAC mk i (D˜ i)(2) The”
Compact E-Cash (2005, methodology): “In the common parameters model, we use several previously known results for proving statements about discrete logarithms, such as (1) proof of knowledge of a discrete logarithm modulo a prime [39] or a composite [33, 29], (2) proof of knowledge of equality of representation modulo two (possibly diff”
Direct anonymous attestation (2004, background): “However, proving that a modulus is a safe-prime product is rather inefficient [11] and hence the setup of these schemes is not really practical.”
A Practical and Provably Secure Coalition-Resistant Group Signature Scheme (2000, background): “GM also needs to provide a proof that n is the product of two safe primes ([CM99a] shows how this can be done).”