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.