On the Complexity of Symmetric Boolean Functions in Multiparty Private Simultaneous Messages

summary

Video file (mp4)

The gist

The gist The paper studies communication complexity for symmetric Boolean functions in Multiparty Private Simultaneous Messages (PSM), which is a model for non-interactive secure computation, and

In short

The paper studies communication complexity for symmetric Boolean functions in Multiparty Private Simultaneous Messages (PSM), a model for secure computation where parties encode inputs using shared randomness. The authors establish superlinear lower bounds ($\Omega(n\log n)$) for functions like OR and MAJ, while constructing protocols with total communication $\widetilde{O}(n^{3/2})$ for perfect privacy, improving on previous quadratic bounds.

Key concepts

Multiparty Private Simultaneous Messages (PSM)
A model for secure computation where $n$ parties each encode their input using shared randomness and send messages to an evaluator. The evaluator computes the function output without knowing the inputs or the randomness, requiring privacy regarding what is learned.
Perfect Privacy
The strictest privacy requirement in PSM, demanding that the distribution of messages sent by all parties remains identical whenever two different input sets yield the same function output. This ensures no information about individual inputs leaks during computation.
Support Privacy
A weaker privacy notion requiring only that the distributions of messages sent by different inputs have the same support. This means the set of possible outcomes for each party's message must be identical, even if the exact probability distribution differs slightly.

Terminology used across episodes

This episode discusses

The paper

On the Complexity of Symmetric Boolean Functions in Multiparty Private Simultaneous Messages · Read on arXiv

New York University · Tufts University

Multiparty Private Simultaneous Messages (PSM), also known as Decomposable Randomized Encoding (DRE) or information-theoretic garbling, is a model for non-interactive secure computation. Each party encodes its input using shared randomness and sends a message to an evaluator who does not know that randomness. The evaluator must recover the function output without learning anything else about the inputs. Perfect privacy requires identical transcript distributions on inputs with the same output. We also study the weaker notion of support privacy, which requires only that these distributions have the same support. We study the communication complexity of symmetric Boolean functions when each of the n parties holds one input bit. Lower bounds. We prove a superlinear lower bound for support-private PSM protocols computing OR n. Our technique gives Ω(n n) lower bounds for MAJ n and EMAJ n (with even n), and an Ω(n q) lower bound for MOD q when q at most(1-c)n for a fixed constant c>0. Upper bounds. We construct perfectly private PSM protocols of total communication (n 3/2) for every symmetric Boolean function, improving on the known quadratic bound. For MAJ n, known branching-program constructions yield an upper bound of O(n cubed n n). For EMAJ n and MOD q with prime q, the lower bounds are tight up to constant factors in the stated regimes. Under support privacy, we obtain (n) communication for every symmetric Boolean function. Earlier lower-bound techniques of Ball et al. (ITCS 2020) yield only trivial linear bounds for symmetric Boolean functions. Concurrent and independent work by Holmgren and Wu proves a ω(n) lower bound for OR n using the same combinatorial core. Both works used AI assistance.

Transcript

Introduction to the show: ident: Security Radio. Generated commentary on the latest security and cryptography papers.

Nadia: I'm Nadia.

Elias: And I'm Elias, here with Priya.

Nadia: Today's paper: "On the Complexity of Symmetric Boolean Functions in Multiparty Private Simultaneous Messages".

Elias: The gist The paper studies communication complexity for symmetric Boolean functions in Multiparty Private Simultaneous Messages (PSM), which is a model for non-interactive secure computation,

Nadia: First, who's behind it and why it matters.

Paper summary: Nadia: We’re diving into what the paper actually claims about these communication complexities. It starts by setting up their combinatorial technique to prove a superlinear lower bound for support-private PSM protocols computing ORn.

Elias: That technique involves something called an f-cube system representation, which they use to isolate the correctness and privacy properties when proving those lower bounds.

Priya: The paper then uses things like agreement lemmas, specifically Lemma thirteen for OR, which relies on Higman’s lemma and Ramsey’s theorem to build up the combinatorial bound.

Nadia: They lift that lower bound on the individual message complexity to a bound on the total communication complexity using a lifting lemma in section two point two <ref:2610.21216#pg1>.

Elias: So what they get is Theorem one which states for any perfectly correct, support-private PSM protocol computing OR, the communication complexity C(OR) is omega of n <ref:2610.21216#pg1>.

Priya: That’s interesting because the known upper bound for OR and AND in this setting is O of n log n Ish13. So settling the exact cost of securely computing OR remains open.

Nadia: They also have Theorem two which gives a lower bound for MAJ or EMAJ when n is even, stating that their communication complexity is omega of n log n <ref:2610.21216#pg1>.

Elias: And for MODq functions, they prove a lower bound that says the communication complexity satisfies C(MODq) is omega of n log q when q is less than or equal to one minus c times n for some fixed constant c greater than zero.

Priya: That means if you’re working with moduli that are too large compared to n, they have a superlinear cost for support privacy on MODq <ref:2610.21216#pg3>.

Nadia: On the upper bound side, they construct perfectly private PSM protocols with a total communication of Oe(n cubed over two) for every symmetric Boolean function.

Elias: That’s an improvement over what was known before, which was just a quadratic bound. For MAJ specifically, known branching-program constructions yield an upper bound of O of n log three n log log n.

Priya: And for EMAJn and MODq with prime q, they found that the lower bounds they established are tight up to constant factors in the regimes where they apply <ref:2610.21216#pg3>.

Nadia: Under support privacy, though, they managed to get a quasilinear bound of Oe(n) for every symmetric Boolean function. That’s a significant improvement over the quadratic bound for perfect privacy.

Conclusion: Elias: So looking at the whole paper "On the Complexity of Symmetric Boolean Functions in Multiparty Private Simultaneous Messages," we see they establish very specific costs for different functions under different privacy models.

Nadia: They show that while perfect privacy might push you toward quadratic communication complexity, support privacy allows for a quasilinear bound of Oe(n) for every symmetric Boolean function.

Priya: That’s the big picture: knowing how to trade perfect versus support privacy changes the communication cost from something quadratic down to something linear in n.

Elias: The paper provides a general combinatorial framework and specific protocols that achieve these bounds, which helps us understand the cost of privacy when you're doing non-interactive secure computation.

Nadia: It really puts things into perspective for applied security researchers about how cheaply we can actually achieve these secure computations in practice.

Elias: They also highlight the tension between lower bounds and upper bounds, showing where the exact cost of securely computing functions like OR is still open, even with better techniques.

More episodes

← Home