Sunday, May 19, 2013
School on Information-Theoretic Cryptography
Last week the school on Mathematics of Information-Theoretic Cryptography was held at the Lorentz Center in Leiden, Netherlands. It was intended as a warm up for the workshop following next week at the same center, and that aims to bring together people working in the field, and present latest results on a variety of i-t topics.
I quite enjoyed the school and found it very rewarding, as most of the lectures took special interest in giving careful presentations, on blackboard, with no hesitation on going into the details of what was being discussed. People in the audience feeling akin to take notes were able to do it without loosing track of what the lecturer was saying.
The school was opened by Jesper Buus Nielsen on Monday. He gave an intuitive presentation on Secure Multiparty Computation (MPC). He discussed aspects of passive security, the UC model, and the efficiency of MPC. Things like Shamir Secret Sharing, security of protocols via simulators and environments, dispute control technique, randomness extraction with Vandermonde matrices, SIMD operations and its relation to Benes networks, and more was dissected.
Tuesday and Wednesday were dedicated to a more in-deep range of mathematical topics. Peter Beelen gave a comprehensive introduction of function fields, which constitutes one of the building blocks of algebraic geometric secret sharing. Besides it can be hard to understand for someone with a no-so-wide knowledge in Algebra, he basically started from the scratch, giving examples and intuitions on why concepts are developed in a particular way. He also settled practice exercises that were later resolved on the board. He discussed objects like valuation rings, places, formal expressions known as differentials, the Riemann-Roch theorem, Ihara's constant, and recursively constructions of tower of function fields. I think it was a meticulous introduction, and surely papers dealing with AG secret sharing are much more understandable for anyone who attended this lecture. Chaoping Xing discussed aspects of Algebraic Curves. He was mainly concerned with three applications; algebraic geometric codes (comparison and improvements on bounds of the asymptotic behaviour, and generalization of
Reed-Solomon codes), field multiplication on extension fields (alternative to convolution product in polynomial rings, defined via two maps and the Schur product, and its connection to function fields), and lastly, perhaps a somewhat less crypto-related application, the Quasi-Monte Methods.
Carles Padro gave explicit definitions of secret sharing schemes seen as random variables, realizations of SS for general access structures, and the relation to matroids and polymatroids. Also discussed on lower and upper bounds of the Information Rate. Thursday was devoted to arithmetic SS, and was driven by Ronald Cramer and Ignacio Cascudo. They explained the Codex Framework, which tries to embody together SS schemes that are multiplicative. Many of the aspects discussed the previous days crystalized in this framework. As an aside, Ronald also informally explained the research development on the topic in, roughly, the last twenty years.
The last day, Friday, Yuval Ishai also talked about MPC and Zero-Knowledge Proofs. He noted that historically i-t cryptography and honest majority MPC have made use of 2PC and ZKP, whereas the other direction seems less explored. He gave high level description on several topics regarding this connection, the one I enjoyed the most was the description of the "MPC in the Head" technique.
All the material is available at the school website.