Cryptography: Science or Magic?
Are there ciphers that cannot be broken? Can you share a secret between five people so that you do not get any information about the secret if you just have four of the shares? Can you have a solid encryption without a key being transmitted between the sender and receiver? Can you prove the outcome of a coin-toss experiment without being there to watch it? Can you prove you know a secret without revealing any information whatsoever about the nature or content of this secret?
In 1926, Vernam developed a cipher he thought was unbreakable. You convert your message to binary and then generate a random string of binary numbers and add those together to get the ciphertext. But is this an unbreakable cipher? Vernam did not have a mathematical proof for this, but had some empirical evidence from field trials in the U. S. Army Signal Corps. But that is not enough to justify a belief in the mathematical impossibility of it being breakable. It turns out that, as Claude Shannon proved in 1949, the ciphertext is statistically independent of the encoded message since the random binary string has a 50% probability of changing any given character. The Vernam cipher became the predecessor of the modern one-time pad cipher.
If you are the owner of a bank and wants to keep your core information a secret, can you split your message among your vice presidents and prevent an attacker knowing anything if they capture one of the executives? The basic idea is that you take the core information, generate a random string of binary digits and add it to the secret. Then you give the random string to one executive and the sum of the secret and the random string to the other person. This means that even if one of them is captured, it is not possible to learn anything about the core information. You have to have both of them. This was later generalized to an arbitrary number of shares and a threshold below which you get no information.
Follow Debunking Denialism on Facebook or Twitter for new updates.
What about cryptography without sharing a secret key? If Alice and Bob each has a key, can they send a secret box between each other without an adversary finding it out? Well, Alice starts by applying her key, sending the result to Bob, who applies his key and sends it back to Alice, who takes away her key and sends it to Bob who removes his key and opens the box. Is this legitimate? No, it turns out. Because this method uses binary numbers and modulo 2 operations, if you add all the three cryptotexts sent between Alice and Bob, you get the cleartext. This is because the two keys occur twice and the message occur three times. Since each key occurs twice, it canceled (think adding 1 and 1 to a 0 or 1 modulo 2), and two of the messages cancels, the only thing that remains is the message. This was just an illusion.
James L. Massey was Professor Emeritus of Digital Technology at ETH Zurich who worked a lot on Random access communications research and cryptography. In 2001, he gave a talk hosted by The School of Engineering, Electrical Engineering and Computer Science at Massachusetts Institute of Technology and filmed by MIT World on the topic of cryptography entertainingly called Cryptography: Science or Magic? with major emphasis on to what degree it can be proven that cryptography systems work (science) or if it is merely an illusion (magic). In particular, Massey discusses five cryptography tricks: unbreakable cryptography, no-leak secret sharing, no-key cryptography, no-watch coin tossing and no-knowledge proofs.
Many of the advanced cryptography issues that Massey discusses are neither known to be magic or science, because there is currently no proof that it is extremely hard or intractable to factor the product of two enormously large primes. Perhaps, in the future, someone will develop a faster or more efficient method of factoring large numbers. He is disappointed that so few people are interested in working on many of these issues and notes that the hardest problems are those that no one is working on.
