3

Is it possible to use a public key scheme such as DSA as a commitment scheme? Are there any problems with doing this?

  • I'm not particularly knowledgeable about commitment schemes, but is there a reason you wouldn't use a standard block cipher for this? Encrypt the data, distribute the ciphertext, then release the key later. – Polynomial Nov 28 '12 at 10:03
  • I am new to this as well. I'd like to know if there are any security characteristics specific to commitment schemes which are not available through block ciphers / public key schemes? – DaTaBomB Nov 28 '12 at 10:18
  • I'll poke Thomas Pornin (our resident cryptographer) about this when I see him. – Polynomial Nov 28 '12 at 10:24
9

The answer can be yes or no depending on what you mean by commitment.

In a commitment scheme, you have a piece of data (d) from which you compute a value c which you publish; at a later date, you publish d. This is a commitment if the following is true:

  • From c, one cannot recompute d.
  • Everybody knowing c and d must be able to ascertain that they match.
  • It must not be possible, even for you, to find a d' distinct from d but which still matches c.

On the surface, this looks a lot like a cryptographic hash function, with some subtle details. If you compute c as h(d) for a hash function h (say SHA-256), then you fulfill the commitment properties, except that the commitment is vulnerable to exhaustive search on the data d. One could try potential data elements d, and hash them all, to see if one matches c. That's a problem also encountered with storing password hashes. The solution is randomization: you compute c as h(r||d) where r is some random padding (say 16 random bytes). When you open the commitment, you publish both r and d. The randomness of r protects against exhaustive search.

What would a signature scheme like DSA do in that picture? Not much, really. Instead of hashing, you could sign, but since everybody can verify the signature, you still would have the exhaustive search issue (DSA includes some random data, but not in the "right place" for a commitment scheme). Indeed, DSA begins by hashing the data, so you are really using a hash function, and the DSA around it is a needless complication.

Some commitment schemes provide more than just the ability to commit to an arbitrary value; they also allow to prove without opening the commitment that the committed-to value fulfills some algebraic properties. This is used, for instance, in some electronic voting protocols (the vote is encrypted, but the voter can show that the vote is either a 0 or a 1, not another integer). This kind of commitment requires mathematics besides just a hash: it may reuse some elements which are also used in some asymmetric encryption and signature algorithms (like operations modulo a big prime), but not just the asymmetric encryption or signature algorithms alone.

0

You can obtain a commitment from a public-key encryption scheme by having Alice obtain $(PK,SK) = Gen(1^n,r_g)$ (where $r_g$ is the random coins for the $Gen$ algorithm). To commit to the message $m$ she sends $PK$ and $c=E_{PK}(m;r_e)$ to Bob, where $r_e$ is the random coins used in the encryption. To open the commitment in a later point in time Alice sends $m,r_g$ to bob, who in turn obtains $(PK,SK) = Gen(1^n,r_g)$ and verifies that $c=E_{PK}(m;r)$.

Just sending $c$ and $PK$ in the commit phase and later send $SK$ and $m$ in the opening does not guarantees binding since there might be other $SK'$ and $m'$ such that $m'=D_{SK}(m)$. The same holds for sending $r_e$ in the opening phase.

For more details see this.

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.