First day of CRYPTO. Nothing happened… Just kidding. Actually, the first day was quite busy and eventful. It was headlined by the session on lattices and fully-homomorphic encryption. The one talk that I’d like to highlight was delivered by Craig Gentry (and co-authored by Amit Sahai and Brent Waters). It describes a particularly elegant and succinct scheme for fully-homomorphic encryption (FHE) based on the approximate eigenvector method whose underlying assumption is hardness of learning with errors problem. The previous record for conceptually simple FHE was held by Zvika Brakerski, covered on this blog in two posts, and the new scheme builds in large part upon Zvika’s work. Actually, in an opening quite unusual for an academic paper, it starts with a quote from one of these posts!
In the new scheme, to add and multiply encrypted plaintexts, one simply adds and multiplies the corresponding ciphertexts, followed by a simple post-processing step that requires no additional key – almost a dream FHE construction. Although conceptual clarity comes at a cost – the scheme is not very fast or space-efficient – it has excellent explanatory value, in addition to constructing the first new identity-based FHE scheme.
The first invited talk of this conference was given by Cindy Cohn, the legal director and the general counsel of EFF. The offer was apparently extended before Snowden’s leaks hit the Internets but the decision to invite an EFF speaker could not have been more appropriate even with the benefit of hindsight. Cindy Cohn reviewed the legal landscape of electronic surveillance and wiretapping in the US, and then proceeded to point out multiple ways in which the actual practice of Internet-wide data collection, according to the leaked documents, contradicted either the spirit or the letter of the law. She affirmed the active stance EFF is taking on these issues, and concluded with a call for a political solution, similar to the Church Committee created in response to abuses of the Nixon administration. She even named her preferred candidate to lead the commission – Senator Ron Wyden, D-OR. Although the talk mostly avoided fear-mongering and sensationalism, much of it was based on some educated interpretation of the leaked PowerPoint slides – not the most reliable of sources. (If there’s anything that truly shocked me about Snowden’s allegations it was the dismal design of the NSA slides. In comparison, the fatal slide deck that could have prevented – but hadn’t – the Columbia disaster, looked quite tame and readable.)
Windows On Theory 