Paper 2022/1596

LowMS: a new rank metric code-based KEM without ideal structure

Nicolas Aragon, NAQUIDIS Center
Victor Dyseryn, XLIM, University of Limoges
Philippe Gaborit, XLIM, University of Limoges
Pierre Loidreau, University of Rennes 1, Direction Générale de l'Armement, French National Centre for Scientific Research, IRMAR
Julian Renner, Technical University of Munich
Antonia Wachter-Zeh, Technical University of Munich

We propose and analyze LowMS, a new rank-based key encapsulation mechanism (KEM). The acronym stands for Loidreau with Multiple Syndromes, since our work combines the cryptosystem of Loidreau (presented at PQCrypto 2017) together with the multiple syndrome approach, that allows to reduce parameters by sending several syndromes with the same error support in one ciphertext. Our scheme is designed without using ideal structures. Considering cryptosystems without such an ideal structure, like the FrodoKEM cryptosystem, is important since structure allows to compress objects, but gives reductions to specific problems whose security may potentially be weaker than for unstructured problems. For 128 bits of security, we propose parameters with a public key size of 4,6KB and a ciphertext size of 1,1KB. To the best of our knowledge, our scheme is the smallest among all existing unstructured post-quantum lattice or code-based algorithms, when taking into account the sum of the public key size and the ciphertext size. In that sense, our scheme is for instance about 4 times shorter than FrodoKEM. Our system relies on the hardness of the Rank Support Learning problem, a well-known variant of the Rank Syndrome Decoding problem, and on the problem of indistinguishability of distorted Gabidulin codes, i.e. Gabidulin codes multiplied by an homogeneous matrix of given rank. The latter problem was introduced by Loidreau in his paper.

Available format(s)
Public-key cryptography
Publication info
Code-based cryptography Rank-metric cryptography Post-quantum cryptography
Contact author(s)
victor dyseryn_fostier @ unilim fr
2022-11-21: approved
2022-11-16: received
See all versions
Short URL
Creative Commons Attribution


      author = {Nicolas Aragon and Victor Dyseryn and Philippe Gaborit and Pierre Loidreau and Julian Renner and Antonia Wachter-Zeh},
      title = {LowMS: a new rank metric code-based KEM without ideal structure},
      howpublished = {Cryptology ePrint Archive, Paper 2022/1596},
      year = {2022},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.