Questions tagged [statistical-distance]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
0 votes
0 answers
41 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 ...
  • 1
2 votes
1 answer
86 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.$$...
  • 381
1 vote
1 answer
49 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 \...
  • 311
2 votes
1 answer
93 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}...
  • 791