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

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. [ABSTRACT FROM AUTHOR]

Copyright of Advances in Mathematics of Communications is the property of American Institute of Mathematical Sciences and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)