Ouroboros-E: An efficient lattice-based key-exchange protocol

Published in IEEE International Symposium on Information Theory (ISIT) 2018, 2018

Recommended citation: Deneuville, J.-C., Gaborit, P., Guo, Q., and Johansson, T. (2018, June). Ouroboros-E: An Efficient Lattice-based Key-Exchange Protocol. In 2018 IEEE International Symposium on Information Theory (ISIT) (pp. 1450-1454). IEEE. https://deneuville.github.io/files/ISIT18.pdf


The BitFlipping algorithm is a hard decision decoding algorithm originally designed by Gallager in 1962 to decode Low Density Parity Check Codes (LDPC). It has recently proved to be much more versatile, for Moderate Parity Check Codes (MDPC) or Euclidean metric. We further demonstrate its power by proposing a noisy Euclidean version of it. This tweak allows to construct a lattice based key exchange analogous to the Ouroboros protocol for Hamming metric but with a reduction to the Short Integer Solution (SIS) problem. The very efficient decoding algorithm permits to consider smaller alphabets than for NTRU or Ring-LWE decryption algorithms. Overall we obtain a new protocol which competes with the recent NewHope and Kyber proposals, and also with NTRU. The resulting scheme exploits the cyclicity of the error, and benefits from the security of the renowned SIS problem.

Download paper here


  title={Ouroboros-{E}: An Efficient Lattice-based Key-Exchange Protocol},
  author={Deneuville, {Jean-Christophe} and Gaborit, Philippe and Guo, Qian and Johansson, Thomas},
  booktitle={2018 IEEE International Symposium on Information Theory (ISIT)},