*Bounty: 500*

*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 primeif 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.