Wyner-Ziv reconciliation for key exchange based on Ring-LWE

Charbel Saliba; Laura Luzzi; Cong Ling

Paper 2020/076

Wyner-Ziv reconciliation for key exchange based on Ring-LWE

Charbel Saliba, Laura Luzzi, and Cong Ling

Abstract

We consider a key encapsulation mechanism (KEM) based on ring-LWE where reconciliation is performed on an $N$-dimensional lattice using Wyner-Ziv coding. More precisely, we consider Barnes-Wall lattices and use Micciancio and Nicolosi's bounded distance decoder with polynomial complexity $\mathcal{O}(N \log^2(N))$. We show that in the asymptotic regime for large $N$, the achievable key rate is $\Theta(\log N)$ bits per dimension, while the error probability $P_e$ vanishes exponentially in $N$. Unlike previous works, our scheme does not require a dither.

Metadata

Available format(s): PDF
Category: Public-key cryptography
Publication info: Preprint. MINOR revision.
Contact author(s): c ling @ imperial ac uk
History: 2020-01-26: received
Short URL: https://ia.cr/2020/076
License: CC BY

BibTeX

@misc{cryptoeprint:2020/076,
      author = {Charbel Saliba and Laura Luzzi and Cong Ling},
      title = {Wyner-Ziv reconciliation for key exchange based on Ring-{LWE}},
      howpublished = {Cryptology {ePrint} Archive, Paper 2020/076},
      year = {2020},
      url = {https://eprint.iacr.org/2020/076}
}