Number generation for Fujisaki-Okamoto commitment scheme parameters

Question

I need to implement the Fujisaki-Okamoto commitment scheme for a project such that I can demonstrate performance of various zero-knowledge proofs in relation to one another, for example Boudot's "proof that a committed number belongs to an interval" (see §3.1 if you are interested in what this entails, though it is not directly relevant) among others. In the Fujisaki-Okamoto commitment scheme, a message $x$ is committed as $C=g^{x}h^{r}\mod{n}$. ($r$ is a random value in $ℤ^{*}_{n}$).

This requires me to generate numbers $n$, $g$, and $h$ where $n$ is a large composite number whose factorization is unknown to Alice and Bob. I have implemented it as $n=pq$, where $p$ and $q$ are both large primes such that the discrete logarithm problem is unfeasible, so I know its factorization behind-the-scenes. However $p$ and $q$ are dynamically generated each time I create an instance, so they are not static although I save their values (the chance that they are composite does not exceed $2^{-100}$). As for $g$ and $h$, "$g$ is an element of large order in $ℤ^{*}_{n}$, and $h$ is an element of large order of the group generated by $g$" (such that the discrete logarithm of [$h$ in base $g$] and of [$g$ in base $h$] are unknown by Alice).

Unfortunately, this is very difficult for me to Google as I really don't know how to start here. I can't find much about Fujisaki-Okamoto scheme at all, actually, but my problem is not in using it but in how to generate these numbers to get it working in the first place.

Basically my question comes down to two things:

1. What are the theoretical requirements behind $h$ and $g$ in this scheme?
2. What algorithms can be used to generate $g$ and $h$?

Answer 1

If you can select the distinct secret primes $p$ and $q$ such that $(p-1)/2$ and $(q-1)/2$ are also prime, then it becomes easy. For a random value $r$, $g = r^2$ will have order precisely $(p-1)(q-1)/4 \approx n/4$ unless $r, r-1$ or $r+1$ happens to not be relatively prime to $n$ (which, if you select $r$ randomly in the range $[2, n-2]$, happens with probability less than $3/p + 3/q$, which is negligible. And, if you select $h$ the same way (select a different random value $s$ and square it $h = s^2$), then it is guaranteed to be in the group generated by $g$.

So, it boils down to:

• When it comes time to select $p$ and $q$, select safe primes (which takes rather a bit more time, but is still doable)

• To select $g$ and $h$, select independent random values $r, s \in [2, n-2]$, and set $g = r^2 \bmod n$ and $h = s^2 \bmod n$

You could replace that last step by selecting a random exponent $\lambda$ and computing $h = g^\lambda$; I assume that you would prefer not knowing the discrete log of $h$ yourself.