A digital signature scheme based on the vector space factorization problem and the MPC-in-the-Head paradigm

Philippe Gaborit; Mercedes Haiech; Romaric Neveu

doi:10.3934/amc.2025003

Article Contents

2025, Volume 19, Issue 5: 1433-1459. Doi: 10.3934/amc.2025003

This issue Previous Article Five-Lee-weight linear codes over $ \mathbb{F}_{q}+u\mathbb{F}_{q} $ Next Article New ternary self-orthogonal codes and related LCD codes from weakly regular plateaued functions

A digital signature scheme based on the vector space factorization problem and the MPC-in-the-Head paradigm

University of Limoges, France

^*Corresponding author: Mercedes Haiech
^*Corresponding author: Mercedes Haiech

Received: October 2023

Revised: July 2024

Early access: January 23, 2025

Published online: January 23, 2025

Abstract / Introduction Full Text(HTML) Figure(4) / Table(7) Related Papers Cited by

Abstract

At a time when post-quantum cryptography is more and more present in the cryptographic landscape, it is of great interest to find new hard problems on which we can rely. Here, we present a new problem, the vector space factorization problem, and use it to build a signature scheme. The idea of factorizing subspaces of a finite field is used in rank metric codes, most notably in the decoding of LRPCs. In this context, one of the subspaces is known to factorize. Factorizing without the knowledge of both subspaces appears in the signature scheme Murave, in which the rank support basis decomposition problem is introduced from a coding theory in rank metric point of view. In Bro's thesis, the SquareSpace problem is introduced, where one wants to find the "square root" of a subspace. We generalize here this problem into the vector space factorization problem, which is the same as the rank support basis decomposition problem introduced in Murave, the difference being we do not look at it from a coding theory point of view, but really from a vector subspace one. We use it here to build a zero-knowledge proof of knowledge. The scheme uses the MPCitH paradigm, and especially the TCitH framework, which is an efficient way to build ZK proofs. We study the difficulty of solving the vector space factorization problem by detailing the combinatorial attacks on the problem, analyzing their complexity, and describing an algebraic model to solve the problem. We then explain the MPC protocol used to build the signature scheme. Finally, this construction allows us to obtain sizes of signature of 8.9 to 10.9 kB for the first security level defined by NIST, which is reasonable as MPC-in-the-Head signatures typically range from 2.5 kB for an MQ instance to 14 kB for lattice-based instances.

Keywords:

Mathematics Subject Classification: Primary: 58F15, 58F17; Secondary: 53C35.

Citation:

Full Text(HTML)

Figure 1. Example of TreePRG

Download: Full-size image PowerPoint slide

Figure 2. A simplified MPCitH protocol

Download: Full-size image PowerPoint slide

Figure 3. A simplified TCitH protocol. In practice, the commitments and the final response are different than what is depicted here

Download: Full-size image PowerPoint slide

Figure 4. MPC protocol to check the solution of a VSF instance

Download: Full-size image PowerPoint slide

Table 1. Sizes of standardized signature schemes for NIST security level 1 in bytes

Scheme	Public key size	Signature size
Dilithium [6]	1 312 B	2 420 B
Falcon [21]	897 B	666 B
SPHINCS+ (short version) [5]	32 B	7 856 B

| Show Table

DownLoad: CSV

Table 2. Sizes of alternative signature schemes for NIST security level 1 given in bytes (B) or megabytes (MB)

Scheme	Public key size	Signature size
MIRA [3] & [16]	84 B	5 640 B
RYDE [11] & [16]	86 B	5 956 B
MinRank Dual Support [12]	57 B	2 813 B
RSD Dual Support [12]	53 B	2 857 B
SDitH [1] & [17]	120 B	8 241 B
WAVE [7]	3.7 mB	822 B
UOV (short) [10]	66 576 B	128 B
SquareSpace signature [13]	1 700 B	0.5 mB
MQ [8]	35	2 555 B
Lattices [18]	702	15 305 B
Our work	210 B	8 915 B

| Show Table

