4
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.