As the editor quite rightly says, “Conferences are places where we get to see and hear about solutions. ... Rarely is there an opportunity to talk about problems that have not been solved yet,” but this is precisely what newly starting researchers need to hear about. Hence, the editor and the funder, TÜBITAK, deserve to be congratulated on organizing such a conference and on arranging such distinguished invited speakers. This volume is the post-proceedings.
There is then a question of the breadth of the conference. The title certainly reads pretty broadly. But in fact this has been construed to exclude mathematical problems that are not directly computational (such as the Riemann hypothesis), computational problems that are not directly expressible in terms of pure mathematics (such as the predictability of the Madden-Julian oscillation), and problems of computer science such as P = NP. We are left with a range of topics that could broadly be characterized as “cryptography and coding theory,” with a couple of exceptions.
The first paper, “The Past, Evolving Present, and Future of the Discrete Logarithm,” by Joux, Odlyzko and Pierrot, is an excellent survey of the field and its open problems. The diagrams showing the applicability of the various known algorithms are especially clear. The next paper, “Isogenies in Theory and Praxis,” by Frey, is mathematically much more challenging, but again lives up to the aim of the collection by clearly stating a number of problems. In “Another Look at Security Theorems for 1-Key Nested MACs,” Koblitz and Menezes continue their iconoclastic look at the cryptographic literature. The section in their conclusion on “Right Definitions” should be required reading for all researchers in cryptography.
These papers are followed by a variety of papers in the broad area of polynomials over finite fields and related topics. I am not qualified to review these in detail, but again most of them clearly list open problems and characterize areas of applicability (the discussion of bent functions on page 204 is particularly good).
There is then a paper by Stipcevic and Koç on “True Random Number Generators.” The authors list a variety of open problems, mostly structural rather than mathematical, but also, in a manner similar to Koblitz and Menezes, cast doubt upon the correctness, in the general sense, of a significant amount of past literature. Their section on “Random Numbers in Deterministic Cryptography” should also be required reading.
There is then a paper “How to Sign Paper Contracts: Conjectures and Evidence Related to Equitable and Efficient Collaborative Task Scheduling,” by Brier, Naccache, and Xia. Despite the words “Sign” and “Contract” in the title, this isn’t about cryptography, but rather, as the subtitle suggests, about task scheduling protocols. How do all N parties to a contract each end up with a contract signed by (himself and) all the others? The simplest protocol is that the originator prints and signs N copies, circulates them (in one envelope) to the next and so on, and the last signatory returns N−1 copies to the others (in N−1 envelopes). This takes one more step than minimal, and costs 2N−2 envelopes (the minimum), but the cost is not equitably distributed. Alternatively, each party prints a copy, signs it, circulates it clockwise, and repeats. This takes N−1 steps (the minimum), but costs N(N−1) envelopes, albeit equitably distributed. The authors have done much computation and produce interesting conjectures on possible protocols.
Two further papers, “Theoretical Parallel Computing Models for GPU Computing,” by Nakano, and “Membrane Computing: Basics and Frontiers,” by Paun, are interesting, but seem rather off-topic compared with the rest of the collection.
The last paper is “A Panorama of Post-Quantum Cryptography,” by Barreto and many co-authors. It is worth recalling what this means: cryptography that does not rely on a quantum device (but may therefore have problems with randomness: see that paper), but that is proof against an opponent who does (and can therefore factor numbers and compute discrete logarithms). This looks at a variety of schemes, and I was pleased to be reminded that Merkle’s scheme [1] is really a post-quantum scheme. The whole “post-quantum” area is very fast moving, and this excellent paper is inevitably outdated. In the negative sense, this is caused by the recent break [2] of the, hitherto very promising, GGH multilinear map. On the positive side, the paper comments (p. 431) that “homomorphic encryption remains not practical.” I would have agreed with this comment had he not encountered [3], where a calculation, that would probably have taken minutes had it been performed, but involved joining databases that could not legally be joined, was performed in 2.5 days. Certainly much more expensive, but legally feasible.
In sum, this is a worthwhile collection, especially for young researchers.