Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Lecture notes in computer science

Compressing Unit-Vector Correlations via Sparse Pseudorandom Generators

Amit Agarwal, Elette Boyle, Niv Gilboa, Yuval Ishai, Mahimna Kelkar, Yiping Ma

Published Jan 1, 2024• 7 citations
Publisher
DOI
10.1007/978-3-031-68397-8_11

Related papers

Efficient Pseudorandom Correlation Generators for Any Finite Field

Zhe Li, Chaoping Xing, Yizhou Yao +1 more

Lecture notes in computer science•Jan 1, 2025•18 citations

Efficient Pseudorandom Correlation Generators: Silent OT Extension and More

Elette Boyle, Geoffroy Couteau, Niv Gilboa +3 more

Lecture notes in computer science•Jan 1, 2019•270 citations

Efficient Pseudorandom Correlation Generators from Ring-LPN

Elette Boyle, Geoffroy Couteau, Niv Gilboa +3 more

Lecture notes in computer science•Jan 1, 2020•127 citations

On Compressing Linearly Shared Correlations

Geoffroy Couteau, Alexander Koch, Nikolas Melissaris +3 more

Lecture notes in computer science•Nov 5, 2026•0 citations

Compressing Correlations via Secret Replication: PCFs from Symmetric Cryptography

Yuval Ishai, Hugo Krawczyk, Tal Rabin

We revisit the question of securely compressing multiparty correlations using only symmetric cryptography. A linear correlation C, defined by a linear subspace C ⊆ 𝔽ⁿ, samples a secret random 𝐜 ∈ C and assigns to each party a fixed subset of the entries of 𝐜. Gilboa and Ishai (Crypto 1999) and Cramer, Damgård and Ishai (TCC 2005) provide a general technique for securely compressing many independent samples from C by replicating independent keys of a pseudorandom function (PRF) among the parties. This implies a pseudorandom correlation function (PCF) for C from any PRF, where the PCF key size scales with the number of minimal-support codewords in C. We observe that the above generalizes to other types of useful target correlations C_T by using a secret replication pattern obtained via a random secret assignment of parties in C to parties in C_T. We present several corollaries of this general blueprint. These include a re-derivation of two-party PCF constructions for VOLE and subfield-VOLE over small domains (Roy, Crypto 2022) as well as new multiparty PCFs for small-domain VOLE-style correlations, including scalar-vector multiplication triples and their authenticated variants. Finally, we discuss applications to secure computation.

Leibniz international proceedings in informatics•Jan 1, 2026•0 citations

Improved Constructions for Distributed Multi-Point Functions

Elette Boyle, Niv Gilboa, Matan Hamilis +2 more

A Distributed Point Function (DPF) is a crypto-graphic primitive used for compressing additive secret shares of a secret unit vector across two parties. Many DPF applications require compressed shares of a sparse weight- t vector, namely a Distributed Multi-Point Function (DMPF). Despite the strong motivation and prior optimization efforts, in most use cases the best practical implementation of DMPF is still a simple brute-force combination of$t$independent DPFs. We present new constructions and optimized implementations of DMPFs in different parameter regimes, providing significant efficiency savings over existing approaches. We showcase our new constructions within applications of pseu-dorandom correlation generators (PCGs) and 2-server private set intersection (PSI). Incorporating our tools into the state-of-the-art PCG for “silent” generation of binary multiplication triples (FOLEAGE, Bombar et al, ePrint'24) yields a x2.68 improvement in throughput, with only x 1.4 blowup in the seed size. On a single core of our benchmark machine, our implementation silently generates up to 22.1 million triples per second, outperforming even the best “non-silent” protocol (Roy, CRYPTO'22), which generates 16 million triples per second.

IEEE Symposium on Security and Privacy (S&P)•May 12, 2025•13 citations
We revisit the question of securely compressing multiparty correlations using only symmetric cryptography. A linear correlation C, defined by a linear subspace C ⊆ 𝔽ⁿ, samples a secret random 𝐜 ∈ C and assigns to each party a fixed subset of the entries of 𝐜. Gilboa and Ishai (Crypto 1999) and Cramer, Damgård and Ishai (TCC 2005) provide a general technique for securely compressing many independent samples from C by replicating independent keys of a pseudorandom function (PRF) among the parties. This implies a pseudorandom correlation function (PCF) for C from any PRF, where the PCF key size scales with the number of minimal-support codewords in C. We observe that the above generalizes to other types of useful target correlations C_T by using a secret replication pattern obtained via a random secret assignment of parties in C to parties in C_T. We present several corollaries of this general blueprint. These include a re-derivation of two-party PCF constructions for VOLE and subfield-VOLE over small domains (Roy, Crypto 2022) as well as new multiparty PCFs for small-domain VOLE-style correlations, including scalar-vector multiplication triples and their authenticated variants. Finally, we discuss applications to secure computation.
A Distributed Point Function (DPF) is a crypto-graphic primitive used for compressing additive secret shares of a secret unit vector across two parties. Many DPF applications require compressed shares of a sparse weight- t vector, namely a Distributed Multi-Point Function (DMPF). Despite the strong motivation and prior optimization efforts, in most use cases the best practical implementation of DMPF is still a simple brute-force combination oftttindependent DPFs. We present new constructions and optimized implementations of DMPFs in different parameter regimes, providing significant efficiency savings over existing approaches. We showcase our new constructions within applications of pseu-dorandom correlation generators (PCGs) and 2-server private set intersection (PSI). Incorporating our tools into the state-of-the-art PCG for “silent” generation of binary multiplication triples (FOLEAGE, Bombar et al, ePrint'24) yields a x2.68 improvement in throughput, with only x 1.4 blowup in the seed size. On a single core of our benchmark machine, our implementation silently generates up to 22.1 million triples per second, outperforming even the best “non-silent” protocol (Roy, CRYPTO'22), which generates 16 million triples per second.