LRPC codes with multiple syndromes: near ideal-size KEMs without ideals. (arXiv:2206.11961v1 [cs.CR])

We introduce a new rank-based key encapsulation mechanism (KEM) with public
key and ciphertext sizes around 3.5 Kbytes each, for 128 bits of security,
without using ideal structures. Such structures allow to compress objects, but
give reductions to specific problems whose security is potentially weaker than
for unstructured problems. To the best of our knowledge, our scheme improves in
size all the existing unstructured post-quantum lattice or code-based
algorithms such as FrodoKEM or Classic McEliece. Our technique, whose
efficiency relies …

size