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
- What are the new primitives needed, both in terms of security and in terms of design constraints?
- How do we ensure their security?
- How do higher level protocols use them?
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.
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: https://eurocrypt.iacr.org/2023/travel.php
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
- 14:00 – 15:00 Joint Session with SSR
- Presentation by Luis Brandao
- Open discussion with the room on related topics (see SSR website)
- 15:00 – 15:30 coffe break
- 15:30 – 16:30 Marc Beunardeau: Plonk Like Arithmetisation [slides]
- 16:30 – 17:30 Dimitry Khovratovich: Lookup arguments and design of hash functions
3.2 Sunday 23rd of April
3.2.1 Morning: Use Cases
- 9:00 – 10:00 Eli Ben-Sasson A wish list of constraints for STARK-friendly crypto primitives [slides]
- 10:00 – 10:15 coffee break
- 10:15 – 11:05 François-Xavier Standaert Mid-Size Primes for Symmetric Cryptography with Strong Embedded Security [slides]
- 11:05 – 12:00 Pascal Paillier cancelled
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
- Title
- Algebraic cryptanalysis: how Gröbner bases techniques can be used in cryptanalysis
- Slides
- [link]
- Abstract
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
- Title
- Plonk Like Arithmetisation
- Slides
- [slides]
- Abstract
- 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
- Title
- Tackling advanced cryptography … toward standards?
- Abstract
- see SSR website
4.4 Dmitry Khovratovich
- Title
- Lookup arguments and design of hash functions
- Abstract
- 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
- Title
- Permutations of finite fields
- Abstract
- 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
- Title
- Transciphering with TFHE: a challenge for symmetric designers.
- Abstract
- 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
- Title
- On the history of MPCFHEZK-friendly symmetric crypto
- Slides
- [link]
- Abstract
- 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
- Title
- A wish list of constraints for STARK-friendly crypto primitives
- Slides
- [link]
4.9 François-Xavier Standaert
- Title
- Mid-Size Primes for Symmetric Cryptography with Strong Embedded Security
- Slides
- [link]
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).