Smaller public keys for MinRank-based schemes
Open Access
- 1 January 2025
- journal article
- research article
- Published by Walter de Gruyter GmbH in Journal of Mathematical Cryptology
- Vol. 19 (1)
Abstract
MinRank is an NP-complete problem in linear algebra whose characteristics make it attractive to build post-quantum cryptographic primitives. Several MinRank-based digital signature schemes have been proposed. In particular, two of them, MIRA and MiRitH, have been submitted to the NIST post-quantum cryptography standardization process. In this article, we propose a key-generation algorithm for MinRank-based schemes that reduces the size of the public key to about 50% of the size of the public key generated by the previous best (in terms of public-key size) algorithm. Precisely, the size of the public key generated by our algorithm sits in the range of 328–676 bits for security levels of 128–256 bits. We also prove that our algorithm is as secure as the previous ones.Keywords
All Related Versions
This publication has 19 references indexed in Scilit:
- MinRank in the Head2023
- MR-DSS – Smaller MinRank-Based (Ring-)Signatures2022
- Improvement of Algebraic Attacks for Solving Superdetermined MinRank Instances2022
- Efficient Key Recovery for All HFE Signature Variants2021
- Improved Cryptanalysis of UOV and Rainbow2021
- Improvements of Algebraic Attacks for Solving the Rank Decoding and MinRank Problems2020
- On the Complexity of “Superdetermined” Minrank InstancesLecture Notes in Computer Science, 2019
- Efficient Zero-Knowledge Authentication Based on a Linear Algebra Problem MinRank2001
- Cryptanalysis of the HFE Public Key Cryptosystem by Relinearization1999
- The Computational Complexity of Some Problems of Linear AlgebraJournal of Computer and System Sciences, 1999