Questions tagged [probability]
The probability tag has no usage guidance.
13
questions
0
votes
3answers
87 views
Derivation of birthday paradox probability
I am trying to come up with an explanation of the probability of birthday collision.
$P$(no collision among t people) = $(1− \frac{1}{365}) · (1-\frac{2}{365}) ··· (1-\frac{t-1}{365})$
For one ...
0
votes
0answers
18 views
Difference between P[C=c|M=m] and P[M=m|C=c] in a uniform key space and a non-uniform message space [on hold]
Consider the following shift cipher scheme
M = {'hi','no','in'}.
$Pr[C = xy | M = hi ] = 1/26$
Given that m = hi, there is just one ...
0
votes
0answers
20 views
Again on discrete gaussians over lattices
Define
$$\rho_{s,c}(x) = exp(-\pi \cdot \frac{\|x - c\|^2}{s^2})$$
and
$$\rho_{s,c}(L) = \sum_{x \in L} \rho_{s,c}(x)$$
Then Discrete Gaussian over $L$ with center $c$ and standard deviation $s$ is ...
1
vote
2answers
60 views
Is there only one formula for the statistical difference between a pair of distribution ensembles?
Statistical closeness implies computational indistinguishability was recently posed. It revolves around a numeric value $\Delta(n)$ of the statistical difference between a pair of distribution ...
6
votes
2answers
366 views
Statistical closeness implies computational indistinguishability
This is so trivial that authors usually don't bother to give an explicit proof. But for me there is some vagueness.
We say that two ensembles $X_n$ and $Y_n$ are statistically close, if
$$ \Delta(n) ...
0
votes
1answer
40 views
What is / How would I calculate the number of bits(?) I need to make the probability of a collision very small?
If I wanted to create a TOTP-esque algorithm that generated a string n characters long, with each character being a base64 character, generated from a user secret <...
3
votes
2answers
52 views
What's the meaning of probabilities in differential privacy formula?
I don't understand what does it mean by "The probability is taken is over the coin tosses of K."
Does it mean, the probability distribution is generated based on exactly same data but only the ...
0
votes
1answer
29 views
Can randomness protect a list of signatures against forgery attacks?
Suppose we have a list of signatures $S = [s_1, .., s_n]$ for a list of messages $M = [m_1, .., m_n]$, and we want to verify that $S$ is a valid signature of $M$, so each $s_i$ should be valid for ...
3
votes
0answers
68 views
What is the probability equation of rotational cryptanalysis on modulo multiplication?
The answer in this question defined how to calculate the probability of rotational cryptanalysis on modulo multiplication $\odot$. This paper defined an algebraic equation of how to calculate the ...
1
vote
2answers
357 views
Why the definition in $\epsilon$-differential privacy is multiplicative rather than additive？
According to its mathematical definition, a random algorithm $M: D\rightarrow R$ satisfies $\epsilon$-differential privacy if the adjacent datasets $x, y \in D$ where $D$ is a whole dataset and ...
0
votes
2answers
150 views
Meet-in-the-middle probability of success
In page 358 of Bruce Schneier's Apllied Crypto, when explaining the meet-in-the-middle attack, he states that the success probability is «1 in $2^{2m - 2n}$» with two plaintext/ciphertext pairs, and «...
7
votes
2answers
2k views
Using a hash function as a random number generator
Using MD5 or SHA1 for instance, and applying integers (as seed so to speak) to the hash function, in sequence, and only keeping, say, the first 64 bits of the resulting hash, do we always have a ...
2
votes
1answer
76 views
Is there a rule of thumb for ZK protocols?
There's always a small chance for many zero knowledge protocols that the prover had a lot of luck to prove something to the verifier.
Take the Ali Baba cave as an example:
The prover has a 50% ...
