Ran Canetti has written a post on the Berkeley Simons Institute blog concerning new assumptions used in recent cryptographic work on problems such as obfuscation, and concerning how the theory community should view such work.
It has been too long and now there is no point telling stories from the last two days of FOCS, such as the distinguished theoretician who “flew” on the zip-line on Fremont street and then got drunk at Double Down and asked the two big scary guys who were playing pool if they were twins (they said they were).
As soon as the videos of the conference go online, however, I would suggest to everybody who wasn’t there to watch Dan Spielman’s invited talk, which was phenomenal. Dan talked about the problem of solving linear equations when the constraint matrix is the Laplacian of a graph, the result of a long-term collaboration with Shang-hua Teng. Two major parts of this research program have gone on to become their own research area:
The CNN reports that Iraqi insurgents have been able to see the video feeds from the cameras of the remote-control planes (“drones”) that are used by American forces to gather intelligence and for targeted strikes.
How did the Iraqi insurgents manage to break the encryption used by the American military? That was easy: the video feed is sent in the clear from (some of) the drones. And with what sophisticated eavesdropping devices did the Iraqi insurgents manage to capture the video signal? With standard satellite dishes, and with a Russian program originally written to watch satellite TV channels for free.
Well, thanks God this incredible oversight has been exposed, so that it can be fixed.
“We have known about this for years.” Military sources told CNN. In fact, during the 2003 invasion, the Iraqi army was able to see the feeds from the drones, and hence locate and destroy some of them.
And what exactly was anybody thinking? “Encryption was found to slow the real-time link.” The military source told CNN: “The encryption therefore was removed from many feeds.”
I cannot do justice to it, because every sentence on every page is very special, but here is about one of their products:
One very important result from our advances in mathematics is a new patent-pending encryption algorithm called Neutronic Encryption™. Unlike strong encryption algorithms widely used today, Neutronic Encryption is not based directly on fixed prime points, but rather on the Neutronic forces that govern the distribution of the primes themselves. The resulting encryption is theoretically impossible to break.
And, in more detail,
Singularics has advanced the state of the art in cryptography by developing a new theoretically unbreakable public-key algorithm called Neutronic Encryption™.
Our advances in Prime Number Theory have led to a new branch of mathematics called Neutronics. Neutronic functions make possible for the first time the ability to analyze regions of mathematics commonly thought to be undefined, such as the point where one is divided by zero. In short, we have developed a new way to analyze the undefined point at the singularity which appears throughout higher mathematics.
This new analytic technique has given us profound insight into the way that prime numbers are distributed throughout the integers. According to RSA’s website, the RSA public key encryption algorithm has an installed based of nearly one billion. Each of these instances of the prime number based RSA algorithm can now be deciphered using Neutronic analysis . Unlike RSA, Neutronic Encryption is not based on two large prime numbers but rather on the Neutronic forces that govern the distribution of the primes themselves. The encryption that results from Singularics’ Neutronic public-key algorithm is theoretically impossible to break.
And you know what else you can do with this newly discovered netronic forces of the primes, besides breaking RSA and realizing impossible-to-break encryption? Continue reading
Having nearly extinguished my sabbatical credit, this semester I am teaching CS276: Foundations of Cryptography.
As in the 2002 edition, the course will teach, in some order, the progression from one-way functions to pseudorandom permutations, the use of pseudorandom permutations to do private-key encryption and authentication, the notion of trapdoor permutations, the notion of commitment scheme and zero-knowledge proofs, and the use of those tools, plus possibly random oracles, to achieve various notions of security for public-key encryption and signatures. Finally, a few bewildering lectures on multi-party computations.
What is the right order in which to teach all this? The “logical” order is roughly the one outlined above, which is also the order in Goldreich’s books
, in the Katz-Lindell book, and in many courses, including Jonathan’s and Salil’s.
A problem with this approach is that incoming students, who want to see how to design a cryptographic protocol and reason about it, are treated to week after week of purely complexity-theoretic results. Furthermore, there is a problem in motivating the notion of one-way functions because the most likely candidates are block cipher (i.e., pseudorandom permutations) constructions and number-theoretic functions. But motivating one-way functions with block ciphers defies the whole purpose of constructing block ciphers from one-way functions, and the number-theoretic candidates mostly come with trapdoors and are better introduced when talking about trapdoor permutations.
Our 2002 syllabus was organized by starting with trapdoor permutations and public-key encryption, and doing the one-way function theory and the private-key encryption later. Our reasoning was that students had already seen (usually, several times) RSA and the notion of public-key encryption, and could be immediately confronted with the point of modern cryptography by showing what kind of problems arise if one uses plain RSA to do deterministic encryption. Then the notion of message indistinguishability and semantic security arise quite naturally, and when later one gets to the theory of one-way functions it is good to already have an intuitive grasp of indistinguishability.
This year I would like to try something different (which is similar to the order in Mihir’s and Boaz’s courses) by starting with the definition of block cipher / pseudorandom permutation, showing how to do private-key encryption and authentication using block ciphers, and then showing how construct block ciphers from one-way permutations. (Perhaps giving number-theoretic candidates of one-way permutations.) Then continuing with trapdoor permutations and public-key encryption.
The idea is to keep a logical order in which the cleaner private-key theory is done first, but also to give the students a chance to see functioning protocols right away.
What would you do?