Low-Complexity Cryptography

Lisa Kohl (CWI) & Nicolas Resch (UvA)

Benny Applebaum (Tel-Aviv University)

Abstract: A pseudorandom generator (PRG) is locally computable if each output bit depends on only a small subset of input bits; such generators have found numerous applications in recent years. This survey provides an overview of the landscape of locally-computable PRGs, including search-to-decision reductions, direct and indirect constructions, security against restricted classes of algorithms, and known attacks. I will also discuss several connections between this problem and other questions in complexity theory, and highlight some open problems.

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.

Marshall Ball (NYU Courant)

Abstract: TBD

Simona Samardjiska (Radboud University)

Abstract: TBD

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).

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.