Public-Key Encryption from the MinRank Problem

Rohit Chatterjee; Changrui Mu; Prashant Nalini Vasudevan

Paper 2025/1833

Public-Key Encryption from the MinRank Problem

Rohit Chatterjee

, National University of Singapore

Changrui Mu

, Carnegie Mellon University

Prashant Nalini Vasudevan

, National University of Singapore

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.
Keywords: Public Key Cryptography Post-Quantum Cryptography Code-based Cryptography MinRank
Contact author(s): rochat @ nus edu sg
changrui mu @ u nus edu
prashvas @ nus edu sg
History: 2025-10-08: approved; 2025-10-04: received; See all versions
Short URL: https://ia.cr/2025/1833
License: CC BY

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}
}