0
$\begingroup$

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.

$\endgroup$

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.