Questions tagged [probability]
The probability tag has no usage guidance.
26
questions
3
votes
1answer
54 views
Laplace Inequality
I am trying to prove that if $r_i \sim Lap(0,1/\varepsilon)$ where $\varepsilon >0$ then:
$$Pr[r_i \geq 1+r^*] \geq e^{-\varepsilon}Pr[r_i \geq r^{*}]$$.
I know that for $r*>0$ it satisfies ...
2
votes
0answers
19 views
Probability that length of shortest nonzero vector is less than a number
Let $\Lambda\subset \mathbb{Z}^n$ be an $n-$ dimensional lattice with determinant $d$. We know that the probability that a uniformly random integer vector $x$ is a point in $\Lambda$ is given by $\...
3
votes
1answer
142 views
Likelihood of signature collision with EdDSA
Taking EdDSA as an example, given the length of a signature is 512-bits for a given data payload,
what is the probability of a collision where there is another 512-bit value that is also a valid ...
1
vote
1answer
67 views
Probability that rank of a square matrix, whose each element is uniformly random from a ring of integers modulo prime p, is not full
I am currently reading a paper from CRYPTO, which is a top conference in cryptology. In the paper, the authors use a thereom like the one given below without a rigorous proof:
the probability that $...
5
votes
1answer
513 views
Is it possible to construct a PRNG where the output numbers have a certain distribution of hamming weights?
I am in need of a non-uniform random number generator where each n-bit output has a hamming weight with a certain binomial distribution.
For example, I would like a non-uniform PRNG which generates ...
0
votes
2answers
84 views
Random Oracle to prove an Authenticated DH protocol
I am trying to understand how they use the random oracle to solve the CDH. For example, in the security proof on page 7 of the following paper; A Lightweight Message Authentication Scheme for Smart ...
0
votes
1answer
34 views
How to have a bound (upper or lower) of Gaussion distribution over lattice based crypto>
In lattice-based crypto, we always need to sample 'noise' from Gaussian distribution, but how to measure the bound the noise? For example, if the Gaussian distribution is D_{u,\sigma}, where u is the ...
1
vote
0answers
39 views
Primal and dual attack against NTRU
I am looking at the primal attack against schemes in the second round of the NIST Post-Quantum Standardization Project. The cost of primal attack usually comes from an estimate described in NewHope ...
2
votes
1answer
91 views
Statistical distance in distributions
I have two questions regarding to statistical distance in distributions.
1: If $Z$ is uniform random variable over $N$ consecutive integers and
$m < N$ then $Z$ mod $m$ has statistical distance ...
1
vote
1answer
55 views
Compute statistical distance between two distributions over tuples
Let $X$ denote one distribution. Let $f,g, \text{ and } h$ denote three functions. If we have the results: $g(X)$ is within a negligible statistical distance of $h(X)$. Is it possible to prove
$$(f(...
1
vote
0answers
61 views
How do I calculate the conditional probability of a Caesar cipher?
I have a frequency distribution of letters for the plaintext and the ciphertext.
I'm trying to determine the conditional probabilities to identify the plaintext/ciphertext pairings.
If I encrypt ...
0
votes
1answer
73 views
$X_ {i_1}, . . . , X_{ i_ k} $ are IID random variables or not?
In this paper
secret
sharing is to distribute information (the secret) over
a set of participants such that the secret can only be reconstructed if certain authorized combinations of participants join ...
0
votes
1answer
63 views
Can anybody please explain why is the probabilty of finding a desired message for random chaining values equal $2^{-224}$?
Can someone explain why does probability is equal $2^{-224}$ in the following piece of paper?
The length of messages blocks in Hamsi is equal 32 and the length of chaining values is equal 256.
2
votes
0answers
36 views
decrypting a one-time-pad that outputs 0,1 in preknown probabilities
assuming a two users want to use a one time pad ciphersystem, and they are using a program that was developed by a third party that was supposed to create random undependable bits, but for some reason ...
0
votes
3answers
197 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 ...
1
vote
0answers
30 views
Again on discrete gaussians over lattices [duplicate]
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
87 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
524 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) ...
1
vote
1answer
54 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
83 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 ...
4
votes
0answers
104 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 ...
2
votes
2answers
922 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
206 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 Ā«...
6
votes
2answers
4k 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
86 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% ...
