Paper 2021/077

Magnetic RSA

Rémi Géraud-Stewart and David Naccache

Abstract

In a recent paper Géraud-Stewart and Naccache \cite{gsn2021} (GSN) described an non-interactive process allowing a prover $\mathcal{P}$ to convince a verifier $\mathcal{V}$ that a modulus $n$ is the product of two randomly generated primes ($p,q$) of about the same size. A heuristic argument conjectures that $\mathcal{P}$ cannot control $p,q$ to make $n$ easy to factor. GSN's 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. This paper proposes an alternative process applicable in settings where $$ co-generates a modulus $$ with a certification authority $$. If $$ honestly cooperates with $$, then $$ will only learn the sub-products $$ and $$. A heuristic argument conjectures that at least two of the factors of $$ are beyond $$'s control. This makes $$ appropriate for cryptographic use provided that \emph{at least one party} (of $$ and $$) is honest. This heuristic argument calls for further cryptanalysis.