# Tag Info

## 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