Nombre: Ronald Cramer (CWI Amsterdam & Mathematical Institute, Leiden University)

Título: Special Codes in Secure Computation and Complexity and Their Connection to Algebraic Geometry

Resumen: Towers of algebraic functions fields over finite fields have played a major role in the theory of error correcting codes since Tsfasman and Vladuts broke the classical coding benchmark, the Gilbert-Varshamov bound in the early 1980s.

Recently (Chen/Cramer -- CRYPTO 2006, Cascudo/Chen/Cramer/Xing -- CRYPTO 2009), it has been discovered that towers also have an important bearing on secure multi-party computation, in particular to asymptotically good strongly multiplicative secret sharing schemes. These results have meanwhile found surprising applications in foundational work by Ishai/Kushilevitz/Ostrovsky/Sahai (e.g., STOC 2007, FOCS 2009) on two-party cryptography. In this talk I will elaborate on these connections.

I will also announce recent work (Cascudo/Cramer/Xing, 2009/2010) where we introduce a novel tower paradigm for several classes of special codes in secure computation and complexity, and significantly improve all previously known bounds and results for these classes of codes.