Enabling PERK and other MPC-in-the-Head Signatures on Resource-Constrained Devices

Slim Bettaieb; Loïc Bidoux; Alessandro Budroni; Marco Palumbi; Lucas Pandolfo Perin

Paper 2024/088

Enabling PERK and other MPC-in-the-Head Signatures on Resource-Constrained Devices

Slim Bettaieb, Technology Innovation Institute

Loïc Bidoux, Technology Innovation Institute

Alessandro Budroni

, Technology Innovation Institute

Marco Palumbi, Technology Innovation Institute

Lucas Pandolfo Perin

, Technology Innovation Institute

Abstract

One category of the digital signatures submitted to the NIST Post-Quantum Cryptography Standardization Process for Additional Digital Signature Schemes comprises proposals constructed leveraging the MPC-in-the-Head (MPCitH) paradigm. Typically, this framework is characterized by the computation and storage in sequence of large data structures both in signing and verification algorithms, resulting in heavy memory consumption. While some research on the efficiency of these schemes on high-performance machines has been done, studying their performance and optimization on resource-constrained ones still needs to be explored. In this work, we aim to address this gap by (1) introducing a general method to reduce the memory footprint of MPCitH schemes and analyzing its application to several MPCitH proposed schemes in the NIST Standardization Process. Additionally, (2) we conduct a detailed examination of potential memory optimizations in PERK, resulting in a streamlined version of the signing and verification algorithms with a reduced memory footprint ranging from 22 to 85 KB, down from the original 0.3 to 6 MB. Finally, (3) we introduce the first implementation of PERK tailored for Arm Cortex M4 alongside extensive experiments and comparisons against reference implementations.

Note: Revision

Metadata

Available format(s): PDF
Category: Implementation
Publication info: A major revision of an IACR publication in TCHES 2024
Keywords: Post-Quantum Cryptography PERK Stack Usage Cortex M4
Contact author(s): slim bettaieb @ tii ae
loic bidoux @ tii ae
alessandro budroni @ tii ae
Marco Palumbi @ tii ae
lucas perin @ tii ae
History: 2024-07-04: revised; 2024-01-19: received; See all versions
Short URL: https://ia.cr/2024/088
License: CC BY

BibTeX

@misc{cryptoeprint:2024/088,
      author = {Slim Bettaieb and Loïc Bidoux and Alessandro Budroni and Marco Palumbi and Lucas Pandolfo Perin},
      title = {Enabling {PERK} and other {MPC}-in-the-Head Signatures on Resource-Constrained Devices},
      howpublished = {Cryptology ePrint Archive, Paper 2024/088},
      year = {2024},
      note = {\url{https://eprint.iacr.org/2024/088}},
      url = {https://eprint.iacr.org/2024/088}
}