Reason for squaring and not arbitrary exponentiation in Wesolowski and Pietrzak verifiable delay functions (VDFs) 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.
Suppose I had an enormous exponent $B$. To compute $g^B\mod G$ (I'll omit &quot;mod $ G$&quot; 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.