Advanced

Ouroboros-E : An Efficient Lattice-based Key-Exchange Protocol

Deneuville, Jean Christophe; Gaborit, Philippe; Guo, Qian LU and Johansson, Thomas LU (2018) 2018 IEEE International Symposium on Information Theory, ISIT 2018 2018-June. p.1450-1454
Abstract

The Bit Flipping 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... (More)

The Bit Flipping 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.

(Less)
Please use this url to cite or link to this publication:
author
organization
publishing date
type
Chapter in Book/Report/Conference proceeding
publication status
published
subject
host publication
2018 IEEE International Symposium on Information Theory, ISIT 2018
volume
2018-June
pages
5 pages
publisher
Institute of Electrical and Electronics Engineers Inc.
conference name
2018 IEEE International Symposium on Information Theory, ISIT 2018
conference location
Vail, United States
conference dates
2018-06-17 - 2018-06-22
external identifiers
  • scopus:85052477089
ISBN
9781538647806
DOI
10.1109/ISIT.2018.8437940
language
English
LU publication?
yes
id
3c7fb5e0-bf06-4d40-ad76-250dbc4b261d
date added to LUP
2018-10-03 10:40:48
date last changed
2019-02-20 11:28:44
@inproceedings{3c7fb5e0-bf06-4d40-ad76-250dbc4b261d,
  abstract     = {<p>The Bit Flipping 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.</p>},
  author       = {Deneuville, Jean Christophe and Gaborit, Philippe and Guo, Qian and Johansson, Thomas},
  isbn         = {9781538647806},
  language     = {eng},
  location     = {Vail, United States},
  month        = {08},
  pages        = {1450--1454},
  publisher    = {Institute of Electrical and Electronics Engineers Inc.},
  title        = {Ouroboros-E : An Efficient Lattice-based Key-Exchange Protocol},
  url          = {http://dx.doi.org/10.1109/ISIT.2018.8437940},
  volume       = {2018-June},
  year         = {2018},
}