This repository contains supplemental material of the article titled "Rhizomes and the Roots of Efficiency—Improving Prio published at Progress in Cryptology — LATINCRYPT 2025.
This project is a fork of divviup/libprio-rs, a rust implementation of Prio.
- Speeds up Polynomial Evaluation in the Lagrange basis.
- Polynomials Basis Extension in the Lagrange basis.
- Polynomial Multiplication in the Lagrange basis.
- Textbook vs Stolon vs Rhizome.
- Use of the Pólya polynomial basis.
- Reduces the number of NTTs.
| Branches | Applications | Benchmarks | Cite |
|---|
Download the Source Code verifier.zip or full.zip
- welcome: This branch contains pointers to the content in this repository.
- main: It follows the main branch of divviup/libprio-rs.
- baseline: This is libprio-rs version 0.18.1-alpha.2 used to make comparisons.
- rhizomes/verifier: Code changes to improve Prio PrepInit verification only.
- rhizomes/full: Code changes to improve Prio both prover and verification.
The VDAF document specifies Prio, a protocol for private aggregation of measurements.
The algorithms introduced in this research work speed up Prio operations as described in the benchmarks section.
Proposed changes to the specification:
-
Use faster polynomial evaluation. (Adopted in v17)
-
Keep polynomials in Lagrange basis.
Clone and benchmark the code using the following commands:
make clone_verifier
make bench_verifier
make graph_verifier
Clone and benchmark the code using the following commands:
make clone_full
make bench_full
make graph_full
DOI: 10.1007/978-3-032-06754-8_16
ePrint: https://eprint.iacr.org/2025/1727
@inproceedings{faz25_rhizomes,
doi = {10.1007/978-3-032-06754-8_16},
title = {{Rhizomes and the Roots of Efficiency—Improving Prio}},
author = {Armando {Faz-Hernandez}},
booktitle = {{Progress in Cryptology — LATINCRYPT 2025}},
pages = {425-449},
publisher = {Springer},
series = {Lecture Notes in Computer Science},
year = {2025},
month = oct,
}License is MPL-2.0.