Adds HAETAE

[mmoeller23]

This commit implements the post-quantum signature scheme HAETAE from

• https://eprint.iacr.org/2023/624
• https://kpqc.cryptolab.co.kr/haetae

The stack strategy can be selected in config.h by setting STACK_STRATEGY to the appropriate value (run "make clean" after the change).

• 0 or undefined: Optimized for speed (default).
• 1: Disable buffers for the polynomials of the verification key in crypto_sign_keypair() and crypto_sign(). This reduces speed, as the key needs to be recomputed after each rejection.
• 2: In addition to 1, sample the hyperball in multiple passes, such that some intermediate values are computed on demand, rather than being buffered. This roughly doubles the runtime of crypto_sign().

[rpls]

Thanks! I'll test it this week. Btw., any chance you also have a suitable pure C implementation for mupq?

[rpls]

Tests pass, but for Testvector-test we need a pure C implementation in mupq.

[mmoeller23]

Tests pass, but for Testvector-test we need a pure C implementation in mupq.

The reference implementation is included in the immediately preceding commit b48968e in the HAETAE2 directory. I did not include it, as the reference implementation only works for HAETAE2 on the embedded system; for HAETAE3 and HAETAE5 it runs fine on the host, but runs out of memory on the embedded system.

In that commit, haetae2 works fine with the Testvector-test. If you copy the ref subdirectory to the haetae3 and haetae5 directories, respectively, and adjust HAETAE_MODE in the config.h files the host implementation will produce the proper testvectors. However, when running on the testboard the reference implementation will run out of memory and not return in these modes.

How do we proceed from here? Does the constallation outlined above work for you, or do we need to have pure C-implementations for all modes, which are able to run on the limited resources of the embedded system? In the latter case, the code will have to deviate substantially from the reference implementation and will be closer to the M4F version.

[markuskrausz]

Tests pass, but for Testvector-test we need a pure C implementation in mupq.

The reference implementation is included in the immediately preceding commit b48968e in the HAETAE2 directory. I did not include it, as the reference implementation only works for HAETAE2 on the embedded system; for HAETAE3 and HAETAE5 it runs fine on the host, but runs out of memory on the embedded system.

In that commit, haetae2 works fine with the Testvector-test. If you copy the ref subdirectory to the haetae3 and haetae5 directories, respectively, and adjust HAETAE_MODE in the config.h files the host implementation will produce the proper testvectors. However, when running on the testboard the reference implementation will run out of memory and not return in these modes.

How do we proceed from here? Does the constallation outlined above work for you, or do we need to have pure C-implementations for all modes, which are able to run on the limited resources of the embedded system? In the latter case, the code will have to deviate substantially from the reference implementation and will be closer to the M4F version.

The memory was only a limitation on the stm32f4discovery for HAETAE3 and 5 right? With the nucleo-l4r5zi and its 640KB of RAM, this should not be an issue.

The Testvector-test probably runs on the host anyway?!

[mmoeller23]

I have added slightly modified reference implementations to all schemes, testvectors.py works now.

CAVEAT: Commit f7aedf0 includes modifications to PQM4 core files that are required to make this work.

1. Applied the patch from issue 310 to
   • ldscripts/stm32f4discovery.ld
   • ldscripts/stm32f4discovery_fullram.ld
2. Patched mk/stm32f4discovery.mk for haetae5 to use the full RAM model for both implementations, just like dilithium5.

[rpls]

Could you add the ref implementations in mupq instead? All portable pure C stuff should go there.

[mmoeller23]

I have removed the pure C reference implementation from this pull request and initiated a new pull request at mupq

https://github.com/mupq/mupq/pull/131

[mmoeller23]

Please do not pull this at the moment

[mmoeller23]

Please do not pull this at the moment

All good, you can pull again.

[markuskrausz]

This implements the HAETAE specification 2.0 and corresponds to the M4 implementation discussed in the 2.0 specification document.