0
$\begingroup$

According to Fiat–Shamir heuristic there are two parameters of the algorithm: big prime number $p$ and primitive root $g$. Thus several questions arise:

  1. How big should the prime number $p$ be? How to select $p$ so that, for example, Pohlig–Hellman algorithm or other known algorithms could not break it?
  2. How to select the primitive root $g$? As far as I know, it is an NP problem
  3. Is it safe to use the same values of $p$ and $g$ for a couple of challenges?
$\endgroup$
1
  • $\begingroup$ @fgrieu Why is it better to use Schnor group instead of safe prime? $\endgroup$ Jul 19 at 13:32
1
$\begingroup$

The Fiat-Shamir heuristic is a general method to construct a non-interactive proof (or signature) scheme from an interactive proof of knowledge scheme. An example of interactive scheme amenable to the Fiat-Shamir heuristic is the protocol in a Schnorr group. That's how I'll interpret the question (that other answer discuss the more general perspective of the Fiat-Shamir heuristic).

A Schnorr group is a subgroup of prime order $q$, and generator $g$, of the multiplicative group modulo some prime $p$. That main group $\mathbb Z_p^*$ has order $\varphi(p)=p-1$. Since the order of a subgroup divides the group order, $q$ must be a prime dividing $p-1$. Since $g$ is a generator, it must be such that $g^q\equiv1\pmod p$ and $g\not\equiv1\pmod p$. The Schnorr group is typically stated as the three integers $(p,q,g)$.

How big should the prime number $p$ be? How to select $p$ so that, for example, Pohlig–Hellman algorithm or other known algorithms could not break it?

For the Schnorr group to be of cryptographic interest, the Discrete Logarithm Problem must be difficult in the Schnorr group. This implies resisting known DLP algorithms. The algorithm that practically determines the required size of $p$ in a Schnorr group is the DLP variant of GNFS, which is index calculus specialized to $\mathbb Z_p^*$. The current record is a 795-bit bit $p$, and a minimum recommended size for current applications is 2048-bit, or 3072-bit for "2030 and beyond".

It's also necessary that $q$ is large enough that Pollard's rho for DLP is infeasible. It's cost is about $\Theta(\sqrt q)$ group multiplications. Thus it's recommended a minimum of 224-bit or 256-bit $q$.

These requirements are enough to insure the Pohlig-Hellman algorithm is not to fear. That's because Pohlig-Hellman requires solving a DLP in each subgroup of order $q^k$ with $k\ge 1$, $q$ prime, and $q^k$ dividing the order of the base group; and $k=1$ is the easiest case.

How to select the primitive root $g$?

This probabilistic polynomial time algorithm will do:

  • choose random prime $q$ of desired size
  • choose random even $r$ for prime $p=qr+1$ of desired size
  • chose random $s$ in $[2,p-2]$, and compute $g=s^{(p-1)/q}\bmod p$, until $g\ne1$ (which is almost certain)
  • as a consistency check, verify $g^q\bmod p=1$ (that holds unless there was an error).

Is it safe to use the same values of $p$ and $g$ for a couple of challenges?

Yes. Knowing the solution to a particular DLP in a Schnorr group demonstrably does not help solve other unrelated random DLPs on the same Schnorr group (there remains the possibility that some precomputation can be amortized between several DLPs, but that's marginal).

Why is it better to use a Schnorr group instead of safe prime $p$?

A safe prime $p$ corresponds to $p-1=2q$, or $r=2$ in the above. While technically that still matches the definition of a Schnorr group, it's not fulfilling a key motivation of Schnorr groups: having an order $q$ of much smaller size than $p$. This is interesting because exponents are in $\mathbb Z_q$, thus shorter $q$ leads to faster exponentiation, shorter secrets, and (in a common variant of the Fiat-Shamir heuristic) shorter signatures. Also, the search of $p$ is slightly more involved. As far as we know, using a Schnorr group with large-enough $q$ and $p$ is as secure as using a safe prime $p$ of comparable size.

$\endgroup$
2
$\begingroup$

There seems to be a confusion here. As fgrieu stated correctly, Fiat-Shamir is a method to make a public-coin (honest-verifier) zero-knowledge proof non-interactive. You do not need to select any parameter for Fiat-Shamir, beyond the hash function: all other parameters are parameters of the interactive protocol which you are making non-interactive, or of the statement you are trying to prove. Typically, for a proof of knowledge of a discrete logarithm, the group, the generator $g$, and the modulus $p$, are part of the description of the statement. Schnorr proof is an interactive proof for handling such statements, and Fiat-Shamir can be used to make it non-interactive.

The parameters of the statement will typically be determined by the context in which you intend to use a zero-knowledge proof for the statement. In general, you will want to use a zero-knowledge proof of knowledge of a discrete logarithm over a group where computing discrete logarithms is believed to be intractable (otherwise, there isn't really a point in proving knowledge of the discrete log). There are tons of standard options for such groups (e.g. ed25519 with any generator, to use the example of your other question).

$\endgroup$

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.