1
$\begingroup$

I was reading the paper One-way Accumulators: A Decentralized Alternative to Digital Signatures by Benaloh and de Mare [link], and in section 4.2, they say that given $z\in (\mathbb{Z}/n\mathbb{Z})^*$ and a set $$\{(z^{1/m_1}, m_1),(z^{1/m_2}),\dots, (z^{1/m_k}, m_k)\}$$ with $m_i \in \mathbb{Z}$, computing $z^{1/r}$ for $r \in \mathbb{Z}$ is hard, which I get since the order of $(\mathbb{Z}/n\mathbb{Z})^*$ is unknown.

However, they say that the problem becomes easy if $r \mid m_1m_2\cdots m_k$, and I do not get how it becomes easy.

For the case $k=1$, we have $z, (z^{1/m_1}, m_1) \text{ and } r \mid m_1$, this is easy since $m_1 = k\cdot r$ for $k\in \mathbb{Z}$ and $(z^{1/m_1})^k = z^{1/r}$

For the case $k=2$, when we have $ m_1 m_2 = k^\prime \cdot r$, we can compute $z^{1/m_1}z^{1/m_2} = z^{(m_1+m_2)/m_1m_2}$ and get $z^{(m_1+m_2)/r}$. However, I do not know how to get rid of the value $m_1+m_2$ to obtain $z^{1/r}$

The case $k>2$ seems even harder.

Any hint on how to move forward will be welcomed

Improve this question
$\endgroup$
2
  • $\begingroup$ HINT: Bezout's identity $\endgroup$
    – Daniel S
    Aug 9 at 7:51
  • $\begingroup$ Would it be better to have the title say "r-th root" in $\mathbb Z/n\mathbb Z$? For consistency with the body of your Question. $\endgroup$
    – hardmath
    Aug 9 at 12:40

1 Answer 1

Reset to default
1
$\begingroup$

The key is to use extended euclidean algorithm. Here's a numerical example, see if you can figure it out yourself.

Given $z, a := z^{1 / 3}, b := z^{1 / 5}$, we can compute $z^{1 / 15} = a^{-1} \cdot b^2 = z^{-5 / 15 + 6 / 15}$.

Cheers!

Improve this answer
$\endgroup$
4
  • $\begingroup$ but this only works if for $z^{1/m_1}, z^{1/m_2}$, $m_1$ and $m_2$ are coprime. However, in the paper, they didn't mention something about the gcd of the $m_i$ $\endgroup$
    – vxek
    Aug 9 at 14:24
  • $\begingroup$ @vxek nope, read about extended euclidean algorithm again $\endgroup$
    – Gareth Ma
    Aug 9 at 15:08
  • $\begingroup$ it seems like using extended euclidean algorithm/ Bezout's identity, I can find $z^{1/r}$ if $r = \dfrac{m_1m_2}{\gcd({m_1,m_2})}$ But I am still struggling to see how the $r$-th root is easy if $r$ is a random integer that divides $m_1m_2$ $\endgroup$
    – vxek
    Aug 9 at 15:59
  • $\begingroup$ @vxek Ah, so you are asking how is computing $z^{1 / 24}$ easy when given $z^{1 / 4}$ and $z^{1 / 6}$. Yes, you are correct that it is hard here. The paper assumes that $m_i$ are mutually coprime e.g. when they're all primes. Stop using symbols :) $\endgroup$
    – Gareth Ma
    Aug 9 at 17:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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