• Joint UK-US team finds way to send perfectly secure secret digital communications without cryptography or quantum computers
• Advances in information theory are behind a new steganography algorithm 
• Undetectable messages are placed within innocuous covertext 
• This has major implications for information security and data compression and storage
• We have come a long way on from invisible ink

A group of scientists from the University of Oxford in England and Carnegie Mellon in Pittsburgh, Pennsylvania, has announced a breakthrough that, it is claimed, will enable the transmission of perfectly secure secret digital communications without the need for cryptography or quantum computers. A new academic paper, Perfectly Secure Steganography Using Minimum Entropy Coupling, describes how, by exploiting the latest advances in the methodology of information theory, it has been possible to develop a new algorithm, the application of which enables a set of data content to be placed within another and disguised so completely that it is undetectable.

Oxford University led the programme in close collaboration with the famous private research university, Carnegie Mellon. The new algorithm is steganographic rather than cryptographic: Steganography is the science (and, in some cases, quite literally, art) of encoding secret information (stegotext) into content (covertext) so innocuous or normal to a reader or viewer that they are not aware the content carries within it a second, hidden, message. Thus, steganography hides a secret message such that anyone other than the intended recipient is quite unaware that the message is encapsulated in the covertext. However, cryptography hides secret content and observers other than an intended recipient are aware that secret content does exist but do not know whether or not it may be decipherable.

The Oxford and Carnegie Mellon teams demonstrated that Christian Cachin’s information theory model of steganography, as articulated at the Massachusetts Institute of Technology (MIT) in 2004 – where “an adversary’s task of distinguishing between an innocent cover message C and a modified message S containing hidden information is interpreted as a hypothesis testing problem. The security of a steganographic system is quantified in terms of the relative entropy (or discrimination) between the distributions of C and S, which yields bounds on the detection capability of any adversary” – can be perfectly secure, but only if it is induced by minimum entropy coupling.

Currently, steganography is not totally secure as it is always possible (to some degree) to detect a hidden message because existing steganography algorithms would subtly change the distribution of the innocuous content. However, the Oxford and Carnegie Mellon teams found that minimum entropy coupling permits two distributions of data to be merged such that their mutual information is maximised while the individual distributions are maintained.

In essence, this means there is no statistical difference between the distribution of the innocuous content and the distribution of content that encodes sensitive information. The new algorithm permits 40% higher encoding efficiency than previous steganography methods across a variety of applications, thus enabling more information to be hidden within a given amount of covertext. What’s more, the research teams found the algorithm to be highly scalable, a property that could be of profound importance not only for information security but also in the fields of data compression and storage.

Something new under the sun?

Ciphers and steganography have been around for a very long time. The fifth century BC Greek historian Herodotus wrote that it was first used by the tyrant Histiaeus, who shaved the head of a male slave then tattooed a message for his nephew Asistagorus on the slave’s bald pate, waited for his hair to grow back, and then sent the slave to deliver the message, which was revealed when the slave’s head was once again shaved. The message was all part of a plot by Histiaeus to overthrow his master, the Persian King of Kings, Darius the Great – it didn’t end well for Histiaeus, however, as, somewhat ironically, his severed head was delivered to Darius to show his traitorous advisor was dead (for a nice recap of the story, read this). 

Later, but not that much later, came the classical invisible inks, the first of which was probably urine-based until the much more pleasantly scented lemon juice alternative was discovered. Elsewhere, artists have long hidden their names and initials and even self-portraits in their paintings. Then, in more recent times, many a modern beat combo placed hidden messages in audio files, The Beatles being particularly prolific in putting back to front messages on or between the tracks of some of their albums.   

For more than a generation, academic researchers have been seriously studying steganography and very recently the new algorithm was tested on auto-generated content applications, such as the GPT-2 open-source language model that is the subject of the furore surrounding the apparent emergence of “sentient” chatbots (which most certainly are not!). However, with AI-generated content set to become commonplace, the use of steganography could well become widespread as content spouted by chatbots and other apps and services become an unremarkable norm. It will be possible to conceal a multitude of stegotext in the multitudes of derivative covertext blurb with which we all will soon be bombarded.

The research team has applied for the new algorithm to be patented for possible commercial use but will provide it to a third party under a free licence for research purposes. They will also present the new algorithm at the 2023 International Conference on Learning Representations that will be held in Kigali, Rwanda, in the first week of May. 

Commenting on the breakthrough, Dr Christian Schroeder de Witt of the Department of Engineering Science at the University of Oxford, who co-authored the paper, said, “Our method can be applied to any software that automatically generates content, for instance probabilistic video filters, or meme generators. This could be very valuable, for instance, for journalists and aid workers in countries where the act of encryption is illegal. However, users still need to exercise precaution as any encryption technique may be vulnerable to side-channel attacks, such as detecting a steganography app on the user’s phone.’

His co-author and colleague Samuel Sokota  of the machine learning department at Carnegie Mellon University, added, “The main contribution of the work is showing a deep connection between a problem called minimum entropy coupling and perfectly secure steganography. By leveraging this connection, we introduce a new family of steganography algorithms that have perfect security guarantees.”