Cryptography
rsa commitments
Updated Wed, 25 May 2022 11:34:10 GMT

Commitment schemes for arbitrarily large integers


My question is about commitment schemes for arbitrarily large integers. One scheme I know uses groups of unknown order (RSA or class group) and depends on the strong-RSA assumption.

You chose a random element $g$ in a group $\mathbb{G}$ of unknown order and define the commitment $Com(n):= g^n$ for any integer $n$. You can turn this into a hiding commitment by choosing an element $h\in \mathbb{G}$ such that the discrete log between $g$, $h$ is unknown and defining the Pedersen commitment $PedCom(n,r):= g^nh^r$ for a randomly chosen secret integer $r$.

Are there other commitment schemes for arbitrarily large integers?

One could decompose the integer and use a polynomial commitment of some sort that does not need hidden order groups, but I suspect such a scheme would not allow for efficient protocols to prove relations between the committed integers.




Solution

A small comments: the Damgard-Fujisaki commitment scheme, which you are referring to, does not depend on the strong RSA assumption. If you instantiate it (for example) over RSA group, it is perfectly hiding, and binding under the factorization assumption. However, the soundness of the zero-knowledge protocol for proving relations between integers committed with DJ relies on the strong RSA assumption.

That being said:

  • In this work, we reduced the assumption for the proofs of relation between DJ-committed integers to RSA instead of strong RSA.
  • In an upcoming Eurocrypt paper (not yet online, but hopefully very soon), we build a new integer commitment scheme over class groups. The main difference with DJ is that DJ requires a class group with a hard-to-factor discriminant, meaning that you need a trusted setup to generate the parameters. In contrast, we only need class groups with a prime discriminant, which can be publicly generated from a shared random string.
  • In the same paper, we also build a bounded integer commitment scheme. Unlike the previous ones, the size of the group grows with a bound on the maximum size of the supported integers. However, the scheme still comes with efficient ZK proof systems for proving relations between the committed integers. Furthermore, the commitment and the proofs are secure under the discrete logarithm assumption.
  • There is always the option of using bit-decomposition of the integer, and committing to the bits, e.g. with a generalized Pedersen commitment (so that the commitment remains compact for arbitrary integers). While this does not directly come with efficient proofs over the integers, for many statements of interest, one can reduce these proofs to statements involving inner products between the committed bits. This was done e.g. in Bulletproof to construct what was (until our upcoming Eurocrypt paper) and still is for some parameters (very large intervals) the most compact range proofs.

As far as I am aware, there does not currently exist any other candidates.