# Feasible to find two sets with the same RSA accumulator value if a prime representative hash function is used?

Consider the RSA accumulator scheme with random oracle as proposed by Barić and Pfitzmann, with the random oracle replaced by a secure hash function $H$ as follows.

For a set $S$, the accumulator value is computed as $acc(S) = x^{\prod_{s \in S} h(s)} \mod N$, where $h(s)$ computes prime representatives by appending $l$ suitable bits to $H(s)$: $h(s) = 2^l H(s) + d$ (using a large enough fixed $l$, and $d$ chosen such that $h(s)$ becomes prime).

Can someone with knowledge of the factorisation of the RSA modulus efficiently compute two distinct sets of elements $S, S'$ that evaluate to the same accumulator value?

While this variant of the RSA accumulator scheme is not universally collision-free because it allows forging of membership proofs for arbitrary elements with knowledge of the factorisation, I can't think of a way how to compute a complete set of elements that evaluates to a particular accumulator value, or to find two sets that evaluate to the same value without computing a preimage of $H$. However I also couldn't find a proof that it is not feasible.

If you are the one to pick $x$ and $N$, finding collisions and second preimages is feasible (and it would appear to be possible while not jeopardizing the security of the system).

Here is one possible approach:

• Search for a set of $n$ preimages $s_0, s_1, ..., s_{n-1}$ such that:

• $\prod h(s_i) -1 = k r$, for a prime $r$ between, say, 256 and 512 bits. This can be done by selecting a set such that the product is about the right size, and checking if the value is a large prime times a smooth number.

• Then, select $p = k'r + 1$ and $q = k''r + 1$, both primes of the appropriate size (at least 1024 bits each), and set $N = pq$

• Then, select $x$ such that the order of $x$ mod $p$ is $r$ and the order mod $q$ is $r$

Publish $N$ and $x$ as the system parameters.

Then, when someone has an accumulation of the set $t_0, t_1, …, t_m$, you can display a second accumulation $t_0, t_1, …, t_m, s_0, s_1, …, s_{n-1}$, which hashes to the same value.

That's because $h(s_0)h(s_1)...h(s_{n-1}) \equiv 1 \pmod r$, and $r$ is the order of $x$, and hence $x^{h(s_0)h(s_1)...h(s_{n-1})} \equiv 1 \pmod N$

Furthermore, I believe that:

• The knowledge of the special form of $N$ (not counting the exact value of $r$) and the knowledge of $x$ does not make $N$ easier to factor

• It appears infeasible, given $N$ and $x$, to determine whether this is being done.

Please let me focus on "hashing to primes" idea.

It is an attractive idea to represent a set with a product of some primes. However, just primes might be not the best choice. For example, what if a pair of distinct $(d_1, d_2)$ exists such that both result in primes $h_1(s)$ and $h_2(s)$? Avoiding this kind of collisions could mean a non-standard requirements for $H()$.

Fortunately we have a map to linear polynomials, plenty of them, that are always relatively prime for distinct set elements: $h(s, z) = 1 + sz$. Bonus: graph representation with bivariate polynomials, IACR 2008/363.

Testing polynomial identity could be done by evaluating at a random point, suggested by Schwartz and Zippel independently, and widely used as an obvious idea. This could be a hidden random point (called toxic waste) evaluated with bilinear pairing.