Wyner-Ziv reconciliation for key exchange based on Ring-LWE
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 O(N log(N)^2). We show that in the asymptotic regime for large N, the achievable key rate is Θ(log N) bits per dimension, while the error probability P_e ≈O(e^-Nϵ). Unlike previous works, our scheme does not require a dither.
READ FULL TEXT