Is there any secure cryptographic commitment scheme, where the verification routine can be implemented in $NC^0$? If so, what is the minimum possible depth of the circuit for verification?

Applebaum et al prove the existence of a commitment scheme where commitment can be done in $NC^0$ and where verification can be done with a $NC^0$ circuit plus a single AND gate of unbounded fan-in. See

However, this does not show how to do the verification in $NC^0$, i.e., in constant depth. Is there a plausible construction to achieve that goal?

For a result of a similar flavor, see also

which gives a plausible construction of a commitment scheme with similar properties; but again their verification scheme involves a $NC^0$ circuit plus a single AND gate of unbounded fan-in.

Motivation. I came across this problem when thinking about how to obfuscate a particular function that uses the verification component of a commitment scheme, but I realized this might be of broader interest.

  • $\begingroup$ If this question can be improved, would anyone mind explaining what I could do to improve it? $\endgroup$
    – D.W.
    Jun 6 '14 at 23:42
  • $\begingroup$ It seems like a nice question to me. I have no idea why it is down-voted. $\endgroup$
    – Kaveh
    Jun 7 '14 at 0:02

No. $\;\;\;\;$ There is also no secure commitment scheme where the verification
routine can be done with bounded fan-in in depth $\:o(\hspace{.02 in}\log(\hspace{.02 in}\log(k)))\:$,
since such circuits have input locality $\:(\hspace{.02 in}\log(k))^{o(1)}$,$\:$ which means one can
efficiently brute-force the bits that might affect the verification circuit's output.

  • $\begingroup$ Does this take into account the randomized encodings / randomizing polynomials in Applebaum, Ishai, and Kushilevitz's Cryptography in NC0? I thought that was designed to deal with exactly this sort of problem. If randomized encodings were not allowed, then your answer would make sense to me (but then all of the paper Cryptography in NC0 would be disallowed as well). Their randomized encodings allow to encode a complex function that's not in NC0, with a function that is in NC0. Thus, it seems you need to show that verification cannot be done in SREN/PREN. Have I missed something? $\endgroup$
    – D.W.
    Jun 8 '14 at 21:23
  • $\begingroup$ My reasoning does not rule out the existence of a secure commitment scheme whose verification routing has a randomized encoding in NC0, even if one assumes that the encoding is by randomizing polynomials. $\:$ If you missed something, then that is the absence of any mention of randomized encodings in your OP. $\;\;\;\;$ $\endgroup$
    – user6973
    Jun 8 '14 at 23:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.