Revisiting algebraic attacks on MinRank and on the rank decoding problem

DOI10.1007/s10623-023-01265-xzbMath1526.94021arXiv2208.05471MaRDI QIDQ6063136

Jean-Pierre Tillich, Magali Bardet, Maxime Bros, Philippe Gaborit, Pierre Briaud

Publication date: 7 November 2023

Published in: Designs, Codes and Cryptography (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2208.05471

zbMATH Keywords

algebraic attackpost-quantum cryptographyNIST-PQC candidatesrank metric code-based cryptography

Mathematics Subject Classification ID

Cryptography (94A60) Decoding (94B35) Quantum cryptography (quantum-theoretic aspects) (81P94)

Related Items (2)

MinRank in the head. Short signatures from zero-knowledge proofs ⋮ Statistical zero-knowledge and analysis of rank-metric zero-knowledge proofs of knowledge

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Distinguisher-based attacks on public-key cryptosystems using Reed-Solomon codes
• Theory of codes with maximum rank distance
• Determinantal rings
• The computational complexity of some problems of linear algebra
• Two attacks on rank metric code-based schemes: RankSign and an IBE scheme
• Key recovery attack for ZHFE
• Identity-based encryption from codes with rank metric
• New technique for decoding codes in the rank metric and its cryptography applications
• An algebraic attack on rank metric code-based cryptosystems
• Improved cryptanalysis of UOV and Rainbow
• An algebraic approach to the rank support learning problem
• Efficient key recovery for all HFE signature variants
• Durandal: a rank metric based signature scheme
• On the complexity of ``Superdetermined minrank instances
• Asymptotic behaviour of codes in rank metric over finite fields
• Improvements of algebraic attacks for solving the rank decoding and MinRank problems
• Design Principles for HFEv- Based Multivariate Signature Schemes
• On the Hardness of the Decoding and the Minimum Distance Problems for Rank Codes
• On the Complexity of the Rank Syndrome Decoding Problem
• Full Cryptanalysis of the Chen Identification Protocol
• Cryptanalysis of MinRank
• On the edge-independence number and edge-covering number for regular graphs
• A new identification scheme based on syndrome decoding
• New Results for Rank-Based Cryptography
• Ideals, Varieties, and Algorithms
• Progress in Cryptology – Mycrypt 2005
• Breaking rainbow takes a weekend on a laptop
• Improving support-minors rank attacks: applications to G\textit{e}MSS and Rainbow
• LRPC codes with multiple syndromes: near ideal-size KEMs without ideals
• MR-DSS -- smaller MinRank-based (ring-)signatures

This page was built for publication: Revisiting algebraic attacks on MinRank and on the rank decoding problem