Paper 2018/013

Hashing solutions instead of generating problems: On the interactive certification of RSA moduli

Benedikt Auerbach and Bertram Poettering

Abstract

Certain RSA-based protocols, for instance in the domain of group signatures, require a prover to convince a verifier that a set of RSA parameters is well-structured (e.g., that the modulus is the product of two distinct primes and that the exponent is co-prime to the group order). Various corresponding proof systems have been proposed in the past, with different levels of generality, efficiency, and interactivity. This paper proposes two new proof systems for a wide set of properties that RSA and related moduli might have. The protocols are particularly efficient: The necessary computations are simple, the communication is restricted to only one round, and the exchanged messages are short. While the first protocol is based on prior work (improving on it by reducing the number of message passes from four to two), the second protocol is novel. Both protocols require a random oracle.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
A minor revision of an IACR publication in PKC 2018
Keywords
RSA parameter validationzero-knowledge proofs
Contact author(s)
bertram poettering @ rhul ac uk
History
2018-01-03: received
Short URL
https://ia.cr/2018/013
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2018/013,
      author = {Benedikt Auerbach and Bertram Poettering},
      title = {Hashing solutions instead of generating problems: On the interactive certification of RSA moduli},
      howpublished = {Cryptology ePrint Archive, Paper 2018/013},
      year = {2018},
      note = {\url{https://eprint.iacr.org/2018/013}},
      url = {https://eprint.iacr.org/2018/013}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.