# Commitment schemes with verification in NC0

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?

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.

• If this question can be improved, would anyone mind explaining what I could do to improve it? – D.W. Jun 6 '14 at 23:42
• It seems like a nice question to me. I have no idea why it is down-voted. – 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
• 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. $\;\;\;\;$ – user6973 Jun 8 '14 at 23:26