MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I'm not quite sure how to phrase this question mathematically, so I am going to express it in words first:

Let us suppose I have a secret $m_1$ and a plausible innocent secret $m_2$. Is there an encryption algorithm which takes $m_1$ and $m_2$ and combines them with 2 public keys $e_1$ and $e_2$ into a ciphertext $c$ such that when a publicly known decryption algorithm is used on $c$ with private key $d_1$, $m_1$ is returned, but if $d_2$ is used instead, $m_2$ is returned, but without knowing the encryption algorithm used it must be plausible that there is only 1 hidden message?

ie: $$D(E(m_1,m_2,e_1,e_2),d_k)=m_k \qquad k\in\lbrace 1,2\rbrace$$

I am thinking it would require a pair of one-way trapdoor functions mingled together somehow so that it would be difficult to compute $d_k$ from $e_k$. But I also have no idea how to make it plausible that there is only 1 possible $d$ (assuming the ENcryption algorithm is unknown to the enemy).

For example, one naive attempt I had was to append two RSA messages together using the same $n$ value but differing $e$, and then decryption involves splitting $c$ into two parts and discarding the irrelevant half depending which private key is used (can be simply indexed as part of each key). The obvious downside to this method is that if you examine the decryption algorithm it is blatantly discarding half the ciphertext, and the enemy will know straight away that he has not recovered the whole message.

share|cite|improve this question
Are you just interested in the existence or do you need an efficient way to find $e_i, d_i$ given $m_i$ ($i = 1, 2$)? – Someone Jul 14 '11 at 12:44
Well, ideally I'd like to know an algorithm that actually works this way, although I don't "need" it. – Damien Zammit Jul 14 '11 at 12:53
For the existence you could just take the RSA with modulus $m = p\cdot q$ where $\mathrm{gcd}(p, q) = 2$. Then "solve" the discrete logarithm problems $m_i^{f_i} = c \bmod p$ and $m_i^{g_i} = c \bmod q$. If $f_i = g_i \bmod 2$ then you should be able to assemble $f_i$ and $g_i$ to get the public exponent $e_i$, and the chance of both equations to hold should be $\frac{1}{4}$ (if not, take another $m$). – Someone Jul 14 '11 at 13:03
If m_1 and m_2 are of comparable length, how are you going to trick the eavesdropper about the quantity of information contained in the message? However you do it, if they only recover a short plaintext from a long ciphertext, they are bound to be suspicious about the apparent inefficiency. – Colin Reid Jul 14 '11 at 16:10
To put a positive spin on Colin's comment, one could use steganographic techniques to hide a small $m_1$ inside a relatively large $m_2$. – Gerry Myerson Jul 15 '11 at 1:05

Your Answer


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

Browse other questions tagged or ask your own question.