CryptoDB
Limits on the Efficiency of (Ring) LWE Based Non-interactive Key Exchange
| Authors: | |
|---|---|
| Download: | |
| Presentation: | Slides |
| Abstract: | $$mathsf {LWE}$$ based key-exchange protocols lie at the heart of post-quantum public-key cryptography. However, all existing protocols either lack the non-interactive nature of Diffie-Hellman key-exchange or polynomial $$mathsf {LWE}$$ -modulus, resulting in unwanted efficiency overhead. We study the possibility of designing non-interactive $$mathsf {LWE}$$ -based protocols with polynomial $$mathsf {LWE}$$ -modulus. To this end, We identify and formalize simple non-interactive and polynomial $$mathsf {LWE}$$ -modulus variants of existing protocols, where Alice and Bob simultaneously exchange one or more (ring) $$mathsf {LWE}$$ samples with polynomial $$mathsf {LWE}$$ -modulus and then run individual key reconciliation functions to obtain the shared key. We point out central barriers and show that such non-interactive key-exchange protocols are impossible if: (1) the reconciliation functions first compute the inner product of the received $$mathsf {LWE}$$ sample with their private $$mathsf {LWE}$$ secret. This impossibility is information theoretic. (2) One of the reconciliation functions does not depend on the error of the transmitted $$mathsf {LWE}$$ sample. This impossibility assumes hardness of $$mathsf {LWE}$$ . We give further evidence that progress in either direction, of giving an $$mathsf {LWE}$$ -based $$mathrm {NIKE}$$ protocol or proving impossibility of one will lead to progress on some other well-studied questions in cryptography. Overall, our results show possibilities and challenges in designing simple (ring) $$mathsf {LWE}$$ -based non-interactive key exchange protocols. |
Video from PKC 2020
BibTeX
@article{pkc-2020-30293,
title={Limits on the Efficiency of (Ring) LWE Based Non-interactive Key Exchange},
booktitle={Public-Key Cryptography – PKC 2020},
series={Public-Key Cryptography – PKC 2020},
publisher={Springer},
volume={12110},
pages={374-395},
doi={10.1007/978-3-030-45374-9_13},
author={Siyao Guo and Pritish Kamath and Alon Rosen and Katerina Sotiraki},
year=2020
}