15th - 17th December 2009  Royal Agricultural College, Cirencester, UK

Invited Speaker: Ronald Cramer

Title: Torsion-Limits for Towers of Algebraic Function Fields and Special Codes in Secure Computation and Complexity.

Abstract: 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 (CRYPTO 2006; Chen/Cramer, CRYPTO 2009; Cascudo/Chen/Cramer/Xing), it has been discovered that towers also have an important bearing on secure multi-party computation. These results have meanwhile found surprising applications in 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) where we introduce a novel tower paradigm for special codes in secure computation and complexity, and significantly improve all previously known bounds for such codes.