Welcome to the resource topic for 2020/1555
Title:
Limits on the Efficiency of (Ring) LWE based Non-Interactive Key Exchange
Authors: Siyao Guo, Pritish Kamath, Alon Rosen, Katerina Sotiraki
Abstract: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 LWE-modulus, resulting in unwanted efficiency overhead. We study the possibility of designing non-interactive LWE-based protocols with polynomial LWE-modulus. To this end, • We identify and formalize simple non-interactive and polynomial LWE-modulus variants of existing protocols, where Alice and Bob simultaneously exchange one or more (ring) LWE samples with polynomial 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 LWE sample with their private LWE secret. This impossibility is information theoretic. 2) one of the reconciliation functions does not depend on the error of the transmitted LWE sample. This impossibility assumes hardness of LWE. • We give further evidence that progress in either direction, of giving an LWE-based 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) LWE-based non-interactive key exchange protocols.
ePrint: https://eprint.iacr.org/2020/1555
Talk: https://www.youtube.com/watch?v=sH8A7BD9iYQ
Slides: https://iacr.org/submit/files/slides/2020/pkc/pkc2020/209/slides.pptx
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .