3
$\begingroup$

With reference to Jan Camenisch and Anna Lysyanskaya's paper A Signature Scheme with Efficient Protocols, in proceedings of SCN 2002, I need some help to understand How to verify that $C_x$ is a commitment to an integer of length $l_m$.

$$C_x = g^x * h^r$$, where $x$ is the secret and $r$ is the randomness; $g$ and $h$ are known parameters

$\endgroup$
1
  • 1
    $\begingroup$ This looks very much like a standard Pedersen commitment (assuming the operations are within a finite group where the discrete log is hard). $\endgroup$
    – SEJPM
    Oct 2, 2020 at 10:38

2 Answers 2

2
$\begingroup$

You want to prove knowledge of an opening $(x,r)$ to a Pedersen commitment, such that $x$ belongs to the range $[0,2^{l_m}]$. Such a proof is called a range proofs, and many methods exist, using bit-decomposition (commit to $x$ bit by bit, prove that the sum of the $x_i\cdot 2^i$ is indeed $x$, and prove that each committed value is a bit) or square decomposition techniques over hidden order groups. I discussed some of these methods in several answers, see here and here. The latest state-of-the-art method for range proofs is Bulletproof, which achieves relatively impressive efficiency guarantees, to the point that it's actually used in several real-world applications (e.g. the cryptocurrencies Monero and Mimblewimble, among others).

$\endgroup$
0
$\begingroup$

The only strategy I know is to use one commitment per bit. Then you can prove that all the commitments corresponding to the $i^{th}$ bit for $i> l_m$ contains zero.

$\endgroup$
1
  • $\begingroup$ I don't get if what you are proposing is making any use of the question's $C_x$. $\endgroup$
    – fgrieu
    Oct 2, 2020 at 12:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.