Reinventing Symmetric Cryptography for Arithmetization over Large fiElds

Introduction

Symmetric cryptography is finding new uses because of the emergence of novel and more complex (e.g. distributed) computing environments.

Advanced Protocols

These environments are based on sophisticated zero-knowledge and Multi-Party Computation (MPC) protocols, which aim to provide strong security guarantees of types that were unthinkable before. In particular, they make it theoretically possible to prove that a computation was done as claimed by those performing it without revealing its inputs or outputs.

This capability would make it possible, for example, for e-governance algorithms to prove that they are run honestly, and overall would increase the trust we can have in various automated processes.

Security Techniques

The security techniques providing these guarantees are sequences of operations in a large finite field GF(q), where typically q > 2^64. However, these procedures also rely on hash functions and other "symmetric" cryptographic algorithms that are defined over GF(2) = {0,1}.

Encoding GF(2) operations using GF(q) operations is very costly: relying on standard hash functions leads to significant performance overhead, to the point where the protocols mentioned before are unusable in practice.

Addressing the Bottleneck

In order to alleviate this bottleneck, it is necessary to devise symmetric algorithms that are natively described in GF(q). This change requires great care, as some hash functions described in GF(q) have already been presented and subsequently exhibited significant flaws.

The inherent structural differences between GF(2) and GF(q) are the cause behind these problems: our understanding of the construction of symmetric primitives in GF(2) does not carry over to GF(q).

Project Goals

With this project, I will bring symmetric cryptography into GF(q) in a safe and efficient way. To this end, I will rebuild the analysis tools and methods that are used both by designers and attackers.

This project will naturally lead to the design of new algorithms whose adoption will be simplified by the efficient and easy-to-use software libraries we will provide.