Compact Witness Extractable Commitments
A witness extractable commitment for a language with corresponding relation is a two round commitment protocol. The receiver's message is generated using a witness , and the sender's commitment to a bit is generated using a statement . Informally speaking, the bit can be efficiently extracted when , however, when , is statistically hidden.
Witness extractable commitments that are compact means that the size of a commitment second message does not depend on the size of the verifier circuit (except for maybe its depth).
1Definition
Fix a language . By and denote the relation and the verification circuit corresponding to respectively. Also, let be the depth of .
A witness extractable commitment scheme for , is a tuple of algorithms having the following interfaces:
, given a security parameter , circuit depth upper bound , and a witness , outputs the commitment first message and a string st representing the internal state. , given a commitment first message , a statement , a bit to commit, and randomness , outputs a commitment . , given a commitment transcript , , a statement , a bit , and random coins , it either accepts or rejects. Extract , given a commitment and internal state , outputs a bit .
We consider the following properties:
Completeness: for every , bit , every statement , every witness , every ,
where, , and .
Statistical hiding: if , then, for any , any , and any sequence of strings
Pseudorandomness of first message: for any and any ,
Extractability: if , then, for any bit , any , any , in the support of , any randomness , and any such that accepts,
Compactness: the parameters and are upper-bounded by some language-independent fixed polynomials in and . In particular, they are independent of the size of the verifier circuit and the size of the statement .
2Construction
maliciously circuit private FHE scheme of [OPP14]
R. Ostrovsky, A. Paskin-Cherniavsky, and B. Paskin-Cherniavsky. Maliciously circuit-private FHE. In CRYPTO, pages 536–553. 2014.
run Output . Keep as internal state. on input first message and bit , output
where, is the circuit defined below and represents the random coins used in the FHE evaluation algorithm.
:
if C(x,w)=1 then
return b
else
return 0
output . : accept iff is equal to .
3Security
Extractability and completeness follow immediately from completeness of FHE.
Compactness also follows from compactness of FHE. In fact, using the FHE in [OPP14], both and only depend on .
Pseudorandomness of FHE ciphertext and public keys imply pseudorandomness of the first message.
If FHE is maliciously circuit private, then, the commitment scheme is statistically hiding.