## CryptoDB

### Pritish Kamath

#### Publications

Year
Venue
Title
2021
JOFC
$\mathsf {LWE}$ 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}$ LWE -modulus, resulting in unwanted efficiency overhead. We study the possibility of designing non-interactive $\mathsf {LWE}$ LWE -based protocols with polynomial $\mathsf {LWE}$ LWE -modulus. To this end, we identify and formalize simple non-interactive and polynomial $\mathsf {LWE}$ LWE -modulus variants of the existing protocols, where Alice and Bob simultaneously exchange one or more (ring) $\mathsf {LWE}$ LWE samples with polynomial $\mathsf {LWE}$ 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 in either of the following cases: (1) the reconciliation functions first compute the inner product of the received $\mathsf {LWE}$ LWE sample with their private $\mathsf {LWE}$ LWE secret. This impossibility is information theoretic. (2) One of the reconciliation functions does not depend on the error of the transmitted $\mathsf {LWE}$ LWE sample. This impossibility assumes hardness of $\mathsf {LWE}$ LWE . We show that progress toward either a polynomial $\mathsf {LWE}$ LWE -modulus $\text {NIKE}$ NIKE construction or a general impossibility result has implications to the current understanding of lattice-based cryptographic constructions. Overall, our results show possibilities and challenges in designing simple (ring) $\mathsf {LWE}$ LWE -based non-interactive key-exchange protocols.
2020
PKC
$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.

#### Coauthors

Siyao Guo (2)
Alon Rosen (2)
Katerina Sotiraki (2)