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 PP to convince a verifier VV of some property, without revealing any further information other than the property.

Σ\Sigma-protocol

We consider some language LL, and a relation RR such that x∈L⟺∃w∣(x,w)∈Rx \in L \iff \exists w \mid (x, w) \in R.

A protocol PP is a Σ\Sigma-protocol for the relation RR iff:

  • PP is of the 3-move form:
    1. PP sends a message aa. (The commitment).
    2. VV sends some response ee. (The challenge).
    3. PP sends a reply zz, and VV decides to accept or reject.

  • Completeness:

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

  • Soundness:

    If x̸∈Lx \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 xx, (a,e,z)(a, e, z), (a,e′,z′)(a, e', z') where e≠e′e \neq e', one can efficiently compute a witness ww such that (x,w)∈R(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 ww from interacting with PP, it means that PP has to know ww.

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

    PK{w∣(x,w)∈L}PK \{w \mid (x, w) \in L \}

  • Honest-Verifier / Zero-Knowledge:

    There exists a polynomial-time simulator MM, which on input xx and a random ee, can output an accepting conversation of the form (a,e,z)(a, e, z) indistinguishable from the real conversations distribution between PP, VV on input xx.

OR Σ\Sigma-protocol

Given L1L_1, L2L_2, R1R_1, R2R_2 from two Σ\Sigma-protocols, one can construct a new Σ\Sigma-protocol for the union of both languages L=L1∪L2L = L_1 \cup L_2 with relation R=R1∪R2R = R_1 \cup R_2.

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

  1. PP computes the first message a1−ba_{1-b}, using xx, ww as input.
    PP chooses ebe_b at random and runs the simulator MM on input (xx, ebe_b).

    (ab,eb,zb)←M(x,eb)(a_b, e_b, z_b) \leftarrow M(x, e_b)

    PP sends output (a0,a1)(a_0, a_1) to VV.
  2. VV chooses a random tt-bit string ss and sends it to PP.
  3. PP sets e1−b=s⊕ebe_{1-b} = s \oplus e_b, and computes the answer zb−1z_{b-1} to challenge eb−1e_{b-1}. PP sends back values (e0,e1,z0,z1)(e_0, e_1, z_0, z_1).
  4. VV checks that s=e0⊕e1s = e_0 \oplus e_1, and that both conversations (a0,e0,z0)(a_0, e_0, z_0) and (a1,e1,z1)(a_1, e_1, z_1) are accepting, on input xx.

Relaxed ZK proofs

Relaxed Σ\Sigma-protocol

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

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

Relaxed unbounded simulation soundness

There exists some PPT simulator SS such that for all PPT adversaries AA,

Pr[VS1(x∗,π∗)=1∧(x∗,π∗)̸∈Q∣(x∗,π∗)←AS1,S2′(1λ)]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 QQ is the set pairs (x,π)(x, \pi) where AA made a query S2(x)S_2(x) and obtained response π\pi.

Stern’s Protocol

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

R={((P,v),x)∈ZqD×L×ZqL×{x∈{0,1}L∣wt(x)=k}∣P⋅x=vmodq}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)∈L(P, v) \in L is not interesting per se, but being able to prove this means knowing a witness xx such that ((P,v),x)∈R((P, v), x) \in R, without disclosing xx.

We have PK{x∣P⋅x=vmodq}PK\{ x \mid P \cdot x = v \mod q \}.

Remarks

  • Imposing a fixed Hamming weight means we do leak some information about xx.

Abstracting Stern’s Protocol

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

  • x∈VALID⟺Tπ(x)∈VALIDx \in VALID \iff T_\pi(x) \in VALID
  • if x∈VALIDx \in VALID and π\pi uniform in SS, then Tπ(x)T_\pi(x) uniform in VALIDVALID.

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∈Rks \in \mathcal{R}^k satisfying the relation:

As=tmodqAs = t \mod q

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

Asˉ=cˉtmodqA \bar{s} = \bar{c} t \mod q

Relaxed Verifiable Encryption

RL={((B,u),(m,1))∈(Rpl×k×Rpl)×(Rpk×Rp)∣Bm=umodp∧m∈Sγk}\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}RLˉ={((B,u),(mˉ,cˉ))∈(Rpl×k×Rpl)×(Rpk×Rp)∣Bmˉ=cˉumodp∧∥mˉ∥∞<12σ∧cˉ∈Cˉ}\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}