Workshop in Milan Next Week

As previously announced, next week Alon Rosen and I are organizing a workshop at Bocconi, which will actually be the union of two workshops, one on Recent Advances in Cryptography and one on Spectral and Convex Optimization Techniques in Graph Algorithms. Here is the program. In short:

• where: Bocconi University’s Roentgen Building (via Roentgen 1, Milano), Room AS01
• when: June 15-18
• what: talks on cryptography and graph algorithms, including two hours devoted to Max Flow in nearly-linear time
• how: register for free

A New Conference on Information-Theoretic Cryptography

A new conference on Information-Theoretic Cryptography is starting next year. It is about topics that I have always been fond of, a former student of mine is in the steering committee, and an academic grandchild of mine is in the program committee of the inaugural conference, so I am very happy to pass along the following announcement from Benny Applebaum.

---

Dear friends,

We are happy to announce the birth of a new conference on Information-Theoretic Cryptography (ITC). Information-theoretic cryptography studies security in the presence of computationally unbounded adversaries and covers a wide array of topics at the intersection of cryptography, coding theory, information-theory and theory of computation. Notable examples include randomness extraction and privacy amplification, secret sharing, secure multiparty computation and proof systems, private-information retrieval and locally decodable codes, authentication codes and non-malleable codes, differential privacy, quantum information processing, and information-theoretic foundations of physical-layer security. See https://itcrypto.github.io for more information.

ITC replaces the International Conference on Information Theoretic Security (ICITS), which was dedicated to the same topic and ran 2005-2017. ITC can be seen as a reboot of ICITS with a new name, a new steering committee and a renewed excitement.  (beware: there is  a fake website for ICITS 2019 created by a known fraudulent organization)

The conference will have two tracks: a conference track and  a “greatest hits” track. The conference track will operate like a traditional conference with the usual review process and published proceedings. The “greatest hits” track consists of invited talks (not included in the proceedings) that highlight the most exciting recent advances in the area. We solicit nominations for “greatest hits” talks from the community.

The first ITC conference will take place in Boston, MA on June 17-19, 2020 (just before STOC).  The submission deadline for ITC 2020 is Dec 16, 2019 and the call for papers (including a nomination procedure for the greatest hits track) is available here:  https://itcrypto.github.io/2020.html

Please submit your best work to ITC 2020! We hope to see many of you there!

best regards,

The Steering Committee:  Benny Applebaum (Chair), Ivan Damgård , Yevgeniy Dodis,  Yuval Ishai, Ueli Maurer,  Kobbi Nissim, Krzysztof Pietrzak, Manoj Prabhakaran, Adam Smith, Yael Tauman Kalai, Stefano Tessaro, Vinod Vaikuntanathan, Hoeteck Wee, Daniel Wichs, Mary Wootters,  Chaoping Xing, Moti Yung

Ran Canetti on Obfuscation and New Assumptions

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.

Cryptography at STOC/FOCS

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:

On the Importance of Fast Encryption

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.”

Neutronic Encryption

Via Boing Boing and Bruce Schneier, I bring you the web site of singularics corporation.

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?

Chickens and Eggs

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?