Public-Key Encryption from the MinRank Problem

Rohit Chatterjee, Changrui Mu, Prashant Nalini Vasudevan

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…