I'm wondering that is there any equivocal commitment scheme (i.e., trapdoor commitment) can be constructed from lattice-based assumptions? I know there are a lot of commitment schemes from lattices as described in More Efficient Commitments from Structured Lattice Assumptions (described in the introduction) but I do not identify any trapdoor commitment scheme from lattice-based assumptions. Thus I'm wondering is there any equivocal commitment scheme? Recall that Pedersen commitment is an equivocal commitment but is constructed from Discrete Log assumption.
$\begingroup$
$\endgroup$
1
-
1$\begingroup$ Minor correction: I believe that Pedersen commitments are constructed from the DLog assumption (because if the prover could generate a commitment he could open in two different ways, he could compute discrete logs) $\endgroup$– ponchoFeb 21 '19 at 3:38
Add a comment
|
$\begingroup$
$\endgroup$
2
If you have a (standard) commitment scheme $C$ and zero-knowledge proofs of knowledge (both exist from LWE -- in fact, both exist from one-way functions), then you necessarily have equivocal commitments. Here is a straightforward equivocal commitment $C_e$: committing with $C_e$ is just committing with $C$, and opening a commitment is done by revealing the committed value $m$, together with a proof of knowledge of an opening to $C$ such that the commitment opens to $m$. It is easy to see that the proof of knowledge property implies that $C_e$ is binding, and the zero-knowledge property implies the existence of a simulator which can fake proofs of opening to any $m$, hence the commitment is equivocal.
That being said, I'm pretty sure there are many direct and relatively efficient constructions of equivocal commitments. For example, the LWE-based fully homomorphic trapdoor functions from this paper are in particular equivocal commitments (see page 5 of the paper).
answered Feb 21 '19 at 12:12
-
$\begingroup$ Thanks for the reply. Do you know any paper describing zero-knowledge proofs of knowledge from LWE? $\endgroup$ Feb 24 '19 at 2:00
-
$\begingroup$ There are dozen papers on zero-knowledge from LWE, a random example of a quite efficient candidate from ring-LWE is given in this paper, but there are really many other examples. At a theoretical level, one-way functions already imply zero-knowledge for NP, hence LWE trivially implies the existence of zero-knowledge proofs for NP. $\endgroup$ Feb 26 '19 at 16:00