{"ID":2860549,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2510.03752","arxiv_id":"2510.03752","title":"Public-Key Encryption from the MinRank Problem","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.","short_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 arisi...","url_abs":"https://arxiv.org/abs/2510.03752","url_pdf":"https://arxiv.org/pdf/2510.03752v1","authors":"[\"Rohit Chatterjee\",\"Changrui Mu\",\"Prashant Nalini Vasudevan\"]","published":"2025-10-04T09:31:58Z","proceeding":"cs.CR","tasks":"[\"cs.CR\"]","methods":"[]","has_code":false}