All Questions
Tagged with cryptography pr.probability
7 questions
8
votes
0
answers
1k
views
Question on randomness extractors
Person A has a source $W$ with min-entropy($W$) = $k$. He also has an extra piece of information about the random source, denoted with $y$, such that min-entropy($W|y$) = $k/3$.
The adversary doesn't ...
- 81
7
votes
3
answers
896
views
A balls and urns model for a hashing problem
Fix $N \in \mathbb{N}$. Suppose we throw $N$ numbered balls into $N$ numbered urns, so that for each $b \in \{1,\ldots,N\}$, ball $b$ lands in urn $j$ with equal probability $1/N$. Choose a number $c \...
- 11.2k
5
votes
2
answers
3k
views
Whitening a random bit sequence
Given an (infinite) stream of uncorrelated random bit with a known "reasonable" bias (say 15-85% 1's) I want to whiten it, e.i. produce a shorter stream of bits that has no bias. The restriction is ...
- 205
3
votes
2
answers
162
views
Breaking the rotate-then-substitute alphabetic cipher
My question is not typical for MathOverflow, and arises in my teaching rather than research, but I think there will be readers who can give interesting answers.
Identify $\{\mathrm{A}, \ldots, \...
- 11.2k
3
votes
1
answer
344
views
The best linear approximation of a random function
Let $\mathcal{F}_n$ be the set of all boolean functions of $n$ variables and let $\xi$ be a random variable with values in the set $\mathcal{F}_n$ with the uniform distribution. We define a new random ...
2
votes
0
answers
88
views
Example of action of an infinitely countable group that has important ergodic/statistical property?
I work in probability and I am looking for an important example of action of an amenable countable group in other areas of math for which the (pointwise) ergodic theorem is actually quite important. ...
- 21
0
votes
1
answer
643
views
A good approximation for collision probability between (two) sets of random variables
We face many places to find the collision probability of two sets (or more) in my case the cryptographic hash functions. We can formalize as;
Given two sets of random variables $\mathbf{A}$ and $\...
- 115