# A Simple Provably Secure Key Exchange Scheme Based on the Learning with Errors Problem

In this paper (A simple provably secure key exchange by Ding et al.) At page number 8, the author gives correctness of the technique as follows

then SK A = SKB with overwhelming probability i.e. if Alice and Bob run the protocol honestly, then they will share an identical key.

The above equation uses Lemma 1 which is as follows

How does the author deduce the above equation using Lemma 1. This equation gives correctness of the technique. Can anyone please help.

• There's a reference to Lemma 1 in what you've reproduced. That lemma's the key. Commented May 25, 2017 at 11:54
• Thanks for replying. How he used lemma 1 to produce this equation Commented May 25, 2017 at 12:11
• I don't have time for a full answer right now. You should add lemma 1 to the question so someone else can use it in their answer. Commented May 25, 2017 at 12:22
• Please see the related posted question on crypto.stackexchange.com/questions/48147/… Thanks Commented Jun 10, 2017 at 6:11
• Please see this bquestion crypto.stackexchange.com/questions/48566/… Commented Jun 23, 2017 at 11:35

First: Lemma 1 says that $||\mathbf{x}|| \leq \alpha q \sqrt{n}$ with overwhelming probability if $\mathbf{x}$ is drawn from the discrete Gaussian since $\frac{1}{2^n}$ is negligible.

Next, from properties of absolute values, $|a + b| \leq |a| + |b|$. So, leaving the $2$ out for now and writing $\mathbf{s_A}^T\mathbf{e_B}$ as $\mathbf{s_A}\cdot\mathbf{e_B}$:

$|\mathbf{s_A}\cdot\mathbf{e_B} + e'_A + \mathbf{s_B}\cdot\mathbf{e_A} + e'_B| \leq |\mathbf{s_A}\cdot\mathbf{e_B}| + |e'_A| + |\mathbf{s_B}\cdot\mathbf{e_A}| + |e'_B|$.

Now, for Euclidean norms, Cauchy-Schwarz says $|\mathbf{a\cdot b}| \leq |\mathbf{a}|\cdot |\mathbf{b}|$, so we have, for example, $|\mathbf{s_A}\cdot\mathbf{e_B}| \leq |\mathbf{s_A}| \cdot |\mathbf{e_B}| \leq (\alpha q \sqrt{n})\cdot (\alpha q \sqrt{n})$, the last inequality coming from Lemma 1.

Let's tackle $e'_A$ and $e'_B$. I could sample a vector $\mathbf{e'}$ from $\mathcal{D_{\mathbb{Z^n},\alpha q}}$ and Lemma 1 would apply to it; if $e'_A$ is a member of $\mathbf{e'}$, it is certainly smaller than $||\mathbf{e'}||$:

$|e'_A| \leq ||\mathbf{e'_A}|| \leq \alpha q \sqrt{n} \leq (\alpha q \sqrt{n})\cdot (\alpha q \sqrt{n})$. Same for $e'_B$.

Thus I have four terms, all $\leq (\alpha q \sqrt{n})\cdot (\alpha q \sqrt{n})$. Multiply back in that $2$ and you have the result.

## Edit

They do a similar procedure later on in Section 4, and explicitly write out norms, for future reference.

• Sir I understand that value of |SA* eB|≤|SA| |eB|≤(αq√n). (αq√n) as ||SA||≤(αq√n) and ||eB||≤(αq√n) but how would alone |e'B|≤(αq√n). (αq√n). Thanks Commented May 26, 2017 at 4:28
• I was making a transitive argument: if $A \leq B$ and $B \leq C$, then $A \leq C$. Since $|e'_B| \leq ||\mathbb{e'_B}||$ (true since $e'_B$ is a member of $\mathbb{e'_B}$, and $\mathbb{e'_B} \leq \alpha q \sqrt{n}$ (from Lemma 1, and $\alpha q \sqrt{n} \leq \alpha q \sqrt{n} \cdot \alpha q \sqrt{n}$ (true for numbers bigger than 1), we have $|e'_B| \leq \alpha q \sqrt{n} \cdot \alpha q \sqrt{n}$. Does that make sense? It's a chain of inequalities.
– user47922
Commented May 26, 2017 at 4:42
• Also: only $e'_B$ is in the paper, and is a scalar. $\mathbb{e'_B}$ is a vector I introduced so that I could use Lemma 1; recall that it deals with vector samples. In the paper, they drew the scalar $e'_B$ directly from $\mathcal{D_{\mathbb{Z},\alpha q}}$. Instead, I drew a vector $\mathbb{e'_B}$ from $\mathcal{D_{\mathbb{Z^n},\alpha q}}$ to use Lemma 1.
– user47922
Commented May 26, 2017 at 4:46
• ok sir understood. Thanks for putting up lot of effort. Commented May 26, 2017 at 6:21
• I have confusion in lemma 2 on page number 6. Can you please explain its proof. Commented Jun 9, 2017 at 8:59

This lemma is used to conclude that a sample from $\mathcal{D}_{\mathbb{Z}^n,\alpha q}$ is (with overwhelming probability) less than or equal to $\alpha q \sqrt{n}$.

Now, because all values $\textbf{s}_{\textbf{A}},\textbf{s}_{\textbf{B}},\textbf{e}'_{\textbf{A}},\textbf{e}'_{\textbf{B}}$ are sampled from $\mathcal{D}_{\mathbb{Z}^n,\alpha q}$ , so $\textbf{s}_{\textbf{A}}^T\textbf{e}_{\textbf{B}}$ is less than or equal to $(\alpha q \sqrt{n})(\alpha q \sqrt{n})$. This bound is also true for each of other values $\textbf{e}_{\textbf{A}}^T\textbf{s}_{\textbf{B}}, \textbf{e}'_{\textbf{A}},\textbf{e}'_{\textbf{B}}$ and so the upper bound is determined.

• Oops! Didn't see your answer. I spent about an hour trying to figure out how to type $\mathcal{D_{\mathbb{Z^n},\alpha q}}$.
– user47922
Commented May 25, 2017 at 21:42
• @hamidreza I accept galvatron explanation as answer, as it contains detailed explanation. Thanks for answering. Commented May 26, 2017 at 6:23
• @hamidreza Please see the related posted question on crypto.stackexchange.com/questions/48147/…. Thanks Commented Jun 10, 2017 at 6:10