Paper 2024/1004

Relaxed Vector Commitment for Shorter Signatures

Abstract

MPC-in-the-Head (MPCitH) has recently gained traction as a foundation for post-quantum signature schemes, offering robust security without trapdoors. Despite its strong security profile, MPCitH-based schemes suffer from high computational overhead and large signature sizes, limiting their practical application. This work addresses these inefficiencies by relaxing vector commitments within MPCitH-based schemes. We introduce the concept of vector semi-commitment, which relaxes the binding property of traditional vector commitment. Vector semi-commitment schemes may allow an adversary to find more than one preimage of a commitment. We instantiate vector semi-commitment schemes in both the random oracle model and the ideal cipher model, leveraging recent optimizations on GGM tree such as correlated GGM tree. We apply the ideal-cipher-based vector semi-commitment scheme to the BN++ signature scheme and prove it almost fully secure in the ideal cipher model. Implementing these improvements in the AIMer v2.0 signature scheme, we achieve up to 8.7% shorter signatures and up to 112% faster signing and verification speeds, setting new benchmarks for MPCitH-based schemes.

Note: This paper is a revised version of Eurocrypt 2025 paper having the same name. In the proceeding version, the proposed signature scheme includes correlated GGM trees with secret key root. Kosuge and Xagawa pointed out that EUF-CMA security proof is wrong in private communication. We admitted that our security proof is wrong, and removed ``the secret key root'' from the signature scheme while maintaining cGGM itself. The change from the previous version is written in the paper.