# Tag Info

Accepted

### How to check whether the permutation is random or not

There are at most $n \cdot (n - 1)$ permutations of $\mathbb Z/n\mathbb Z$ of the form $x \mapsto ax + b$: if $n$ is prime, there are $n - 1$ choices for $a$ and $n$ choices for $b$ under which this ...
• 48.8k
Accepted

• 143k

### Pseudo-random permutation of a range

The problem is small enough that the desired PRP can be implemented as a small array of 16 values initialized using the Fisher-Yates shuffle, with a pseudo-random generator deciding the indexes of the ...
• 143k
Accepted

### Is 3 rounds of Feistel enough for making a PRP?

Wel'll consider a symmetric Feistel cipher with $n$-bit block using ideal independent random functions at each round. Making it computationally indistinguishable from a random permutation requires ...
Accepted

### Permutation for which an inverse is a hard problem

It is obviously possible; one simple example is the function $f(x) = g^x - 1 \bmod p$, where $p$ is a large prime, and $g$ generates the entire group $\mathbb{Z}_p^*$; this is permutation over the ...
• 149k
Accepted

### Can we use a PRF as a PRP?

If the output domain is large enough so that the probability of getting a collision in the PRF is negligible, then the output of a PRP and PRF are indistinguishable. Thus, in principle, the answer is ...
Accepted

### PRP vs PRF for the F-function of a Feistel network

Does it impact Luby and Rackoff's observation regarding 3 and 4-round Feistel networks with ideal F-functions? No. What are the theoretical cryptographic implications of using a PRP instead of a ...
• 46.2k
Accepted

### Sponge with PRF instead of PRP

I sent a mail to the Keccak team asking about this, and I got a response from one of the authors (Joan Daemen to be specific). According to him, we actually can instantiate Sponge functions and ...
• 9,519

### Why are $\lceil 1/\operatorname{entropy-per-bit} \rceil$ number of bits not sufficient to generate an unbiased bit?

Entropy and bias are not the same. Yes, total entropy is additive so as you suggest 7 bits of badrand() produce a total of 1.064 bits of entropy. So? How would you ...
• 15.6k

### Why are $\lceil 1/\operatorname{entropy-per-bit} \rceil$ number of bits not sufficient to generate an unbiased bit?

The other answer actually says that you need 2527 bits of input for each 256 bits of hash output. That's 9.9 bits per bit, not much worse than 7. The same calculations gives 849 input bits per output ...
• 777
Accepted

### Why are $\lceil 1/\operatorname{entropy-per-bit} \rceil$ number of bits not sufficient to generate an unbiased bit?

I will take a slightly different approach, a side step to a simpler problem to gain intuition. Let's say we have a fair 6 sided die. And we wish to draw a number uniformly from 1 to 4. It can't be ...
• 11.9k
Accepted

### How are the keys used in cryptography generated?

Cryptographic keys should generally be generated secretly and uniformly at random in the cryptosystem's key domain; that is in the set of valid keys for the cryptosystem. What makes a key valid ...
• 143k