This repository implements the core algorithms from SLAP: Succinct Lattice-Based Polynomial Commitments from Standard Assumptions (Springer LNCS version: https://link.springer.com/chapter/10.1007/978-3-031-58754-2_4). SLAP gives a lattice-based polynomial commitment with polylogarithmic verification and proof size under Module-SIS, inspired by FRI and a Merkle-PRISIS tree. This repo is a usable prototype of that construction:
- Merkle-PRISIS commitment, matching Fig. 3: CRS sampled honestly via TrapGen/SamplePre and random units; commit/open with bit-reversed leaves and verification of path equations and public beta shortness checks.
- Split-and-fold evaluation protocol, matching Fig. 4: same-point batching, low-bit chunking, partial evaluations at (u^{2^k}), folding of polynomials/states/commitments, Fiat-Shamir transcript over Blake3, public shortness checks scaled per round.
- Field adapter for (\mathbb{Z}_q \to R_q) packing.
- Parameter builder enforcing Table 3 and Lemma 4.1 constraints; toy parameters in tests.
What is not implemented (paper leaves this open or out of scope):
- Fiat-Shamir-with-aborts rejection sampling for zero-knowledge (paper only references the standard paradigm and does not fix thresholds or retry policy).
- CRS sampling via reductions (MSIS -> h-PRISIS); code uses the honest sampler from Fig. 3 as intended.
- Distinct-point batching (paper notes only same-point batching is handled).
- Extractor tooling, hardened parameter sets, side-channel hardening, CRS attestation, and production deployment guidance.
Status: Functional prototype matching the paper's specified algorithms; passes the included unit tests. Not production-hardened; uses demo-sized parameters.