Post Quantum Zero Knowledge

Efficient Hybrid Exact/ Relaxed Lattice Proofs and it's Applications to Rounding and VRFs (Notes)

Basics of a Lattice

A lattice is a discrete, linear structure extending infinitely in every direction. Mathematically, given a set of linearly independent vectors

$b_1,b_2,b_3,....,b_n$ in

${\mathbb{R}}^{\mathbb{m}}$, the lattice

$\Lambda$ they generate can be defined as:

In the cryptographic setting, the public matrix

$A$ is often a random

$n\times m$ matrix over some finite field or ring, like

$\mathbb{Z}\mathbb{/}\mathbb{qZ}$ where

$q$ is a large prime. It serves as the public parameter for the system.

The public vector

$s$ is a random vector chosen from some distribution, often uniform or Gaussian over

$\mathbb{Z}\mathbb{/}\mathbb{qZ}$. This vector is kept secret and forms the basis for cryptographic operations.

Addressing the Fundamental Lattice Relation

Here, we have a public matrix and vector

$A$ and

$t$, tinted in blue, and a secret vector

$s$.

Where the absolute value of

$s$ is bounded to 1.

Now there are 2 ways to prove this relation.

1. Exact Proofs: To prove knowledge of
   $s^{\prime }$ satisfying exactly the above relation. Where coefficients of
   $s^{\prime }$ are bounded by an absolute value to < 1.
2. Relaxed (approximate) Proofs: To prove the knowledge of (
   $\overline{c},s^{\prime }$), where
   $\overline{c}$ is a scalar such that

$$\overline{c}.t=A.s^{\prime }$$ and

$$||s|{|}_{\mathrm{\infty }}\le B$$

with

$B>>1$, we call this constraint a "soundness slack".

Here

$\overline{c}$ is primarily referred to as the relaxation factor.

Exact Proofs are in practical cases less efficient than Relaxed (Approximate) proofs, mainly because exact proof sizes range from about ~40KB - ~14KB. However, in case of Relaxed Proofs the proof sizes shrink down to about ~3KB.

In most cases and applications, such as group and ring signatures, relaxed proofs are very efficient.

But some settings cannot afford relaxed proofs. Such as the rounding proof, that is

• proving
  $\lfloor {Bs}_p\rfloor =v$, where
  $B$ is a public matrix and
  $s$ is a private vector.
• cannot do a relaxed range prove here, because of the rounding error.
• needs to be tightly bound hence, there can't be any slack.

What can we do for protocols where the exactness is partially required?

• Hybrid Exact/Relaxed Proofs

One such example is LANES+, a framework for compact hybrid exact/relaxed proofs.

Applications of LANES+

1. Compact lattice based rounding proofs