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

Correlated Pseudorandomness in Secure Computation

Geoffroy Couteau

Published Mar 20, 2024• 0 citations
OpenAlex

Related papers

Generalized Pseudorandom Secret Sharing and Efficient Straggler-Resilient Secure Computation

Fabrice Benhamouda, Elette Boyle, Niv Gilboa +3 more

Lecture notes in computer science•Jan 1, 2021•14 citations

On the Security of Pseudorandomized Information-Theoretically Secure Schemes

Koji Nuida, Goichiro Hanaoka

Lecture notes in computer science•Jan 1, 2010•3 citations

Share Conversion, Pseudorandom Secret-Sharing and Applications to Secure Computation

Ronald Cramer, Ivan Damgård, Yuval Ishai

Lecture notes in computer science•Jan 1, 2005•238 citations

Efficient Oblivious Pseudorandom Function with Applications to Adaptive OT and Secure Computation of Set Intersection

Stanisław Jarecki, Xiaomin Liu

Lecture notes in computer science•Jan 1, 2009•300 citations

On Quantum Secure Compressing Pseudorandom Functions

Ritam Bhaumik, Benoît Cogliati, Jordan Ethan +1 more

Lecture notes in computer science•Jan 1, 2023•3 citations

Dory: Streaming PCG with Small Memory

Xiaojie Guo, Hanlin Liu, Zhicong Huang +6 more

Pseudorandom correlation generators (PCGs) have been popular in generating a huge amount of correlated randomness, a critical resource in secure computation. However, existing PCGs are memory-consuming and not friendly to resource-constrained devices. Even for moderate devices, the need for large memory can also be a disadvantage in applications like zero-knowledge proofs or large-scale secure computation. In this paper, we propose a malicious streaming PCG (sPCG), which generates a bounded number of tuples of subfield vector oblivious linear evaluation (sVOLE) on-the-fly, each with sublinear memory and computation. 1)We propose an efficient protocol that replaces the relaxed distributed comparison function in the best pseudorandom correlation function (PCF) for sVOLE (CRYPTO'22), which has the same streaming features for any polynomial number of tuples. With this protocol, our sPCG is doubly efficient in memory and the computation per sVOLE. Moreover, we augment the black-box distributed setup to malicious security and yield$4 \times$communication improvement. Our sPCG can be extended to a more efficient sVOLE PCF with the same improvements in memory and computation, and a$2 \times$faster malicious non-black-box distributed setup. 2)We present a practical attack on the Learning Parity with Noise (LPN) assumption for expand-accumulate codes with regular noise, revealing that some previous parameters provide around$14 \sim 22$bits of security over binary noises, far below the target 128 bits. To address this, we introduce a low-Hamming-weight noise distribution to withstand the attack. We then derive some updated LPN parameters with the new noise distribution, restoring 128-bit security and reducing the noise-related computation and communication. 3)We provide an implementation of our sPCG for the special case of correlated oblivious transfer (COT). In addition to the improvements over the best PCF, our sPCG can have a comparable end-to-end performance to Ferret (CCS'20) and the PCG from expand-convolute codes (CRYPTO'23), two state-of-the-art PCGs, with the advantage of being able to produce 10 million COTs on-the-fly and reducing the memory from 337 MB and 624 MB to 20 MB, respectively.

IEEE Symposium on Security and Privacy (S&P)•May 18, 2026•2 citations
Pseudorandom correlation generators (PCGs) have been popular in generating a huge amount of correlated randomness, a critical resource in secure computation. However, existing PCGs are memory-consuming and not friendly to resource-constrained devices. Even for moderate devices, the need for large memory can also be a disadvantage in applications like zero-knowledge proofs or large-scale secure computation. In this paper, we propose a malicious streaming PCG (sPCG), which generates a bounded number of tuples of subfield vector oblivious linear evaluation (sVOLE) on-the-fly, each with sublinear memory and computation. 1)We propose an efficient protocol that replaces the relaxed distributed comparison function in the best pseudorandom correlation function (PCF) for sVOLE (CRYPTO'22), which has the same streaming features for any polynomial number of tuples. With this protocol, our sPCG is doubly efficient in memory and the computation per sVOLE. Moreover, we augment the black-box distributed setup to malicious security and yield4×4 \times4×communication improvement. Our sPCG can be extended to a more efficient sVOLE PCF with the same improvements in memory and computation, and a2×2 \times2×faster malicious non-black-box distributed setup. 2)We present a practical attack on the Learning Parity with Noise (LPN) assumption for expand-accumulate codes with regular noise, revealing that some previous parameters provide around14∼2214 \sim 2214∼22bits of security over binary noises, far below the target 128 bits. To address this, we introduce a low-Hamming-weight noise distribution to withstand the attack. We then derive some updated LPN parameters with the new noise distribution, restoring 128-bit security and reducing the noise-related computation and communication. 3)We provide an implementation of our sPCG for the special case of correlated oblivious transfer (COT). In addition to the improvements over the best PCF, our sPCG can have a comparable end-to-end performance to Ferret (CCS'20) and the PCG from expand-convolute codes (CRYPTO'23), two state-of-the-art PCGs, with the advantage of being able to produce 10 million COTs on-the-fly and reducing the memory from 337 MB and 624 MB to 20 MB, respectively.