Paper 2025/2035 Original: eprint.iacr.org/2025/2035 ↗
Multivariate Commitments and Signatures with Efficient Protocols
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.
Metadata
- Available format(s)
PDF- Category
- Cryptographic protocols
- Publication info
- Preprint.
- History
- 2025-11-03: last updated
- 2025-11-03: published
- Short URL
- https://ia.cr/2025/2035
- License
- https://creativecommons.org/licenses/by/4.0/
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}
}