PRUNE-HORST

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

Documentation

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

Implementations

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

The Makefile included in the reference and fast implementations has the following targets:

$ make
Please choose a target:
        analyze          runs static analyzers
        bench            runs speed benchmarks
        clean            cleans up
        format           formats the code using .clang-format rules

Warning: make bench with the reference implementation is slow because of the textbook AES implementation.

The Makefile of the debug implementation in addition provides make ivs and make check targets.

Test values

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

• KAT/PQCsignKAT_64_S.rsp, KAT/PQCsignKAT_64_M.rsp, KAT/PQCsignKAT_64_L.rsp: .rsp KAT file generated by running make, for the PRUNE-HORST versions S, M, and L.

Intellectual property

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.

Acknowledgments

Thanks to Samuel Neves for helping optimize our code.