Paper 2024/465

Efficient Multi-instance Vector Commitment and Application to Post-quantum Signatures

Abstract

The MPC-in-the-Head (MPCitH) and the VOLE-in-the-Head (VOLEitH) paradigms have recently been utilized to develop post-quantum signatures. Both rely on a mechanism that allows the signer to commit to $N$ values and then later open all-but-one. In particular, MPCitH-based signatures achieve this using a puncturable pseudorandom function (PPRF) primitive, while VOLEitH-based signatures utilize an all-but-one vector commitment scheme. A novel and efficient multi-instance PPRF, introduced by Bui et al. (Asiacrypt'24), provides a significant performance boost for MPCitH-based signatures, employing only a fixed-key block cipher to instantiate the PPRF while being provably secure in the ideal cipher model. This work presents an efficient multi-instance vector commitment derived from multi-instance PPRF. Our vector commitment scheme is secure in the multi-instance setting, when handling repetitive parallel executions. As a result, it can be directly applied to enhance the efficiency of VOLEitH-based signatures. We implemented our vector commitment scheme into FAEST (\url{faest.info}), a round one candidate in the NIST post-quantum cryptography standardization. According to our experimental implementation, we achieve $10\%-27\%$ improvement in both signing and verification times for various settings. % In particular, for 128-bit security (128S), we gain $23\%$ improvement with a reasonable trade-off of security loss. On the other hand, we adapt the VOLE-in-the-Head framework to the Multivariate Quadratic (MQ) problem, achieving a reduction in signature size. Specifically, for a 128-bit security level, our approach yields signature sizes between 3.1KB and 3.6KB with a small field size parameter.

Note: The previous version of the paper was titled ``Shorter VOLEitH Signature from Multivariate Quadratic''. Compared to that version, we now highlight the Vector Commitment construction as the main contribution, and we have fixed the round-by-round security analysis in the MQ-based signature.