Paper 2017/640

Non-Interactive Provably Secure Attestations for Arbitrary RSA Prime Generation Algorithms

Fabrice Benhamouda, Houda Ferradi, Rémi Géraud, and David Naccache


RSA public keys are central to many cryptographic applications; hence their validity is of primary concern to the scrupulous cryptographer. The most relevant properties of an RSA public key $(n,e)$ depend on the factors of $n$: are they properly generated primes? are they large enough? is ee co-prime with $\phi(n)$? etc. But of course, it is out of question to reveal nn's factors. Generic non-interactive zero-knowledge (NIZK) proofs can be used to prove such properties. However, generic NIZK proofs are not practical at all. For some very specific properties, specialized proofs exist but such ad hoc proofs are naturally hard to generalize. This paper proposes a new type of general-purpose compact non-interactive proofs, called attestations, allowing the key generator to convince any third party that nn was properly generated. The proposed construction applies to any prime generation algorithm, and is provably secure in the Random Oracle Model. As a typical implementation instance, for a 138-bit security, verifying or generating an attestation requires $k=1024$ prime generations. For this instance, each processed message will later need to be signed or encrypted 14 times by the final users of the attested moduli.

Note: One word was missing from the title / Some non-math LaTeX remained in the abstract.

Available format(s)
Publication info
Published elsewhere. MINOR revision.ESORICS 2017
RSA key generationrandom oraclenon-interactive proof
Contact author(s)
remi geraud @ ens fr
2017-07-06: revised
2017-07-05: received
See all versions
Short URL
Creative Commons Attribution


      author = {Fabrice Benhamouda and Houda Ferradi and Rémi Géraud and David Naccache},
      title = {Non-Interactive Provably Secure Attestations for Arbitrary RSA Prime Generation Algorithms},
      howpublished = {Cryptology ePrint Archive, Paper 2017/640},
      year = {2017},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.