Source-linked AI summary
Improved lower bounds for decomposable randomized encoding
Justin Holmgren, Kewen Wu
TL;DR
Optimal DRE size remains unresolved even for OR, despite its centrality as a complexity measure. This paper uses combinatorial arguments to prove superlinear lower bounds for OR, a periodicity condition for linear-size symmetric-function DREs, and a quadratic lower bound for general functions.
Problem
DRE size is the main complexity measure in cryptographic applications, yet optimal size is unknown even for OR: its best prior lower bound is 2n against an O(n log n) construction.
Source: §1 · p. 2Method
The proof constructs an anti-embedding family of strings and combines extremal-combinatorial bounds with König's lemma, hypergraph Ramsey, and Higman's lemma.
Source: §2 · p. 8Results
The results establish OR complexity ω(n), periodicity for symmetric functions with linear-size DREs, Ω(n log n) under symmetric support, and quadratic lower bounds for general functions.
Source: §1.1 · p. 3, §1.1.2 · p. 4, §2 · pp. 7–8Takeaways & Limitations
The paper's results also extend beyond perfect correctness and privacy to settings with imperfect correctness and privacy.
Source: §1.1 · p. 3The explicit bound obtained from quantitative versions of the preceding results is not primitive recursive.
Source: §4.3.2 · p. 16
Abstract
from arXiv · showhide
A decomposable randomized encoding (DRE) for a function $f$ allows $n$ parties, using shared randomness, to encode their individual inputs locally so that the collection of encodings reveals $f(x_1,\ldots,x_n)$ and nothing else. DREs are widely used in efficient multiparty computation. Their main complexity measure is size, the total bit length of the local encodings. Yet the optimal DRE size remains poorly understood even for the $n$-bit OR function. We prove the first superlinear lower bound for OR and, more generally, for every non-periodic symmetric function. Under an additional symmetry assumption, we prove a sharp $\Omega(n\log n)$ lower bound for OR, matching the classic construction of Feige, Kilian, and Naor (STOC 1994). We also prove the first $\Omega(n^2)$ lower bound on DRE size for non-explicit Boolean functions.
1 Introduction
The paper studies DRE size, which remains poorly understood even for OR, and develops lower bounds and structural characterizations for symmetric and general Boolean functions. Its results include a superlinear lower bound for OR, a sharp bound for a structured class of OR encodings, and a quadratic worst-case bound.
1.1.1 Lower bounds for perfect DREs
- DRE(OR_n)=ω(n), and every symmetric function with a perfect constant-alphabet DRE must be periodic.The periodicity theorem yields the superlinear OR bound.Source: §1.1.1 · p. 3
- A symmetric function has linear perfect DRE complexity if and only if it has constant period.Functions with period a have a perfect DRE over an alphabet of size at most a!.Source: §1.1.1 · p. 3
- For every n, some Boolean function f requires DRE(f)≥c·n^2, improving the prior general lower bound by a logarithmic factor.The bound is existential; the paper notes that its proof is nonconstructive.Source: §1.1.1 · p. 3, §1.2 · p. 5
1.1.2 Statistical, probabilistic, and structural extensions
- With sufficiently small errors depending on K, a statistical DRE of a symmetric function forces periodicity, and linear statistical and perfect DRE complexity coincide.The equivalence applies to sufficiently small statistical error.Source: §1.1.2 · p. 4
- The authors also extend the quadratic lower-bound result to random Boolean functions, even for statistical DREs.The supplied passage does not state the quantitative bound for this extension.Source: §1.1.2 · p. 4
- Under symmetric support on input 0^n, every perfect DRE of OR_n has size Ω(n log n), matching the classic O(n log n) construction.The symmetry condition is imposed on the support of the encoding of 0^n.Source: §1.1.2 · p. 4
1.2 Discussions and AI disclosure
- For fixed K, the universal period is 2^O(K), and the paper’s function-dependent period bound is at most 2^K; OR examples make these bounds essentially optimal.The input-length threshold for the general theorem is enormous and is not primitive recursive, leaving the ω(n) rate numerically uninformative.Source: §1.2 · p. 5
- The quadratic lower bound is nonconstructive, and finding an explicit function with genuinely quadratic DRE complexity remains open.Local embeddings of symmetric functions do not yet yield a global characterization of general Boolean functions with small DREs.Source: §1.2 · pp. 5–6
2 Proof overview
The proof overview develops a local representation of Boolean functions from small-alphabet DREs, then uses it to establish quadratic lower bounds and classify symmetric functions with linear-size DREs. For OR, it outlines both a superlinear lower bound and an optimal lower bound under a symmetric-support assumption.
A common combinatorial recipe
- A small-alphabet DRE locally represents f(x ⊕ J) using labels L_i(x) and decoders D_{J,b} that do not depend on x.This representation supplies a succinct description of f in local neighborhoods and underlies several of the proofs.Source: §2 · p. 6
Quadratic lower bounds for general Boolean functions
- For any fixed d ≥ 2, comparing the quantities with |W| ≥ 2n/poly(n) yields DRE(f) = n log K = Ω(n²), a quadratic lower bound.Source: §2 · p. 7
- The overview also points to an average-case quadratic lower bound for statistical DREs, obtained by a robust version of the general-function argument.The robust argument is formalized in Section 5.1.Source: §2 · p. 7
Classification for symmetric functions with linear DRE
- A symmetric function with a constant-alphabet perfect DRE must be periodic, with interior periodicity extended to weights near the boundaries.The proof first establishes local periodicity, patches intervals to obtain interior periodicity, then handles boundary weights by reducing mismatches to OR or its negation.Source: §2 · p. 7
Superlinear lower bounds for OR
- DRE(OR_n) = ω(n): extremal combinatorial arguments rule out arbitrarily large families of strings with the required anti-embedding property over a fixed alphabet.The argument uses König’s lemma, the hypergraph Ramsey theorem, and Higman’s lemma.Source: §2 · p. 8
Structured optimal lower bound for OR
- Under a symmetric-support assumption, the overview targets an Ω(n log n) lower bound for OR using an equal-multiset obstruction.Perfect correctness excludes equal multisets on any nonempty coordinate set; the proof argues that a small alphabet would force such equality.Source: §2 · p. 8
3 Lower bounds for general Boolean functions
This section proves that some Boolean functions require quadratic-size DREs. It compresses local truth-table neighborhoods into decoder and label descriptions, then counts those descriptions against the possible restrictions of Boolean functions.
Theorem 1.5
- For every n, there exists a Boolean function f with DRE(f) ≥ c·n^2 for a universal constant c > 0.The theorem establishes a quadratic lower bound for general Boolean functions.Source: §3 · p. 8
Local representation
- A perfect DRE yields local decoders D_{J,b} and labels L_i(x) that recover f(x ⊕ J) from f(x) and the labels on J.The decoders may depend on f, J, and b, but not on x; this compresses local neighborhoods without recording every nearby function value.Source: §3 · pp. 8–9
Counting argument
- The proof counts restrictions to points near a large, well-separated set W and bounds their number using the local representation.Recording the local decoders, labels, and values on W gives too few possibilities to account for all Boolean functions when n is sufficiently large.Source: §3 · pp. 9–10
4 Classification of symmetric functions
The section analyzes structural constraints on perfect DREs over a fixed alphabet, showing that sufficiently large symmetric Boolean functions with such encodings must be periodic and that anti-embedding families derived from perfect DREs of OR_n have bounded dimension.
4 Classification of symmetric functions
- For each fixed K, every sufficiently large symmetric function with a perfect DRE over alphabet [K] has period aK.The proof shows periodicity between weights BK and n − BK, then rules out boundary exceptions by reducing them to OR.Source: §4 · pp. 10–11
4.1 Almost periodicity
- A symmetric function with a perfect DRE over [K] is periodic with period aK across an interior interval of Hamming weights.The local-periodicity lemma applies between ℓ = u + 2K and r = u + 1 + n − u − 2K; overlapping intervals extend the pattern away from the boundaries.Source: §4.1 · pp. 11–12
4.2 Reduction between perfect DREs
- Perfect DREs are preserved under rearranging inputs, output reversal, input negation, restriction, and projection, with projection increasing the alphabet to [Kd].These closure properties enable the boundary-exception reduction to OR.Source: §4 · p. 11, §4.2 · p. 13
4.3 Lower bounds for OR
- For each fixed K, ORn having a perfect DRE over alphabet [K] implies n ≤ nK; consequently, DRE(ORn) = ω(n).The proof extracts a local anti-embedding family from a perfect DRE and applies a combinatorial bound on its dimension.Source: §4.3 · p. 14
4.3.1 Local anti-embedding family
- A fixed yes-transcript can be realized by some randomness for each nonempty input support S, yielding strings indexed by subsets for the local anti-embedding family.All nonzero inputs share the yes-transcript distribution, whose support is disjoint from the no-transcript distribution.Source: §4.3.1 · pp. 14–15, §4.3 · p. 14
- Any perfect DRE of OR_n yields a family of strings with anti-embedding structure.The local anti-embedding argument also uses a correctness contradiction: a constructed encoding would put an output-1 input's encoding in the support for output 0.Source: §4.3.1 · p. 15
4.3.2 Finiteness of local anti-embedding family
- The cited statements include Kőnig’s infinity lemma [Kőn27] for infinite rooted trees with finite branching, infinite hypergraph Ramsey [Ram30] for homogeneous infinite subsets, and Higman’s lemma [Hig52] for subsequences.Source: §4.3.2 · p. 15
- Quantitative versions give an explicit bound on the family dimension, but that bound is not primitive recursive.Source: §4.3.2 · p. 16
- Valid local anti-embedding families exist in only finitely many dimensions, as an infinite path would contradict their defining property.The proof constructs a path of families, homogenizes finite-set colorings, and uses a subsequence embedding to obtain the contradiction.Source: §4.3.2 · p. 16
5 Statistical and probabilistic extensions
The section extends DRE lower-bound arguments to statistical correctness and privacy errors, including average-case bounds for general Boolean functions and a periodicity classification for symmetric functions.
5 Statistical and probabilistic extensions
- For nonconstant f, the reference-distribution formulation relates decoding error δ to worst-case decoder error e within privacy error η; optimizing η can change δ.The stated bounds include δ ≤ 2(e + η).Source: §5 · p. 17
5.1 Average-case lower bounds for general Boolean functions
- For uniformly random Boolean functions, at most 2^(-γ·2^n/n^2) of truth tables admit the counted short descriptions.The proof obtains this bound when H(θ) + 2c < 1, with γ depending on θ and c.Source: §5.1 · p. 18
5.2 Symmetric classification with statistical error
- For fixed K and sufficiently small δ + η, every sufficiently large-n symmetric function with a statistical DRE has period aK.The theorem specifies thresholds εK and NK, and period aK.Source: §5.2 · p. 19
- The robust proof glues overlapping local periodic intervals and restricts only O_K(1) input bits before embedding OR.The interval length need only be at least aK + 1; restricting O_K(1) bits limits the alphabet blowup.Source: §5.2 · pp. 19–20
6 Tight structured lower bound for OR
The section proves an Ω(n log n) size lower bound for perfect DREs of OR under symmetric support on the zero-input encoding. Its proof obtains K = Ω(n^1/3) by using an acyclic graph induced by the encoding.
6 Tight structured lower bound for OR
- The theorem provides evidence toward Conjecture 1.10 under a structural assumption.The assumption is symmetric support on the zero-input encoding.Source: §6 · p. 20
- Ω(n log n) size is necessary for every perfect DRE of ORn whose zero-input support is symmetric.The proof establishes K = Ω(n^1/3), which gives size n log K = Ω(n log n).Source: §6 · pp. 20–21
- Symmetric support rules out directed cycles in the encoding-derived graph, allowing a topological order that yields K = Ω(n^1/3).A directed cycle would make the corresponding encoding equivalent up to permutation to the zero-input encoding, contradicting correctness.Source: §6 · p. 21