New answers tagged

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 ...
user avatar
  • 31

Top 50 recent answers are included