Public-Key Encryption from the MinRank Problem

Rohit Chatterjee; Changrui Mu; Prashant Nalini Vasudevan

Paper 2025/1833 Original: eprint.iacr.org/2025/1833 ↗

Public-Key Encryption from the MinRank Problem

Rohit Chatterjee

Changrui Mu

Prashant Nalini Vasudevan

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.

Metadata

Available format(s): PDF
Category: Public-key cryptography
Publication info: Preprint.
History: 2025-10-04: last updated; 2025-10-04: published
Short URL: https://ia.cr/2025/1833
License: https://creativecommons.org/licenses/by/4.0/

BibTeX

@misc{cryptoeprint:2025/1833,
      author = {Rohit Chatterjee and Changrui Mu and Prashant Nalini Vasudevan},
      title = {Public-Key Encryption from the MinRank Problem},
      howpublished = {Cryptology {ePrint} Archive, Paper 2025/1833},
      year = {2025},
      url = {https://eprint.iacr.org/2025/1833}
}