DownLoad: CSV

Table 3. Simulations of the algebraic attack

$ q $	$ m $	$ r $	$ n $	Nb. unknowns	Nb. equations	$ D_{ff} $	$ d $	$ (a, b) $
2	11	2	2	13	14	3	3	(2, 3)
2	17	2	2	19	26	3	3	(1, 4)
2	17	3	3	46	48	$ \ge $ 5	$ \ge $ 5	(2, 7)
2	23	3	3	58	84	4	$ \ge $ 5	(2, 6)
2	29	3	3	70	120	4	$ \ge $ 4	(2, 6)
3	11	2	2	13	14	3	4	(3, 4)
3	17	2	2	19	26	3	4	(2, 4)
3	17	3	3	46	48	$ \ge $ 5	$ \ge $ 5	(4, 9)
3	23	3	3	58	84	$ \ge $ 4	$ \ge $ 5	(3, 8)
3	29	3	3	70	120	$ \ge $ 4	$ \ge $ 4	(3, 7)
5	17	2	2	19	26	3	6	(3, 4)
7	17	2	2	19	26	3	8	(3, 4)
11	17	2	2	19	26	3	12	(3, 4)
19	47	5	5	268	440	$ \ge $ 4	$ \ge $ 4	(16, 21)
128	31	4	4	129	180	$ \ge $ 4	$ \ge $ 4	(11, 15)

| Show Table

DownLoad: CSV

Table 4. Simulations of the algebraic attack

$ q $	$ m $	$ r $	$ n $	Nb. unknowns	Nb. equations	$ D_{ff} $	$ d $	$ (a, b) $
2	17	3	2	22	22	3	4	(2, 4)
2	17	3	3	32	24	5	$ \ge $ 6	(7, 2)
2	23	3	3	38	42	4	$ \ge $ 5	(2, 6)
2	29	3	3	44	60	4	4	(3, 4)
3	17	3	2	22	22	4	6	(3, 6)
3	17	3	3	32	24	$ \ge $ 7	$ \ge $ 7	(12, 3)
3	23	3	3	38	42	5	$ \ge $ 6	(4, 7)
3	29	3	3	44	60	4	$ \ge $ 5	(2, 9)
7	17	3	2	22	22	4	$ \ge 7 $	(8, 8)
19	47	5	5	142	110	$ \ge $ 4	$ \ge $ 4	(1, 68)
128	31	4	4	75	60	$ \ge $ 5	$ \ge $ 5	(1, 46)

| Show Table

DownLoad: CSV

Table 5. Parameters for a generic instance and their associated bit security. Complexities do not take into account the polynomial costs of the attack

NIST Security Level	$q$	$m$	$r$	$n$	Combinatorial	Algebraic	Hybrid
1	19	47	5	5	151	276	151
1	128	31	4	4	146	160	146

| Show Table

DownLoad: CSV

Table 6. Sizes of signature for a VSF instance (in bytes)

NIST Security Level	$q$	$m$	$r$	$n$	$N$	$ \tau$	$ \rho$	$\|\sigma\|$	$\|\mathsf{pk}\|$
1	19	47	5	5	256	20	31	14 606 B	293 B
1	19	47	5	5	2048	14	31	10 925 B	293 B
1	128	31	4	4	256	20	19	11 749 B	210 B
1	128	31	4	4	2048	14	19	8 925 B	293 B

| Show Table

DownLoad: CSV

Table 7. Size of signature for a SquareSpace instance (in Bytes)

NIST Security Level	$q$	$m$	$r$	$N$	$ \tau$	$ \rho$	$\|\sigma\|$	$\|\mathsf{pk}\|$
1	1451	131	4	256	20	13	19 943 B	1 664 B
1	1451	131	4	2048	14	13	14 661 B	1 664 B

| Show Table

DownLoad: CSV

Related Papers

Cited by

References

