Cryptography
encryption diffie-hellman key-exchange
Updated Mon, 19 Sep 2022 09:09:47 GMT

Commutable and Composable Asymmetric Encryption/Decryption


I have a need for the following encryption properties: $f(g(v_\text{plaintext}) = v_\text{ciphertext}$ needs to be decryptable by $f^{-1}(g^{-1}(v_\text{ciphertext}))$ and $f$ and $g$ need to be different. The idea goes like this.

  1. A user is going to encrypt some plaintext (DB credentials) with a private key they control. $g(v_\text{plaintext})$

  2. A server is going to encrypt $g(v_\text{plaintext})$ with a private key that it controls. $f(g(v_\text{plaintext})) = v_\text{ciphertext}$.

  3. Sometime in the future the server will ask the user to decrypt using their private key and send the result back to the server. $g^{-1}(v_\text{ciphertext})$.

  4. Server will take the result from the previous step and decrypt the ciphertext: $f^{-1}(g^{-1}(v_\text{ciphertext})) = v_\text{plaintext}$.

The reason that I find this procedure desirable is that:

  1. the DB credentials ($v_\text{plaintext}$) are never sent over the wire unencrypted
  2. the owner of the DB credentials is able to encrypt on their side (client-side using $g$).

Anyone know of a set of cryptographic primatives that would get me there?

Solution

Anyone know of a set of cryptographic primatives that would get me there?

The Pohlig-Hellman cipher [1] would appear to be the right general direction.

This algorithm is a secret key algorithm, and is done as follows: there is a public prime $p$, and each side has a secret key $a$ (or $b$ for another secret key held by a second party).

Encryption is simple, $E_a(m) = m^a \bmod p$, to decrypt, you compute $a^{-1} \bmod p$ and then compute $D_a(c) = c^{a^{-1}} \bmod p$

This encryption has the property that $E_a(E_b(m)) = E_b(E_a(m))$ (because they're both $m^{ab} \bmod p$), and so you can decrypt in any order (just like you asked for).

And, it also has the property that someone who hears $E_a(m), E_b(m), E_a(E_b(m))$ cannot recover $m$; I suspect this is an important property in your scenario.

Your protocol design would appear to work with a symmetric cipher such as Pohlig-Hellman (because in your protocol, the user does all the $g$ operations and the server does all the $f$ operations). If you decide you need an asymmetric one (that is, one where someone can encrypt with a public key, and decrypt with a private one), the obvious way to do this would be to extend Pohlig-Hellman with an Integrated Encrypted System approach; also have a public generator $g$, and have a private key be a value $x$, and the public key $g^x \bmod p$. To encrypt a value $m$, the encryptor:

  • selects a random value $y$
  • computes $g^y \bmod p$ and $(g^x)^y \bmod p$
  • computes $z = \text{kdf}( (g^x)^y \bmod p )$ (using a key derivation function with a long output, such as SHAKE)
  • outputs the ciphertext $g^y \bmod p, m^z \bmod p$

The decryption algorithm is obvious. And, if the later Pohlig-Hellman operations (either symmetric or asymmetric) only modify the second component and leave the first component untouched, you retain the commutativity property.

[1]: Actually, it appears to be rather hard to find papers on this - all searches on Pohlig-Hellman tend to point you to the discrete log algorithm by the same inventors. You could search on the 'Shamir Three Pass' algorithm, which is based on essentially the same idea...

Comments (5)

  • +0 – I'm studying this response, now. It will take me some time to digest. I'll default to accepting if I don't think this is wrong after mulling it over for an hour or two (that is, if I don't understand but don't doubt that it's true then I'll accept). But, on its surface this looks like the right approach. The security of this approach relative to the XOR approach suggested in my question's comments is due to the hardness of solving the discrete log problem relative to the hardness of inverting XOR operations. Is that right? — Aug 19, 2022 at 13:13  
  • +1 – @fuzzybear3965: actually, it's the Diffie-Hellman problem, not the discrete log - otherwise, yes, that's right — Aug 19, 2022 at 13:14  
  • +0 – All "sides" (owners of a and b) have access to Ed25519 private keys. Is it possible to use these for a and b? I ask because Ed25519 are "signature keys" and we use these for verifying identity but not encrypting data. We have an SDK which uses these keys but it exposes no "encryptData" method only "sign" methods. — Aug 19, 2022 at 13:19  
  • +0 – Considering your edit: The "Pohlig-Hellman cipher" is not the same as en.wikipedia.org/wiki/Pohlig%E2%80%93Hellman_algorithm ? — Aug 19, 2022 at 13:26  
  • +1 – @fuzzybear3965: it's not the same - the Wikipedia page talks about the discrete log algorithm... — Aug 19, 2022 at 13:27  

References