Paper 2025/2035

Multivariate Commitments and Signatures with Efficient Protocols

Thibauld Feneuil, CryptoExperts (France)

Jules Maire, École Normale Supérieure - PSL

Matthieu Rivain, CryptoExperts (France)

Julia Sauvage, Sorbonne University

Damien Vergnaud, Sorbonne University

Abstract

We revisit multivariate commitments based on the hardness of solving systems of multivariate quadratic (MQ) equations over finite fields. We analyze a simple construction where a message µ is committed as c = (µ + F(r), G(r)), with F and G random quadratic maps. We prove that the scheme is computationally hiding assuming the intractability of the MQ problem. Its binding property reduces to solving random bilinear systems. We prove that this problem is NP-complete and study the performance of existing algebraic and hybrid attacks. We show that this commitment is well-suited for integration with zero-knowledge proofs. Using the Threshold-computation-in-the-Head framework, we construct zero-knowledge efficient arguments of knowledge for the opening and arguments for relations on committed values. We apply this to construct an efficient blind signature scheme à la Fischlin, and we demonstrate that our techniques yield a fully multivariate construction of signatures with efficient protocols, enabling practical post-quantum anonymous credentials.

BibTeX

@misc{cryptoeprint:2025/2035,
author = {Charles Bouillaguet and Thibauld Feneuil and Jules Maire and Matthieu Rivain and Julia Sauvage and Damien Vergnaud},
title = {Multivariate Commitments and Signatures with Efficient Protocols},
howpublished = {Cryptology {ePrint} Archive, Paper 2025/2035},
year = {2025},
url = {https://eprint.iacr.org/2025/2035}
}