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:
- RO is much more efficient than NR-PRF.
- By using RO, we loose the homomorphism of NR-PRF. As a result, we can only achieve the “ListOT” correlation, rather than standard OT.
ListOT means that the sender can get two lists \(L_0, L_1\) while the receiver gets an index \(b\), a “list index” \(v\), and a value \(y\). The values should satisfy the following requirements.
- Correctness: Viewing \(L_0, L_1\) as Python
dict’s, it should hold that \(y = L_b[v]\). - Sender Security: The missing values in \(L_0, L_1\) should appear pseudorandom to the receiver.
- Receiver Security: The index \(b\) should be pseudorandom to the sender (notice that the \(v\) value is not pseudorandom.)
By running benchmark on the extension phase (without setup), the authors claim that their protocol achieves better throughput than SoftSpokenOT at the same communication level. Compared with previous PCF designs, the new protocol shows advantage in every metric. Compared with the state of the art LPN-based PCG (Raghuraman, Rindal, and Tanguy 2023), their protocol still falls behind in terms of performance.
One very nice feature of their protocol and public-key PCF in general, is that they support the PKI-style setup. This means that the parties only need to interact in one round to exchange the public keys of each other. Then they can generate the correlations by only local computation. This is the minimal communication possible to generate multiparty correlations and is highly desirable in practice.