Welcome to the resource topic for 2025/1685
Title:
Toss: Garbled PIR from Table-Only Stacking
Authors: Lucien K. L. Ng, Vladimir Kolesnikov
Abstract:Garbled Circuits (GC) are a foundational primitive for secure two-party computation (2PC). Garbled Private Information Retrieval (GPIR) is a GC technique for looking up a public array or database (DB) on a private index unknown to either party. GPIR immediately enables GC evaluation of functions implemented as a publicly known lookup table (LUT).
However, GPIR is costly. It can be realized by a linear scan, by adapting Garbled RAM, by stacking GC branches implementing access to table elements, and, most recently, via the GC lookup table scheme logrow (Heath et al., Eurocrypt 2024). For an N-row DB lookup of m-bit rows, logrow has computation cost \approx O(N m \kappa) and communication cost O(m(\log N \cdot \kappa + N)). This makes logrow practical only for tables up to about 2^{15} rows.
We propose Toss, a new efficient GPIR protocol with dramatically reduced bandwidth consumption—an especially scarce resource in MPC—both asymptotically and concretely. Our communication cost is O\!\left(\sqrt{N}\, m \sqrt{\kappa}\right) with a small constant, which is sublinear in both N and the security parameter \kappa. Our computation cost is O\!\left(N m \kappa + \bigl(\sqrt{N/\kappa}\, m + N\bigr) c_\kappa \right), where c_\kappa is the cost of a hash evaluation. This computation cost is comparable to, or slightly lower than, that of logrow.
In concrete terms, for a 2^{20}-row LUT of 8-bit items, we achieve more than a 31\times reduction in communication compared to logrow. On a laptop over a 100 Mbps channel, throughput increases from approximately 10.6 lookups/s to 81 lookups/s, a >7.5\times improvement. On a 10 Mbps channel, Toss achieves more than 28\times better throughput. The improvement grows with N; for example, for N=2^{25} and m=32, the gain exceeds 512\times.
Toss builds on stacked garbling (SGC) and logrow, incorporating multiple low-level optimizations and requiring a reworking of their internals and interfaces. We emphasize that constructing GPIR directly from SGC incurs logarithmic computational overhead, which decreases throughput in typical “laptop + LAN” testbeds. Our design avoids this pitfall. We implement Toss and report on its performance, demonstrating its substantial communication savings and practical efficiency.
ePrint: https://eprint.iacr.org/2025/1685
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .