Does this algorithm exist - a secret secret? - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-18T16:01:36Z http://mathoverflow.net/feeds/question/70319 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/70319/does-this-algorithm-exist-a-secret-secret Does this algorithm exist - a secret secret? Damien Zammit 2011-07-14T12:24:36Z 2011-07-14T12:24:36Z <p>I'm not quite sure how to phrase this question mathematically, so I am going to express it in words first:</p> <p>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?</p> <p>ie: $$D(E(m_1,m_2,e_1,e_2),d_k)=m_k \qquad k\in\lbrace 1,2\rbrace$$</p> <p>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).</p> <p>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.</p>