2
$\begingroup$

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.

Improve this question
$\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$
    – poncho
    Feb 21 '19 at 3:38
3
$\begingroup$

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

Improve this answer
$\endgroup$
2
  • $\begingroup$ Thanks for the reply. Do you know any paper describing zero-knowledge proofs of knowledge from LWE? $\endgroup$
    – CryptoLover
    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$
    – Geoffroy Couteau
    Feb 26 '19 at 16:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.