Subject: [Suit] PQM signature algorithm ROM requirements

From: Koen Zandberg <[email-masked]>
Date: Thu, 24 Mar 2022 14:01:38 +0100

Hi all,

During the discussion of the draft-ietf-suit-manifest document and the 
MTI part there was some discussion on PQM algorithms implementation 
sizes[1]. One question that was  raised was whether the ROM requirements 
on the algorithms in question (HSS-LMS and Falcon) is verification only, 
or includes the signing code. The short answer here is that the numbers 
in table 5 include the signing code. Based on our measurements with the 
same code base and on the same hardware, for HSS-LMS, a verification 
only build needs 2864 bytes for the HSS-LMS code. For Falcon it is 10112 
bytes for verification only. (gcc 10.3.1 with -Os)

The HSS-LMS implementation used is the hash-sigs repo [2] from Cisco. 
The Falcon implementation used is based on the reference implementation 
[3]. The code to get these numbers is of course available online [4][5].

Best regards,
Koen Zandberg

[1]: Article to appear in ACNS 2022. Preprint: 
https://eprint.iacr.org/2021/781.pdf
[2]: https://github.com/cisco/hash-sigs
[3]: https://falcon-sign.info/
[4]: 
https://github.com/future-proof-iot/RIOT/tree/postquantum_crypto/tests/bench_hash-sigs
[5]: 
https://github.com/future-proof-iot/RIOT/tree/postquantum_crypto/pkg/falcon_sig

---

From: Russ Housley <[email-masked]>
Date: Thu, 24 Mar 2022 11:54:19 -0400

Koen:

Thanks for doing the work.  For HSS-LMS I expected the vast bull of the size to come from the SHA-256 part of the implementation, and this small code size aligns with that expectation.

Russ

> On Mar 24, 2022, at 9:01 AM, Koen Zandberg <[email-masked]> wrote:
> 
> Hi all,
> 
> During the discussion of the draft-ietf-suit-manifest document and the MTI part there was some discussion on PQM algorithms implementation sizes[1]. One question that was  raised was whether the ROM requirements on the algorithms in question (HSS-LMS and Falcon) is verification only, or includes the signing code. The short answer here is that the numbers in table 5 include the signing code. Based on our measurements with the same code base and on the same hardware, for HSS-LMS, a verification only build needs 2864 bytes for the HSS-LMS code. For Falcon it is 10112 bytes for verification only. (gcc 10.3.1 with -Os)
> 
> The HSS-LMS implementation used is the hash-sigs repo [2] from Cisco. The Falcon implementation used is based on the reference implementation [3]. The code to get these numbers is of course available online [4][5].
> 
> Best regards,
> Koen Zandberg
> 
> [1]: Article to appear in ACNS 2022. Preprint: https://eprint.iacr.org/2021/781.pdf
> [4]: https://github.com/future-proof-iot/RIOT/tree/postquantum_crypto/tests/bench_hash-sigs
> [5]: https://github.com/future-proof-iot/RIOT/tree/postquantum_crypto/pkg/falcon_sig

---

From: Brendan Moran <[email-masked]>
Date: Mon, 28 Mar 2022 11:02:59 +0000

Hi David,

You had expressed some concern about the size of Falcon during the meeting. Do you think that 10kB for the algorithm is more plausible?

Naturally, we will need to see what NIST picks, but the performance and size of Falcon are quite appealing for an infinite signature scheme.

It may be that there are better options for the Falcon implementation as well. Pqm4 has some interesting benchmarks: https://github.com/mupq/pqm4/blob/master/benchmarks.md

In particular, I’m keen to understand what’s meant by Falcon using 388 bytes of RAM: https://github.com/mupq/pqm4/blob/master/benchmarks.md#signature-schemes-1

Unfortunately, that benchmark table does not have entries for verify-only code size.

Best Regards,
Brendan

> On 24 Mar 2022, at 15:54, Russ Housley <[email-masked]> wrote:
>
> Koen:
>
> _______________________________________________
> Suit mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/suit

IMPORTANT NOTICE: The contents of this email and any attachments are confidential and may also be privileged. If you are not the intended recipient, please notify the sender immediately and do not disclose the contents to any other person, use it for any purpose, or store or copy the information in any medium. Thank you.