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)


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.