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


Cryptography in NC0.  Benny Applebaum, Yuval Ishai, Eyal Kushilevitz.  Section 7.


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


Cryptography with Constant Input Locality.   Benny Applebaum, Yuval Ishai and Eyal Kushilevitz.  Journal of Cryptology, 2009, 22:429-469.


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