3
$\begingroup$

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$?
$\endgroup$
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I am using Java, and generating primes with BigInteger.probablePrime(int bitLength, Random rnd) and a SecureRandom for the RNG. I am willing to generate $p$ and $q$ as safe-primes, especially if it makes it easier, but I'm unaware of any method to ensure it is a safe prime other than generating primes at random and checking that they are safe primes or Sophie Germain primes. I assume there is a more reliable method? $\endgroup$ – Mike Carpenter Sep 24 '15 at 15:56
  • $\begingroup$ @MikeCarpenter: there are moderately faster ways to find Sophie Germain primes (as you can sieve for values $p$ for which neither $p$ nor $(p-1)/2$ has a small factor before doing the Miller-Rabin tests); however I wouldn't know if Java provides such a facility. $\endgroup$ – poncho Sep 24 '15 at 16:14
  • $\begingroup$ I am sure I can find a way to do so. Since that is outside the scope of the original question, which you answered wonderfully, I'll do my own research on that. I don't expect it should be as difficult to find information as this was, since it is much more general! $\endgroup$ – Mike Carpenter Sep 24 '15 at 16:19

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.