The construction of special kinds of codes, which require certain combinatorial properties regarding the componentwise products of the words in the code and in particular, the existence of asymptotically good constructions of these codes, have found many recent applications in information-theoretical cryptography such as multiparty computation (starting with the work by Cramer, Damgaard and Maurer, EUROCRYPT 2000), zero knowledge (Ishai, Kushilevitz, Ostrovsky and Sahai, STOC 2007) and leakage resilient cryptography (in the work on correlation extractors by Ishai, Kushilevitz, Ostrovsky and Sahai, FOCS 2009). All these works use (slightly different flavors of) secret sharing schemes with algebraic properties, which we call arithmetic secret sharing schemes.
In this talk, which is a continuation of Ronald Cramer's, we survey the latest works on asymptotically good arithmetic secret sharing, topic started by Chen and Cramer in CRYPTO 2006. We show how to construct these asymptotically good families of arithmetic secret sharing schemes based on the theory of algebraic function fields. More precisely, we will introduce a new limit that, for a tower of function fields with a given Ihara limit and a positive integer r, gives information on the cardinality of the asymptotic size of the r-torsion sub-groups of the associated degree-zero divisor class groups. We will show how towers with small torsion limits give rise to families of linear codes with special combinatorial properties, which yield new asymptotic results in arithmetic secret sharing and consequently in the cryptographic applications above, as well as in the seemingly unrelated topic of the bilinear complexity of multiplication in finite extensions of a given finite field. This is joint work with Ronald Cramer (CWI Amsterdam) and Chaoping Xing (NTU Singapore).
Copyright. All Rights Reserved.