# Is there an oblivious decryption scheme?

1. Alice has $K$;
2. Bob has $E(K, m)$;

Is there such a scheme that enables Alice decrypts $E(K, m)$ without knowing $m$, and Bob gets $m$ ?

-

More generally, any encryption that is commutative can be used because then:

$$(D_k \circ D_K \circ E_k \circ E_K)(m) = m$$

I.e. Bob can encrypt the ciphertext $E_K(m)$ with a new key $k$, then gives that to Alice for decoding with $K$ and finally decodes it himself with $k$.

Stream ciphers are commutative, as is exponentiation modulo $n$ (used in RSA) and multiplication on an elliptic curve.

-

Yes.

The easiest way is if $K$ is an RSA private key, and Bob has the public key.

Then, here's how it works; we'll call the ciphertext that Bob has $C$:

• Bob selects a random number $r$, and computes both $C \cdot r^e \bmod N$ and $r^{-1} \bmod N$ (where $e$ and $N$ are the public exponent and the modulus from the public key)

• Bob sends $C \cdot r^e \bmod N$ to Alice

• Alice uses her private key to compute $(C \cdot r^e)^d = C^d \cdot r \pmod{n}$, and sends that back to Bob

• Bob then computes $(C^d \cdot r) \cdot r^{-1} = C^d \pmod{n}$; that is the decrypted message (and Bob can then remove the RSA padding).

Alice learns nothing, because since $r$ is a random number, so is $r^e$, and so the value she sees is uncorrelated to the original message. Bob learns the decryption, but he doesn't learn anything else.

Now, it is possible to do this with any encryption algorithm (using secure circuits), however it is a lot more work.

-