Take the 2-minute tour ×
Information Security Stack Exchange is a question and answer site for Information security professionals. It's 100% free, no registration required.

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

share|improve this question
    
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
add comment

1 Answer

up vote 6 down vote accepted

The answer can be yes, no, of whuuuut? 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, ton 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 the same problem than storing password hashes. 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; it may reuse some elements which are also used in some asymmetric encryption and signature algorithms (like operations modulo a big prime), but not the asymmetric encryption or signature algorithms themselves.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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