Talking with some friends we arrived at following puzzle: Alice wants to send Bob some message, but Alice has to make sure that some condition is met before allowing Bob to read the message.

This is easily solvable by taking these steps:

  1. Alice encrypts the message using Bob's public key $$e=\texttt{Enc}(m,pk_{Bob})$$
  2. Alice also computes a signature of the message using its secret key $$s_1=\texttt{Sign}(\texttt{Hash}(m), sk_{Alice})$$
  3. Alice now encrypts the first encripted message using its public key $$e'=\texttt{Enc}(m,pk_{Alice})$$
  4. Alice sends over to Bob the pair $(e',s_1)$.
  5. When some condition is met, Alice encrypts is secret key using Bob's public key $$e_k=\texttt{Enc}(sk_{Alice}, pk_{Bob})$$ and computes a signature of if $$s_1=\texttt{Sign}(\texttt{Hash}(sk_{Alice}), sk_{Alice}),$$ seding both to Bob.
  6. Bob can use the pair $(e_k,s_1)$ to find Alice´s secret key $$sk_{Alice}=\texttt{Dec}(e_k, sk_{Bob})$$ to dechipher the first layer of the encryption. $$e=\texttt{Dec}(e', sk_{Alice})$$
  7. Finally, using its private key, Bob can read the message. $$m=\texttt{Dec}(e, sk_{Bob})$$

This solution works, but we were wondering if there is a more general case where it does not matter the order of which one encrypts the message, the message can be obtained back by applying the decryption methods in any order.

Hence the question: is there any encryption scheme which holds commutable under self-composition?

  • $\begingroup$ When you say "secret key", do you mean the private key that corresponds to the public key, or a "secret key" as in a random string of bits (as in the type used in symmetric cryptography, e.g. AES)? The two are not interchangeable terms and have different meanings. Your "signatures" would actually be a "MAC" and not a signature if the "secret key" is a "secret key" (as in random string of bits) instead of a "private key". $\endgroup$ – Ella Rose Mar 8 '18 at 1:04
  • $\begingroup$ You have a few issues with notations: I believe $e'$ is supposed to encrypt $e$ and not $m$, also $s_1$ is used twice for different meanings, and you don't explain what the purpose of the signatures are. Also, $sk_Bob$ should be the key used to decrypt $e_k$, not $s_1$ $\endgroup$ – Florian Bourse Mar 8 '18 at 8:25
  • $\begingroup$ I don't see any commutative property in the protocol you explained. Am I missing something? $\endgroup$ – Florian Bourse Mar 8 '18 at 8:26
  • $\begingroup$ I think what you have come up with here, is a variant of a commitment scheme. $\endgroup$ – SEJPM Mar 8 '18 at 12:40

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.