New answers tagged pseudorandomness
0
votes
Can polynomial sized DNF be used to construct weak PRF
I believe the answer is no, due to "algebraic attacks". That is, take the lowest width (say at most d) term T from the DNF which we denote C.
then T(1+C) = 0, where T has low degree < w
...
Top 50 recent answers are included
Related Tags
pseudorandomness × 55pseudorandom-generators × 18
cc.complexity-theory × 14
randomness × 11
cr.crypto-security × 9
reference-request × 8
randomized-algorithms × 7
co.combinatorics × 6
derandomization × 6
circuit-complexity × 5
boolean-functions × 5
extractors × 4
expanders × 3
graph-theory × 2
lower-bounds × 2
polynomial-time × 2
hash-function × 2
fourier-analysis × 2
upper-bounds × 2
sample-complexity × 2
natural-proofs × 2
ds.algorithms × 1
graph-algorithms × 1
complexity-classes × 1
automata-theory × 1