Submission to NIST's Post-Quantum Cryptography Project, structured as per https://csrc.nist.gov/groups/ST/post-quantum-crypto/submission-requirements/digital-optical-media.html.
PRUNE-HORST is a stateless hash-based signature scheme designed by Jean-Philippe Aumasson and Guillaume Endignoux while working in Kudelski Security's research team.
Content of this submission package
Supporting_Documentation/submission.pdf: Reference documentation of PRUNE-HORST, include specification, security analysis, performance analysis.
Supporting_Documentation/latex_source/: LaTeX source of the reference documentation.
Supporting_Documentation/master_thesis_endignoux_guillaume.pdf: Masters thesis of Guillaume Endignoux, containing detailed analyses related to PRUNE-HORST's security.
Supporting_Documentation/parameters.py: Python script to compute the security of a PRUNE-HORST instance given a set of parameters.
Reference_Implementation/: Our reference C89 implementation, without AES-NI nor SIMD instructions.
Additional_Implementations/fast: Our fast C89 implementation, with AES-NI and SIMD instructions.
Additional_Implementations/debug: A version of the fast implementation that prints intermediate values. This directory includes intermediate values files for each of the three PRUNE-HORST versions.
The directory Optimized_Implementation/ contains a placeholder referring to the code under Reference_Implementation/, since our optimized implementation (as per NIST's requirements) is the same as our reference implementation.
$ make Please choose a target: analyze runs static analyzers bench runs speed benchmarks clean cleans up format formats the code using .clang-format rules
make bench with the reference implementation is slow because of the textbook AES implementation.
KAT/: Includes NIST's s PQCgenKAT_sign.c, rng.c, and rng.h, as well as a Makefile that we created to generate the files PQCsignKAT_64.req and PQCsignKAT_64.rsp required by NIST, using fast implementation.
KAT/PQCsignKAT_64_all.req: .req KAT file generated by running
make, same for all PRUNE-HORST versions.
Copyright notices are included in the header of each source code file. Our original source code of PRUNE-HORST is copyright © 2017 Nagravision S.A., and was written by Jean-Philippe Aumasson and Guillaume Endignoux.
The fast, AES-NI-based Haraka implementation is copyright © 2016 Stefan Kölbl.
Our source code is released under Apache 2.0 license.
Patent situation: We haven't filed any patent related to PRUNE-HORST nor are we aware of existing patent or patent application covering PRUNE-HORST.
Thanks to Samuel Neves for helping optimize our code.