Secret code or foreign language? For machines, it might not matter. Without any prior knowledge, artificial intelligence algorithms have cracked two classic forms of encryption: the Caesar cipher and Vigen猫re cipher. As translating languages is similar to decoding a cipher, the approach may improve translation software.
To break the ciphers, and colleagues at the University of Toronto and Google used a type of algorithm called a generative adversarial network. The GAN started with no knowledge of ciphers or language, but by analysing thousands of English sentences and lines of coded text, it was able to start switching between the two. The texts were in no way related, for instance, it could have started with Alice鈥檚 Adventures in Wonderland in English and To Kill a Mockingbird in cipher text.
After analysing the texts, one part of the algorithm makes guesses about the cipher, and another part determines if the result makes sense based on what it has learnt about English. If it doesn鈥檛, the algorithm updates its next guesses accordingly. This process was then repeated thousands of times, until the GAN reached near perfect accuracy on cipher text generated by the Caesar and Vigen猫re ciphers (see box).
Advertisement
Cunning codes
The Caesar cipher is one of the earliest known codes. It is named after Julius Caesar who, suspecting eavesdropping, decided to shift each letter in his messages by three places along the alphabet. For example, 鈥淐aesar鈥� became 鈥淔dhvdu鈥�. Doing this for every letter meant that a page of Latin became a page of seemingly impenetrable gobbledygook. But for anyone who knew the cipher, getting the original message just involved moving each letter back three places.
Invented in the 16th century, the Vigen猫re cipher uses a similar method to the Caesar cipher, but switches the amount of alphabet shifting with each letter. A keyword determines the amount of the shift, so once the sender and the receiver have agreed on this word, it is easy to switch between the original message and cipher text.
The GAN broke the ciphers by learning a method similar to frequency analysis. The underlying principle of this technique is that if you know how frequently each letter appears in a language, you can try to match them by looking at the frequencies at which letters crop up in the cipher text. For example, 鈥渆鈥� is the most common letter in English, occurring nearly 13 per cent of the time. Whatever 鈥渆鈥� corresponds to in the cipher text should also appear with a similar frequency, giving a clue on how to break the code.
For frequency analysis to work effectively, you need a lot of text to ensure accurate frequencies. But this is rarely available when intercepting secret messages, so the method is often more thought-provoking than useful at cracking actual codes.
鈥淔or cryptanalysis, their results are way behind current achievements,鈥� says Bernhard Esslinger, head of the open-source encryption project . 鈥淏ut for automated translation of human languages, this could be interesting.鈥�
When learning to translate, it is usually easy to get lots of examples of the two languages: just raid a library or scrape text off the internet. The tricky bit is working out how to switch between the two.
The best translation software currently relies on learning from pairs of translated sentences. For example, Google Translate originally learned to translate between French and English by analysing thousands of documents from the United Nations and European Parliament that had already been professionally translated.
But such accurate translations don鈥檛 exist for many language pairings. So translation engines normally use English as a stepping stone, first translating to English and then to the actual target language.
As the new approach doesn鈥檛 require paired sentences, the stepping stone could be ditched. This process, called unsupervised translation, is something that Facebook is , as well as Google. 鈥淯nsupervised translation is super-hot right now. It鈥檚 not just an interesting idea, it鈥檚 getting really impressive results,鈥� says Gomez.
Reference:
