22 November 2021 - Léo Perrin Speaker Léo Perrin Title Designing hash functions in GF(q) is (much) harder than it looks Abstract Symmetric primitives such as hash functions are usually designed so as to map bitstrings of arbitrary length to bitstrings of fixed length (typically, 256 bits). This scope statement makes sense: first, the objects they are intended to operate on are essentially bitstreams (e.g. computer files or web communications), and their inner operations are intended to be run on CPUs or dedicated hardware that provides operations on 8- to 64-bit words. For example, the widely used hash function SHA-2 is built using operations of Z / 2^32 Z and bitwise logical gates applied on 32-bit words. However, this paradigm is reaching its limit in new domains such as MPC, zero-knowledge proofs, and other advanced protocols. In these contexts, the objects dealt with are tuples of finite field elements, and the operations that are available correspond to finite field arithmetic. Furthermore, for implementation reasons, these finite fields are usually of a large size (typically, GF(q) where q=2^n or q is an n-bit prime, and where n > 63). Such algorithms have been nicknamed "arithmetization-oriented". At first glance, this change in the underlying structure of the symmetric primitives might seem easily manageable. After all, current bit-oriented primitives are already designed using word-based operations. However, in this talk, I will show that it is unfortunately not as simple by presenting some attacks that target recent arithmetization-oriented hash functions such as gMiMC or Poseidon. Some of the attacks I will present come from a joint work with Tim Beyne, Anne Canteaut, Itai Dinur, Maria Eichlseder, Gregor Leander, Gaëtan Leurent, María Naya-Plasencia, Yu Sasaki, Yosuke Todo, and Friedrich Wiemer that was published at CRYPTO in 2020. Bio Léo Perrin is a researcher ("chargé de recherche") in the COSMIQ team at Inria, in Paris. He obtained master's degrees both from Centrale Lyon (France) and KTH (Sweden), as well as a PhD in computer science from the University of Luxembourg (Luxembourg). His research deals with symmetric cryptography (both design and cryptanalysis), discrete mathematics (in particular boolean functions), and the standardization of cryptographic algorithms. More information can be found on his webpage - https://who.paris.inria.fr/Leo.Perrin/ Nov 22 2021 11.30 - 12.30 22 November 2021 - Léo Perrin Security, Privacy & Trust Seminar by Léo Perrin Join Zoom Meeting https://ed-ac-uk.zoom.us/j/85893451329 Meeting ID: 858 9345 1329 Passcode: D92pTgTP
22 November 2021 - Léo Perrin Speaker Léo Perrin Title Designing hash functions in GF(q) is (much) harder than it looks Abstract Symmetric primitives such as hash functions are usually designed so as to map bitstrings of arbitrary length to bitstrings of fixed length (typically, 256 bits). This scope statement makes sense: first, the objects they are intended to operate on are essentially bitstreams (e.g. computer files or web communications), and their inner operations are intended to be run on CPUs or dedicated hardware that provides operations on 8- to 64-bit words. For example, the widely used hash function SHA-2 is built using operations of Z / 2^32 Z and bitwise logical gates applied on 32-bit words. However, this paradigm is reaching its limit in new domains such as MPC, zero-knowledge proofs, and other advanced protocols. In these contexts, the objects dealt with are tuples of finite field elements, and the operations that are available correspond to finite field arithmetic. Furthermore, for implementation reasons, these finite fields are usually of a large size (typically, GF(q) where q=2^n or q is an n-bit prime, and where n > 63). Such algorithms have been nicknamed "arithmetization-oriented". At first glance, this change in the underlying structure of the symmetric primitives might seem easily manageable. After all, current bit-oriented primitives are already designed using word-based operations. However, in this talk, I will show that it is unfortunately not as simple by presenting some attacks that target recent arithmetization-oriented hash functions such as gMiMC or Poseidon. Some of the attacks I will present come from a joint work with Tim Beyne, Anne Canteaut, Itai Dinur, Maria Eichlseder, Gregor Leander, Gaëtan Leurent, María Naya-Plasencia, Yu Sasaki, Yosuke Todo, and Friedrich Wiemer that was published at CRYPTO in 2020. Bio Léo Perrin is a researcher ("chargé de recherche") in the COSMIQ team at Inria, in Paris. He obtained master's degrees both from Centrale Lyon (France) and KTH (Sweden), as well as a PhD in computer science from the University of Luxembourg (Luxembourg). His research deals with symmetric cryptography (both design and cryptanalysis), discrete mathematics (in particular boolean functions), and the standardization of cryptographic algorithms. More information can be found on his webpage - https://who.paris.inria.fr/Leo.Perrin/ Nov 22 2021 11.30 - 12.30 22 November 2021 - Léo Perrin Security, Privacy & Trust Seminar by Léo Perrin Join Zoom Meeting https://ed-ac-uk.zoom.us/j/85893451329 Meeting ID: 858 9345 1329 Passcode: D92pTgTP
Nov 22 2021 11.30 - 12.30 22 November 2021 - Léo Perrin Security, Privacy & Trust Seminar by Léo Perrin
