Crate composite_modulus_proofs 

Proofs of properties of RSA or Paillier modulus

Implements the protocols described in the papers Efficient Noninteractive Certification of RSA Moduli and Beyond and UC Non-Interactive, Proactive, Distributed ECDSA with Identifiable Aborts. Also refer this.

For a given composite RSA or Paillier modulus N

• Proof that gcd(x, N) = 1 for a given x
• Proof that N is square free
• Proof that N is product 2 distinct primes
• Proof that N is a Blum integer and square-free
• A more efficient proof that N is a Blum integer and square-free

Uses following math

• Legendre and Jacobi symbols,
• square roots modulo prime and composite numbers,
• checking if a composite number is formed of prime powers.

By default, it uses standard library and rayon for parallelization.

For no_std support, build as

cargo build --no-default-features

and for wasm-32, build as

cargo build --no-default-features --target wasm32-unknown-unknown

Modules

blum_integer

blum_powers

Proof that modulus N is of form p^a*q^b where p and q are Blum primes. Described in section 3.5 of the paper Efficient Noninteractive Certification of RSA Moduli and Beyond

error

gcd_is_one

Proof that gcd(x, phi(N)) = 1 where x is coprime to a composite N and phi is the Euler’s totient Described in section 3.1 of the paper Efficient Noninteractive Certification of RSA Moduli and Beyond

macros

math

Math utilities like Legendre and Jacobi symbols, square roots modulo prime and composite numbers, checking if a composite number is formed of prime powers.

paillier_blum_modulus

Proving that a modulus is a Paillier-Blum modulus, i.e. gcd(N, phi(N)) = 1 for modulus N=p*q where p and q are Blum primes, i.e. p mod 4 = 3 and q mod 4 = 3 using the protocol described in Fig 12, section 5.2 in the paper UC Non-Interactive, Proactive, Distributed ECDSA with Identifiable Aborts

product_of_two_primes

Proof that modulus N is the product of two distinct primes. So N could be of form p*q but not p*q*r or p^a*q^b where p, q and r are primes and a, b > 1. Described in section 3.4 of the paper Efficient Noninteractive Certification of RSA Moduli and Beyond

setup

square_free

Proof that modulus N is square-free. Described in section 3.2 of the paper Efficient Noninteractive Certification of RSA Moduli and Beyond Uses the proof protocol of gcd(x, phi(N)) = 1 where x is set to N since gcd(N, phi(N)) = 1 implies N is square free as per Lemma A.3 of the paper

two_prime_divisors

Proof that modulus N has exactly two distinct prime divisors. So N could be of form p^a*q^b but not p*q*r where p, q and r are primes. Described in section 3.4 of the paper Efficient Noninteractive Certification of RSA Moduli and Beyond

util

Macros

join

report_error_if_any