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, privacy policy and cookie policy

Browse other questions tagged or ask your own question.