I had asked a question related to this before: Oblivious Decryption: Decrypting with a private key, without knowing the message

@rikhavshah has an answer, which I would like to discuss the security of.

Simply put:

• Alice has an RSA public key $$(e, N)$$ and a private key $$(d,N)$$
• There's a ciphertext $$x$$, padded and encrypted using Alice's public key.
• Bob doesn't know what the padded plaintext $$m_p$$ is, but has the ciphertext $$x$$.
• Bob randomly chooses a mask $$r$$ from $$\{1,\cdots,N-1\}$$, calculates $$x\,r^e\bmod N$$ and sends it to Alice.
• Alice decrypts $$x\,r^e$$ by computing $$(x\,r^e)^d\bmod N$$, which is also $$x^d\,r\bmod N$$, and sends it to Bob
• Bob multiples the value by $$r^{-1}$$ (the modular multiplicative inverse of $$r$$ modulo $$N$$, which with overwhelming odds is well-defined) to extract $$x^d\bmod N = m_p$$. And later on removes/decodes the padding to extract $$m$$.

This way, Alice decrypts $$x$$, without knowing what $$m_p$$ is. Bob knows the value of $$m_p$$ without knowing the value of Alice's private exponent $$d$$

Is there a known attack, that this scheme is vulnerable to? Can the choice of $$r$$ make this more or less secure? Or simply, how can we approach this scheme and make it secure?

Note: as @rikhavshah has also mentioned in their answer, this has a potential attack where Bob can get Alice to decrypt anything encrypted with her public key. But this is actually what the scheme requires. So I wouldn't consider this as a vulnerability. And please assume, they are using a signature scheme to verify each-others identity.

• @fgrieu thanks for the remarks, I've updated the bullet point. Please do not hesitate to modify, if you see some other flaws in notation. Oct 3, 2018 at 15:46

In the last bullet of the question, Bob computes $$x^d\bmod N=m_p$$. This the padded message $$m$$. Padding must be removed from $$m_p$$ by Bob to get back $$m$$. And serious problems can occur if Bob leaks at what step the padding check fails, just like in James Manger's A Chosen Ciphertext Attack on RSA Optimal Asymmetric Encryption Padding (OAEP) as Standardized in PKCS #1 v2.0 (in proceedings of Crypto 2001).

If Bob leaks where the padding fails (e.g. by timing), and allows that to occur often enough (some thousands times) for different $$x$$ chosen by an adversary, then an active adversary can decipher a message, unbeknown to Bob, even though Alice would have refused to decipher the message should the adversary have asked Alice directly (because Alice authenticates who she accepts messages from).

There is no proof that having $$(N,e)$$ and the capability to raise to the power $$d$$ modulo $$N$$ (by querying Alice) does not allow Bob to factorize $$N$$ and get at $$d$$ (or an equivalent). That's only widely conjectured.

It should also be emphasized that Bob does not have $$d$$, but has access to something almost as good: the capability to raise to the power $$d$$ modulo $$N$$. And he can share that capability (by forwarding requests to Alice and her answers, or just revealing his credentials w.r.t. Alice).

Also: even with secure padding such as OAEP verified by Bob without leaking anything other than success/failure, Bob should still be careful that messages deciphered with the help of Alice that pass the padding check are in no way authenticated. For example, if a (genuine) message $$x$$ has deciphered to "the winner is Carol", and Bob later gets a message $$x'$$ that decipher to "repeat: winner is Malory", Bob should not leak that he is surprised, for that would reveal that the winner is not Malory to whoever (e.g. Malory) generated the bogus $$x'$$.

Aside of these, and standard implementation attacks on Alice and Bob (e.g. side-channel leakage), I see no other attack specific to the protocol.

Per comment: I do not see that the protocol is sensitive to minor imperfection in the generator for $$r$$, including w.r.t. Alice trying to get at $$m$$.

• I've updated the question to state the padded message $m_p$ instead of $m$. Considering Bob decodes within their own privacy. Can we say we'll be immune to this attack? How can this be leaked? Oct 3, 2018 at 15:47
• Manger's CCA attack applies if one knows the ciphertext being depadded, and information about the success of depadding. This information can be leaked if Bob is decrypting the ciphertext someone else sent to him and sends them back the plaintext/error message. It can also be leaked if an adversary gains some insight into Bob's computations, eg measuring his power consumption. The adversary may also be able to time how long it takes for Alice to decrypt, which can cause leakage. Oct 3, 2018 at 15:58
• These attacks are about RSA in general, and not the particular protocol you ask about. There are standard ways of avoiding them (see PKCS #1 v2.1). Oct 3, 2018 at 16:00
• @rikhavshah and also fgrieu, other than this, which seems to be avoidable, do you see any more possible attacks? Oct 3, 2018 at 16:01
• @fgrieu Does the choice of $r$ or the the protocol itself, can cause Alice to access the value of $m_p$? I think one of the most important aspects of the protocol is to also hide the value of that from Alice. Oct 3, 2018 at 19:21