Matryoshka: Hiding Secret Communication in Plain Sight

We want to enable a pair of communicating users to exchange secret messages while hiding the fact that secret communication is taking place. We propose a linguistic steganography approach, where each human message is hidden in another human-like message. A hard open question is how to keep the steganographic message small -- existing related tools tend to blow up its size, thereby revealing the use of steganography. We encrypt by compressing each message, mapping it to a plausible sequence of words (using a language model), and letting the human user edit the outcome to produce a human-like message; we decrypt with a Viterbi-like state decoder. Our approach aims in producing text that a human can edit and fix with minimal effort. As a first step, we build a prototype of our system that helps users encrypt English messages (into English messages), and we report on first experiments on Mechanical Turk.