#StackBounty: #rsa #key-generation #accumulators Criteria for public modulus of RSA accumulator

Bounty: 500

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^ybmod 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.


Get this bounty!!!

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.