5
$\begingroup$

I recently used a custom construction as a commitment scheme, which was taken from the standard picture you give people while explaining commitment schemes.

Basically commitment schemes can be described in terms of physical objects, as "put the information to commit to in a lockable box, give the other person the box and keep the key. As soon as you want to prove that you had the information at the previous time, give him the key to verify".

Now Schneier (in Applied Cryptography 2nd edition p. 86) describes a block cipher based commitment following the exact same principle (with block ciphers). Choose some random value (B does) and let A encrypt it using the key to which A wants to commit, basically exchanging "key" and "content".

Now for the custom scheme:

Suppose you are using an authenticated encryption scheme (e.g. AES-GCM) and you want to commit to a value $R$.

  1. Encrypt $R$ using a randomly chosen $k$ and choose a random IV and append the tag. ($=IV||C||tag$)
  2. Send $k$ to the verifier at the point of verification.

So the question:
Is authenticated encryption the computer equivalent to a lockable box (in this context)? or equivalently: Can the above commitment scheme be broken (and if yes, how?)

For me it looks like the above question is equivalent to:
Given a ciphertext with tag, there's only one key that will produce the correct tag with the given ciphertext, meaning the corresponding plaintext can't be altered.

$\endgroup$
  • 1
    $\begingroup$ Just found this old question via Google. This recent paper studies the connection between authenticated encryption and commitments: eprint.iacr.org/2017/664.pdf . (Disclosure: I am a co-author.) The tl;dr is that some authenticated encryption schemes can be treated as commitments, but only if collision-resistant primitives (e.g. HMAC) are used. The paper shows an attack which breaks the binding security of GCM. GCM is not a committing encryption scheme because its MAC is not collision-resistant. $\endgroup$ – pg1989 Aug 18 '17 at 23:50
2
$\begingroup$

No.


Yes, by choosing an authenticated encryption scheme with a known $\:I\hspace{.03 in}V\hspace{.04 in}||\hspace{.04 in}C\hspace{.04 in}||\hspace{.04 in}tag\:$ and $k_{\hspace{.02 in}0}$ and $k_1$ such that decrypting $\:I\hspace{.03 in}V\hspace{.04 in}||\hspace{.04 in}C\hspace{.04 in}||\hspace{.04 in}tag\:$ with $k_{\hspace{.02 in}0}$ and $k_1$ yields different outputs, neither of which are $\perp$.

These three links describe a black-box construction of authenticated encryption from one-way functions. $\:$ On the other hand, there is no known construction of non-interactive commitments from one-way functions, and this paper declares, "We rule out the possibility of black-box constructions of non-interactive commitments from general (possibly not one-to-one) one-way functions." However, Naor's scheme comes close.


The only candidate constructions of non-interactive commitments that I'm aware of either use a

$\:$ (1) key agreement scheme with sufficient completeness (this is the standard way to do it), or
$\;\;\;\;$
$\:$ (2) family of injections given by tuples of multi-variate polynomials over finite fields, or a
$\;\;\;\;$
$\:$ (3) keyless CRHF (these cannot be secure against non-uniform committers), or a
$\;\;\;\;$
$\:$ (4) hitting one-way function (in addition to presumably being only computationally hiding,
$\:$ these are also not known to be binding against (uniform) efficient committers)

.

$\endgroup$
  • $\begingroup$ in "easy" words: There's no known secure non-interactive commitment scheme based entirely on symmetric crypto? $\endgroup$ – SEJPM Jul 17 '15 at 16:04
  • $\begingroup$ Right. $\:$ (I just expanded on that in my answer.) $\;\;\;\;$ $\endgroup$ – user991 Jul 17 '15 at 16:25

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.