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
3
votes
Does there exist constant overhead reduction between common cryptographic primitives?
I'm not sure if it would qualify as a reduction in your terms per se, but there is certainly a connection between universal hashing and error-correcting codes. Universal hashes are often used in ...
- 720
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,350
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