Let $(E,D)$ be the encryption/decryption of an authenticated encryption scheme. Consider the following commitment scheme.

  1. Generate a random key $k$. Commit to $m$ by sending $c=E_k(m)$.
  2. Reveal $m$ by sending $k$.

The hiding property of the above commitment scheme follows directly from standard assumptions on the confidentiality of $E$. However, I can't figure out if this is binding. It seems that most security notions for authentication do not consider swapping out the keys. In particular, is there a property that guarantees that $D_{k'}(c)$ fails to verify/decrypt?

  • 1
    $\begingroup$ The standard AEAD definition doesn't cover binding, but there are newer encryption schemes which does. "encryptment" and similar terms is a good starting point for the current research on efficient algorithms for it. $\endgroup$
    – Natanael
    Nov 14, 2019 at 23:04

1 Answer 1


is there a property that guarantees that $D_{k'}(c)$ fails to verify/decrypt?

No, there is not; all the security guarantees that authenticated encryption provides is of the form "if you don't know the keys, then it is difficult to..."; it says nothing about the difficulty of anything if you do know the keys.

And, it turns out that, with GCM, you can generate a ciphertext that authenticates with two different keys, and it's not that difficult.

Here's how it works; you pick two random keys $k_0, k_1$, a random authentication tag $t$, and an appropriate nonce and AAD. Then, GCM has the property that, if you have a 32 byte ciphertext consisting of the 16 byte blocks $X_a, X_b$, this ciphertext would authenticate (in the context you picked) if:

$$h^3 X_a + h^2 X_b = C$$

where $h$ is the authentication key generated by the key, and $C$ is a constant that depends on the key, authentication tag, nonce and AAD, and all math is in $GF(2^{128})$

The two different keys generate different $h$ and $C$ values, and hence we can generate two simultaneous equations:

$$h_0^3 X_a + h_0^2 X_b = C_0$$

$$h_1^3 X_a + h_1^2 X_b = C_1$$

Everything here is known except for $X_a, X_b$; you have two simultaneous linear equations, and so you can solve for $X_a, X_b$, thus giving you a ciphertext that will decrypt to something with two different keys.

Now, this method doesn't give you any control over what they decrypt to, but still, that is enough to show that GCM isn't binding.

Instead, it would make a lot more sense to use a hash function, that is, $\text{Hash}(r, M)$ for a random fixed length nonce $r$. The collision resistance property means that it is binding. And, if the random nonce $r$ you include is longer than the hash, then it is plausible that even a computationally unbounded attacker cannot get more than weak probabilistic information of what you committed to.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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