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

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

연구 분야: Cryptography

학회: Australasian Conference on Information Security and Privacy

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 (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.