Memory Evaluation of Picnic3-L1 for opt-mem mismatch

[GeorgeTasop]

Hello, while I was trying to integrate to my code your version of Picnic3-L1, that I found out that is provided by this project, I stumbled upon a mismatch regarding the memory requirements of Picnic3-L1, as reported in my STM32CubeIDE and in your benchmark file.

As a matter of fact, the memory reported in my IDE, checks out with the statements made in the README.md file in the original repository:

opt-mem: similar to opt, but makes some tradeoffs to reduce memory even further, such as not storing the whole Merkle tree in memory, and recomputing it as needed. Currently, only signing is optimized to use less RAM, verification is the same as opt. None of the changes break compatibility with the Picnic specification.

And the reported memory requirements in the original repository's benchmarks are:

Signature Schemes

Scheme	Implementation	Key Generation [bytes]	Sign [bytes]	Verify [bytes]
picnic3l1	opt	820	69,228	87,812
picnic3l1	opt-mem	828	24,676	32,436

So the memory required for the Verify operation in the opt-mem variant should be the same as the opt variant, which is 87,812 bytes. (this issue is raised in the original repository here)

Your Memory Evaluation reports:

Signature Schemes

Scheme	Implementation	Key Generation [bytes]	Sign [bytes]	Verify [bytes]
picnic3l1	opt	800	32,244	32,236
picnic3l1	opt-mem	808	24,656	32,444

I see that the code in pqm4, is exactly the same in the original repository (except for some flag names that are changed). Am I missing something? Is the memory reported here actually correct and this is only a typo in the original repo? And what could be possibly be missed to make my IDE report different stack usage?

I opened an issue on the original repository and I thought it would be useful to discuss this issue here as well.

P.S: The way that I integrated Picnic, is by copying the code and carefully building my project by passing the same flags as pqm4's build system. I have already done it in a number of other PQ algorithms and it's the first time I come across a memory mismatch.

Feel free to contact me for any other information that may be missing.

Thanks for your time, George

[mkannwischer]

Picnic is no longer a candidate in the NIST competition and will be removed in #238. Closing this issue.