3
$\begingroup$

I saw a paper LLW21 in EUROCRYPT 2021 that used this lemma, but there was no proof or references.

How should this lemma be proved ? enter image description here

$\endgroup$

2 Answers 2

2
$\begingroup$

In general the total variation distance (what you call the statistical distance --- both names are used) between (even continuous!) Gaussians is hard to compute. See for example this. Instead, people often instead compute a different measure of distance between Gaussians, and then use this quantity to bound the total variation distance.

Specifically, in terms of the KL divergence, the bound

$$\Delta(P, Q) \leq \sqrt{\frac{1}{2}\mathsf{KL}(P||Q)}$$

is known as Pinsker's inequality, where $\Delta(P, Q) := \frac{1}{2}\lVert P-Q\rVert_1$ is the Total Variation distance.

Throughout, I will write $P$ for the distribution with pmf proportional to $\exp(-\pi \lVert\vec x\rVert_2^2/\sigma^2)$, and $Q$ for the distribution with pmf proportional to $\exp(-\pi \lVert \vec x-\vec c\rVert_2^2/\sigma^2)$. I'll write the proportionality constants as $C_P$ and $C_Q$.

Anyway, one can compute that

$$\mathsf{KL}(P||Q) = \sum_{\vec x}P(\vec x)\left(\frac{\pi \lVert \vec c\rVert_2^2}{\sigma^2}-2\langle\vec x,\vec c\rangle\right) + \ln(C_P/C_Q)$$

By considering pairs of points $\vec x, -\vec x$ (where $P(\vec x) = P(-\vec x)$), one can see that the $-2\langle\vec x,\vec c\rangle$ term will cancel (it doesn't for the total variation distance, and is the reason why bounding it directly is annoying). For the proportionality constants, it is known (Lemma 2.7) that $C_P \leq C_Q$, under your condition that $\sigma \geq \omega(\sqrt{\log n})$. Applying Pinsker's inequality, and we get

$$ \Delta(P, Q) \leq \sqrt{\frac{\pi}{2}}\frac{\lVert \vec c\rVert_2}{\sigma}. $$

Note that this constant may be an artifact of my normalization of Gaussians. If you use the alternative normalization $\exp(-\lVert \vec x\rVert_2^2/(2\sigma^2))$ that some authors prefer, you get the bound

$$\Delta(P, Q) \leq \frac{1}{2}\frac{\lVert \vec c\rVert_2}{\sigma}$$

I won't check which normalization your paper uses, as either way I imagine the above is good enough for you.

$\endgroup$
0
$\begingroup$

You probably should define $\mathsf{SD}$ and $\mathcal{D}$.

There is a much simpler 1-dimensional version that is proved, see Lemma 2.1 of Asharov-Jain-Wichs, 2011. The proof is one-line:

Smudging lemma for uniform distribution

In [LLW21], $\mathcal{D}$ denotes $n$-dimensional discrete Gaussian. I did not find a proof, but there is another similar lemma with proof (which I did not read): https://eprint.iacr.org/2022/055.pdf

$\endgroup$
1
  • 1
    $\begingroup$ The smudging lemma of 2022/055 is different. It is bounding the distance between a sub-set sum of Gaussians and that same distribution plus some independent gaussian noise. In particular, all gaussians are centered in it. $\endgroup$
    – Mark Schultz-Wu
    Commented Feb 8 at 0:57

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.