3
$\begingroup$

I'm implementing the Camenish-Lysyanskaya dynamic accumulator. It seems to me that the accumulator is provably secure because the trapdoor is unknown to the attacker.

The risks should be the fact that, given the Euler theorem, I can forge an element that is was not accumulated but still passes the test, namely:

$v^x\equiv v^{x\mod\phi}\mod n$

where $v$ is the accumulator without $x$, $\phi$ is the Euler function, and

$x\mod\phi\equiv x_f$

so we have a forged $x$ that passes the test.

What if I don't care about the factorization of n and I even publish $\phi$, but I just require that an acceptable integer $x_{acc}$ must be $A<x_{acc}<A+\phi$ with $A<\phi$.

This means that if, for example my input is the string "user1" this string will be hashed into an integer in the accepted interval.

If $\phi$ is large enough, I still can defy collisions and stop caring about keeping $\phi$ secret. All the possibly forged inputs fall automatically out of the specified interval so they will be discarded immediately. In other words there is no valid integer congruent to integer that maps the input "user1"

What do you think? Is this feasible? Or am I missing something obvious? I understand I may have skipped something important, I am not in the field, please ask for clarifications.

|improve this question
$\endgroup$
4
$\begingroup$

I guess you are missing something.

If you know that the accumulator value is $a=v^{\prod_i x_i} \bmod n$ to a set of values $x_i$ and you know the factorization of $n$, then it is easy to for any arbitrary $y$ relatively prime to $n$ (in RSA accumulators you accumulate primes) a value $k$ such that $y\cdot k \equiv 1 \pmod{\varphi(n)}$ as the value $\varphi(n)$ is public. So anyone can pretend that any arbitrary value $y$ has been accumulated using $a^k$ as the membership witness and note that the verification $a\equiv (a^k)^y \bmod n$ holds. I guess that you would not like to have that "feature".

So either you make the factorization not public (use a trusted setup) or if this is not possible you can go with trapdoor free RSA accumulators (basically by computing an RSA modulus in a way that the factorization is unknown to anybody).

|improve this answer
$\endgroup$
  • $\begingroup$ @gurghet nope, you can choose $y$ as you want and then compute $k$ such that the equation holds. $\endgroup$ – DrLecter Apr 26 '14 at 0:48
  • $\begingroup$ It seems from what you write that you accumulate yk not y alone. Moreover, and this may be the dealbreaker i forgot to mention, A is actually smaller than phi, so yk even for k=2 is outside of the acceptable range $\endgroup$ – gurghet Apr 26 '14 at 1:06
  • $\begingroup$ @gurghet nope, you can freely choose $y$ (whatever size you want) and then compute $k$ (you have to compute such a "$k$" for every "honestly" accumulated value and you cannot distinguish then from from honestly computed ones....that's the problem... $\endgroup$ – DrLecter Apr 26 '14 at 1:15
  • $\begingroup$ Are you talking about collisions in the input, isn't that a separate problem? I mean, if phi thends to infinity, you obviously can't find such a k. But the thing i don't understand is why should I let an attacker choose the k? The attacker is allowed to give me the raw input not the item to be checked itself. $\endgroup$ – gurghet Apr 26 '14 at 1:34
  • 1
    $\begingroup$ @gurghet If you want to use an accumulator in the public then it has to be trapdoor-free, i.e., if you use an RSA accumulator no one must know the factorization. You would have to compute the modulus in a multiparty fashion such that no party knows the factorization. If you switch to DL accumulators (without the restriction to accumulate primes) you have the same problem with the trapdoor. Btw. why do you want to publish the factorization? Is this bitcoin stuff you are doing? $\endgroup$ – DrLecter Apr 26 '14 at 6:54

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.