New answers tagged

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