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.

Improvements

• Speeds up Polynomial Evaluation in the Lagrange basis.
• Polynomials Basis Extension in the Lagrange basis.
• Use of the Pólya polynomial basis.
• Reduces the number of NTTs.

Download the Source Code verifier.zip or full.zip

• 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.

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: ia.cr/2025/1XXX

@inproceedings{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 = {1-26},
  publisher = {Springer},
  series = {Lecture Notes in Computer Science},
  year = {2025},
}

License is MPL-2.0.