Reinventing Symmetric Cryptography for Arithmetization over Large fiElds

Symmetric cryptography is finding new uses because of the emergence of novel and more complex (e.g. distributed) computing environments.These are based on sophisticated zero-knowledge and Multi-Party Computation (MPC) protocols, and they 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 would make it possible e.g. for e-governance algorithms to prove that they are run honestly; and overall would increase the trust we can have in various automated processes.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}.

But encoding GF(2) operations using GF(q) operations is very costly: relying on standard hash functions leads to significant performance overhead, to the point were the protocols mentioned before are unusable in practice.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: 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).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.