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

##### Abstract

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)
Category
Public-key cryptography
Publication info
Preprint.
Keywords
Code-based cryptography Rank-metric cryptography Post-quantum cryptography
Contact author(s)
victor dyseryn_fostier @ unilim fr
History
2022-11-21: approved
See all versions
Short URL
https://ia.cr/2022/1596

CC BY

BibTeX

@misc{cryptoeprint:2022/1596,
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{https://eprint.iacr.org/2022/1596}},
url = {https://eprint.iacr.org/2022/1596}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.