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:

  1. $T$ receives $U$ and produces a bitstring $c$.
  2. $P$ receives $U,c$ and $v \in U$ and produces a bitstring $p$.
  3. $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:

  1. $T$ produces $c$, which represents a basis for $U$
  2. $P$ produces some $p$
  3. $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)$



Your Answer

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

Browse other questions tagged or ask your own question.