Commutable and Composable Asymmetric Encryption/Decryption

Question

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?

Answer 1

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-1}$ 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...

Answer 2

Elliptic curve-based Diffie-Hellman (ECDH) Private Set Intersection (PSI) uses very similar technique, i.e. given $m$, do $m\cdot x$, then do $m\cdot x\cdot y$, where $x$ and $y$ are private keys of two sides.

Clearly, $x$ and $y$ are invertible, i.e. it's trivial to compute $m\cdot x\cdot y\cdot x^{-1}\cdot y^{-1}=m$.

The only issue being that $m$ is not the plaintext as you asked. It's the hash value of raw message, since you must hash the message to a point on the elliptic curve in order to do ECDH multiplication.