# How to show that Cx is a commitment to a integer of length lm

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

• This looks very much like a standard Pedersen commitment (assuming the operations are within a finite group where the discrete log is hard).
– SEJPM
Oct 2 '20 at 10:38

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).
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.
• I don't get if what you are proposing is making any use of the question's $C_x$.