# 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^m}$, the lattice $Λ$ they generate can be defined as:


In the cryptographic setting, the public matrix $A$ is often a random $n × m$ matrix over some finite field or ring, like $\mathbb{Z/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/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'$ satisfying exactly the above relation. Where coefficients of $s'$ are bounded by an absolute value to < 1.
2. **Relaxed (approximate) Proofs**: To prove the knowledge of ($\bar{c}, s'$), where $\bar{c}$ is a scalar such that

$$\bar{c}.t = A.s'$$ and
$$||s||_\infty \leq B$$

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

Here $\bar{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