RSA accumulator is an authenticated set built from cryptographic assumptions in hidden-order groups such as $\mathbb{Z}^\times_N$. Any set $S=\{e_1,e_2,\ldots,e_n\}$ can be commited via a commitment $c=g^{\prod_{i\in[n]} \mathsf{H}(e_i)}\in\mathbb{Z}^\times_N$ where $\mathsf{H}:S\rightarrow\mathbb{P}$ is a random oracle that maps the set $S$ to the set of primes $\mathbb{P}$. The memebership proof $\pi_j=g^{\prod_{i\in[n]\setminus \{j\}} \mathsf{H}(e_i)}=c^{1/\mathsf{H}(e_j)}\in\mathbb{Z}^\times_N$ allows anyone to verify $e_j\in S$ if and only if $c=(\pi_j)^{\mathsf{H}(e_j)}$.

My question is what if the commiter commits $c=\pm1$ dishonestly. Then for any odd prime $\mathsf{H}(e_j)$ the membership proof $\pi_j=\pm 1$ (respectively) will fool the verifier. Eliminating $\pm 1$ resolves the issue but does not it eliminate honestly computed commitments too? Or is there any reason to believe that the commitment $c$ can never be $\pm 1$ in the above setting?


1 Answer 1


It has been resolved using the discussion of the following question,
Is it possible to have square-free order(s) in $\mathbb{Z}^\times_N$?

In conclusion, the commitment $c=\pm 1$ can be eliminated safely with these three realistic assumptions,

i) $N=(2p+1)(2q+1)$ is a product of two safe primes $p'=2p+1$ and $q'=2q+1$.
ii) $\mathsf{H}$ maps each $e_i$ to odd primes except $p$ and $q$.
iii) The element $g$ is chosen to be $1<g<p'-1$ and $1<g<q'-1$.

Now, we prove that $c\ne\pm 1$ in the above setting.

Denote $d$ as the order of $g$, so $d$ divides the order of $\mathbb{Z}^\times_N$ that is $4pq$. Let, $m=\prod_{i\in[n]} \mathsf{H}(e_i)$ be the exponent. Since, $\mathsf{H}(e_i)$s are odd, $m$ is odd.

If $g^m=1$ then $d$ divides $m$. So, $d$ divides $\mathsf{gcd}(m,4pq)=1$ which implies $d=1$. In $\mathbb{Z}^\times_N$, the only element with order $d=1$ is the identity $1$ itself. But, $g>1$, so, $c\ne 1$.
Similarly, if $g^m=-1$ then $g^{2m}=1$, so $d$ divides $2m$. So, $d$ divides $\mathsf{gcd}(2m,4pq)=2$ which implies $d=2$. It means either $g=-1 \pmod{p'}$ or $g=-1 \pmod{q'}$ or both i.e., $g=-1 \pmod{N}$. Hence, $g\ge p'-1$ or $g\ge q'-1$. But, $g< p'-1$ and $g< q'-1$. Hence, $c\ne-1$.


Your Answer

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

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