4
$\begingroup$

In Wesolowski's VDF (verifiable delay function) a prover produces a pair $(x, y)$ and needs to argue to the verifier that the pair satisfies $y = x^e \pmod N$ for some $e$ computable to both. The verifier is compute limited and $e$ is really large, so cannot compute $x^e\pmod N$ herself. The prover needs to convince the verifier with the verifier doing little work.

To achieve this, the verifier generates a challenge $c$ which is prime, and the prover responds with $\pi = x^{\lfloor e/c\rfloor}\pmod N$. Now the verifier can be convinced if $y = \pi^c x^{r}\pmod N$, where $r$ is the remainder of $e$ divided by $c$.

How does the primality of $c$ come into play? Is there a forged proof attack for composite challenges?

In [1] the base difficulty assumption is this game:

Game 1: We are given an $N$ guaranteed to be a product of two primes . We choose $u\neq 1$. After this we're given a uniform random k-bit prime $c$. We win if we output $v$ such that $v^c = u\pmod N$.

Does this game become easier if instead we're given just a random k-bit number? The reduction from the VDF problem to Game 1 does not seem to use the fact that $c$ is a prime either.


Later on [2] names the statement "Game 1 is hard" the adaptive root assumption. They also work with primes only, with no justification.

$\endgroup$

1 Answer 1

4
$\begingroup$

Actually [2] does have an explanation:

The reason we cannot choose $c$ uniformly in some interval, but must choose it from $\mathrm{Primes}(k)$, is because a random $c$ in $\{1, \ldots, 2^k\}$ has a reasonable chance of being a smooth integer. The adversary can then win by outputting $u= a^B$ where B is the product of small prime powers up to some bound k, and later chosing $v = a^{B/c}$. Choosing $c$ as a prime number eliminates this attack.

So Game 1 does become easier if we give the player a random $k$ bit integer instead.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.