Cryptology ePrint Archive: Report 2021/052

Elementary Attestation of Cryptographically Useful Composite Moduli

Rémi Géraud-Stewart and David Naccache

Abstract: This paper describes a non-interactive process allowing a prover to convince a verifier that a modulus $n$ is the product of two primes ($p,q$) of about the same size. A further heuristic argument conjectures that $p-1$ and $q-1$ have sufficiently large prime factors for cryptographic applications.

The new protocol relies upon elementary number-theoretic properties and can be implemented efficiently using very few operations. This contrasts with state-of-the-art zero-knowledge protocols for RSA modulus proper generation assessment.

The heuristic argument at the end of our construction calls for further cryptanalysis by the community and is, as such, an interesting research question in its own right.

Category / Keywords: public-key cryptography / RSA, moduli, prescribed bits, factoring, attestation

Original Publication (with minor differences): SECITC 2020

Date: received 14 Jan 2021, last revised 21 Jan 2021

Contact author: david naccache at ens fr

Available format(s): PDF | BibTeX Citation

Version: 20210122:030647 (All versions of this report)

Short URL: ia.cr/2021/052