Cosmiq Homepage | Léo Perrin's Homepage | ReSCALE

STAP'23: Symmetric Techniques for Advanced Protocols

Table of Contents

Algorithms from symmetric cryptography such as hash functions, and stream/block ciphers, have been at the heart of many higher level cryptographic protocols. However, in recent years, the specific design requirement of new advanced protocols has given raise to new needs that are improperly addressed by state-of-the-art algorithms: while safe, current algorithms like AES or SHA-3 are too inefficient in these contexts.

From arithmetization-oriented hash functions enabling a cheap zero-knowledge verification of their evaluation, to homomorphic encryption-friendly stream ciphers, new symmetric algorithms need to be designed and analyzed.

The aim of this workshop is to bring together the users of such primitives, their designers, and their analysts. It will be organized as a sequence of invited talks and tutorials revolving around such questions as

The invited speakers come from different communities: zero-knowledge, symmetric cryptography, mathematics… There will also be a rump-style session during which participants are invited to informally introduce their work on either designing new symmetric primitives, or their need for new ones.

Picture of Léo Perrin

Figure 1: STAP: Symmetric Techniques for Advanced Protocols!

STAP is an affiliated workshop of EUROCRYPT'23 that will take place on Saturday 22nd and Sunday 23rd of April 2023. Registration must be made through the Eurocrypt website here. More information is available here. If you have any question, you can reach me at leo . perrin @ inria . fr.

1 Mailing List

Let's the momentum of the conference going! I am setting up a mailing list to discuss all things STAPs, from new results to open problems. To sign up, simply click on this link and fill out the form. See you there!

2 Location

from the eurocrypt chairs

The affiliated events will be held at ENS Lyon on the sciences campus. The closest metro stations are Gerland and Debourg (both on line B). Be aware that there is another ENS Lyon campus next to the Debourg station (humanities): the affiliated events are located in the sciences campus.

Address: 46 allée d'Italie

More details:

3 Program

3.1 Saturday 22nd of April

3.1.1 Morning: Emerging Symmetric Ciphers

  • 10:00 – 10:30 Registration and coffee
  • 10:30 – 10:40 Opening remarks
  • 10:40 – 11:30 Christian Rechberger: On the history of MPCFHEZK-friendly symmetric crypto [slides]
  • 11:30 – 12:00 Lightning introductions: willing participants are invited to introduce themselves to the audience, and to quickly present topics of interest to them.

3.1.2 Lunch (12:00 – 14:00)

3.1.3 Afternoon: Practical Aspects

3.2 Sunday 23rd of April

3.2.1 Morning: Use Cases

3.2.2 Lunch (12:00 – 14:00)

3.2.3 Afternoon: Fundamental Aspects

  • 14:00 – 14:55 Gohar Kyureghyan: Permutations of finite fields
  • 14:55 – 15:45 Magali Bardet: Algebraic cryptanalysis: how Gröbner bases techniques can be used in cryptanalysis [slides]
  • 15:45 – 16:00 Closing Remarks

4 Details of the Talks

Work in progress

4.1 Magali Bardet

Algebraic cryptanalysis: how Gröbner bases techniques can be used in cryptanalysis

Gröbner basis is a powerfull tool to solve algebraic systems. It is well known that solving algebraic systems is hard, and that Gröbner basis have a doubly exponential complexity in the worst case. However, in most cases the cost is simply exponential, and can even be polynomial for particular systems.

In this talk I will present Gröbner basis tools in general, its potential use in cryptanalysis through various examples and how its complexity can be estimated.

4.2 Marc Beunardeau

Plonk Like Arithmetisation
In this tutorial we will review what the arithmetisation step is and what role it plays in a zero-knowledge proving system. We will then focus on the Plonk proving system and it variants, by giving an intuition on how it works and showing how to exploit some of its properties to efficiently implement some functions.

4.3 Luis Brandao

Tackling advanced cryptography … toward standards?
see SSR website

4.4 Dmitry Khovratovich

Lookup arguments and design of hash functions
Recent advances in zero knowledge proof systems cover lookup arguments: proofs that part of the computation trace is a subset of some big table. In this talk we explain how these arguments are constructed and what their cost is – and how they can be used to improve ZK SNARKs for conventional hash functions such as SHA-2/3 and, moreover, how new hash functions can be constructed which are fast both in native and ZK execution. We also explain how to design and ZK-represent compact S-boxes when working in a big field.

4.5 Gohar Kyureghyan

Permutations of finite fields
In this talk we describe different representations of permutations of finite fields and discuss advantages for using a particular one. Further, we present several constructions of large families of permutations and outline how they can be modified to fulfill properties required in some of cryptological applications.

4.6 Pascal Paillier

Transciphering with TFHE: a challenge for symmetric designers.
This talk focuses on the essential features of Torus FHE (TFHE) one has to know in order to design a good symmetric cipher for homomorphic transciphering. I will be covering the various operations that TFHE supports natively and how to find good trade-offs between memory and efficiency in their parametrization. This can serve as a toolbox for scheme designers in their quest for the perfect primitive.

4.7 Christian Rechberger

On the history of MPCFHEZK-friendly symmetric crypto
In the last decade, concretely efficient new designs in symmetric cryptography that are friendly for zero-knowledge proofs (ZK), secure multiparty computation (MPC), or (fully) homomorphic encryption (FHE) environments have been appearing at an increasingly fast pace. In the talk we review and classify this space, and as ourselves: How did we get here? And where do we go from here?

4.8 Eli Ben-Sasson

A wish list of constraints for STARK-friendly crypto primitives

4.9 François-Xavier Standaert

Mid-Size Primes for Symmetric Cryptography with Strong Embedded Security

5 Acknowledgements

The logo of the workshop was made by Clémence Bouvier.

5.1 Funding

This workshop receives funding from the ERC StG ReSCALE (grant agreement 101041545).

Last Update (by me): 04/05/2023