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).

Metadata
Available format(s)
PDF
Publication info
Published elsewhere. Presented at the IEEE Information Theory Workshop 2012 (ITW), Lausanne, Switzerland, September 2012 (invited talk by Cramer). An earlier version was presented as part of Cramer's invited talk at the 30th Annual IACR EUROCRYPT, May 2011, Tallinn, Estonia.
Contact author(s)
cramer @ cwi nl
History
2012-11-13: last of 3 revisions
2012-07-16: received
See all versions
Short URL
https://ia.cr/2012/388
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2012/388,
      author = {Ignacio Cascudo and Ronald Cramer and Chaoping Xing},
      title = {The Arithmetic Codex},
      howpublished = {Cryptology ePrint Archive, Paper 2012/388},
      year = {2012},
      note = {\url{https://eprint.iacr.org/2012/388}},
      url = {https://eprint.iacr.org/2012/388}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.