I am trying to find an efficient method of doing the following:
Let $U$ be a $d$-dimensional linear subspace of $\mathbb{F}_q^n$. I want a protocol between a trusted party $T$, a prover $P$ and a verifier $V$ that goes like this:
- $T$ receives $U$ and produces a bitstring $c$.
- $P$ receives $U,c$ and $v \in U$ and produces a bitstring $p$.
- $V$ receives $v,c$ and $p$, and accepts or rejects the proof $p$.
I want the protocol to be complete, meaning that for any $U$, and any $v \in U$ the prover $P$ can produce a proof $p$ that is accepted by $V$.
And I want the protocol be sound, meaning that for an honest $T$, if $v \not \in U$ the prover $P$ can not produce a proof $p$ that is accepted by $V$ with a probability greater than some $\epsilon$.
An obvious way of doing this does not use $P$ at all:
- $T$ produces $c$, which represents a basis for $U$
- $P$ produces some $p$
- $V$ knows a basis for $U$, so it can check if $v \in U$, and accepts the "proof" $p$ if and only if $v \in U$ (regardless of what $p$ actually is)
In this case the size of $c$ is quite large, representing (a basis for) $U$ takes $d (n-d) \log_2(q)$ bits. I am wondering if we can do better, in the sense that $|c|+|p| < d (n-d) \log_2(q)$