Paper 2012/388

The Arithmetic Codex

Ignacio Cascudo, Ronald Cramer, and Chaoping Xing

Abstract

We introduce the notion of {\em arithmetic codex}, or {\em codex} for short. It encompasses several well-established notions from cryptography (arithmetic secret sharing schemes, i.e., enjoying additive as well as multiplicative properties) and algebraic complexity theory (bilinear complexity of multiplication) in a natural mathematical framework. Arithmetic secret sharing schemes have important applications to secure multiparty computation and even to {\em two}-party cryptography. Interestingly, several recent applications to two-party cryptography rely crucially on the existing results on ``{\em asymptotically good} families'' of suitable such schemes. Moreover, the construction of these schemes requires asymptotically good towers of function fields over finite fields: no elementary (probabilistic) constructions are known in these cases. Besides introducing the notion, we discuss some of the constructions, as well as some limitations.

Note: Change log: Not taking the property claimed in Lemma~1 (Version~3) as a condition in the codex definition as introduced in this eprint paper, was meant to further simplify our prior definitions. However, this Lemma~1 is incorrect~\cite{CCMPX12}. A similar mistake appears in the talk notes from the electronic proceedings as handed out at Proc.\ IEEE Symp.\ Inf.\ Theory, Sept.\ 2012 (see Remark~3 there). In this Version~4 we have corrected it by, once again, taking it as a condition in the definition. Note that the mistake does not appear in prior codex definitions (such as the one presented at Eurocrypt 2011).