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.

  • 1
    $\begingroup$ 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$ $\endgroup$
    – 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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.