Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.
  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$ ?

share|improve this question

2 Answers 2

up vote 3 down vote accepted

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.

share|improve this answer

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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