\(\mathsf {LWE}\)-based key-exchange protocols lie at the heart of post-quantum public-key cryptography. However, all existing protocols either lack thenon-interactive nature of Diffie–Hellman key exchange orpolynomial\(\mathsf {LWE}\)-modulus, resulting in unwanted efficiency overhead. We study the possibility of designing non-interactive\(\mathsf {LWE}\)-based protocols withpolynomial\(\mathsf {LWE}\)-modulus. To this end, we identify and formalize simple non-interactive and polynomial\(\mathsf {LWE}\)-modulus variants of the existing protocols, where Alice and Bobsimultaneously 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 in either of the following cases: (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 show that progress toward either a polynomial\(\mathsf {LWE}\)-modulus\(\text {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}\)-based non-interactive key-exchange protocols.

1. For simplicity, we only describe the\(\mathsf {LWE}\)-based variant; the ring version is obtained by replacing\({\varvec{A}},{\varvec{x}}_1,{\varvec{x}}_2, {\varvec{e}}_1,{\varvec{e}}_2\) with ring elements from some chosen polynomial ring and using the corresponding polynomial multiplication.

2. A typical size ofq is\(\approx 2^{13}\) and there are proposals that even use\(q = 257\) [18].

3. Note that by symmetry and monotonicity of\(\mathcal {D}_\beta \),\(\Pr [ax = 0] \le \Pr [a(|x| -1) = 0] + \Pr [x = 0]\). Combining with the fact that\(\Pr [ax=0]+\Pr [a(|x| -1) = 0]\le 1\) for\(a\ne 0\), and\(\Pr [x = 0]\le 1/(1 + 2e^{-1/\beta ^2})\), we conclude that\(\Pr [ax = 0]\le (1+ \Pr [x = 0])/2\le 9/10\) for\(\beta >10\).

4. If\({\varvec{w}}= (w^{(1)},w^{(2)}, \dots , w^{(n)})\) such that\(\gcd (w^{(1)},w^{(2)}, \dots , w^{(n)}, q) = 1\) and\(\mathbf {u}\) is uniform in\(\mathbb {Z}_q^n\), then\({\varvec{w}}^T\mathbf {u}\) is also uniform in\(\mathbb {Z}_q\).

5. The top singular value being 1.

6. Observe that since\(\xi \) is a probability distribution over\(\mathbb {Z}_q^k\), it follows that\(\mu \) is also a probability distribution.

7. Because for\(x \in [-\pi /2, \pi /2]\),\(\cos (x) \le 1- x^2/(4\pi ^2)\).

8. Because for\(x \in [-\pi /2, \pi /2]\),\(\cos (\pi + x) \ge -1+ x^2/(4\pi ^2)\).

9. In particular, Bogdanov et al. [4] showed that\(\text {RD}_2(1+\mathcal {D}_\sigma ||\mathcal {D}_\sigma ) = \exp (2\pi (1/\sigma )^2)\) which is bounded away from 1 for any discrete Gaussian distribution\(\mathcal {D}_\sigma \) with standard deviation\(\sigma \ge 1\).

The authors thank Martin Albrecht, Jacob Alperin-Sheriff, Prabhanjan Ananth, Leo Ducas, Daniel Wichs and anonymous reviewers of PKC 2020 and Journal of Cryptology for useful comments and advice.

Authors and Affiliations

1. NYU, Shanghai, China

   Siyao Guo

2. TTIC, Chicago, USA

   Pritish Kamath

3. IDC, Herzliya, Israel

   Alon Rosen

4. UC, Berkeley, USA

   Katerina Sotiraki

Corresponding author

Correspondence toKaterina Sotiraki.

Communicated by Damien Stehlé

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Supported by Shanghai Eastern Young Scholar Program SMEC-0920000169 and the NYU Shanghai Boost Fund.

Work done while at MIT, supported by NSF awards CCF-1733808, IIS-1741137 and MIT-IBM Watson AI Lab and Research Collaboration Agreement No. W1771646.

Supported by ISF Grant No. 1399/17 and via Project PROMETHEUS (Grant 780701).

Work done while at MIT, research supported in part by NSF/BSF Grant #1350619, an MIT-IBM grant, a DARPA Young Faculty Award, MIT Lincoln Laboratories and Analog Devices

A Self-contained Proof of Theorem1

In Sect.4, we use two Lemmas2 and4 in order to bound the key agreement probability by\(\max _{c\in \mathbb {Z}_q{\setminus }\{0\}}|{\mathbb {E}}_{e \leftarrow \xi }[\chi _c(e)]\). In this section, we give a self-contained proof for Lemma3 without explicitly using the notion of maximal correlation. However, this proof is essentially an unrolling of the proof using maximal correlation.

Claim 3

For any\(m\ge 1\), balanced\(f,g:\mathbb {Z}^m_q\rightarrow \{0,1\}\), and\(\mu _\mathcal {X}\) as in Theorem1, it holds that

where for any\(z \in \mathbb {Z}_q\),\(\xi (z)=\Pr [{\varvec{x}}_1^T{\varvec{e}}_2 - {\varvec{e}}_1^T{\varvec{x}}_2 = z]\).

Combining the above claim with the fact that\(\max _{c\in \mathbb {Z}_q{\setminus }\{0\}} |{\mathbb {E}}_{e \leftarrow \xi }[\chi _c(e)]|\le 1-\Omega (1/q^2)\) (see Claims1 and2), Theorem1 follows.

Proof

Let\(F({\varvec{x}})=(-1)^{f({\varvec{x}})}\) and\(G({\varvec{x}})=(-1)^{g({\varvec{x}})}\). Then, for any\({\varvec{c}}\in \mathbb {Z}_q^m\), let\(\hat{F}({\varvec{c}})={\mathbb {E}}_{{\varvec{x}}\leftarrow \mathcal {U}(\mathbb {Z}_q^m)} [F({\varvec{x}})\chi _{{\varvec{c}}}(-{\varvec{x}})]\) and\(\hat{G}({\varvec{c}})= {\mathbb {E}}_{{\varvec{x}}\leftarrow \mathcal {U}(\mathbb {Z}_q^m)}[G({\varvec{x}})\chi _{{\varvec{c}}}(-{\varvec{x}})]\). Note that for any\({\varvec{x}}\in \mathbb {Z}_q^m\),\(F({\varvec{x}})=\sum _{{\varvec{c}}\in \mathbb {Z}_q^m}\hat{F}({\varvec{c}})\chi _{{\varvec{c}}}({\varvec{x}})\) and\(G({\varvec{x}})=\sum _{{\varvec{c}}\in \mathbb {Z}_q^m}\hat{G}({\varvec{c}})\chi _{{\varvec{c}}}({\varvec{x}})\). Observe that\({\varvec{X}}\) is distributed uniformly and\({\varvec{Y}}={\varvec{X}}+{\varvec{e}}\), where\({\varvec{e}}\leftarrow \xi ^{\otimes m}\).

The first equality follows by linearity of expectation and the fact that\({\varvec{X}}\) is uniform over\(\mathbb {Z}^m_q\). For the next inequality, we use triangle inequality and that\(|{\mathbb {E}}[\chi _{{\varvec{c}}}({\varvec{e}})]|\) is real, since\(\xi \) is symmetric. The next two inequalities follow by Cauchy–Schwarz and Parseval’s identity, which states that\(\sum _{\varvec{c}}{\left|\hat{F}({\varvec{c}}) \right|}^2 = {\mathbb {E}}\left[ {\left|F({\varvec{X}}) \right|}^2\right] = 1\). The desired conclusion follows from the fact that\(\Pr [f({\varvec{X}})=g({\varvec{Y}})]=\frac{1+{\mathbb {E}}[\overline{F({\varvec{X}})}G({\varvec{Y}})]}{2}\).\(\square \)

Ring-LWE case. We get a similar result for the Ring-LWE case. In this case, we say that\({\varvec{w}}\) is drawn from\((\mathcal {X}^n)^{*}\) if its coefficients are drawn from\(\mathcal {X}^n\) conditioned on\({\varvec{w}}\) being a unit of\(R_q\).

Theorem 5

Let\(n,q\ge 1\) be integers and\(R_q\) be as above. Assume that the distribution\(\mathcal {X}\) over\(\mathbb {Z}_q\) is symmetric and for any\(a\in \mathbb {Z}_q{\setminus }\{0\}\),\(\Pr [az= 0]\le 9/10\) and\(\Pr [az= q/2]\le 9/10\) and\((\mathcal {X}^n)^*\) as above. Let\(\mu _{\text {RLWE},\mathcal {X}}({\varvec{X}},{\varvec{Y}})\) be the joint distribution of

where\(\cdot \) is polynomial multiplication,\({\varvec{a}}\leftarrow \mathcal {U}(R_q)\),\({\varvec{e}}_1,{\varvec{e}}_2\leftarrow \mathcal {X}^n\) and\({\varvec{x}}_1,{\varvec{x}}_2\leftarrow (\mathcal {X}^n)^{*}\). Then for any\(m\ge 1\), and any balanced functions\(\text {Rec}_1,\text {Rec}_2:R^m\rightarrow \{0,1\}\) with respect to the marginal distributions of\(\mu _{\text {RLWE},\mathcal {X}}^{\otimes m}\), it holds that

Proof

We proceed as in the LWE case by proving claims similar to Claims1,2 and3. For\({\varvec{c}}\in R_q\), we define\(\chi _{{\varvec{c}}}:R_q\rightarrow \mathbb {C}\) as\(\chi _{{\varvec{c}}}({\varvec{x}}) = e^{-2\pi i \cdot \left\langle {\varvec{c}}, {\varvec{x}} \right\rangle /q}\), where\(\left\langle {\varvec{c}}, {\varvec{x}} \right\rangle \) is the inner product of the coefficient vectors of\({\varvec{c}}\) and\({\varvec{x}}\) over\(\mathbb {Z}_q\). Then, the following claims hold.

Claim 4

For any\(m\ge 1\) and balanced\(f,g:R^m_q\rightarrow \{0,1\}\), it holds that

where for any\({\varvec{z}}\in R_q\),\(\xi ({\varvec{z}})=\Pr [{\varvec{x}}_1\cdot {\varvec{e}}_2 - {\varvec{e}}_1\cdot {\varvec{x}}_2 = {\varvec{z}}]\).

Claim 5

\(|{\mathbb {E}}_{{\varvec{e}}\leftarrow \xi }[\chi _{\varvec{a}}({\varvec{e}})]|\le \max _{{\varvec{c}}\in R_q{\setminus } \{\varvec{0}^n\}} {\mathbb {E}}_{{\varvec{e}}\leftarrow \mathcal {X}^n}[\chi _{\varvec{c}}({\varvec{e}})]|\).

Claim 6

For any\({\varvec{c}}\in R_q{\setminus }\{\varvec{0}^n\}\),\(|{\mathbb {E}}_{{\varvec{e}}\leftarrow \mathcal {X}^n}[\chi _{\varvec{c}}({\varvec{e}})]|\le 1-\Omega (1/q^2)\).

The proofs are almost identical to the corresponding proofs of Claims1,2 and3, so we omit them.\(\square \)

Reprints and permissions