Skip to main content
OverflowAI is here! AI power for your Stack Overflow for Teams knowledge community. Learn more
4 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 ...
orlp's user avatar
  • 885
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 ...
Biu's user avatar
  • 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$ ...
Or Meir's user avatar
  • 5,615
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 ...
AnonTCS's user avatar
  • 71

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