# 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. – Michael Snook May 25 '17 at 11:54
• Thanks for replying. How he used lemma 1 to produce this equation – vivek May 25 '17 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. – Michael Snook May 25 '17 at 12:22
• Please see the related posted question on crypto.stackexchange.com/questions/48147/… Thanks – vivek Jun 10 '17 at 6:11
• Please see this bquestion crypto.stackexchange.com/questions/48566/… – vivek Jun 23 '17 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 – vivek May 26 '17 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 May 26 '17 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 May 26 '17 at 4:46
• ok sir understood. Thanks for putting up lot of effort. – vivek May 26 '17 at 6:21
• I have confusion in lemma 2 on page number 6. Can you please explain its proof. – vivek Jun 9 '17 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 May 25 '17 at 21:42
• @hamidreza I accept galvatron explanation as answer, as it contains detailed explanation. Thanks for answering. – vivek May 26 '17 at 6:23
• @hamidreza Please see the related posted question on crypto.stackexchange.com/questions/48147/…. Thanks – vivek Jun 10 '17 at 6:10

A question came to when reading this is that: in section 4 (lemma 9), they claim that $8n\beta^2\leq q/4-2$, then $SK_a=SK_b$.

My question is that since they use $l_\infty$ norm as they said at beginning of section 4, does $||a\cdot b||_\infty \leq ||a||_\infty\cdot ||b||_\infty$ holds? It seems that for infinity norm, above inequality may not hold. If so, how do they compute $8n\beta^2\leq q/4-2$?

• Answers are not the place to ask questions. You should post this as a new question with a link to the current question. – mikeazo Aug 22 '17 at 11:45