Questions tagged [statistical-distance]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
3 votes
2 answers
97 views

A Smudging Lemma in Lattice

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 ?
constantine's user avatar
1 vote
1 answer
61 views

Modulo bias: How to compute statistical distance?

Assume we have two uniform distributions $X=U(\mathbb{Z}_m)$ and $Y=U(\mathbb{Z}_n) \bmod m$, for $m,n \in \mathbb{N}$. The statistical distance is defined as: $$ \Delta(X, Y) = \frac{1}{2} \sum_{a \...
mti's user avatar
  • 655
0 votes
2 answers
57 views

Statistical distance for multiplicative blinding

A common way to mask an integer $x$ in a range is to add a uniformly random integer $r$ from a much larger range. More formally, if $x$ lies in $[0,...,2^k)$ and $r$ in $[0,...,2^{k + l})$, then $$\...
user34968's user avatar
1 vote
0 answers
56 views

What is a reasonable statistical distance bound in a SZK construction?

Many works, such as [YCX21] cite that $2^{-40}$ is a reasonable statistical distance for zero-knowledge proof based signatures, even when the security level is $\lambda = 128$.. I was wondering if ...
Lev's user avatar
  • 443
1 vote
0 answers
59 views

ddh and statistical distance

Let $\mathbb{G}$ be a cyclic group of prime order q and generated by g. Let $D$ be the uniform distribution over $\mathbb{G}^3$. Let $D_{dh}$ be the uniform distribution over the set of all DH-triples ...
Cristie's user avatar
  • 93
0 votes
0 answers
91 views

Can two ciphertexts that decrypt to the same plaintext be statistically "distant"?

It might be a little dumb: I think it should be possible, if I encrypt a plaintext using the same public key twice, it should be possible to end up with two ciphertexts that for whom the statistical ...
Aryan's user avatar
  • 1
2 votes
1 answer
115 views

Statistical Distance and Learning with Rounding

Given an integer $b$ modulo a prime $q$, one can define a `rounding’ function $\lfloor b\rceil_p$ for a prime $p$, $p<q$, as follows: $$\lfloor b\rceil_p = \lfloor \frac{p}{q}\cdot b\rceil\bmod p.$$...
a196884's user avatar
  • 381
1 vote
1 answer
122 views

How to complete this proof of statistically indistinguishable distributions?

Given that: $$ SD\bigg( (r, \langle r, s \rangle),(r, b) \bigg) < \mathrm{negl}(n)$$ where $SD$ stands for statistical distance, $r$ is random uniform in $\{0,1\}^n$, $s$ is random uniform in $S \...
Anon's user avatar
  • 403
2 votes
1 answer
475 views

About the definition of distinguishing advantage and computational indistinguishability

Given a polynomial-time adversary $A$ with binary output, the distinguishing advantage of $A$ with respect two games $G, H$ is defined as $$ \newcommand{\adv}{\mathbf{Adv}} \newcommand{\pr}{\mathbf{Pr}...
AYun's user avatar
  • 849