Can RSA be securely used for “blind decryption”?

Question

Assume we have the following setup:

• A client with trusted storage and computing capabilities (e.g. a smartcard)
• A server with trusted computing and short-term storage capabilities (e.g. RAM + CPU, possibly with something like Intel SGX). The server has no trusted large-scale long-term storage capabilities and may only store small amounts of data confidential and integrity protected (like the HTTPS private key).

The problem is: The server should be able to be shut-down and started-up, no passwords should be involved and the server has no HSM, yet the server should be able to provide somewhat secure access to some data without the clients needing to decrypt it themselves (for complexity reasons). So the storage need to be encrypted and the transfer (-> TLS) as well.

---

The solution is now (what I call it): blinded decryption.

The server uses some homomorphic encryption scheme (e.g. EC-ElGamal or RSA) with the message space $\mathcal M$. He chooses a random $k\in \mathcal M$ and uses $H(k)$ ($H:\mathcal M \rightarrow \{0,1\}^{256}$) as the key for the authenticated encryption of the data. The server now either stores the (asymmetric) encryption of $k$, called $\mathcal E(k)$ in his trusted area of the drive(s) or may store it in an untrusted section (with back-ups) if server authentication is required and the private key for this authentication is already stored in the trusted area.

For the temporary unlock of the encrypted data, the server loads $\mathcal E(k)$. Then he blinds it using some operation $f(\cdot,\cdot)$ (multiplication for ElGamal and RSA, addition for EC-ElGamal) using some random $r\in \mathcal M$ as $c=f(\mathcal E(k),\mathcal E(r))=\mathcal E(g(k,r))$ with $g(\cdot,\cdot)$ being the "inner homomorphism" (same as $f$ in many cases). The $r$ is kept available in trusted short-term memory and the $c$ is sent to the client.

The client decrypts $c$ using his trusted device and returns $c'=g(k,r)$ to the server. Finally the server unblinds $c'$ using his $r$ and uses the obtained $k$ to derive $H(k)$ and allow access to the data.

---

Now (finally) the question:
Given the above and standard assumptions (RSA-assumption, DDH-assumption in ECC and $\mathbb Z_p^*$,$H$ is a random oracle, the symmetric encryption is secure and authenticated,...) is it safe to instantiate $\mathcal E$ with textbook RSA?

---

As pointed out in the comments, every good question about "is this secure?" requires a threat model, so here's mine:
The security of the whole protocol is broken if an attacker is able to learn the secret symmetric key $H(k)$ while it's valid. The attacker may not compromise the server (i.e. he can't control/spy on RAM / CPU and may not learn the stored $\mathcal E(k)$). An attacker not breaking into the server may have successfully attacked the client (except for the trusted device) and he may be able to completely modify and read the network traffic. I think an attacker without having broken into the server may be computationally unbounded.

---

If not clear until now, the instantiation of $\mathcal E(k)$ is $\mathcal E(k):=k^e \bmod N$ with $e,N$ being standard RSA parameters.

Answer 1

Let's try to simplify and abstract your protocol a bit. Instead of your server and client, we just have two parties, let's call them Sally and Charlie.

• Charlie has a key pair $K = (K_i, K_u)$ for a suitable asymmetric cryptosystem $\mathcal E$. We assume that this cryptosystem is partially homomorphic, such that $\mathcal E_K(a) \otimes \mathcal E_K(b) = \mathcal E_K(a \odot b)$, where $\otimes$ and $\odot$ are two group operations.

• Sally knows the public half $K_u$ of Charlie's key pair, so that she can compute $\mathcal E_K(a)$ given a plaintext $a$, but not the private half $K_i$ that would let her compute $a$ from $\mathcal E_K(a)$.

• Sally has a message $\mathcal E_K(m)$ encrypted with Charlie's key pair, and wants to decrypt it without revealing the decrypted message $m$ to Charlie (or to anyone who might impersonate him).

• Charlie wants to help Sally decrypt her message, but does not wish to reveal his private key $K_i$, or anything equivalent to it, to Sally (or to anyone who might impersonate her).

The protocol you've suggested amounts to Sally picking a random element $r$ uniformly from the group of all possible plaintexts, encrypting it using $K_u$ to get $\mathcal E_K(r)$, and sending $\mathcal E_K(m) \otimes \mathcal E_K(r) = \mathcal E_K(m \odot r)$ to Charlie. Charlie then decrypts the message, and sends $m \odot r$ back to Sally, who applies the group inverse $r^{-1}$ of $r$ to obtain $m = (m \odot r) \odot r^{-1}$:

1. $S:\ $choose $r$ uniformly at random, compute $E_K(r)$ and $r^{-1}$;
2. $S \to C:\ \mathcal E_K(m) \otimes \mathcal E_K(r) = \mathcal E_K(m \odot r)$;
3. $C:\ $decrypt $\mathcal E_K(m \odot r)$ to get $m \odot r$;
4. $C \to S:\ m \odot r$;
5. $S:\ $compute $m = (m \odot r) \odot r^{-1}$.

The first security claim (that Charlie cannot learn $m$) should be easy to prove, regardless of the specific cryptosystem used. Since the plaintexts form a group, and $r$ is chosen uniformly at random from that group, $m \cdot r$ is also uniformly distributed, and so reveals no information about $m$ to anyone who doesn't know $r$. Indeed, even if Sally repeats the protocol with several different random values $r_i$, and so reveals $m \odot r_i$ to Charlie, this will give him no additional information as long as all the $r_i$ are uniformly chosen and independent of $m$.

The tricky part is the second claim, and especially the part about Charlie not revealing "anything equivalent to $K_i$" to Sally. After all, in the protocol as described, Charlie is acting as an unrestricted decryption oracle!

It seems to me that, for this protocol to make sense at all, we need at least the following assumptions:

• Sally cannot be compromised in any manner that would directly reveal $m$ to the attacker; she can only be made to disclose $\mathcal E_K(m)$.

• Access to Charlie is strictly limited, so that even if an attacker obtains $\mathcal E_K(m)$, they cannot simply query Charlie for $m$.

The latter assumption may indeed make sense in your scenario, where Charlie is physically connected to Sally (and only intermittently so connected, being securely stored at other times), if we also assume that Sally is resistant to active compromise (i.e. she may certain data items, but an attacker cannot modify her behavior). That's a pretty huge assumption in practice, but if you're willing to make it, the protocol described above seems like it should work.

(That said, if you're really willing to make all those assumptions, why not simply have Charlie store $m$ and provide it directly to Sally upon request? I'm having some trouble coming up with a reasonable attack scenario where that wouldn't be secure, yet the protocol above would be.)