### 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.

Available format(s)
Category
Public-key cryptography
Publication info
Published elsewhere. MINOR revision.SECITC 2020
Keywords
RSAmoduliprescribed bitsfactoringattestation
Contact author(s)
david naccache @ ens fr
History
2021-01-22: revised
See all versions
Short URL
https://ia.cr/2021/052

CC BY

BibTeX

@misc{cryptoeprint:2021/052,
author = {Rémi Géraud-Stewart and David Naccache},
title = {Elementary Attestation of Cryptographically Useful Composite Moduli},
howpublished = {Cryptology ePrint Archive, Paper 2021/052},
year = {2021},
note = {\url{https://eprint.iacr.org/2021/052}},
url = {https://eprint.iacr.org/2021/052}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.