Lattice-based Cryptography: Zero-Knowledge Proofs of Knowledge

Posted on

ZK proofs and \(\Sigma\)-protocols

In the general sense, a Zero-Knowledge proof allows a prover \(P\) to convince a verifier \(V\) of some property, without revealing any further information other than the property.

\(\Sigma\)-protocol

We consider some language \(L\), and a relation \(R\) such that \(x \in L \iff \exists w \mid (x, w) \in R\).

A protocol \(P\) is a \(\Sigma\)-protocol for the relation \(R\) iff:

  • \(P\) is of the 3-move form:
    1. \(P\) sends a message \(a\). (The commitment).
    2. \(V\) sends some response \(e\). (The challenge).
    3. \(P\) sends a reply \(z\), and \(V\) decides to accept or reject.

  • Completeness:

    If \(P\) and \(V\) are honest and follow the protocol on \((x, w) \in R\), then \(V\) always accept.

  • Soundness:

    If \(x \not\in L\), no cheating prover can convince an honest verifier of the opposite, except with some small probability.

  • Knowledge extractor / Special soundness:

    Given two accepting transcripts on the same input \(x\), \((a, e, z)\), \((a, e', z')\) where \(e \neq e'\), one can efficiently compute a witness \(w\) such that \((x, w) \in R\).

    From what I understand, this is essentially the “proof of knowledge” part of a ZKPoK. If an extractor can always compute \(w\) from interacting with \(P\), it means that \(P\) has to know \(w\).

    Sometimes the following notation seems to be used to express the proof of knowledge:

    \[PK \{w \mid (x, w) \in L \}\]

  • Honest-Verifier / Zero-Knowledge:

    There exists a polynomial-time simulator \(M\), which on input \(x\) and a random \(e\), can output an accepting conversation of the form \((a, e, z)\) indistinguishable from the real conversations distribution between \(P\), \(V\) on input \(x\).

OR \(\Sigma\)-protocol

Given \(L_1\), \(L_2\), \(R_1\), \(R_2\) from two \(\Sigma\)-protocols, one can construct a new \(\Sigma\)-protocol for the union of both languages \(L = L_1 \cup L_2\) with relation \(R = R_1 \cup R_2\).

For a proof of \(x \in L\), the following protocol does not leak information about which of the two languages \(x\) comes from.

  1. \(P\) computes the first message \(a_{1-b}\), using \(x\), \(w\) as input.
    \(P\) chooses \(e_b\) at random and runs the simulator \(M\) on input (\(x\), \(e_b\)).

    \[(a_b, e_b, z_b) \leftarrow M(x, e_b)\]

    \(P\) sends output \((a_0, a_1)\) to \(V\).
  2. \(V\) chooses a random \(t\)-bit string \(s\) and sends it to \(P\).
  3. \(P\) sets \(e_{1-b} = s \oplus e_b\), and computes the answer \(z_{b-1}\) to challenge \(e_{b-1}\). \(P\) sends back values \((e_0, e_1, z_0, z_1)\).
  4. \(V\) checks that \(s = e_0 \oplus e_1\), and that both conversations \((a_0, e_0, z_0)\) and \((a_1, e_1, z_1)\) are accepting, on input \(x\).

Relaxed ZK proofs

Relaxed \(\Sigma\)-protocol

Given two NP-languages \(L \subseteq \bar{L}\), defined by the relations \(R \subseteq \bar{R}\), a relaxed \(\Sigma\)-protocol for \(L, \bar{L}\) is a 3-round 2-party protocol between algorithms (\(P\), \(V\)), that satisfies standard compleness and ZK, but with the following difference:

Knowledge extractor \(M\) is only guaranteed to output a witness \(w\) such that \((x, w) \in \bar R\).

Relaxed unbounded simulation soundness

There exists some PPT simulator \(S\) such that for all PPT adversaries \(A\),

\[Pr[V^{S_1}(x^*, \pi^*) = 1 \wedge (x^*, \pi^*) \not\in Q \mid (x^*, \pi^*) ← A^{S_1, S_2'}(1^\lambda)]\]

is negligible, where \(Q\) is the set pairs \((x, \pi)\) where \(A\) made a query \(S_2(x)\) and obtained response \(\pi\).

Stern’s Protocol

Stern’s protocol allows to prove knowledge of a binary vector \(x\) of fixed Hamming weight such that \(P\cdot x = v \mod q\), where \((P, v, q)\) is public. The simple idea is to send to the verifier a permutation \(\pi(x)\) of the vector so that the constraint is satisfied but does not leak any information about \(x\).

\[R = \left\{((P, v), x) \in \mathbb{Z}_q^{D \times L} \times \mathbb{Z}_q^L \times \{x \in \{0, 1\}^L \mid wt(x) = k \} \mid P \cdot x = v \mod q \right\}\]

Note that here, having \((P, v) \in L\) is not interesting per se, but being able to prove this means knowing a witness \(x\) such that \(((P, v), x) \in R\), without disclosing \(x\).

We have \(PK\{ x \mid P \cdot x = v \mod q \}\).

Remarks

  • Imposing a fixed Hamming weight means we do leak some information about \(x\).

Abstracting Stern’s Protocol

Libert et al provide a more general Stern-like protocol which gets rid of the Hamming weight constraint. Now, \(x\) belongs to a set \(VALID \subset \{-1, 0, 1\}^L\) endowed with permutations \(\{T_\pi\}_{\pi \in S}\) such that:

  • \(x \in VALID \iff T_\pi(x) \in VALID\)
  • if \(x \in VALID\) and \(\pi\) uniform in \(S\), then \(T_\pi(x)\) uniform in \(VALID\).

Fiat-Shamir with Aborts

Fiat-Shamir with Aborts is a proof of knowledge for proving linear relations, also based on the hardness of lattice problems. Given an \(s \in \mathcal{R}^k\) satisfying the relation:

\[As = t \mod q\]

the construction is a proof of knowledge of some low-norm \(\bar{s}\) and \(\bar{c}\) satisfying:

\[A \bar{s} = \bar{c} t \mod q\]

Relaxed Verifiable Encryption

\[\begin{aligned} R_L = \{ ((B, u), (m, 1)) \in (\mathcal{R}_p^{l \times k} \times \mathcal{R}_p^l) \times (\mathcal{R}_p^k \times \mathcal{R}_p) \\ \mid Bm = u \mod p \wedge m \in S_\gamma^k \} \\ \end{aligned}\]\[\begin{aligned} R_{\bar{L}} = \{ ((B, u), (\bar{m}, \bar{c})) \in (\mathcal{R}_p^{l \times k} \times \mathcal{R}_p^l) \times (\mathcal{R}_p^k \times \mathcal{R}_p) \\ \mid B \bar{m} = \bar{c} u \mod p \wedge \lVert \bar{m} \rVert_{\infty} < 12\sigma \wedge \bar{c} \in \bar{\mathcal{C}} \} \end{aligned}\]