12 - Arithmetic Codices

Summary

Introduction

We introduce the notion of an arithmetic codex [43, 57], or codex for short, and develop its basic theory. Codices encompass several well-established notions from cryptography (various types of arithmetic secret-sharing schemes, which all enjoy additive as well as multiplicative properties) and from algebraic complexity (bilinear complexity of multiplication in algebras) in a single mathematical framework. Arithmetic secret-sharing schemes have important applications to secure multiparty computation (MPC) and even to two-party cryptography. One such application, known as “MPC-in-the-head,” can be found in Chapter 8.

Interestingly, several recent applications to two-party cryptography (including the one we present in this book) rely crucially on the existence of certain asymptotically good schemes. It is intriguing that their construction requires asymptotically good towers of algebraic function fields over a finite field: no elementary (probabilistic) constructions are known in these cases. Besides introducing the notion, we discuss some of the constructions, as well as some limitations.

Throughout this chapter, let K be a field, let p > 0 be a prime number, let v be a positive integer, and define q=p^v. Let F_q be a finite field with q elements.

The Codex Definition

For our purposes, a K-algebra is a commutative ring such that K is a subring (see Section 10.8). By definition of a subring, the multiplicative unity of a K-algebra is precisely the multiplicative unity of K. It is henceforth denoted by 1. Recall that a K-algebra is in particular a K-vector space.

Powers of a Space

Taking powers of a subspace of a K-algebra R plays a fundamental role in the definition and study of codices. Suppose that C ⊂ R is a K-vector subspace of R, with R viewed as a K-vector space. In general, of course, the space C is not closed under multiplication. For example, take R = K[X], the polynomial ring over K, and let C be the subspace of polynomials of degree ≤ t for some positive integer t.

We define, for each positive integer d, the “closure” of C under “d-multiplication” as the subspace C^∗d ⊂ R generated by the elements of R that can be written as a product of d elements selected from C. Formally, we have the following:

DEFINITION 12.1 (SET OF d-PRODUCTS) Let R be a K-algebra. Let C ⊂ R be a K-vector subspace. Let d≥ 0 be an integer.