5
$\begingroup$

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
enter image description here

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

enter image description here

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

$\endgroup$
7
  • $\begingroup$ There's a reference to Lemma 1 in what you've reproduced. That lemma's the key. $\endgroup$ Commented May 25, 2017 at 11:54
  • $\begingroup$ Thanks for replying. How he used lemma 1 to produce this equation $\endgroup$
    – vivek
    Commented May 25, 2017 at 12:11
  • $\begingroup$ 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. $\endgroup$ Commented May 25, 2017 at 12:22
  • $\begingroup$ Please see the related posted question on crypto.stackexchange.com/questions/48147/… Thanks $\endgroup$
    – vivek
    Commented Jun 10, 2017 at 6:11
  • $\begingroup$ Please see this bquestion crypto.stackexchange.com/questions/48566/… $\endgroup$
    – vivek
    Commented Jun 23, 2017 at 11:35

2 Answers 2

6
$\begingroup$

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.

$\endgroup$
7
  • $\begingroup$ 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 $\endgroup$
    – vivek
    Commented May 26, 2017 at 4:28
  • $\begingroup$ 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. $\endgroup$
    – user47922
    Commented May 26, 2017 at 4:42
  • $\begingroup$ 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. $\endgroup$
    – user47922
    Commented May 26, 2017 at 4:46
  • $\begingroup$ ok sir understood. Thanks for putting up lot of effort. $\endgroup$
    – vivek
    Commented May 26, 2017 at 6:21
  • $\begingroup$ I have confusion in lemma 2 on page number 6. Can you please explain its proof. $\endgroup$
    – vivek
    Commented Jun 9, 2017 at 8:59
4
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ 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}}$. $\endgroup$
    – user47922
    Commented May 25, 2017 at 21:42
  • $\begingroup$ @hamidreza I accept galvatron explanation as answer, as it contains detailed explanation. Thanks for answering. $\endgroup$
    – vivek
    Commented May 26, 2017 at 6:23
  • $\begingroup$ @hamidreza Please see the related posted question on crypto.stackexchange.com/questions/48147/…. Thanks $\endgroup$
    – vivek
    Commented Jun 10, 2017 at 6:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.