Limits on the Efficiency of (Ring) LWE Based Non-interactive Key Exchange

摘要

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, 1. 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. 2. 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. 3. 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.