New answers tagged pseudo-random-function
3
Yes, NIST recommends $\epsilon \le 2^{-64}$. They consider such a sequence to have "full entropy". It's in the definitions (page 4) of SP800-90C.
Converting that to a probability bias, $P(x_i = 0, x_i = 1) \approx 0.5 \pm 2^{-66}$.
The interesting thing is that if the Leftover Hash Lemma is used, $\epsilon$ can be set by the designer. ID ...
1
You could leverage hash functions which are built off of the sponge construction, to serve as both a randomness extractor & entropy pool, simultaneously. The sha3-512 standardized hash function would be suitable, as it offers various strengths, including always producing bits that appear random & statistically-independent of the input data's bit ...
1
This is pretty common and easy to fix. Although that's a really poor RNG :-)
In the case of very small computational capabilities (e.g. Arduino Uno), we'd extract via the von Neumann technique as per the other answer [see note though]. For larger devices (e.g. ARM, Snapdragon and bigger) we leverage the Leftover Hash Lemma (LHL). That allows extraction in $...
2
If the outputs of badrand are independent and identically distributed you can use a randomness extractor function with $m=1$ and $k=-n\lg 0.9$.
If you're prepared to have a non-deterministic waiting time for an output, the von Neumann extractor is good way to get probability exactly 0.5 out of i.i.d. bit outputs. Sample pairs of bits until you get a pair ...
2
is $\Pi$ chosen plain-text secure (CPA)?
Not necessarily; you could easily design a collision resistant hash function for which this construction is not CPA secure.
For a trivial example, let $H'$ be an arbitrary collision resistant hash function as set $H(x)= 0 | H'(x)$; $H$ is obviously just as collision resistant as $H'$, but in this construction there ...
2
I hope that I am misunderstanding your question otherwise it looks horribly unsafe and deterministic. See, Play a CPA game.
Round 1:
choose two messages $m_0$ and $m_1$ and send it to oracle, and you get either $H(k)⨁ m_1$ or $H(k)⨁ m_2$. You now have two candidates for $H(k)$.
Round 2 repeat the same with different messages and you know $H(k)$,
A hash ...
3
It depends what you mean by collision resistance.
If by collision resistance you mean that the output of $H(.)$ cannot be distinguished from a stream with full collision entropy (i.e. a $H_2=\ell$) then by Jensen's inequality we cannot distinguish from a stream with Shannon entropy at least this large and so the conditions for a one-time pad are met.
If by ...
0
A lot of answers here for part (a) about how to use distinguisher for F' into distinguisher for F. A hint for part b). Suppose we have some $x' \in \{0,1\}^{n-2}$, what do you expect to get for $F'_k(x'||1)$ and $F'_k(0||x')$.
0
A hint for part (a): If $R(x)$ is a truly random function, then so is $R'(x) = R(0|x) | R(1|x)$
Now to prove [$F$ pseudorandom $\implies F'$ pseudorandom],
we will prove the contrapositive [$F'$ not pseudorandom $\implies F$ not pseudorandom].
Suppose $F'$ is not pseudorandom. That means there is a distinguisher $D'$ which can guess with a probability higher ...
3
I would like to improve upon @fkraiem answer (i.e. give a simpler construction):
you must exhibit a pseudorandom generator G such that L is not a pseudorandom generator.
Take any pseudorandom number generator $PRG : \{0,1\}^{n-1} \rightarrow \{0,1\}^{l(n)}$.
Now define $G : \{0,1\}^n \rightarrow \{0,1\}^{l(n)}$ to be $G(x_1 | x_2 ... | x_n) = PRG(x_1 | x_2 ....
Top 50 recent answers are included
