# What is the concrete communication complexity of Commitment schemes?

Say you want to commit an $n$-bit plaintext, $x \leftarrow ^ r \{0,1\}^n$.

What is the concrete communication cost, in terms of $n$, of the following:

• Data sent by verifier to initialize (applies in Pedersen, may not apply in other schemes).
• The commitment
• The decommitment

I read this description of the Pedersen scheme. Since the scheme only allows you to commit to values in $Z_q$, I assume that, in order to avoid dealing with enormous primes, in practice you would break up your input into $b$-bit blocks such that $q > 2^b$. It seems reasonable to me to pick $b=128$, $q$ a 129-bit prime chosen such that $p=2q+1$, making $p$ a 130-bit prime. I assume $p$, $q$ and $g$ (the generator) are publicly known and calculated before hand. In this case, the cost of sending 128 bits would be:

• Data sent by verifier: $h =g^a\mod p$, a 130-bit number
• The commitment: $c = g^m h^r \mod p$, another 130-bit number.
• The decommitment: $m, r \in Z_q$, two 129-bit numbers.

So the total communication cost would be $\frac{518 n}{128}$ bits.

Is this right?

If there are other commitment schemes that are better, feel free to give concrete numbers for those instead. However, I would like to commitment scheme to be self contained, so this paper, while it provides very clear explanations of its concrete security, doesn't fit the requirements I need because it requires a common reference string.

• Pedersen with a 130 bit modulus would be completely breakable; the committer can make any commitment decommit to anything he likes, by computing the discrete log of $h$ – poncho May 24 '18 at 15:38

The simplest commitment scheme is a hash based commitment; to commit to a value $M$, the committer selects a fixed length value $R$ and publishes $\operatorname{Hash}(R \mathbin\Vert M)$; to decommit, he publishes the values $R$ and $M$.

If the Hash function is collision resistant, then the committer cannot commit to two different messages; if $R$ is long enough, then it is infeasible to recover $M$ from the commitment.

With this in mind, and assuming we're using a 256 bit hash (such as SHA256) as our hash function, and a 128 bit $R$:

• Data sent by verifier: none

• The commitment: 256 bits

• The decommitment: 128+n bits

This is a total of 384+n bits.

I believe that it can be shown that you cannot do better without reducing the practical security of the system below the "128 bit" level