# Questions tagged [probability]

Questions about the branch of mathematics concerned with modeling and analyzing random phenomena.

30 questions
Filter by
Sorted by
Tagged with
27 views

### Can we determine a security parameter in the hybrid argument where the number of hybrids is polynomially bounded but not known?

Let $\lambda$ be a statistical security parameter. Consider a security proof that is based on hybrid argument, where there are polynomially many (say, $n = p(\lambda)$) hybrids, $H_1, ..., H_n$. Any ...
155 views

### Can you have perfect secrecy with countable message/key spaces by dropping countable additivity?

This classic paper by Chor and Kushilevitz shows that if the key space and the message space are both countably infinite, then it is impossible to have a perfectly secure private-key encryption scheme....
76 views

### On The Next Bit Test

I would like to know what $O(v(n))$ really means in detailed and simple words please. I found it everywhere in the literature I am reviewing but I cannot find what the intuition of it (especially if ...
64 views

### Explaining the reason of radically more accuracy while using different set of hash functions instead of same set of hash functions on some operations

So I am looking for an explanation of an experiment. In this experiment, I took a set of k hash functions. Say the total number of data points I am working on is d. Call an algorithm A which used that ...
75 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 ...
19 views

519 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 ...
93 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 ...
38 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 ...
41 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 ...
130 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 ...
71 views

66 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 <...
85 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 ...
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 ...
109 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 ...
990 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 ...
219 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 «...