# Efficient interactive proof of existence of path in a graph

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.