# Choosing a suitable prime for accumulators

I am trying to work out accumulators and generate $$S = \{ e_1,e_2 \ldots, e_n \}$$ from this (Section 3.4 - Choosing a Suitable Prime).

For each element of $$e_i$$ compute its representation $$x_i$$.(This I want to calculate).

To compute representation($$x_i$$) use following ( According to the paper $$x_i$$ should be calculated like this and this part I need help with. Please help me understand this)

We are interested in obtaining a prime solution of the linear system, that represents a Universal-2 hash function.

Lemma: Let H be a universal-2 family from $$\{0,1\}^{3k}$$ to $$\{0,1\}^k$$. Then, for all but a $$2^{-k}$$ fraction of the functions $$h \in H$$. For every $$e \in \{0,1\}^k$$ a fraction of at least $$1/ck$$ of the elements in $$f^{-1}(e)$$ are primes, for some small constant c.

We accept a prime inverse only if it is greater than $$\sqrt{2^{3k}}$$. Since domain of H is $$\{0,1\}^{3k}$$. So, by the results of prime number theory, the density of big prime numbers that are less than $$2^k$$ is about $$1/2k$$ for all but a $$2^{\Omega(k)}$$ fraction of functions in family H.*

Please help me, how can I calculate $$x_i$$ as a representation of $$e_i$$?

I'll use as reference Michael T. Goodrich, Roberto Tamassia, Jasminka Hasic's An Efficient Dynamic and Distributed RSA Accumulator from arXiv (2009), not the version originally in proceedings of ISC 2002 or linked in the question.

Disclaimer: I discover this paper while writing this answer, thus the following is highly tentative. Further, there are important things that I fail to make sense of, which means my understanding or the paper is wrong. Therefore, do not use the following for anything more serious than an exploration.

### Preliminary: choice of RSA modulus $$N=P\,Q$$, and base $$a$$.

When it is wished to store $$e_i$$ of up to $$k$$ bits, the scheme as described starts by generating “strong primes¹” $$P$$ and $$Q$$ of at least $$3k/2$$ bits each. I believe they additionally need to be at least as large as required for security of RSA (that's not stated). The article's Experimental Results states "the parameter $$N$$ of the RSA accumulator is a 200-bit integer", but if I understand the rest suggests $$k=165$$, which would make $$N$$ 495-bit. Even this would have been too low when the article came out, see this. Such disregard for a safe choice of $$N$$ in both the theoretical and practical parts of the article is crying to be fixed. I'll have a try at that.

The article's reference for “strong primes¹” is the Handbook of Applied Cryptography definition 4.52:

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$$.

In the context of RSA accumulators and problems that rely on the Strong RSA assumption (including the question's scheme), I would require at least (i) to hold for $$P$$ and $$Q$$; and for good measure I'd use safe primes of the same bit size, as required in the article's reference [6], Josh Benaloh and Michael de Mare's One-way accumulators: A decentralized alternative to digital signatures, in proceedings of Eurocrypt 1993 (with extended abstract).

For a modern implementation I would consider $$k=680$$, and $$P$$ and $$Q$$ random 1024-bit safe primes in the interval $$[2^{1023.5},2^{1024})\,$$, which are easy to generate.

Also, it's required “a suitably-large base $$a$$ that is relatively prime to $$N=P \,Q$$”. For lack of other guidance, I'd consider $$a=\lfloor\pi\,2^{2045}\rfloor$$.

### Primes representative of the $$e_i$$ to be accumulated.

The paper defines a function \begin{align}h:\{0,1\}^{3k}&\mapsto\{0,1\}^k\\ x\quad&\to h(x)\underset{\text{def}}=U\times x\end{align} where $$U$$ is a binary matrix of $$k$$ lines and $$3\,k$$ columns. And it defines the prime representative of $$e_i$$ to be accumulated as a prime $$p_i$$ in $$[2^{3k/2},2^{3k})$$ such that $$h(p_i)=e_i$$ (assimilating integers to bitstrings per e.g. big-endian convention).

In order to find $$p_i$$ from $$e_i$$, we can simplify the system of $$k$$ binary equations with $$3k$$ binary unknowns $$U\times x=e_i$$, enumerate solutions at least $$2^{3k/2}$$, and stop at the first prime $$x$$ found. I located no requirement on the enumeration order, but I guess that it must be deterministic, and pseudo-random would not harm.

The rest seems standard use of an RSA accumulator.

¹ Note: In normal RSA, it's dubious that strong primes are really needed nowadays. Condition (i) [resp. (ii)] aims at blocking Pollard's $$p-1$$ [resp. William's $$p+1$$] factoring, but that becomes hopeless as $$p$$ increases (as needed to resist GNFS), and could only really help in multi-target attacks at low parametrization. Condition (iii) aims at blocking a cycling attack but seems pointless, see Ronald L. Rivest and Robert D. Silverman's Are ‘Strong’ Primes Needed for RSA?. None of these conditions are required by the conservative FIPS 186-4 appendix B3 for primes 1024-bit or larger intended for RSA moduli used in signature.

² Nothing in either the paper or the HAC hints at how large in the context of RSA accumulators. The guidance in FIPS 186-4 is not intended for this context; using it for (i) would be adventurous.

• Thanks for your answer. Is there a python library which does all this hard work? – Tabz Oct 23 at 19:07
• @Tabz: not one I know. I'll ping you should that change, you got me hooked on RSA accumulators. – fgrieu Oct 24 at 9:19