2
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Actually, the prover doesn't do repeated squaring; instead, the prover raises $g$ to the power $\lfloor 2^t / \ell \rfloor$, which (unless $\ell$ happens to be a power of 2) is not computed by repeated squaring... $\endgroup$
    – poncho
    Dec 11 '20 at 5:33
2
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ Computing $g^B$ can be done with $(1 + o(1))\log_2 B$ squarings/multiplies (where $o(1)$ refers to a value that gets arbitrarily small as $B$ grows larger); one would expect that an implementation would use such an algorithm, and hence the time taken wouldn't be that much larger than a simple squaring method with the same total bit length $\endgroup$
    – poncho
    Dec 10 '20 at 22:40
  • $\begingroup$ Right, I used $t=\log_2 B$. I don't know how to get it to $1+o(1)$; what if $B$ has Hamming weight exactly equal to $\frac{1}{2}\log_2 B$? $\endgroup$
    – Sam Jaques
    Dec 10 '20 at 22:43
  • 2
    $\begingroup$ One algorithm that achieves $1 + o(1)$ is windowing; you select a value $2^t$ and compute $g^i$ for $0 \le i < 2^t$. Then, you successively do $t$ squarings followed by one multiply by $g^{b}$, where $b$ is the next base-$2^t$ digit of the exponent. This computes $g^B$ with $\log_2 B$ squaring and circa $\log_2 B/t + 2^t$ multiplies; the latter is $o(1) \cdot \log_2 B$ if $t$ is selected properly $\endgroup$
    – poncho
    Dec 10 '20 at 22:53
  • $\begingroup$ The proof of exponentiation mentioned here seems to work for arbitrary exponents. Don't think this is absolutely identical to the ones in the VDF paper though. This PoE could be made non-interactive in the same way as other similar proofs-of-X. $\endgroup$ Dec 12 '20 at 0:01
2
$\begingroup$

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.

$\endgroup$
3
  • 1
    $\begingroup$ The verifier doesn't know $p$ and $q$. $\endgroup$
    – Sam Jaques
    Dec 10 '20 at 22:44
  • $\begingroup$ The generation of a $T$-bit number is a really big deal, now that you mention it, especially because this needs to be sent to all the parties! In the original protocol it only takes $O(\log t)$ bits of communication to send the delay parameter $t$, but with a large exponent it would take $O(t)$ bits! So they would need to instead send the seed and all parties would generate the exponent themselves, but then there are issues about the time/parallelism for that computation. $\endgroup$
    – Sam Jaques
    Dec 10 '20 at 22:46
  • 1
    $\begingroup$ @SamJaques: oops, I assumed the paper was based on the time lock work by Wagner; I'll update the answer $\endgroup$
    – poncho
    Dec 11 '20 at 4:57
0
$\begingroup$

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.

$\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.