<p>Is there any secure cryptographic <a href="https://en.wikipedia.org/wiki/Cryptographic_commitment" rel="nofollow noreferrer">commitment scheme</a>, where the verification routine can be implemented in $NC^0$?  If so, what is the minimum possible depth of the circuit for verification?</p>

<p>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</p>

<ul>
<li><a href="http://www.cs.technion.ac.il/~yuvali/pubs/AIK04.ps" rel="nofollow noreferrer">Cryptography in NC0</a>.  Benny Applebaum, Yuval Ishai, Eyal Kushilevitz.  Section 7.</li>
</ul>

<p>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?</p>

<p>For a result of a similar flavor, see also</p>

<ul>
<li><a href="http://www.eng.tau.ac.il/%7Ebennyap/pubs/input-locality-full-revised-1.pdf" rel="nofollow noreferrer">Cryptography with Constant Input Locality</a>.   Benny Applebaum, Yuval Ishai and Eyal Kushilevitz.  Journal of Cryptology, 2009, 22:429-469.</li>
</ul>

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

<hr>

<p><strong>Motivation.</strong> I came across this problem when thinking about <a href="https://crypto.stackexchange.com/q/16602/351">how to obfuscate a particular function that uses the verification component of a commitment scheme</a>, but I realized this might be of broader interest.</p>

CC BY-SA 3.0
2014-06-06T23:42:01.433Z
If this question can be improved, would anyone mind explaining what I could do to improve it?
D.W.
CC BY-SA 3.0
2014-06-07T00:02:20.520Z
It seems like a nice question to me. I have no idea why it is down-voted.
Kaveh
<cc.complexity-theory><cr.crypto-security><circuit-complexity><bounded-depth>
Commitment schemes with verification in NC0
D.W.
# Commitment schemes with verification in NC0

(Asked by: username_0 on 2014-06-06)

Is there any secure cryptographic [commitment scheme](https://en.wikipedia.org/wiki/Cryptographic_commitment), 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](http://www.cs.technion.ac.il/~yuvali/pubs/AIK04.ps). 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](http://www.eng.tau.ac.il/%7Ebennyap/pubs/input-locality-full-revised-1.pdf). 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](https://crypto.stackexchange.com/q/16602/351), but I realized this might be of broader interest.

**Tags:** cc.complexity-theory, cr.crypto-security, circuit-complexity, bounded-depth
> **Comments:**
> **username_0**: If this question can be improved, would anyone mind explaining what I could do to improve it?  
> **username_1**: It seems like a nice question to me. I have no idea why it is down-voted.  

---

## 0 answers

