A Statistically-Hiding Integer Commitment Scheme Based on Groups with Hidden Order

We present a statistically-hiding commitment scheme allowing commitment to arbitrary size integers, based on any (Abelian) group with certain properties, most importantly, that it is hard for the committer to compute its order. We also give efficient zero-knowledge protocols for proving knowledge of the contents of commitments and for verifying multiplicative relations over the integers on committed values. The scheme can be seen as a generalization, with a slight modification, of the earlier scheme of Fujisaki and Okamoto [14]. The reasons we revisit the earlier scheme and give some modification to it are as follows: - The earlier scheme [14] has some gaps in the proof of soundness of the associated protocols, one of which presents a non-trivial problem which, to the best of our knowledge, has remained open until now. We fill all the gaps here using additional ideas including minor modification of the form of a commitment.- Although related works such as |8, 3, 10, 4| do not suffer from the main problem we solve here, the reason for this is that they use “commitments” with a single base (i.e., of form c = gs mod n). Such commitments, however, cannot satisfy the standard hiding property for commitments, and hence protocols using them cannot in general be (honest-verifier) zero-knowledge nor witness indistinguishable.- In a computationally convincing proof of knowledge where the prover produces the common input (which is the type of protocol we look at here), one cannot completely exclude the possibility that a prover manages to produce a common input on which he can cheat easily. This means that the standard definition of proofs of knowledge cannot be satisfied. Therefore we introduce a new definition for computationally convincing proofs of knowledge, designed to handle the case where the common input is chosen by the (possibly cheating) prover.- Our results apply to any group with suitable properties. In particular, they apply to a much larger class of RSA moduli than the safe prime products proposed in [14] - Potential examples include RSA moduli, class groups and, with a slight modification, even non-Abelian groups.Our scheme can replace the earlier one in various other constructions, such as the efficient interval proofs of Boudot [4] and the efficient proofs for the product of two safe primes proposed by Camenisch and Michels [9].