Reason for squaring and not arbitrary exponentiation in Wesolowski and Pietrzak verifiable delay functions (VDFs)

Question

I'm working at understanding the Wesolowski and Pietrzak RSA group based VDFs (verifiable delay functions). These basically work by requiring the prover to do a bunch of repeated squaring within a semiprime group G of unknown order, and then computing a proof that a verifier can check without having to do the time consuming work of repeated squaring mod G. These can be used for proof of work, trustworthy randomness beacons, spam prevention, etc.

I'm curious as to why both rely on computing (g^(2^t) mod G) as the work to be done rather than just computing g to the power of some arbitrary huge exponent mod G. (The huge exponent could be generated by e.g. running a CSPRNG seeded by a known input.) In this case you could compute a proof of exponentiation for g^bignum mod G and supply that to the verifier.

Does the use of repeated squaring rather than some arbitrary exponent have any cryptographic significance? Is it just simpler? Just curious so I can understand why these choices were made.

Also curious about the generator (g). Any reason it needs to be a particular number, or should it just be something like 3? Maybe I didn't catch it but I didn't see that discussed.

Answer 1

Suppose I had an enormous exponent $B$. To compute $g^B\mod G$ (I'll omit "mod $ G$" from now on), I would use a square-and-multiply method: I would compute $g$, $g^2$, $g^4$,\dots, $g^{2^t}$, where $t$ is the bit-length of $B$, then multiply all $g^{2^i}$ for $i=1$ in the binary representation of $B$. Note that this involves, at most, $t$ squarings and $t$ multiplications (I'll assume squaring and multiplication take the same amount of time, which isn't exactly accurate but is good enough for this explanation), so the delay is at most time $2t$ times the time for a single square/multiplication.

However, the exact time is less clear; it will depend on the Hamming weight of G, how we store intermediate values, or whether we keep a running product of all $g^{2^i}$ that we have reached so far, etc. And note that we had to compute $g^{2^t}$ anyway to find $g^B$.

The proof of exponentiation for a big number shouldn't vary that much from the proof of repeated squaring. I'm also not sure the Pietrzak verification method works with arbitrary exponents (probably? but it will need some modification).

So basically, arbitrary large exponents should work, but it will be more complicated than just repeated squaring.

The generator cannot be an arbitrary number because it needs to change for every use. If the same generator were used in two different applications, someone could save all the values of $g^{2^t}$ and just look them up in memory the second time, and thus they would not have the required delay. The time-lock game in Definition 2 says that $g$ is uniformly random; the construction doesn't mention this but I think this is a basic assumption of all VDFs.

Answer 2

Does the use of repeated squaring rather than some arbitrary exponent have any cryptographic significance? Is it just simpler?

Mostly, it makes the description simpler.

The prover and the verifier jointly compute $g^{2^t} \bmod G$; however they don't don't do it in a balanced way.

The prover does the vast bulk of the work, computing all but a factor of $\ell$ of the exponent (where $\ell$ is a modest prime); that is, it computes $g^{\lfloor 2^t / \ell \rfloor}$; the verifier takes it the rest of the way (applying the final exponent of $\ell$ to it), and verifies that the final product (after multiplying the final factor of $g^{2^t \bmod \ell}$) is the expected value.

Now, one could rewrite this to use a large random $T$ value instead of $2^t$, however it's more complex (as the compution of $T / \ell$ and $T \bmod \ell$ is necessarily more complex), and it is not at all clear what benefit that additional complexity would bring.

---

[Previous incorrect answer]

The $2^T$ method does make it cheaper to do the verification step cheaper; given that's the step that we expect to be cheap, reducing the cost is significant.

With $2^T$, the verifier would need to compute $2^T \bmod p-1$ and $2^T \bmod q-1$ (where $p, q$ are the prime factors of $G$); this can be done using $O(\log T)$ modular multiplies.

In contrast, if we were to use a CSRNG-generated T-bit number, the verifier would need to generate that $T$ bit number (which obviously takes $O(t)$ time).

I don't know if that's the reasoning they used to select the squaring method; however that would appear to be a reasonable decision.

Answer 3

To complement the other answers, let me add that Wesolowski's proof of repeated squaring has been extended to arbitrary exponents (confirming Sam Jaques' guess that it can be done). For example, such an extension can be found in this recent paper. The generalization does not really lead to a better VDF, since repeated squaring works perfectly fine for that, however it has many other applications. Essentially, it allows to produce a succinct proof of knowledge of an arbitrarily large exponent, which is used in the previously cited work to build accumulators and positional vector commitments with very good efficiency. Even more recently, these results have been used to give new constructions of SNARKs.