What are criteria for generation of an RSA public modulus used in an RSA accumulator, and their rationale? Are there special requirements in some sub-cases, like for «one-way» accumulators?

Josh Benaloh and Michael de Mare's One-way accumulators: A decentralized alternative to digital signatures, in proceedings of Eurocrypt 1993, prescribes the public modulus to be a rigid integer. That's defined as $\,n\,=\,p\,q\,$ with $p$ and $q$ safe primes and $\,|p|\,=\,|q|\,$ (equal bit size). Then $\,n=(2p'+1)\,(2q'+1)\,$ with $p$, $p'$, $q$, $q'$ (large) primes. The subgroup of quadratic residues of $\mathbb Z_n^*$ has order $n'=p'\,q'$. And the function $e_{n,y}(x)\underset{\text{def}}=x^y\bmod n\,$ is a permutation of this group when $\gcd(y,n)=1$. The authors argue:

Thus, if the factorization of $n$ is hidden, “random” exponentiations of an element of this group are extremely unlikely to produce elements of any proper subgroup. This means that repeated applications of $e_n(x,y)$ are extremely unlikely to reduce the size of the domain or produce random collisions.

More precisely, what kind of disaster can strike if we used random primes? Is there a positive security argument relying on safe primes? Also, is there a justification for $\,|p|\,=\,|q|\,$ beyond getting $\,|p|\approx|q|\,$, which helps against ECM factorization?

What about the different recommendations in Michael T. Goodrich, Roberto Tamassia, Jasminka Hasic's An Efficient Dynamic and Distributed RSA Accumulator (arXiv), 2009), originally in proceedings of ISC 2002? They ask strong primes without justification, referencing the HAC's definition:

A prime number $p$ is said to be a strong prime if integers $r$, $s$, and $t$ exist such that the following three conditions are satisfied:
 (i)    $p−1$ has a large prime factor, denoted $r$;
 (ii)   $p+1$ has a large prime factor, denoted $s$; and
 (iii)  $r−1$ has a large prime factor, denoted $t$.

When the application is RSA signature and encryption, these requirements are obsoleted¹ by the need to dimension $\,n\,=\,p\,q\,$ for resistance to GNFS. Are these requirements appropriate in the case of RSA accumulators, and if so for what quantitative meaning of large?

¹ FIPS 186-4 appendix B.3 drops these requirements for 1024-bit or larger primes, and that seems conservative. There's a discussion in Ronald L. Rivest and Robert D. Silverman's Are ‘Strong’ Primes Needed for RSA?, but it does not consider the interest of (i) and (ii) in multi-target attacks, where the adversary's goal is to factor any of many public moduli.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.