Public-Key Encryption from the MinRank Problem
Rohit Chatterjee, Changrui Mu, Prashant Nalini Vasudevan
2026Year
Abstract
We construct a public-key encryption scheme from the hardness of the (planted) MinRank problem over uniformly random instances. This corresponds to the hardness of decoding random linear rank-metric codes. Existing constructions of public-key encryption from such problems require hardness for structured instances arising from the masking of efficiently decodable codes. Central to our construction is the development of a new notion of duality for rank-metric codes.
Ask about this paper
Your agent reads all of it.
Lune indexed this paper to the last equation, along with the top-tier papers that cite it. Ask a question and the answer quotes them.
Builds on2
Related papers
- A Minrank-Based Encryption Scheme à la Alekhnovich-RegevThomas Debris-Alazard, Philippe Gaborit, Romaric Neveu, Olivier RuattaEUROCRYPT 2026
- Using the Planted Clique Conjecture for Cryptography: Public-Key Encryption from Planted Clique and Noisy k-LIN over ExpandersRiddhi Ghosal, Isaac M. Hair, Aayush Jain, Amit SahaiSTOC 2025 · 1 citation
- Hardness of Range Avoidance and Remote Point for Restricted Circuits via CryptographyYilei Chen, Jiatu LiSTOC 2024 · 4 citations
- Analysis of the Security of the PSSI Problem and Cryptanalysis of the Durandal Signature SchemeNicolas Aragon, Victor Dyseryn, Philippe GaboritCRYPTO 2023 · 8 citations
- Chosen Ciphertext Security from Injective Trapdoor FunctionsSusan Hohenberger, Venkata Koppula, Brent WatersCRYPTO 2020 · 18 citations
