# Are Fujisaki commitments binding if the factorization of the group is known?

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?

• 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)$? – Squeamish Ossifrage Jun 20 '19 at 16:50
• 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$. – Zarquan Jun 20 '19 at 17:20

## 1 Answer

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.