4 votes
Accepted

Is there a notion of indistinguishability obfuscation for almost equivalent circuits?

I think the notion you're looking for is differing-inputs indistinguishability obfuscation(diO), or originally called extractability iO: https://eprint.iacr.org/2013/650.pdf The definition of diO ...
  • 148
2 votes
Accepted

Graph associated to a mathematical statement (for the purpose of zero-knowledge proofs)

The $NP$-problem here is not the problem of finding y,z,n, but rather the following problem: "Given a mathematical statement $A$ that can be encoded in $n$ bits, does there exist a proof of $A$ ...
  • 5,190
1 vote

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 ...
  • 71

Only top scored, non community-wiki answers of a minimum length are eligible