Talks

Here are my Slides. The design of PCF follows two paradigms in general. The “DPF+LPN” approach, where one uses binary-tree-based DPF as FSS for point functions for comparison functions to generate correlations on sparse vectors (e.g. sparse COT, sparse VOLE), and then compress the correlation with an appropriate Learning Parity with Noise (LPN) assumption. Notice that we want to achieve super-polynomial “stretch” so that the LPN assumption must support a “fast” evaluation algorithm. Existing works uses Expand-Accumulate LPN (Boyle et al. 2022) assumption or the Variable-Density LPN assumption (Couteau and Ducros 2023; Boyle et al. 2020). Another line of work focuses on working with more expressive HSS/FSS and propose to use public key operation to generate each correlation. Notice that the LPN assumption only requires matrix-vector multiplication operation and is generally considered to be much “lighter” than public-key operations (e.g., exponentiation modulo an RSA modulus or lattice operations with superpolynomial modulus to noise ratio). The advantage of this line of work is that the constructions are very simple and elegant. One work by Orlandi et al. uses Pailliar to construct PCF for OT (Orlandi, Scholl, and Yakoubov 2021) while a recent work by Bui et al. uses Naor-Reingold PRF to achieve the same goal (Bui et al. 2024). One interesting observation is that the “public-key PCF” constructions can generate OT correlations directly, while constructions in the previous genre usually generate Correlated OT first. In Asiacrypt 2024, a new paradigm is proposed, trying to achieve a middle ground between the two genres (Couteau et al. 2024). The work builds on the framework of (Bui et al. 2024) but replaces the Naor-Reingold constrained PRF with a much simpler RO design. This brings the following changes: ...

This is a project that runs in the Lattice lab, starting from Hanlin Liu, who first envisioned the possibility of substituting LWE-based cryptography with LPN (spoiler alert we currently do not know how to achieve this goal). A significant goal is to construct a digital signature a la Dilithium at least in terms of performance. Alas, the Fiat-Shamir with Abort technique does not work directly with LPN, although some folks have come up with variants of the LPN assumption to accommendate with this technqiue (e.g. (“Durandal: A Rank Metric Based Signature Scheme SpringerLink” n.d.)). We consider the status quo unsatisfactory. ...

This is a Crypto 2022 paper that describes how to construct authenticated garbled circuit using correlations that allow efficient PCGS (e.g., MT, VOLE). Using the AGC, we can run actively secure 2PC afterwards. This work inspired us to conduct a follow-up work Authenticated Garbling From Correlated OT. Here is the slides I have prepared Slides.

Since random vector commitment is used extensively in MPCitH and VOLEitH applications, with some of them being post quantum signatures, which is efficiency sensitive (e.g. TLS needs fast authentications for smooth browsing experience), it’s a natural question to optimize this component. One possible way to do this is to replace the cryptograhpic hash function invocation at the bottom layer of the GGM tree with AES-based hash functions which are relatively lightweight when the key is fixed. ...

This is a Crypto 2019 paper by Boneh et al. In this paper the authors utilize the fact that the verifier can only make linear queries to the instance string and the PCP/IOP proof string in order to make a decision. Building on this property, we can design proof systems that allow proving statements that are shared among multiple verifiers. This proof system in particular appear useful for the GMW transformation, which is the topic of another talk. ...

My first talk is about memory-hard functions but they are kind of lost

Generating Boolean Beaver triples has always been an intriguing problem. On one hand, Overdrive-type FHE-based solutions offers asympototically-good solutions, and for suitable field size the concrete efficiency is also considered state-of-the-art. On the other hand, the current best practice for generating authenticated Boolean Beaver triples remains MASCOT-type COT-based protocols, which has communication of \(O(N^2 m)\) for generating \(m\) triples among \(N\) parties. I guess this is a follow-up of Ring-LPN PCG. ...

This is a Eurocrypt 2023 submission that describes the application of EA-LPN in constructing PCF for garbled circuit correlations. They also present three applications of their construction, albeit not very convincing in their practical values. I gave a talk about this paper and also discussed the merit of it at <2024-02-27 二>. Here is the ipe source.

The \( n^2 \) computational overhead of PCGs for the OLE/MT correlation has long been a trouble and only recently have we come up with some creative solution (for authenticated triples over \( \mathbb{F}_2 \)). This is a Crypto 2020 paper that shows how to create such a correlation over \( \mathbb{F}_{2^{\rho}} \) using Ring-LPN. I recall giving talks about this construction in various occacions but the details have been lost now. <2024-02-28 三> ...

This is a follow-up work of Fully Linear PCP. LATTICE group meeting at <2021-10-27 三> Slides Meeting with Huawei at <2021-11-18 四> Slides