In the paper "Efficient Zero-Knowledge Proofs for Commitments from Learning with Errors over Rings", they gave a commitment from Ring-LWE: to commit to a polynomial $m$ in $Rq(Zq[x]/(x^n+1))$, choose vector $a$, $b$ in $Rq$ randomly, then the commitment is $c = am+br+e$ (where $r$ is random in $Rq$, $e$ is the error).

They gave the proof on the hiding the binding properties in Theorem 3.1 in the paper, but it seems that they only proved the binding property provided that the adversary choose m randomly. Why can we assume that? My understanding: we should prove that when the public parameters are fixed, then it's difficult to find such $m$ such that $am+br = f'^-1e'-f''^-1e''$ (Theorem 3.1 in the paper)

  • $\begingroup$ I think the hiding property comes from the fact that $c=am+br+e$ is pseudorandom. Note that RLWE samples and the uniform ones are indistinguishable based on the hardness of the decision RLWE. You see that $br+e$ is an RLWE sample, hence pseudorandom and adding it by $am$ would still yield a pseudorandom vector $c$. $\endgroup$ May 8 at 23:37
  • $\begingroup$ Then, what about the binding property? Hiding is just like what you say. $\endgroup$ May 10 at 2:09

Your Answer

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

Browse other questions tagged or ask your own question.