Dory: Streaming PCG with Small Memory

Xiaojie Guo, Hanlin Liu, Zhicong Huang, Hongrui Cui, Wenhao Zhang, Cheng Hong, Xiao Wang, Kang Yang, Yu Yu

Abstract

Dory introduces a novel "streaming" Pseudorandom Correlation Generator (PCG) designed to produce cryptographic randomness on-the-fly with sublinear memory requirements. By replacing complex data structures with a simplified binary tree accumulation method and addressing a critical security vulnerability in previous Learning Parity with Noise (LPN) constructions, Dory achieves over a 15x reduction in memory usage compared to state-of-the-art protocols like Ferret. This makes efficient Secure Multi-Party Computation (MPC) viable for resource-constrained edge devices.

Introduction

Secure Multi-Party Computation (MPC) enables collaborative data processing without compromising privacy. However, the efficiency of most MPC protocols hinges on a "preprocessing phase" that generates vast quantities of correlated randomness, such as sVOLE or Correlated Oblivious Transfer.

Existing Pseudorandom Correlation Generators (PCGs) typically operate monolithically, requiring the expansion of a small seed into a massive batch of correlations simultaneously. For large-scale computations involving millions of correlations, this approach can consume hundreds of megabytes of RAM, posing a significant barrier for mobile devices or cloud environments where memory is a constrained resource. Dory addresses this bottleneck by providing a streaming PCG that generates correlations individually as needed, maintaining a minimal memory footprint.

Methodology: Efficient Streaming via Tree Accumulation

Dory's architecture is built upon the "Expand-Accumulate" (EA) Learning Parity with Noise (LPN) framework. The core innovation lies in the transition from complex ternary trees to a more efficient Correlated GGM (cGGM) tree for accumulation.

Figure 1: The cGGM tree structure used by the Sender and Receiver to compute prefix sums for the EA-LPN framework.

In this construction, the sum of all leaf nodes in any sub-tree is equal to the root of that sub-tree. This property allows Dory to compute the necessary prefix sums for the "Accumulate" phase of EA-LPN in $O(\log N)$ time and memory. Furthermore, the authors introduced a maliciously secure setup using random linear universal hashing to verify tree consistency against active adversaries.

A critical technical contribution is the discovery and mitigation of a security flaw in the "regular noise" distribution used in prior EA-LPN works over binary fields. The authors found that predictable noise patterns reduced security from 128 bits to as low as 14 bits. To resolve this, Dory implements relaxed regular noise, where each noise block contains a uniform element at a random position, successfully restoring 128-bit security.

Performance and Streaming Properties

The effectiveness of Dory was evaluated using a C++ implementation on the EMP-toolkit, comparing it against established protocols like Ferret and EC-code PCG.

Figure 2: Comparison of streaming properties and setup costs between Dory ("This work") and prior state-of-the-art PCG constructions.

As shown in the comparison table, Dory is uniquely positioned as an "on-the-fly" generator with significantly lower memory requirements. For generating 10 million COTs, Dory requires only 20 MB of memory, a 16.7x improvement over Ferret (337 MB) and a 31.2x improvement over EC-code PCG (624 MB). Additionally, Dory's malicious setup communication is four times more efficient than previous best-in-class PCF constructions.

Discussion and Future Work

Dory demonstrates a strategic trade-off: it prioritizes memory efficiency over raw throughput. While Dory is approximately 2x slower than monolithic PCGs in high-bandwidth LAN environments due to the overhead of re-traversing tree paths, its sublinear memory footprint makes it indispensable for memory-limited scenarios.

The "relaxed regular noise" finding serves as a cautionary tale for structured noise distributions in LPN-style hardness assumptions. Future research may focus on reducing the computational overhead of the malicious security check, which currently requires expanding the tree twice, or further optimizing the "bootstrapping" phase required after consuming a fixed number of correlations.

Summary updated

BibTeX
@article{guo2025dory,
  author = {Xiaojie Guo and Hanlin Liu and Zhicong Huang and Hongrui Cui and Wenhao Zhang and Cheng Hong and Xiao Wang and Kang Yang and Yu Yu},
  title = {{Dory: Streaming PCG with Small Memory}},
  journal = {IACR Cryptol. ePrint Arch.},
  year = {2025},
}

Loading related content...

Figure