**An Efficient Range-Bounded Commitment Scheme**

*Zhengjun Cao*

**Abstract: ** Checking whether a committed integer lies in a specific interval has many cryptographic applications. In Eurocrypt'98, Chan et al. proposed an instantiation (CFT for short). Based on CFT, Boudot presented an efficient range-bounded commitment scheme in Eurocrypt'2000. Both CFT proof and Boudot proof are based on the
encryption $E(x, r)=g^xh^r\ \mbox{mod}\ n$, where $n$ is an RSA
modulus whose factorization is \textit{unknown} by the prover. They
did not use a single base as usual. Thus an increase in cost occurs.
In this paper we show that it suffices to adopt a single base. The
cost of the improved Boudot proof is about half of that of the
original scheme. Moreover, the key restriction in the original
scheme, i.e., both the discrete logarithm of $g$ in base $h$ and
the discrete logarithm of $h$ in base $g$ are unknown by the prover,
which is a potential menace to the Boudot proof, is definitely
removed.

**Category / Keywords: **cryptographic protocols / range-bounded commitment, knowledge of a discrete logarithm, zero-knowledge proof

**Date: **received 20 Sep 2007

**Contact author: **caozhj at shu edu cn

**Available format(s): **PDF | BibTeX Citation

**Version: **20070921:073340 (All versions of this report)

**Short URL: **ia.cr/2007/376

[ Cryptology ePrint archive ]