Abstracts

• Yilei Chen

Fiat-Shamir: from practice to theory

The Fiat-Shamir transform is a general method for reducing interaction in public-coin protocols by replacing the random verifier messages with deterministic hashes of the protocol transcript. The soundness of this transformation is usually heuristic and lacks a formal security proof. Instead, to argue security, one can rely on the random oracle methodology, which informally states that whenever a random oracle soundly instantiates Fiat-Shamir, a hash function that is ``sufficiently unstructured'' (such as fixed-length SHA-2) should suffice. Recently, progress has been made in analyzing the soundness of Fiat-Shamir transform via concrete, falsifiable properties of cryptographic hash functions. In this talk I will survey the recent results on Fiat-Shamir and mention future directions.

• Dooho Choi
  Quantum Algorithms and Quantum Circuits for Cryptography

Since Peter Shor discovered the order finding quantum algorithm in 1994,

large-scale quantum computer poses the most destructive risk to the modern public-key cryptography. In this presentation, the basic quantum computation and quantum algorithms which are related in the quantum analysis of the cryptography are introduced. And it is addressed the concept of the quantum security evaluation for the cryptography. Finally, the efficient quantum arithmetic circuit for AES implementation in the quantum computer.

• Sanjam Garg
  The Tale of Two-Round MPC

A decade ago, we did not know if multiparty secure computation (MPC) could be realized in two rounds. Providing the first progress on this problem, in 2014 the first construction of a two-round MPC protocol based on indistinguishability obfuscation was obtained. Subsequently, a sequence of works reduced the assumptions needed in these constructions to just two-round oblivious transfer; the minimal assumption necessary for the task. Additionally, several surprising extensions (e.g. two-round MPC with reusable first round message) from a broad range of assumptions have also been obtained. In this talk, I will survey this line of work.

Laconic Cryptography (and the special case of PSI)

Laconic cryptography is an emerging paradigm which enables realizing cryptographic tasks with asymptotically-optimal communication in just two messages. In this setting, the receiver has a potentially large input, and the size of her protocol message only depends on the security parameter, and not her input size. The second message, sent by the sender, may grow with the size of the sender’s input, but should be independent of the receiver’s input size. In this talk, I will survey the recent results in the space of laconic cryptography and talk about new results in the context of Laconic Private Set Intersection.

• Jon-Lark Kim
  Code-based cryptography with a recent approach

In this talk, we introduce basic facts on error-correcting codes and then move to the well known code-based cryptography such as McEliece cryptosystem and Niederreiter cryptosystem. We discuss Syndrome Decoding Problem and Information Set Decoding. We survey various code-based cryptosystems submitted to NIST Post-Quantum Cryptography. Finally we explain a recent approach to code-based cryptosystem.

• Gregor Leander
  Lower Bounds on Degrees and Arguments against Integral Attacks for Block Ciphers
  I will explain how the division property allows to get strong and tight security arguments against integral attacks for Block ciphers.

• Changmin Lee

An LLL algorithm for module lattices

The LLL algorithm takes as input a basis of a Euclidean lattice, and, within a polynomial number of operations, it outputs another basis of the same lattice but consisting of rather short vectors. In this lecture, we provide how to generalize the LLL algorithm to R-modules contained in K^n for arbitrary number fields K and dimension n, with R denoting the ring of integers of K.

• Thomas Prest

f-divergences in statistical security proofs

The statistical distance is an ubiquitous tool in cryptography to formalise statistical security arguments. However, it is also one specific instance of a much larger class of divergences called f-divergences. While f-divergences as a whole are routinely studied in probability theory, most works in cryptography only consider the statistical distance.

In the recent years, several works report improved security proofs when replacing the statistical distance with other divergences. In this talk, I will survey a few works (by myself or other authors) that follow this line of thought. I will focus mostly on the Rényi divergence since it is the most prevalent divergence in the works I discuss, however the main takeaway that I want to convey is simply that one should choose the right divergence for a given situation.

Post-quantum multi-recipient KEMs and their applications

A multi-recipient key encapsulation mechanism, or mKEM, provides a scalable solution to securely communicating to a large group, and offers savings in both bandwidth and computational cost compared to the trivial solution of communicating with each member individually. All prior works on mKEM are only limited to classical assumptions and, although some generic constructions are known, they all require specific properties that are not shared by most post-quantum schemes. In this work, we first provide a simple and efficient generic construction of mKEM that can be instantiated from versatile assumptions, including post-quantum ones. We then study these mKEM instantiations at a practical level using 4 post-quantum mKEMs (lattice- and isogeny-based Round 3 candidates to the NIST PQC process), and CSIDH, and show that compared to the trivial solution, our mKEM offers savings of at least one order of magnitude in the bandwidth, and make encryption time shorter by a factor ranging from 1.92 to 35. Additionally, we show that by combining mKEM with the TreeKEM protocol used by MLS − an IETF draft for secure group messaging − we obtain significant bandwidth savings. Finally, we focus on lattice-based mKEMs; we study the concrete security of mKEMs based on existing schemes (FrodoKEM, Kyber, etc.) and propose new parametrizations that are tailored to the mKEM setting.

• Hwajeong Seo

Post-quantum Cryptography in Practice

Due to the rapid development of quantum computers, traditional public key cryptography algorithms should be converted to post-quantum (quantum-safe) cryptography algorithms. Recently, NIST held post-quantum cryptography standardization and it has entered the third phase. NIST requested many requirements for candidates of post-quantum cryptography. Among them, efficient implementation is critical criteria to be adopted in real-world applications. In this talk, we introduce the-state-of-art implementation of post-quantum cryptography in modern computing environments.

• Fang Song

Quantum-secure key-length extension

To be announced soon

• Yongsoo Song

On Multi-key Homomorphic Encryption

To be announced soon

• Frederik Vercauteren

Fun at the CSIDH

CSIDH is an example of a possibly post-quantum secure cryptosystem and is based on computing isogenies between supersingular elliptic curves. In this talk, I will present an overview of the CSIDH cryptosystem, including recent results on cryptanalysis and more constructive aspects, i.e. examples of cryptographic protocols built on top of CSIDH.

• Keita Xagawa

Security of NIST PQC KEM Candidates — Theory and Practice of the FO-like Transformations

All NIST PQC Round-3 KEM Candidates use the variants of the Fujisaki-Okamoto (FO) transformation that converts a weakly secure PKE scheme into a strongly secure KEM/PKE scheme in the (quantum) random oracle model ((Q)ROM).

On the theory side, I will give a survey of the FO-like transformations and their security proofs in the QROM. On the practice side, I will also explain some tricks for efficiency and generic fault-injection attacks against KEM candidates.