[1]	C. Aguilar-Melchor, T. Feneuil, N. Gama, S. Gueron, J. Howe, D. Joseph, A. Joux, E. Persichetti, T. Randrianarisoa, M. Rivain and D. Yue, SD-in-the-Head Signature Scheme, Submission to the 1st round of the NIST additional signatures project. 2023. https://sdith.org/.
[2]	C. Aguilar-Melchor, N. Gama, J. Howe, A. Hülsing, D. Joseph and D. Yue, The return of the SDitH, Advances In Cryptology – EUROCRYPT 2023, Lecture Notes in Comput. Sci., 14008 (2023), 564-596. doi: 10.1007/978-3-031-30589-4_20.
[3]	N. Aragon, L. Bidoux, J. Chi-Domínguez, T. Feneuil, P. Gaborit, R. Neveu and M. Rivain, MIRA: a Digital Signature Scheme based on the MinRank problem and the MPC-in-the-Head paradigm, 2023. https://pqc-mira.org/index.html.
[4]	N. Aragon, P. Gaborit, A. Hauteville, O. Ruatta and G. Zémor, Low rank parity check codes: New decoding algorithms and applications to cryptography, IEEE Transactions on Information Theory, 65 (2019), 7697-7717. doi: 10.1109/TIT.2019.2933535.
[5]	Aumasson, J., Bernstein, D., Beullens, W., Dobraunig, C., Eichlseder, M., Fluhrer, S., Gazdag, S., Hülsing, A., Kampanakis, P., K¨olbl, S., Lange, T., Lauridsen, M., Mendel, F., Niederhagen, R., Rechberger, C., Rijneveld, J., Schwabe, P. and Westerbaan, B., SPHINCS+, Submission to the 3rd round of the NIST post-quantum project., 2023. https://sphincs.org/.
[6]	S. Bai, L. Ducas, E. Kiltz, T. Lepoint, V. Lyubashevsky, P. Schwabe, G. Seiler and D. Stehlé, CRYSTALS-Dilithium, Submission to the 3rd round of the NIST post-quantum project, 2022. https://pq-crystals.org/dilithium/index.shtml.
[7]	G. Banegas, K. Carrier, A. Chailloux, A. Couvreur, T. Debris-Alazard, P. Gaborit, P. Karpman, J. Loyer, R. Niederhagen, N. Sendrier, B. Smith and J. Tillich, WAVE, Submission to the 1st round of the NIST additional signatures project, 2023. https://wave-sign.org/.
[8]	C. Baum, W. Beullens, S. Mukherjee, E. Orsini, S. Ramacher, C. Rechberger, L. Roy and P. Scholl, One Tree to Rule Them All: Optimizing GGM Trees and OWFs for Post-Quantum Signatures, Chung, KM., Sasaki, Y. (eds) Advances in Cryptology – ASIACRYPT 2024. Lecture Notes in Computer Science, vol 15484. Springer Nature Singapore, 2024.
[9]	J. Berthomieu, C. Eder and M. Safey El Din, Msolve: A library for solving polynomial systems, 2021 International Symposium On Symbolic And Algebraic Computation, Association for Computing Machinery (ACM), New York, (2021), 51-58.
[10]	W. Beullens, M. Chen, J. Ding, B. Gong, M. Kannwischer, J. Patarin, B. Peng, D. Schmidt, C. Shih, C. Tao and B. Yang, Unbalanced Oil and Vinegar, Submission to the 1st round of the NIST additional signatures project, https://www.uovsig.org/, 2023.
[11]	L. Bidoux, J. Chi-Domínguez, T. Feneuil, P. Gaborit, A. Joux, M. Rivain and A. Vinçotte, RYDE: A digital signature scheme based on rank-syndrome-decoding problem with mpcith paradigm, Designs, Codes and Cryptography, (2025), 1573-7586 doi: 10.1007/s10623-024-01544-1.
[12]	L. Bidoux, T. Feneuil, P. Gaborit, R. Neveu and M. Rivain, Dual Support Decomposition in the Head: Shorter Signatures from Rank SD and MinRank, Chung, KM., Sasaki, Y. (eds) Advances in Cryptology – ASIACRYPT 2024. Lecture Notes in Computer Science, Springer Nature Singapore, 15484 (2024), 38-69. doi: 10.1007/978-981-96-0888-1_2.
[13]	M. Bros, Algebraic cryptanalysis and contributions to post-quantum cryptography based on error-correcting codes in the rank-metric, Ph.D Thesis, Université de Limoges, 2022.
[14]	T. Chien Lau and C. How Tan, Rank preserving code-based signature, 2020 IEEE International Symposium On Information Theory (ISIT), (2020), 846-851.
[15]	J. Faugère, M. Safey El Din and P. Spaenlehauer, Gröbner bases of bihomogeneous ideals generated by polynomials of bidegree (1, 1): Algorithms and complexity, Journal Of Symbolic Computation, 46 (2011), 406-437.
[16]	T. Feneuil, Building MPCitH-based signatures from MQ, MinRank, and Rank SD, Applied cryptography and network security. Part I, Lecture Notes in Comput. Sci., 14583 (2024), 403–431. doi: 10.1007/978-3-031-54770-6_16.
[17]	T. Feneuil, A. Joux and M. Rivain, Syndrome decoding in the head: Shorter signatures from zero-knowledge proofs, Advances In Cryptology – CRYPTO 2022, Lecture Notes in Comput. Sci., 13508 (2022), 541-572. doi: 10.1007/978-3-031-15979-4_19.
[18]	T. Feneuil and M. Rivain, Threshold Computation in the Head: Improved Framework for Post-Quantum Signatures and Zero-Knowledge Arguments, Cryptology ePrint Archive, Paper 2023/1573, 2023.
[19]	T. Feneuil and M. Rivain, Threshold linear secret sharing to the rescue of mpc-in-the-head, Advances In Cryptology – ASIACRYPT 2023, Lecture Notes in Comput. Sci., 14438 (2023), 441-473. doi: 10.1007/978-981-99-8721-4_14.
[20]	A. Fiat and A. Shamir, How to prove yourself: Practical solutions to identification and signature problems, Advances in Cryptology—CRYPTO '86 (Santa Barbara, Calif., 1986), Lecture Notes in Comput. Sci., Springer-Verlag, Berlin, 263 (1987), 186-194.
[21]	P. Fouque, J. Hoffstein, P. Kirchner, V. Lyubashevsky, T. Pornin, T. Prest, T. Ricosset, G. Seiler, W. Whyte and Z. Zhang, Falcon: Fast-Fourier Lattice-based Compact Signatures over NTRU, Submission to the 3rd round of the NIST post-quantum project, (https://falcon-sign.info/ 2022).
[22]	A. Hauteville, Décodage en métrique rang et attaques sur un système de chiffrement à base de codes LRPC, Université de Limoges, France, https://inria.hal.science/hal-01755842, 2014.
[23]	Y. Ishai, E. Kushilevitz, R. Ostrovsky and A. Sahai, Zero-knowledge from secure multiparty computation, STOC'07—Proceedings of the 39th Annual ACM Symposium on Theory of Computing, Association for Computing Machinery (ACM), New York, (2007), 21-30.
[24]	D. Kales and G. Zaverucha, An attack on some signature schemes constructed from five-pass identification schemes, Cryptology And Network Security, 12579 (2020), 3-22. doi: 10.1007/978-3-030-65411-5_1.
[25]	J. Katz, V. Kolesnikov and X. Wang, Improved non-interactive zero knowledge with applications to post-quantum signatures, Proceedings Of The 2018 ACM SIGSAC Conference On Computer And Communications Security, (2018), 525-537
[26]	T. Lau and C. Tan, MURAVE: A new rank code-based signature with MUltiple RAnk VErification, Code-Based Cryptography, 12087 (2020), 94-116. doi: 10.1007/978-3-030-54074-6_6.
[27]	R. Perlner and D. Smith-Tone, Rainbow Band Separation is Better than we Thought, Cryptology ePrint Archive, Paper 2020/702, 2020.