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.



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.


You can engage in Secure Twoparty Computation, e.g. using Garbled Circuits. You can build a circuit of a decryption function with two inputs, i.e. the key and the ciphertext. You can obliviously transfer the key and the encrypted message and evaluate the garbled circuit.

A tool to build and evaluate a garbled circuit could be CBMC-GC. I think it is secure under semi-honest attacker, only, so I use SCAPI with malicious secure OT and cut-and-choose for the circuit in order to achieve security against an active attacker.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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