Suppose Alice wants to convince Bob that she has found a path of length $M$ between vertices $v$ and $w$ in a certain graph. Bob can verify this claim in $O(M)$ time by having Alice send the list of vertices. Is there a faster, cryptographically secure method to verify the claim?

Formally, suppose for each positive integer $N$, we have a graph $G_N$ with $N$ vertices labelled $1$ to $N$ (so $\log N$ bits are required to specify a vertex). Suppose we have a circuit which determines whether two vertices of $G_N$ are adjacent, whose size is polynomial in $\log N$. Does there exist an interactive protocol such that:

  1. If Alice has a path, Bob will be convinced; Alice's runtime will be $O(M)O((\log N)^k)$ and Bob's runtime will be $o(M)O((\log N)^k)$.
  2. If there is no such path, an adversary Eve, subject to the standard cryptographic model and limited to time $O(M)O((\log N)^k)$, has negligible probability of convincing Bob.

(To keep things simple I'm ignoring the distinction between finding a path and proving one exists).

My thinking so far: Suppose Bob generates a function $f$ from $G_N$ to a finite group $H$, and another function $g:G_N\times G_N\to H$ such that $g(x,y)=f(x)f(y)^{-1}$ whenever $x$ and $y$ are adjacent.

For example, take $H$ to be a linear algebraic group over a finite field, and choose $f$ to be a polynomial map to some affine subset of $H$. The adjacency circuit could be converted to a polynomial, from which we can produce a polynomial map $u:G_N\times G_N\to H$ which maps each edge to the identity. Finally set $g(x,y)=f(x)f(y)^{-1}u(x,y)$.

Now Bob sends $g$ to Alice, who multiplies the values of $g$ for all edges along her path, sending the result to Bob. Finally Bob checks that Alice's response equals $f(w)f(v)^{-1}$. However I'm not sure if there is a scheme to generate $f$ and $g$ which makes it difficult for Eve to recover $f$ (or another function $f_1$ satisfying the same identity).

I previously asked an analogous question in terms of complexity classes, but after more thought this is closer to what I'm looking for.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.