mupq / pqm4

Post-quantum crypto library for the ARM Cortex-M4
284 stars 72 forks source link

Improve Dilithium (speed) verification stack usage #346

Closed mkannwischer closed 2 months ago

mkannwischer commented 3 months ago

Once upon a time, we wrote a paper on memory-efficient Dilithium [1] which included a speed-optimized version of verification that still included some memory optimizations that don't come at a performance penalty.

Unfortunately with the update of the reference code to round 3 that version did not get migrated leading to some complaints about verification memory consumption.

I finally found some time to port these. Verficication speed is essentially unchanged, but stack consumption is much better.

[1] https://eprint.iacr.org/2020/1278

The change is essentially this: before Scheme Implementation Key Generation [bytes] Sign [bytes] Verify [bytes]
dilithium2 clean 38,304 51,968 36,192
dilithium2 m4f 38,296 49,416 36,220
dilithium2 m4fstack 4,408 5,072 2,704
dilithium3 clean 60,832 79,616 57,728
dilithium3 m4f 60,824 68,864 57,720
dilithium3 m4fstack 4,408 6,608 2,704
dilithium5 clean 97,696 122,724 92,940
dilithium5 m4f 97,688 116,076 92,932
dilithium5 m4fstack 4,408 8,136 2,712
after Scheme Implementation Key Generation [bytes] Sign [bytes] Verify [bytes]
dilithium2 clean 38,304 51,968 36,192
dilithium2 m4f 38,296 49,416 9,012
dilithium2 m4fstack 4,408 5,072 2,704
dilithium3 clean 60,832 79,616 57,728
dilithium3 m4f 60,824 68,864 9,880
dilithium3 m4fstack 4,408 6,608 2,704
dilithium5 clean 97,696 122,724 92,940
dilithium5 m4f 97,688 116,076 11,944
dilithium5 m4fstack 4,408 8,136 2,712
mkannwischer commented 3 months ago

See https://groups.google.com/a/list.nist.gov/g/pqc-forum/c/F4-PyxwFD_g/m/098dlKP8AQAJ

mkannwischer commented 2 months ago

Since there were no objections in the last month, I'm going to merge this now.