PRUNE-HORST in Go: Post-Quantum cryptographic algorithm by JP and Guillaume

Congratulations to Dr. Jean-Philippe Aumasson https://twitter.com/veorq and Guillaume Endignoux https://twitter.com/GEndignoux on submitting their Post-Quantum cryptographic algorithm PRUNE-HORST https://github.com/gravity-postquantum/prune-horst to NIST’s Computer Security Resource Center’s call for proposals https://csrc.nist.gov/news/2016/public-key-post-quantum-cryptographic-algorithms.


PRUNE-HORST is a stateless hash-based signature scheme that they created while working in Kudelski Security’s research team. The paper explaining their work is at https://github.com/gravity-postquantum/prune-horst/blob/master/Supporting_Documentation/master_thesis_endignoux_guillaume.pdf, with a reference implementation at https://github.com/gravity-postquantum/prune-horst in the C language.

I got a piece of the action when they finished it, and I was able to port it to the Go programming language at https://github.com/orijtech/prunehorst. I started working on it 5 days ago in my free time and very early mornings before bed.

code announcement

For hashing, the code uses Haraka v2, an efficient Post-Quantum short-input hashing scheme that we also ported to Go https://github.com/orijtech/haraka/. Haraka has two variants Haraka256 and Haraka512 which are the 256 and 512 bit variants respectively. JP advocated for, and implemented the AES Native Instructions(AES-Ni) routine in Go-ASM replacing the AES routine that I had written in pure Go. His change to this diff https://gist.github.com/odeke-em/235c9b2de3228154539e4ed6f8251b61/ sped up the entire PRUNE-HORST algorithm up by ~82%!!


The port was a fun, great and important open source code collaboration between JP from Kudelski Security and I from orijtech, Inc. Thank you, and I look forward to hopefully more collaborations in the future!

Kudelski Security * orijtech, Inc collaboration celebration

Kind regards,

Emmanuel T Odeke

orijtech, Inc.