2
$\begingroup$

In this paper, on page 33, we are presented with Claim 5.2 which is supposed to show that for the selected parameters in LWE, namely:

  • $\alpha(n)=o(1/(\sqrt{n}\log n))$
  • $p\ge 2$ and $n^2<p<2n^2$ and is a prime
  • $m=(1+\varepsilon)(n+1)\bmod p, \varepsilon > 0$

It holds that $$\Pr_{e\sim\chi^{\star k}}\left[|e|<\frac{\left\lfloor\frac{p}{2}\right\rfloor}{2}\right] > 1-\delta(n)$$Where $\delta(n)$ is a negligible function in $n$.

I am having trouble understanding the proof, specifically why the sample taken from $\chi^{\star k}$ which is the same as $\sum_{i=1}^k{\lfloor px_i\rceil\bmod{p}}$, and the difference between it and the value $\sum_{i=1}^k{px_i}\bmod p$ is at most $k\le m<\frac{p}{32}$.

Initially I thought it might be due to the difference in magnitude (where $m=O(n\log n), p=O(n^2)$, but in that case, the $\frac{p}{32}$ could be some other constant (for example $\frac{p}{12}$). Then I saw this paper which talks about the standard deviation. Thinking about it more I though that it might be something along the lines of $k$ times the standard deviation, however this doesn't actually help me.

I'd appreciate if someone could help me figure this out.

Thanks.

$\endgroup$

2 Answers 2

1
$\begingroup$

Not marking as the answer because I am not fully sure that this is the correct answer to this question. This is what I came up with after consulting with friends, it does check out, but might not be the right way to solve it:

Theorem: If for some $m=1.1n\log p$ and $n^2<p<2n^2$ is a prime, it holds that for any $k\in\{0,1,...,m\}$:$$\Pr_{e\sim\chi^{\star k}}\left[|e|<\frac{\left\lfloor\frac{p}{2}\right\rfloor}{2}\right] > 1-\delta(n)$$for some negligible function in $n$: $\delta(n)$.

Proof: We first want to clarify the following:$$\text{Sampling }\chi^{\star k}=\text{Sampling }\overline{\Psi}_{\alpha}^{\star k}$$ The latter half is sampling the additive sum distribution of the discretization of $\Psi_{\alpha}$ for $k$. Since $\Psi_{\alpha}$ is the normal distribution (with defined variance and mean according to the overview section) in $\mathbb{T}$, it means that every value sampled from $\Psi_{\alpha}$ will be in $[0,1)$. This means that multiplying it by $p$, will yield a value that is distributed in accordance with the $\Psi_{\alpha}$ distribution but scaled by a factor of $p$. Due to the above, we can deduce that sampling a single value from $\overline{\Psi}_{\alpha}$ is identical to sampling a value from $\Psi_{\alpha}$, scaling it by $p$ and getting the whole part of it:$$x\sim\Psi_{\alpha}\rightarrow \lfloor px\rceil\sim\overline{\Psi}_{\alpha}$$ Furthering this idea, we can safely say that sampling from the additive sum distribution $\overline{\Psi}_{\alpha}^{\star k}$ is equal to sampling $k$ values from $\overline{\Psi}_{\alpha}$, scaling each by a factor of $p$, rounding and then performing modulo $p$ on the resulting value:$$\begin{array}{c}x_1\sim\overline{\Psi}_{\alpha}, x_2\sim\overline{\Psi}_{\alpha},...,x_k\sim\overline{\Psi}_{\alpha}\\\\ x=\sum_{i=1}^{k}\lfloor px_i\rceil\bmod{p}\\\\ x\sim\overline{\Psi}_{\alpha}^{\star k}\end{array}$$ Given normal probability distributions we know that $\Pr[X<x]=\Phi(z)$ where $z=\frac{x-\mu}{\sigma}$ and $\Phi$ is the CDF of the normal distribution. We will show that for $x=\frac{p}{4}$, the resulting value is $1-\delta(n)$ for a negligible function $\delta(n)$. We first prove that the standard deviation is less than $\frac{p}{\sqrt{\log n}}$ and then we show that the function $1-\Phi(z)$ with the aforementioned $z$ is negligible, and as a result we will see that the above probability is $1-\delta(n)$ for some negligible function $\delta(n)$.

Standard Deviation Upper Bound - we first want to prove that the standard deviation of $\overline{\Psi}^{\star k}_\alpha$ is less than $\frac{p}{\sqrt{\log n}}$. First, due to the properties of standard deviation, and the discretization of $\Psi_{\alpha}$ the standard deviation of $\overline{\Psi}_{\alpha}$ is $\alpha\cdot p$, thus $\text{Var}(\overline{\Psi}_{\alpha})=\alpha^2\cdot p^2$. Due to probability rules and the explanation provided when discussing additive sum distribution, the variance of the additive sum distribution $\overline{\Psi}^{\star k}_\alpha$ is $\text{Var}(\overline{\Psi}^{\star k}_\alpha)=k\cdot\alpha^2\cdot p^2$, which means that the standard deviation of it is $\sqrt{k}\cdot p\cdot\alpha$. The following holds:$$\begin{array}{c}m=1.1\cdot n\log p<1.1\cdot n\log (2n^2)=\\=2.2\cdot n\cdot(\log 2 + \log n)\underset{n>2}{<}4.4n\cdot\log n\end{array}$$ We can therefore say that $m=o(n\log(n))$, therefore we get:$$\sqrt{k}\cdot\alpha\cdot p<\sqrt{m}\cdot\alpha\cdot p=o(\sqrt{n\log n})\cdot o\left(\frac{1}{\sqrt{n}\log(n)}\right)\cdot p =o\left(\frac{1}{\sqrt{\log n}}\right)\cdot p$$ For simplicity we will assume: $\sqrt{k}\cdot\alpha\cdot p = \frac{p}{\sqrt{\log n}}$ Therefore we can say that the standard deviation of $e\sim\overline{\Psi}^{\star k}_{\alpha}$ is less than $\frac{p}{\sqrt{\log n}}$

Negligibility - We know that $\frac{\left\lfloor\frac{p}{2}\right\rfloor}{2}<\frac{p}{4}$ and specifically the difference is less than 1 at most. We also know that - in normal distributions. $$\Pr\left[X<x\right] =\Phi(z), z=\frac{x-\mu}{\sigma}$$ Where $\sigma$ is the standard deviation. For our distribution we know that $\mu=0$ and that $\sigma<\frac{p}{\sqrt{\log{n}}}$ which means that $z=\frac{x}{\sigma}>\frac{x}{\frac{p}{\sqrt{\log{n}}}}$. We define $x=\frac{p}{4}$ which is sufficient in our purposes (as $e$ is taken from $\mathbb{Z}_{p}$ which will only hold whole values, therefore taking $\frac{p}{4}$ gives us a slightly better assurance). We therefore get:$$\Pr_{e\sim\overline{\Psi}^{\star k}_\alpha}\left[|e|<\frac{p}{4}\right]=\Phi\left(\frac{\frac{p}{4}}{\sigma}\right)>\Phi\left(\frac{\frac{p}{4}}{\frac{p}{\sqrt{\log{n}}}}\right)=\Phi\left(\frac{\sqrt{\log{n}}}{4}\right)$$

We also know that $\Phi(z)=1-(1-\Phi(z))$, we will now prove that when $z=\frac{\sqrt{\log{n}}}{4}$, the function $1-\Phi(z)$ is negligible in $n$.

We know from probability theory that $$\begin{array}{c}1-\Phi(z)=1-\Phi\left(\frac{\sqrt{\log{n}}}{4}\right)=1-\frac{1}{\sqrt{2\pi}}\int_{-\infty}^{\frac{\sqrt{\log{n}}}{4}}e^{-t^2/2}\text{dt}\approx\\\\\approx\frac{1}{\sqrt{2\pi}}\cdot \frac{e^{-\frac{\left(\frac{\sqrt{\log{n}}}{4}\right)^2}{2}}}{\frac{\sqrt{\log{n}}}{4}}=\frac{4}{\sqrt{2\pi\log{n}}}\cdot e^{-\frac{\log{n}}{32}}\end{array}$$ We used the approximation that $1-\Phi(z)\approx\frac{1}{\sqrt{2\pi}\cdot z}e^{-z^2/2}$.

To prove that this is negligilble with regards to $n$, we will show that the following holds $\lim_{n\rightarrow\infty}{(1-\Phi(z))\cdot n^c}=0,\ \ \forall c>0$, as follows: $$\begin{array}{c} \lim_{n\rightarrow\infty}{(1-\Phi(z))\cdot n^c}=\lim_{n\rightarrow\infty}{\frac{4}{\sqrt{2\pi\log{n}}}\cdot e^{-\frac{\log{n}}{32}}\cdot n^c}\underset{n^c=e^{c\log n}}{=}\\ =\lim_{n\rightarrow\infty}{\frac{4}{\sqrt{2\pi\log{n}}}\cdot e^{-\frac{\log{n}}{32}+c\log{n}}}=\lim_{n\rightarrow\infty}{\frac{4}{\sqrt{2\pi\log{n}}\cdot{e^{\frac{\log{n}}{32}-c\log{n}}}}}=0 \end{array}$$ As a result, we found that $1-\Phi\left(\frac{\sqrt{\log{n}}}{4}\right)$ is a negligible function.

Therefore we have shown that - given our selection of parameters: $$\Pr_{e\sim\overline{\Psi}^{\star k}_\alpha}\left[|e|<\frac{p}{4}\right]>\Phi\left(\frac{\sqrt{\log{n}}}{4}\right)=1-\left(1-\Phi\left(\frac{\sqrt{\log{n}}}{4}\right)\right)=1-\delta(n)$$ Where $\delta(n)=1-\Phi\left(\frac{\sqrt{\log{n}}}{4}\right)$ is a negligible function.

$\endgroup$
1
  • $\begingroup$ While I didn't check each exact implication in your answer, the overall argument is one that works, though explicitly fiddling around with $\Phi$ is typically not useful in lattice-based cryptography. I'll post an answer that is more typical. $\endgroup$
    – Mark Schultz-Wu
    Commented Nov 21 at 20:36
0
$\begingroup$

I'll assume that we have a sample

$$e = \sum_{i = 1}^k\lfloor px_i\rceil\bmod p,$$

where $x_i\sim \mathcal{D}$ are i.i.d. from some distribution $\mathcal{D}$. There are several parts of this that are atypically presented compared to "modern" lattice cryptography. I'll mention them quickly.

  1. $\mathcal{D}$ is distributed on $\mathbb{T} := \mathbb{R}/\mathbb{Z}$, e.g. on the interval $[-1/2,1/2)$ equipped with $\bmod 1$ addition and multiplication. Note that for such $x_i$, $px_i$ is distributed on $[-p/2, p/2)\cong \mathbb{R}/p\mathbb{Z}$, and then $\lfloor px_i\rceil$ is distributed on $[-p/2, p/2)\cap \mathbb{Z}\cong \mathbb{Z}/p\mathbb{Z}$. Modern authors generally ignore these several translation steps, and instead define some distribution $\mathcal{D}_{\mathbb{Z}/p\mathbb{Z}}$ directly on $\mathbb{Z}/p\mathbb{Z}$

  2. It is not clearly useful to analyze $|e\bmod p|$. Implicitly, the main thing one hopes to do is to write $|e\bmod p| \stackrel{\ast}{\leq} |e|$, and then analyze $\Pr[|e| \leq p/4]$ over $\mathbb{Z}$. It is not really clear how one could get tighter bounds without applying inequality $\ast$. As a basic example of this, $|e\bmod p|$ doesn't even formally mean anything until you fix an embedding $\phi:\mathbb{Z}/p\mathbb{Z}\mapsto \mathbb{Z}$. So, it can help clean things up to instead define $\mathcal{D}_{\mathbb{Z}}$ directly over $\mathbb{Z}$. I'll note that in principle one could still get tighter bounds by analyzing $|\phi(e\bmod p)|$ rather than $|e|$ (which is implicity $\sum_{i = 1}^k \phi(x_i)$ --- this can be larger than $p/2$, while $|e\bmod p| \leq p/2$). I just don't think anyone has a reasonable argument why such bounds should be tighter (it would only "really matter" in situations the noise is so high where you would decrypt incorrectly a non-negligible amount of time), or how to compute them.

So, the modern argument would instead let $\mathcal{D}$ be a distribution on $\mathbb{Z}$, and then ask one to analyze

$$ e = \sum_{i= 1}^kx_i, $$ and perhaps show that

$$ \Pr[|e| \leq p/4] \geq 1-\mathsf{negl}(n). $$

This is simple to do using the Chernoff-Cramer argument for a general class of $\mathcal{D}$. The high level idea is to note that, for any increasing function $f(x)$, Markov's inequality implies that

$$ \begin{align*} \Pr[e > p/4] &= \inf_{\lambda>0}\Pr[\lambda e > \lambda p/4]\ &= \inf_{\lambda>0} \Pr[f(\lambda e) > f(\lambda p/4)]\ &\inf_{\lambda>0}\leq \frac{\mathbb{E}[f(\lambda e)]}{f(\lambda p/4)}. \end{align*} So far, it is not clear that we gained anything. Choosing $f(x) := \exp(x)$, we can simplify the expectation

$$ \mathbb{E}[f(\lambda e)] = \mathbb{E}[\exp(\lambda\sum_{i=1}^k x_i)] \stackrel{1}{=} \prod_{i = 1}^k\mathbb{E}[\exp(\lambda x_i)] \stackrel{2}{=}\mathbb{E}[\exp(\lambda x_1)]^n, $$ where (1) uses independence of the $x_i$'s, and (2) uses that they are identically distributed. Then, provided $\mathcal{D}$ is such that one can get nice bounds on $\mathbb{E}[\exp(\lambda x_i)] \leq \exp(\sigma^2\lambda^2/2)$ (the typical term is "sub-Gaussian", and a typical reference is Section 2 of Vershynin), one gets that

$$ \Pr[|e| > p/4] \leq \inf_{\lambda>0} \exp(-\lambda p/4)\exp(n\lambda^2\sigma^2/2) = \exp(-\frac{\lambda p}{2} + n\lambda^2\sigma^2/2). $$

Minimizing the numerator $g(\lambda)$ of $\exp(g(\lambda))$ (set $\lambda$ to be such that $g'(\lambda) = 0$, or $\lambda = \frac{p}{4n\sigma^2}$) then yields that

$$ \Pr[e>p/4] \leq \exp(-\frac{p^2}{8\sigma^2n} +\frac{p^2}{32n\sigma^2}) = \exp(-\frac{3p^2}{32n\sigma^2}). $$

This has the benefit that it works for a wide variety of distributions $\mathcal{D}$, for example

  1. continuous Gaussians,
  2. discrete Gaussians,
  3. binomial random variables,
  4. bounded random variables.

All are sometimes used in lattice-based cryptography, generally because it is surprisingly difficult to accurately sample from discrete Gaussians in constant time.

$\endgroup$

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.