# Latticefold+ summary (draft)

[Latticefold+](https://eprint.iacr.org/2025/247.pdf) is a novel quantum secure folding scheme that improves its predecessor [Latticefold](https://eprint.iacr.org/2024/257.pdf) scheme significantly. Namely, it makes:
* prover faster
* the verification circuit simpler
* folding proofs shorter

Preliminary reading of [introduction to Latticefold](https://hackmd.io/sMhDUNSQQoaTLwe9KrfoIw) is highly recommended as a prerequisite to this post.

This writeup serves a brief summary of Latticefold+ paper.

## Latticefold downside
Essentially, the downside of Latticefold is to require a prover to provide a range proof on all input witnesses using bit-decomposition which slows down a prover significantly

Bit-decomposition is a technique that expresses a value as extraction of its power bits ( sum of power of two)

$x \;=\; \sum_{i=0}^{n-1} b_i \, 2^i,
\qquad b_i \in \{0,1\}.$

Latticefold+ does not use bit-decomposition. It consists of the following components:
1. **New algebraic range proof**
2. **Double commitment** is used to shrink this algebraic range proof
3. **Sumcheck-based transformation** is used to fold statements about double commitments

## New algebraic range proof
Suppose, we would like to prove that
$f = (f_1...f_n) \in Z^n_q$
satisfies $f_i \in (-d/2, d/2)$
for all $i \in [n]$
$d$ is number of commiments

The prover will commit to a vector of ring elements $m = (m_1...m_n) \in R^n_q$ where
$m_i \in R^n_q$ is monomial $m_i = X^{f_i}$
We denote this commitment **com(m)**
In essence, this is Aitaj commitment to m is fast because this is a vector of monomials (TODO see Remark 4.3)

Using Lemma 2.2 if $m_i$ is monomial and $m_i$ and $f_i$ satisfy a simple algebraic relation(which one?) then $f_i \in (-d/2, d/2)$
Hence, we have to complete two tasks:
1. our range proof has to prove that com(m) is a Aitaj commitment of a vector of monomials (section 4.2)
2. prove that m and f satisfy a certain algebraic relations (section 4.3)

Both steps are presented as reductions to checking a simple algebraic relation.
The resulting proof requires no commitment to bit composed vector which is faster than Latticefold

## Double commitments
When applying this range proof to a vector of ring elements $f \in R^n_q$; we can repeat these proofs $d$ times (once for all constant terms in f, once per all vectors of linear terms in f)

This would require the prover to commit to d vectors $m_0,....m_{d-1}$ that would result into large transcript of d commiments $c := (com(m_0)...com(m_{d-1}))$ that must be sent to a verifier .

In section 4.1 of Latticefold+ paper the concept of double comitment is introduced where the prover sends the commitment of commitments to a verifier.

This vector $c$ is not low norm we have to decompose it, to reduce its norm and thern commit its decomposition using Aitaj commitment. We use $dcom(M)$ to denote this double commitment to a matrix $M = [m_0....m_{d-1}] \in R^{n * d}_q$
These double commitments are crucial to make folding proofs shorter and easy to verify. In section 4.3 the range proof with double commiments is presented.

# Commitment transformation
Double commmitments are not linearly homomorphic. These is special technique used to transform these double comiments into some lienar commiments. It is discussed in section 4.4