If I understand correctly, a Fujisaki commitment is as follows: $g^m \cdot h^r $ mod $n$, where $m$ is a message, $r$ is a random number, there exists $a$ such that $h^a = g$, and $n$ is an RSA modulus.

Usually, when I read discussions about this scheme, the holder of the commitment does not know the prime factorization of $n$.

Is it a requirement that the order of the group be unknown to the creator of the commitment? (Note added assumption below.)

EDIT: Note that the message can be replaced with $m+k\cdot \lambda(n)$, where $\lambda(n)$ is the order of $n$. Though this is a threat to the commitment, I am more concerned with commitments of small values ($m << \lambda(n)$), so opening the commitment like this would be rejected. So I will rephrase:

Assuming $m << \lambda(n)$, is a Fujisaki Commitment binding if the prime factorization of $n$ is known?

  • $\begingroup$ What happens if you claim to reveal $m + k\lambda(n)$ for any $k$? Can the verifier tell that you've done so instead of returning a message $m < \lambda(n)$? $\endgroup$ – Squeamish Ossifrage Jun 20 '19 at 16:50
  • $\begingroup$ I didn't consider that because, in my use case, I have a range of possible expected values enforced by a range proof. $m + k \lambda(n)$ would be far outside this range. But, in general, this is correct. Especially considering that the other party probably doesn't know the order of $n$. $\endgroup$ – Zarquan Jun 20 '19 at 17:20

Yes! Note that in the original scheme there are two secrets the committer does not know:

  1. The factorization of the modulus: $N=pq$
  2. The value $a$ such that $h^a=g$.

Therefore, the commitment scheme is still binding, even if the factorization is known. Let's assume committer wants to open the commitment $c=g^m h^r \mod N$ to a different $(m^{*},r^{*})$. It means that she needs to find values $(m^{*},r^{*})$ such that:

$$g^m h^r=g^{m^{*}}h^{r^{*}} \mod N $$

$$\iff g^{m-m^{*}}h^{r-r^{*}}=(h^a)^{m-m^{*}}h^{r-r^{*}}=1 \mod N $$ Which equivalently gives the following equality in the exponents: $$\iff a(m-m^{*})+(r-r^{*})=0 \mod \phi(N) $$

Even if committer knows $\phi(N)$, she does not know $a$, therefore she cannot break the binding property, unless she additionally breaks the Discrete-Log in $\mathbb{Z}^{*}_p$ or $\mathbb{Z}^{*}_q$.

In most definitions of the Fujisaki commitment scheme, $N$ is chosen to be a product of safe primes, so commiter cannot even use Pohlig–Hellman algorithm efficiently, to calculate discrete logs modulo primes.

Trivially, if also $a$ is known to committer, then she can decommit to any $m^{*}$ by choosing an appropriate $r^{*}$ through solving the last equation in the exponents.


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.