Low-Complexity Cryptography

Lisa Kohl (CWI) & Nicolas Resch (UvA)

Yuval Ishai (Technion and AWS)

Abstract: How efficient can secure computation be? I will discuss the goal of minimizing the cost of secure computation under different optimization metrics, and how this goal motivates other questions about low-complexity cryptography that are of independent interest.

Youlong Ding (Hebrew University)

Abstract: Pseudorandom functions (PRFs) are a fundamental primitive in cryptography, with numerous applications across symmetric cryptography, secure computation, and complexity theory. This talk focuses on how to construct PRFs from assumptions related to the hardness of decoding noisy linear codes. In particular, we will see how to obtain log-depth PRFs from (variants of) the Learning Parity with Noise (LPN) assumption. We will also relate the resulting constructions to the framework of substitution-permutation networks (SPNs), a design paradigm dating back to Shannon. The talk is based on joint work with Aayush Jain and Ilan Komargodski.

Kel Zin Tan (NUS Singapore)

Abstract: A random local function defined by a d-ary predicate is one where each output bit is computed by applying to randomly chosen bits of its input. They were put forward by Goldreich as candidates for low-complexity one-way functions, and have subsequently been widely studied also as potential pseudo-random generators. Viewing one-wayness as search and pseudorandomness as decision, it is natural to ask: Does the search hardness imply the decision hardness? In this talk, I will discuss the core ideas from both past and recent works on obtaining search-to-decision for random local functions.

Simona Samardjiska (Radboud University)

Abstract: In recent years, driven by standardization processes for post-quantum cryptography, we have witnessed an enormous improvement in the understanding and development of solid and secure design principles for digital signatures. An interesting class are Fiat-Shamir signatures based on hard equivalence problems that obtained from the well known GMW Σ-protocol by Goldreich, Micali and Wigderson. On a high level, such a problem can be defined as follows: Given two algebraic objects, find – if any – an equivalence that maps one object into the other. Instantiations of these problems are Isomorphism of polynomials, Tensor Isomorphism or Code equivalence over various metrics.

In this talk I will discuss a general approach for reducing the signature size of GMW based signatures intrinsically connected to the equivalence relation used in these signatures. It turns out that using only a small partial information on the equivalence we can prove knowledge of the entire equivalence. The approach can generically be used to drastically reduce signature sizes of these types of digital signatures.

Lorenzo Grassi (Eindhoven University of Technology)

Abstract: Modern cryptography has developed many techniques that go well beyond solving traditional confidentiality and authenticity problems in two-party communication. In order to work, such protocols may rely on the evaluation of symmetric cryptographic primitives, such as pseudorandom functions (PRFs), symmetric encryption schemes, or hash functions, whose details have a big impact on the performances of the considered applications. For this reason, several dedicated MPC-/ZK-/HE-friendly symmetric primitives (defined especially over prime fields) have recently appeared in the literature.In this presentation, I first highlight the design principles of the symmetric primitives that target MPC-/HE-/ZK-applications, comparing them with the ones commonly used for „traditional/classical“ symmetric schemes such as AES or Keccak/SHA-3. Next, for each one of the cited applications, I will present some concrete examples of symmetric primitives published in the literature, including  the MPC-friendly block ciphers MiMC (ASIACRYPT 2016) and HadesMiMC (EUROCRYPT 2020), the ZK-friendly hash functions Rescue (FSE/ToSC 2020) and Poseidon (USENIX 2021), and the FHE-friendly stream cipher Rasta (CRYPTO 2018).