PRUNE-HORST

Submission to NIST's Post-Quantum Cryptography Project, structured as per http://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.

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.

A Makefile is included in Reference_Implementation/ and Additional_Implementations/fast, with the following functionalities:

$ make
Please choose a target:
        ivs              generates intermediate values using the fast code
        check            verifies intermediate values using the fast code
        checkref         verifies intermediate values using the reference code
        bench            runs speed benchmarks
        analyze          runs static analyzers
        format           formats the code using .clang-format rules
        cloc             counts lines of code
        clean            cleans up, except intermediate values file

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 our fast implementation in Reference_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.
KAT/IntermediateValues_S.txt, KAT/IntermediateValues_M.txt, KAT/IntermediateValues_L.txt: The intermediate values generated using the make ivs command, 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.

Our source code is hereby 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.

gendx/prune-horst