Improved lower bounds for decomposable randomized encoding Justin Holmgren∗
Kewen Wu†
arXiv:2609.18020v1 [cs.CC] 16 Sep 2026
Abstract 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 (x1 , . . . , xn ) 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 Ω(n log n) lower bound for OR, matching the classic construction of Feige, Kilian, and Naor (STOC 1994). We also prove the first Ω(n2 ) lower bound on DRE size for non-explicit Boolean functions.
Contents 1 Introduction 1.1 Our results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.1.1 Lower bounds for perfect DREs . . . . . . . . . . . . . . . . . . . . . . . . . . 1.1.2 Statistical, probabilistic, and structural extensions . . . . . . . . . . . . . . . 1.2 Discussions and AI disclosure . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2 2 3 3 4
2 Proof overview
6
3 Lower bounds for general Boolean functions
8
4 Classification of symmetric functions 4.1 Almost periodicity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.2 Reduction between perfect DREs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.3 Lower bounds for OR . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.3.1 Local anti-embedding family . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.3.2 Finiteness of local anti-embedding family . . . . . . . . . . . . . . . . . . . .
10 11 13 14 14 15
5 Statistical and probabilistic extensions 16 5.1 Average-case lower bounds for general Boolean functions . . . . . . . . . . . . . . . . 17 5.2 Symmetric classification with statistical error . . . . . . . . . . . . . . . . . . . . . . 19 6 Tight structured lower bound for OR
∗ †
20
Email: [email protected]. Research conducted in part while employed at NTT Research. Caltech. Email: [email protected]. Research conducted in part while interning at NTT Research.
1
1
Introduction
Randomized encodings, introduced by Applebaum, Ishai, and Kushilevitz [AIK06], are a beautiful relaxation of deterministic computation. The notion, of which there are several flavors, is that Definition 1.1 (Informal). A randomized function fˆ encodes a deterministic function f if it satisfies the following properties: • Correctness. If f (x) ̸= f (x′ ), then fˆ(x) and fˆ(x′ ) have disjoint supports. Moreover, there is an efficient algorithm D, called the decoder, such that D(fˆ(x)) = f (x) with probability 1 (or with high probability).
• Privacy. If f (x) = f (x′ ), then fˆ(x) and fˆ(x′ ) are identically distributed. Moreover, there is an efficient randomized algorithm S, called the simulator, such that S(f (x)) is identically distributed (or statistically close, or computationally indistinguishable) to fˆ(x). In this paper, we focus on decomposable randomized encodings (DREs, also called garbling schemes), which are randomized encodings of the form fˆ(x; r) = fˆ1 (x1 ; r), . . . , fˆn (xn ; r) .
DREs originated in secure two-party computation [Yao86, Kil88] and have since become indispensable throughout cryptography; see [App17, BHR12, Ish13] for surveys. We consider the regime where n grows and each xi is binary. The complementary regime, where the local inputs range over much larger domains, is widely studied in work on private simultaneous messages (PSM) [FKN94, IK97, BKN18, AL21, AHMS20]. For several fundamental complexity measures, such as polynomial degree [AIK06], the minimum complexity of fˆ can be far smaller than that of f . Perhaps the simplest example is the n-bit parity function, which cannot be computed in AC0 [Hås14] but admits a randomized encoding in [ r) ∈ {0, 1}n by NC0 [Kil88]. For n ≥ 2, x ∈ {0, 1}n , and r ∈ {0, 1}n−1 , define XOR(x; [ r)i = XOR(x;
x 1 ⊕ r 1
r
⊕ x ⊕ ri
i−1 i r ⊕x n−1
n
if i = 1, if 1 < i ≤ n − 1, if i = n,
and decode by taking the parity of the n encoding bits. This complexity gap is crucial in recent work on locally sampleable distributions and quantum–classical separations [KOW25, GKM+ 26]. For cryptographic applications, the main complexity measure of a DRE is its size, the total bit length of the local encodings. Unfortunately, even for the n-bit OR function, the optimal size is unknown: a simple construction of Feige, Kilian, and Naor gives an O(n log n) upper bound [FKN94], whereas the best prior lower bound is only 2n [SN24]. For arbitrary n-bit Boolean functions, the best prior lower bound is Ω(n2 / log n), due to Ball, Holmgren, Ishai, Liu, and Malkin [BHI+ 20], while the best general upper bound is exponential [BKN18].
1.1
Our results
We study information-theoretic DREs, so our complexity measure ignores the computational cost of producing or decoding an encoding. We begin with perfect DREs, the cleanest setting, and later consider statistical and structural extensions. In the information-theoretic setting, we directly work on the jointly distributed local messages b Zi := fˆi (b; r) induced by the shared randomness r, which leads to the following succinct formulation. 2
Definition 1.2 (Perfect decomposable randomized encoding). Let f : {0, 1}n → {0, 1}. A perfect DRE of f consists of jointly distributed random variables1 (Zib )i∈[n],b∈{0,1} , each taking values in a finite alphabet [K]. For x ∈ {0, 1}n , write Z x to denote (Zixi )i∈[n] ∈ [K]n . The following conditions must hold: ′
• Correctness. If f (x) ̸= f (x′ ), then the supports of Z x and Z x are disjoint. ′
• Privacy. If f (x) = f (x′ ), then Z x and Z x are identically distributed. The size of the DRE is2 defined to be n log K, and DRE(f ) denotes the minimum size of a perfect DRE of f . We remark that this definition is weaker than definition 1.1 in that it does not require efficient sampling of the distribution of any Z x . Our lower bounds are thus strengthened by ruling out DREs as per definition 1.2. For perfect DREs, we classify all symmetric functions whose DRE complexity is O(n), and we prove a genuinely quadratic lower bound for general functions. We then extend and strengthen these results to the setting of imperfect correctness and privacy. 1.1.1
Lower bounds for perfect DREs
For a symmetric function f : {0, 1}n → {0, 1}, write f (t) for its value on inputs of Hamming weight t. We say f has period a ∈ [n + 1] if f (t) = f (t + a) for all 0 ≤ t ≤ n − a. For symmetric functions, our main structural result is as follows. Theorem 1.3. For every integer K ≥ 1, there exist integers NK , aK ≥ 1 such that if n ≥ NK and a symmetric function f : {0, 1}n → {0, 1} has a perfect DRE with alphabet [K], then f has period aK . Prior to this work, even for the simplest symmetric function, OR, the best lower bound was only DRE(ORn ) ≥ 2n [SN24]. In contrast, Theorem 1.3 immediately yields the superlinear lower bound DRE(ORn ) = ω(n).3 Conversely, the PSM construction of [BGI+ 14] shows that every symmetric function with period a has a perfect DRE over an alphabet of size at most a!. We therefore obtain the following complete qualitative characterization. Corollary 1.4. A symmetric function has linear DRE if and only if it has constant period. For general Boolean functions, we prove a quadratic worst-case lower bound. Theorem 1.5. There exists a universal constant c > 0 such that, for every n ≥ 1, there exists f : {0, 1}n → {0, 1} with DRE(f ) ≥ c · n2 . Prior to this work, the best general lower bound was Ω(n2 / log n) [BHI+ 20]; Theorem 1.5 improves it by a logarithmic factor. 1.1.2
Statistical, probabilistic, and structural extensions
The results in Section 1.1.1 admit several robust extensions. 1
For a positive integer n, we use [n] to denote {1, . . . , n}. Throughout, logarithms are base two. 3 The proof of Theorem 1.3 actually relies on the superlinear lower bound for OR; see Section 2. 2
3
Statistical extension. Definition 1.2 defines perfect DREs. Their statistical counterparts allow small correctness and privacy errors [AIK06, AIKPC15, AHMS20]. Informally, a statistical DRE specifies two reference distributions, Pyes and Pno , and requires Z x ≈ Pyes for x ∈ f −1 (1) and Z x ≈ Pno for x ∈ f −1 (0). The correctness error δ measures the overlap between Pyes and Pno , while the privacy error η is the maximum distance between Z x and the appropriate reference distribution. Perfect DREs correspond to δ = η = 0. Formal definitions and a comparison with prior notions appear in Section 5. We strengthen Theorem 1.3 in this model. Theorem 1.6. For every integer K ≥ 1, there exist εK ∈ (0, 1] and integers NK , aK ≥ 1 such that the following holds. Assume n ≥ NK and a symmetric function f : {0, 1}n → {0, 1} has a statistical DRE with alphabet [K], correctness error δ, and privacy error η. If δ + η ≤ εK , then f has period aK . Together with Corollary 1.4, Theorem 1.6 yields the following qualitative equivalence. Corollary 1.7. A symmetric function has linear statistical DRE (with sufficiently small error) if and only if it has linear perfect DRE, and these conditions hold if and only if the function has constant period. Probabilistic extension. The Ω(n2 / log n) lower bound of [BHI+ 20] holds for a random function. We likewise strengthen Theorem 1.5 to a random function, even in the statistical setting. Theorem 1.8. For every δ̄, η̄ ∈ [0, 1] with δ̄ + 2 · η̄ < 1/2, there is cδ̄,η̄ > 0 such that the following holds. For a uniformly random Boolean function f : {0, 1}n → {0, 1}, except with probability at most n
2
2−cδ̄,η̄ ·2 /n , every statistical DRE of f with correctness error δ ≤ δ̄ and privacy error η ≤ η̄ has size at least cδ̄,η̄ · n2 . A structured lower bound for OR. The proofs of Theorem 1.3 and Theorem 1.6 use corresponding lower bounds for OR as black boxes; see Section 2. It is therefore important to understand the DRE complexity of OR itself. The classic construction of [FKN94] gives DRE(ORn ) = O(n log n), whereas the prior lower bound was only DRE(ORn ) ≥ 2n [SN24]. Theorem 4.3 improves the latter to DRE(ORn ) = ω(n), although the rate hidden by the ω(n) notation is extremely weak; see Section 1.2. To narrow the remaining gap, we prove a matching lower bound for perfect DREs under a symmetry assumption on their support, which captures and goes beyond the classic construction of [FKN94]. n Recall that Z 0 ∈ [K]n denotes the randomized encoding of ORn on input 0n . We say that a DRE n has symmetric support on input 0n if the support of Z 0 is closed under coordinate permutations. Theorem 1.9. Every perfect DRE of ORn with symmetric support on input 0n has size Ω(n log n).
1.2
Discussions and AI disclosure
We next discuss the quantitative aspects of our results and highlight several open problems.
4
On the period. The period aK in Theorem 1.3 and Theorem 1.6 may be chosen as the least common multiple of 1, 2, . . . , 2K, and hence aK = 2O(K) . Apart from the threshold NK , this dependence is essentially optimal: for a fixed alphabet [K], there are perfect DREs for ORm whenever 1 ≤ m ≤ Θ(K) [FKN94]. Consequently, every such m must divide the universal period aK , giving aK = 2Ω(K) . Our proof actually gives a sharper function-dependent statement: if a symmetric function f has a perfect DRE with alphabet [K], then f has a period af satisfying 1 ≤ af ≤ 2K. The OR example again shows that this bound is essentially optimal. On the input length. The threshold NK in Theorem 1.3 is enormous: even for OR, it is not primitive recursive. The proof reduces the general symmetric case to the OR lower bound with an exponential, but still elementary, loss. The OR argument itself uses Higman’s lemma, whose quantitative bounds are necessarily not primitive recursive. Consequently, our bound DRE(ORn ) = ω(n) is numerically uninformative. We nevertheless conjecture the optimal bound below and view the structured lower bound in Theorem 1.9 as supporting evidence. Conjecture 1.10. DRE(ORn ) = Ω(n log n). Regarding Conjecture 1.10, we remark that many existing DRE constructions have a grouptheoretic flavor [FKN94, BGI+ 14, Yos24, HE26] and are based on permutation branching programs [Kil88, Bar89, IK97]. Known complexity-theoretic lower bounds therefore apply to this class of constructions. For example, the analysis of Cai and Lipton [CL94] confirms Conjecture 1.10 for constructions based on constant-read permutation branching programs, a class that includes the classic construction [FKN94]. On the error dependence. Theorem 1.6 requires both the correctness error δ and the privacy error η to be sufficiently small as functions of K. Ishai [Ish13] describes a simple statistical DRE for ORn with alphabet [K] for arbitrarily large n. With suitable choices of Pyes and Pno , this construction has either (δ, η) = (Θ(1/K), 0) or (δ, η) = (0, Θ(1/K)). Thus the hypothesis of Theorem 1.6 must depend on both errors and on K. The value of εK obtained in Theorem 1.6 is itself not primitive recursive in K, again because of the weak quantitative bound for OR. On the worst-case bound. Theorem 1.5 gives an existential quadratic lower bound for Boolean n/2 e functions. This is still exponentially smaller than the upper bound DRE(f ) = O 2 [BKN18]. We expect the worst-case complexity to be much larger and make the following modest conjecture. Conjecture 1.11. There exists f : {0, 1}n → {0, 1} with DRE(f ) = nω(1) . A further limitation of Theorem 1.5 is its nonconstructive proof, whereas [BHI+ 20] give explicit functions, including Element Distinctness and Clique, with Ω(n2 / log n) lower bounds. Finding an explicit function of genuinely quadratic DRE complexity remains open. The same work also constructs a quadratic-size DRE for a candidate pseudorandom function; assuming the candidate is secure, this creates a natural-proofs barrier to constructive superquadratic lower bounds. Curiously, our non-explicit method also stops at quadratic.
5
On linear DRE complexity. Corollaries 1.4 and 1.7 classify only symmetric functions of linear DRE complexity, equivalently those admitting DREs over constant-size alphabets. It remains to characterize the general Boolean functions that admit small DREs. We record two relevant observations. Every nondegenerate monotone Boolean function embeds an OR or AND of superconstant size [Sim82]. Our OR lower bound therefore rules out linear-size DREs for such functions. It is also known that every nondegenerate Boolean function embeds a nontrivial symmetric function of superconstant size [SSW+ 20], to which Theorem 1.3 applies. However, we do not know how to combine this local information into a global characterization. AI disclosure. The authors proved several structured lower bounds for OR, including Theorem 1.9, in fall 2022. More recently, the authors revisited the project with GPT 5.6 Sol and developed the remaining results. The key new observations Lemmas 3.1 and 4.8, while not hard in hindsight, were discovered by GPT. GPT 5.6 Sol was also used to produce the initial draft, which the authors subsequently rewrote in full. The authors remain responsible for all mathematical claims and exposition.
2
Proof overview
This section gives a high-level overview of our proof techniques. A common combinatorial recipe. Fix a perfect DRE of f : {0, 1}n → {0, 1} with alphabet [K]. We first show that it yields a compact representation of local values of f . Fix x ∈ f −1 (1). For each J ⊆ [n], let x ⊕ J be the string obtained by flipping the bits of x in J. Under the same shared randomness, the encodings Z x and Z x⊕J differ only in coordinates in J. Thus, once Z x is fixed, correctness (Definition 1.2) allows f (x ⊕ J) to be determined from J and the replacement symbols on those coordinates. Privacy ensures that, for every x′ ∈ f −1 (1), one can ′ choose randomness under which Z x equals the same fixed transcript. The same local decoding rule therefore applies throughout the fiber f −1 (1). Applying the same argument to f −1 (0) yields local decoders DJ,b : [K]J → {0, 1} and local symbols Li : {0, 1}n → [K] such that • Li (x) records the encoding symbol corresponding to 1 − xi under the chosen randomness; • DJ,b (Li (x))i∈J = f (x ⊕ J) for every J ⊆ [n] and x ∈ f −1 (b).
This local representation underlies several of our proofs: a small-alphabet DRE gives a succinct description of f (x ⊕ J) in local neighborhoods of x. We formalize the perfect case in Lemma 3.1 and extend the argument to statistical DREs in Section 5.1. Quadratic lower bounds for general Boolean functions. The local representation yields the quadratic lower bound for general Boolean functions through a counting argument. Choose a set W ⊆ {0, 1}n of pairwise Hamming distance at least 2d + 1, where d = Θ(1) and |W | ≥ 2n /poly(n). Let R ⊆ {0, 1}n consist of the points at distance exactly d from W . The distance condition ensures that every point in R has a unique representation x ⊕ J, where x ∈ W and |J| = d. The construction above computes f (x ⊕ J) from f (x), DJ,f (x) , and Li (x) for i ∈ J. The decoders DJ,b may depend on f , J, and b, but not on x. As f varies, there are 2|R| = 2|W |·( d ) n
6
possible truth tables on R. On the other hand, the number of local descriptions is at most |W | 2 |{z}
·
n·|W | K | {z }
·
·2·( d ) 2| K {z } d
n
.
f (x) for x ∈ W Li (x) for x ∈ W, i ∈ [n] DJ,b ’s for b ∈ {0, 1}, |J| = d
For any fixed d ≥ 2, comparing these quantities and using |W | ≥ 2n /poly(n) gives DRE(f ) = n log K = Ω(n2 ). We give the formal proof of Theorem 1.5 in Section 3. A robust version of the argument proves Theorem 1.8, the average-case quadratic lower bound for statistical DREs, in Section 5.1. Classification for symmetric functions with linear DRE. We next consider a symmetric function f : {0, 1}n → {0, 1}, writing f (t) for its value on inputs of Hamming weight t. We show that if f has a linear-size DRE—equivalently, one with constant alphabet—then f must be periodic. We prove the perfect version, Theorem 1.3, in Section 4 and its statistical extension, Theorem 1.6, in Section 5.2. Both proofs have three steps. • Local periodicity. For every t sufficiently far from 0 and n, we show that f is periodic between t and t + ∆, where ∆ is an arbitrarily large constant. Among 2K + 1 nearby weights, choose K + 1 with the same function value b, and apply the local representation to their inputs 1t 0n−t . At each coordinate of their common zero tail, two of the K + 1 local labels must coincide. By pigeonholing, some pair of weights t1 , t2 has identical local labels on many coordinates. Flipping any c of those coordinates invokes the same decoder DJ,b on the same symbols, so f (t1 + c) = f (t2 + c). This gives a period of length |t1 − t2 | ≤ 2K. • Almost periodicity. We then show that f is periodic between ℓ = Θ(1) and r = n − Θ(1). This follows by patching together overlapping local periodic intervals. The intervals can begin anywhere away from the boundary and can be made arbitrarily long, allowing their periodic patterns to propagate. • Full periodicity. Finally, we show that the Hamming weights near the boundary obey the periodic pattern established in the interior. We reduce a boundary mismatch to the OR function. Since f is periodic between ℓ = Θ(1) and r = n − Θ(1), a mismatch below weight ℓ implies f (t) ̸= f (t + a) = f (t + 2 · a) = · · · = f (t + m · a), where t = O(1) is the largest outlier weight below ℓ and a = O(1) is the interior period. Standard restrictions and projections reduce this pattern to ORm or its negation. For sufficiently large n, the resulting m contradicts our superlinear DRE lower bound for OR, which we sketch next. Superlinear lower bounds for OR. For OR, perfect privacy makes every nonzero input induce the same encoding distribution Pyes , whose support is disjoint from that of the distribution Pno induced by 0n . Fix a reference string q = (q1 , . . . , qn ) in the support of Pyes . For each ∅ ̸= S ⊆ [n], we construct a string pS ∈ [K]n satisfying pSi = qi
if and only if
i∈ / S.
(2.1)
To obtain pS , let eS ∈ {0, 1}n be the indicator vector of S, choose randomness for which Z eS = q, n and let pS be the corresponding encoding Z 0 . 7
More importantly, these strings satisfy the anti-embedding property (pJi )i∈J ̸= (pL i )i∈J
for every ∅ ̸= J ⊊ L.
Otherwise, switching on the coordinates L \ J would produce a string in the supports of both Pyes and Pno , contradicting correctness. We have thus produced 2n − 1 strings over [K] with the anti-embedding property. Extremalcombinatorial tools bound n in terms of K, implying DRE(ORn ) = ω(n). Concretely, if n were arbitrarily large, König’s lemma (Lemma 4.9) and the hypergraph Ramsey theorem (Lemma 4.10) would yield an arbitrarily long sequence of strings over [K] in which no string is a subsequence of another, contradicting Higman’s lemma (Lemma 4.11). We formalize this argument for perfect DREs in Section 4.3. Its finitary combinatorial form extends to statistical DREs in Section 5.2. Structured optimal lower bound for OR. Finally, we outline the optimal Ω(n log n) lower bound for OR under the symmetry assumption of Theorem 1.9; see Section 6 for the proof. n Assume that the randomized encoding Z 0 has symmetric support. Together with perfect correctness, this implies that there is no nonempty S ⊆ [n] for which the multisets {Zi0 }i∈S and n {Zi1 }i∈S are equal: otherwise, Z 0 would equal Z eS up to a permutation. If the alphabet is too small, however, such equal multisets are unavoidable. A greedy argument starts from a singleton S and adds coordinates while maintaining a multiset difference of size 2, stopping when the multisets agree or no coordinate can be added. Privacy prevents the symbol histograms of (Zib )i∈[n],b∈{0,1} from being too skewed, so the process must end with equal multisets. The proof in Section 6 packages this argument as a topological ordering of an acyclic graph.
3
Lower bounds for general Boolean functions
In this section, we prove Theorem 1.5, restated below. Theorem 1.5. There exists a universal constant c > 0 such that, for every n ≥ 1, there exists f : {0, 1}n → {0, 1} with DRE(f ) ≥ c · n2 . We begin by showing how a perfect DRE locally represents the truth table of f . Lemma 3.1. Fix an arbitrary f : {0, 1}n → {0, 1} and an arbitrary perfect DRE of f with alphabet [K]. There exist functions • DJ,b : [K]J → {0, 1}, where J ⊆ [n] and b ∈ {0, 1}, • Li : {0, 1}n → [K], where i ∈ [n], such that f (x ⊕ J) = DJ,f (x) ((Li (x))i∈J )
holds for all J ⊆ [n] and x ∈ {0, 1}n .
(3.1)
Here x ⊕ J is x with bits in J flipped. Proof. The statement is trivial if f is a constant function. Hence we now assume f −1 (0) and f −1 (1) are both nonempty. Recall Definition 1.2. All Z x with f (x) = 1 (resp., f (x) = 0) have the same distribution Pyes (resp., Pno ) over [K]n . We will construct DJ,1 ’s and Li (x) for x ∈ f −1 (1), i ∈ [n]; the complementary case is analogous. 8
Fix an arbitrary z in the support of Pyes . For each x ∈ f −1 (1), we fix a choice of (Zi0 , Zi1 )i∈[n] with Z x = z and define Li (x) = Zi1−xi . For each J ⊆ [n], define DJ,1 (uJ ) = 1[(z[n]\J , uJ ) is in the support of Pyes ], where 1[E] is the indicator of the event E. Then DJ,1 ((Li (x))i∈J ) = 1[(z[n]\J , (Li (x))i∈J ) is in the support of Pyes ] = 1[(z[n]\J , (Zi1−xi )i∈J ) is in the support of Pyes ] =1
(by the definition of Li (x))
[((Zixi )i∈[n]\J , (Zi1−xi )i∈J ) is in the support of Pyes ]
(by the choice of Z x = z)
= 1[(Z x⊕J ) is in the support of Pyes ] = f (x ⊕ J).
(by the definition of x ⊕ J) (by the correctness of Definition 1.2)
This completes the proof. Lemma 3.1 compresses local neighborhoods: instead of recording every value f (x ⊕ J), it suffices to record the decoders DJ,b and the labels Li (x). We now use this representation to prove Theorem 1.5. Proof of Theorem 1.5. First, if n < 1/c, then the target lower bound is less than n, so any DRE violating the target bound must have a singleton alphabet. Such a DRE can encode only a constant function and the statement naturally holds. Now assume n ≥ 1/c and we will set c > 0 sufficiently small such that n is sufficiently large. Assume for contradiction that DRE(f ) ≤ n2 /4 for all f : {0, 1}n → {0, 1}. By padding dummy alphabet elements, this means every Boolean function has a perfect DRE with alphabet size K = ⌊2n/4 ⌋. Let W ⊆ {0, 1}n be a large set of strings with pairwise Hamming distance at least 5. Note that W can be constructed greedily with size |W | = Ω
2 . n4
n
(3.2)
Define R ⊆ {0, 1}n to be the set of strings of Hamming distance exactly 2 from some string in W . By the definition of W , we have ! n |R| = |W | · . (3.3) 2 We count the possible restrictions to R of the truth tables of all functions f . On the one hand, there are exactly 2|R| . (3.4) On the other hand, we use Lemma 3.1 to provide an upper bound: for each f , we simply record (1) DJ,b for |J| = 2 and b ∈ {0, 1}, (2) Li (x) for i ∈ [n] and x ∈ W , and (3) f (x) for x ∈ W . This upper bounds the number of possibilities by
2K
2
(n)·2 2
· K |W | 9
n
· 2|W | .
Combining with Equations (3.2) to (3.4) and K = ⌊2n/4 ⌋, we have
2
2n/2
(n)·2 2
· 2
|W |·n/4
n
·2
|W |
|W |·(n 2)
≥2
and
|W | = Ω
2 , n4
n
which is impossible for n sufficiently large.
4
Classification of symmetric functions
Recall that for a symmetric function f , we write f (t) for its value on inputs of Hamming weight t. We say that f has period a if f (t) = f (t + a) for every 0 ≤ t ≤ n − a. This section proves Theorem 1.3, restated below. Theorem 1.3. For every integer K ≥ 1, there exist integers NK , aK ≥ 1 such that if n ≥ NK and a symmetric function f : {0, 1}n → {0, 1} has a perfect DRE with alphabet [K], then f has period aK . The proof has three steps. First, we show that f is periodic away from Hamming weights near 0 and n. This is the content of Lemma 4.1, whose proof relies on the local representation in Lemma 3.1. Lemma 4.1. For every integer K ≥ 1, there exist integers BK , aK ≥ 1 such that if a symmetric function f : {0, 1}n → {0, 1} has a perfect DRE with alphabet [K], then f has period aK between Hamming weights BK and n − BK . That is, f (t) = f (t + aK )
holds for all BK ≤ t ≤ n − BK − aK .
Second, we reduce any failure of this pattern at the boundary to the OR function. We use the following closure properties of perfect DREs. Lemma 4.2. Assume f : {0, 1}n → {0, 1} has a perfect DRE with alphabet [K]. • Rearranging. For any permutation π : [n] → [n], fπ : {0, 1}n → {0, 1} has a perfect DRE with alphabet [K], where fπ (x1 , . . . , xn ) := f (xπ(1) , . . . , xπ(n) ). • Reverse. 1 − f has a perfect DRE with alphabet [K]. • Negation. g : {0, 1}n → {0, 1} has a perfect DRE with alphabet [K], where g(x1 , x2 , . . . , xn ) := f (1 − x1 , x2 , . . . , xn ). • Restriction. h : {0, 1}n−1 → {0, 1} has a perfect DRE with alphabet [K], where h(x1 , . . . , xn−1 ) := f (x1 , . . . , xn−1 , 1). • Projection. Partition [n] arbitrarily into m sets E1 , E2 , . . . , Em , each of size at most d. Then F : {0, 1}m → {0, 1} has a perfect DRE with alphabet [K d ], where F (x1 , . . . , xm ) := f (y1 , . . . , yn )
and
The final ingredient is the following lower bound for OR. 10
yi = xj if i ∈ Ej .
Theorem 4.3. For every integer K ≥ 1, there exists an integer nK ≥ 1 such that if ORn has a perfect DRE with alphabet [K], then n ≤ nK . Consequently, DRE(ORn ) = ω(n). We prove Lemma 4.1, Lemma 4.2, and Theorem 4.3 in Sections 4.1 to 4.3, respectively. We now combine these ingredients to prove the classification theorem. Proof of Theorem 1.3. Define NK = aK · (1 + nK aK ) + 2 · BK + aK .
(4.1)
Here nK comes from Theorem 4.3, while aK and BK come from Lemma 4.1. Assume for contradiction that f does not have period aK . By Lemma 4.1, the mismatch can only come from boundary Hamming weights, leading to the following cases. Mismatch from small weights. The periodic interior defines a value for every residue modulo aK . In a residue class with an exception below BK , choose w to be the largest such exception, and put m = ⌊(n − BK − w)/aK ⌋. Then 0 ≤ w < BK and f (w) ̸= f (w + aK ) = f (w + 2 · aK ) = · · · = f (w + m · aK ), where m ≥ nK aK + 1 by Equation (4.1). We will show how to obtain a perfect DRE for ORm . By Lemma 4.2, it suffices to construct ORm from f as follows. • Using Restriction and Negation rules on f , we fix w ones and n−w−aK ·m zeros, which gives a symmetric f ′ : {0, 1}m·aK → {0, 1} satisfying f ′ (0) ̸= f ′ (aK ) = f ′ (2 · aK ) = · · · = f ′ (m · aK ). • Using Projection rule on f ′ , we partition the input bits into blocks of size aK , which gives a symmetric f ′′ : {0, 1}m → {0, 1} satisfying f ′′ (0) ̸= f ′′ (1) = f ′′ (2) = · · · = f ′′ (m). • At this point, f ′′ is either ORm or 1 − ORm , and we simply apply Reverse rule if necessary. By Lemma 4.2, we obtain a perfect DRE for ORm with alphabet [K aK ], which contradicts Theorem 4.3. Mismatch from large weights. Complementing every input bit replaces the weight sequence f (t) by f (n − t) and preserves the common alphabet by Lemma 4.2. A boundary exception above n − BK becomes one below BK , reducing to the preceding case.
4.1
Almost periodicity
To prove Lemma 4.1, we directly define aK = lcm(1, 2, . . . , 2K).
(4.2)
We begin by establishing local periodicity. Lemma 4.4. Let f : {0, 1}n → {0, 1} be symmetric and have a perfect DRE over [K]. For every 0 ≤ u ≤ n − 2K, f has period aK between Hamming weights ℓ and r, where ℓ = u + 2K
and
r =u+1+
n − u − 2K K+1 2
.
Consequently, if 0 ≤ u ≤ n − 2K − K+1 · (2K + aK ), then r ≥ ℓ + aK + 1. 2
11
Proof. The statement is vacuously true if n ≤ 2K; hence we assume n ≥ 2K + 1. Among the 2K + 1 weights between u and u + 2K, at least K + 1 have the same function value in f . Choose u ≤ s0 < s1 < · · · < sK ≤ u + 2K
(4.3)
and b ∈ {0, 1} such that f (sj ) = b for every j. For each t ∈ {s0 , . . . , sK }, let x(t) = 1t 0n−t . Applying Lemma 3.1, we obtain functions • DJ,b : [K]J → {0, 1}, where J ⊆ [n], • Li : {0, 1}n → [K], where i ∈ [n], such that
f (x(t) ⊕ J) = DJ,b (Li (x(t) ))i∈J
holds for all J ⊆ [n] and t ∈ {s0 , . . . , sK }.
(4.4)
Now for each u + 2K + 1 ≤ i ≤ n, the K + 1 symbols Li (x(s0 ) ), . . . , Li (x(sK ) ) must collide. Hence there exist H ⊆ {u + 2K + 1, . . . , n − 1, n} of size |H| ≥
n − u − 2K
(4.5)
K+1 2
and some distinct s, s′ ∈ {s0 , . . . , sK } such that ′
Li (x(s) ) = Li (x(s ) )
for all i ∈ H.
(4.6)
′
Since H ⊆ {u + 2K + 1, . . . , n − 1, n}, we know that both x(s ) and x(s) are all-zero on coordinates in H. Hence for every 0 ≤ p ≤ |H|, we can choose J ⊆ H of size |J| = p and obtain
f (s + p) = f (x(s) ⊕ J) = DJ,b (Li (x(s) ))i∈J (s′ )
= DJ,b (Li (x = f (x
(s′ )
))i∈J
(by Equation (4.4)) (by Equation (4.6))
⊕ J) = f (s′ + p).
(by Equation (4.4))
Without loss of generality, assume s′ < s. This means f has period s − s′ between weights s′ and s + |H|. Since 1 ≤ s − s′ ≤ 2K, it divides aK by Equation (4.2). We may therefore take the period to be aK . In addition, Equations (4.3) and (4.5) and our choice of ℓ, r give s′ ≤ ℓ and r ≤ s + |H|, which completes the proof. We now combine the local intervals to prove Lemma 4.1. Proof of Lemma 4.1. Fix K and set K +1 BK = 2K + · (2K + aK ) . 2 !
The statement is vacuously true if n ≤ BK ; hence we assume n ≥ BK . For each 0 ≤ u ≤ n − BK , we apply Lemma 4.4 and obtain that f has period aK between weights ℓu and ru where ℓu = u + 2K and ru ≥ ℓu + aK + 1 (4.7) Since [ℓu , ru ] ∩ [ℓu+1 , ru+1 ] contains the integer interval [u + 2K + 1, u + 2K + aK + 1], consisting of aK + 1 weights, the period pattern extends. As a result, f has period aK between ℓ0 = 2K ≤ BK
and
rn−BK ≥ n − BK + 2K + aK + 1 ≥ n − BK
as desired. 12
4.2
Reduction between perfect DREs
This subsection proves Lemma 4.2, restated below. Lemma 4.2. Assume f : {0, 1}n → {0, 1} has a perfect DRE with alphabet [K]. • Rearranging. For any permutation π : [n] → [n], fπ : {0, 1}n → {0, 1} has a perfect DRE with alphabet [K], where fπ (x1 , . . . , xn ) := f (xπ(1) , . . . , xπ(n) ). • Reverse. 1 − f has a perfect DRE with alphabet [K]. • Negation. g : {0, 1}n → {0, 1} has a perfect DRE with alphabet [K], where g(x1 , x2 , . . . , xn ) := f (1 − x1 , x2 , . . . , xn ). • Restriction. h : {0, 1}n−1 → {0, 1} has a perfect DRE with alphabet [K], where h(x1 , . . . , xn−1 ) := f (x1 , . . . , xn−1 , 1). • Projection. Partition [n] arbitrarily into m sets E1 , E2 , . . . , Em , each of size at most d. Then F : {0, 1}m → {0, 1} has a perfect DRE with alphabet [K d ], where F (x1 , . . . , xm ) := f (y1 , . . . , yn )
and
yi = xj if i ∈ Ej .
Proof. Fix a perfect DRE of f as in Lemma 4.2. Let Λ be the probability space, and assume that each λ ∈ Λ has nonzero probability mass, so each λ ∈ Λ determines Z(λ) = (Zib (λ))i∈[n],b∈{0,1} in Definition 1.2. As such, the DRE of f given input x is computed by first drawing λ ∈ Λ and then outputting Z x = Z x (λ) deterministically. e Now we handle each reduction separately and provide the corresponding DRE Z. Rearranging.
We rearrange Zejb = Zπb −1 (j) as a perfect DRE of fπ .
Reverse.
We directly set Ze = Z as a perfect DRE of 1 − f .
Negation.
Set Ze1b = Z11−b and Zeib = Zib for i ≥ 2. Then Ze is a perfect DRE of g.
Restriction. Fix an arbitrary λ⋆ ∈ Λ and define q⋆ = Zn1 (λ⋆ ). Then for each λ ∈ Λ with Zn1 (λ) = q⋆ , define Zeib (λ) = Zib (λ) for i ∈ [n − 1]. Then Ze is a perfect DRE of h: given input (x1 , . . . , xn−1 ), the DRE is computed by first drawing λ ∈ Λ conditioned on Zn1 (λ) = q⋆ , and then e outputting Z(λ). To see that Ze is a perfect DRE, we verify conditions in Definition 1.2 directly. ′
′
• If h(x1 , . . . , xn−1 ) = h(x′1 , . . . , x′n−1 ), then Z (x1 ,...,xn−1 ,1) and Z (x1 ,...,xn−1 ,1) are identically distributed. Conditioning both on their last coordinate being q⋆ preserves this equality in distribution. After deleting that coordinate, the resulting distributions are precisely Ze (x1 ,...,xn−1 ) and ′ ′ Ze (x1 ,...,xn−1 ) . ′
′
• If the two values of h differ, correctness implies that Z (x1 ,...,xn−1 ,1) and Z (x1 ,...,xn−1 ,1) have disjoint supports. Because their last coordinates both equal q⋆ after conditioning, their first n − 1 coordinates must differ. Thus the corresponding values of Ze also have disjoint supports. 13
Projection.
For each Ej and b ∈ {0, 1}, group the corresponding local messages into Zejb = (Zib )i∈Ej .
This is a string in [K]|Ej | and we naturally embed it as a number in [K d ] since |Ej | ≤ d. To see that Ze is a perfect DRE of F , for each x ∈ {0, 1}m we observe that Ze x is simply another way of writing Z y , where y ∈ {0, 1}n is given by yi = xj when i ∈ Ej . Hence in light of Definition 1.2, all desired properties of Ze follow directly from those of Z.
4.3
Lower bounds for OR
We now prove the remaining ingredient for Theorem 1.3: a superlinear DRE lower bound for ORn . Theorem 4.3. For every integer K ≥ 1, there exists an integer nK ≥ 1 such that if ORn has a perfect DRE with alphabet [K], then n ≤ nK . Consequently, DRE(ORn ) = ω(n). Theorem 4.3 follows from two lemmas. The first extracts a local anti-embedding family from a perfect DRE, and the second gives a purely combinatorial bound on the dimension of such a family. Lemma 4.5. Assume ORn has a perfect DRE over alphabet [K]. Then there exists a family of strings pS ∈ [K]n , indexed by S ⊆ [n], such that the following holds. • pJJ ̸= pL J for every ∅ ̸= J ⊊ L ⊆ [n]. • pSi = p∅i for every S ⊆ [n] and i ∈ / S. Lemma 4.6. For every integer K ≥ 1, there exists an integer nK ≥ 1 such that if the family of strings in Lemma 4.5 exists, then n ≤ nK . We prove these lemmas in Sections 4.3.1 and 4.3.2, respectively. Proof of Theorem 4.3. Simply combine Lemma 4.5 and Lemma 4.6. 4.3.1
Local anti-embedding family
To prove Lemma 4.5, we fix an arbitrary perfect DRE of ORn with alphabet [K]. For simplicity, we use Λ to denote the probability space of the DRE and assume that each λ ∈ Λ has nonzero probability mass, so each λ determines Z(λ) = (Zib (λ))i∈[n],b∈{0,1} in Definition 1.2. As such, the DRE of ORn given input x is computed by first drawing λ ∈ Λ and then outputting Z x = Z x (λ) deterministically. We start with the following simple observation. Lemma 4.7. For every i ∈ [n] and λ ∈ Λ, we have Zi0 (λ) ̸= Zi1 (λ). Consequently, K ≥ 2. n
Proof. If Zi0 (λ) = Zi1 (λ), then Z 0 (λ) = Z ei (λ) where ei is the indicator vector of i. Since ORn (0n ) = 0 and ORn (ei ) = 1, this violates the correctness property of Definition 1.2. We will upgrade the above pointwise separation to a stronger local anti-embedding property. This crucially requires us to move between different λ’s in Λ. By Definition 1.2, all Z x with x ∈ {0, 1}n \ {0n } have the same distribution Pyes , whose support n is disjoint from that of Pno , the distribution of Z 0 . Fix an arbitrary transcript (q1 , . . . , qn )
in the support of Pyes . 14
For each ∅ = ̸ S ⊆ [n], we use eS ∈ {0, 1}n to denote the indicator vector of S and choose an arbitrary λS ∈ Λ such that Z eS (λS ) = q. Define n
pS = Z 0 (λS ),
(4.8)
which is in the support of Pno . Lemma 4.8 (Local anti-embedding). For every ∅ ̸= S ⊆ [n] and i ∈ [n], we have pSi = qi
if and only if i ∈ / S.
(4.9)
Moreover, if ∅ ̸= J ⊊ L ⊆ [n], then pJJ ̸= pL J. Proof. If i ∈ / S, then the ith coordinate of eS is 0, which, by Equation (4.8), means
n
pSi = Z 0 (λS )
i
= Zi0 (λS ) = (Z eS (λS ))i = qi .
If i ∈ S, then similarly we have Zi1 (λS ) = qi and, by Lemma 4.7, pSi = Zi0 (λS ) ̸= qi . This proves Equation (4.9). For the “moreover” part, assume for contradiction that pJJ = pL J . Define B = L \ J, which is a nonempty set. We will show that Z eB (λL ) = pJ ; this violates the correctness of Definition 1.2 since ORn (eB ) = 1 yet pJ is in the support of Pno . To see this, we divide i ∈ [n] into cases. / L, then (Z eB (λL ))i = Zi0 (λL ) = (Z eL (λL ))i = qi . By Equation (4.9), we have pJi = qi and • If i ∈ hence (Z eB (λL ))i = pJi . • If i ∈ B, then (Z eB (λL ))i = Zi1 (λL ) = (Z eL (λL ))i = qi . By Equation (4.9), we have pJi = qi and hence (Z eB (λL ))i = pJi . L J eB • If i ∈ J, then (Z eB (λL ))i = Zi0 (λL ) = pL i . Since we assumed pJ = pJ , we also have (Z (λL ))i = L J pi = pi .
This completes the proof. To summarize, any perfect DRE of ORn can be turned into a family of strings with anti-embedding structure. This readily proves Lemma 4.5. Proof of Lemma 4.5. Construct pS with Equation (4.8) and define p∅ = q. Then the desired properties follow from Lemma 4.8. 4.3.2
Finiteness of local anti-embedding family
The proof of Lemma 4.6 uses three standard infinitary results. Lemma 4.9 (Kőnig’s infinity lemma [Kőn27]). Every infinite rooted tree in which each vertex has finitely many children contains an infinite path starting at the root. Lemma 4.10 (Infinite hypergraph Ramsey theorem [Ram30]). Let4 H ⊆ N+ be an arbitrary infinite set. For all integers s, r ≥ 1, every coloring of the size-s subsets of H with r colors has an infinite set H ′ ⊆ H all of whose size-s subsets have the same color. Lemma 4.11 (Higman’s lemma [Hig52]). Let Σ be a finite alphabet. For every infinite sequence w1 , w2 , . . . from Σ∗ , there are indices a < b such that wa is a subsequence5 of wb . 4 5
We use N+ = {1, 2, . . .} to denote the set of positive integers. That is, wa can be obtained from wb by deleting symbols.
15
We now prove Lemma 4.6. Quantitative versions of the preceding results yield an explicit bound [ER52, SS11], but it is not primitive recursive. n
Proof of Lemma 4.6. Observe that any valid family of strings pS
o
in Lemma 4.5 of dimension
S⊆[n] n naturally gives valid families of smaller dimensions n′ < n, simply by discarding pS if S ̸⊆ [n′ ] and
n
truncating pS to the first n′ coordinates if S ⊆ [n′ ]. For convenience, we write rS
o
n
≺ pS ′
S⊆[n ]
o
S⊆[n]
if the former family is derived from the latter by the method described. Assume for contradiction that Lemma 4.6 is false. By the discussion above, valid families exist in every dimension n ≥ 1. Given this, we construct a finitely branching rooted forest as follows: for each valid family of dimension n, we create a tree vertex at depth n; then we connect two vertices if their dimensions differ by 1 and they the ≺ relation above. That is, consider two n exactly o n satisfy o S S vertices labeled by R = r and P = p respectively; then R is the parent vertex of ′ S⊆[n ]
S⊆[n]
P if and only if n′ = n − 1 and R ≺ P. The forest has finitely many roots, and, because [K] is finite, each vertex has finitely many children. Hence we can apply Lemma 4.9 and find an infinite path P1 ≺ P2 ≺ P3 ≺ · · · starting at some depth-1 vertex P1 , where each Pd is a valid family of dimension d. We next use this path to define a coloring χ on all nonempty finite subsets of N+ . For each such S, choose any integer d sufficiently large such that d ≥ maxi∈S i and let pS,d ∈ Pd be the string from Pd indexed by S. Define |S| χ(S) = pS,d S ∈ [K] , which lists the symbols on coordinates S in increasing coordinate order. By the ≺ relation defined above, χ(S) does not depend on the choice of d. Observe that for fixed s, the coloring χ(S) on |S| = s has finitely many colors. Hence we can sequentially apply Lemma 4.10 and homogenize as follows: we start with s = 1. By Lemma 4.10, we find an infinite H1 ⊆ N+ and a color c1 ∈ [K] such that χ(S) = c1 for every size-1 set S ⊆ H1 . Then sequentially for s ≥ 2, we apply Lemma 4.10 to find an infinite Hs ⊆ Hs−1 and a color cs ∈ [K]s such that χ(S) = cs for every size-s set S ⊆ Hs . At this point, we can obtain an infinite sequence c1 , c2 , . . . from [K]∗ . By Lemma 4.11, there ′ exist indices d′ < d such that cd′ ∈ [K]d is a subsequence of cd ∈ [K]d . Choose indices 1 ≤ j1 < · · · < jd′ ≤ d witnessing this subsequence embedding. Take any S = {i1 < · · · < id } ⊂ Hd , set S ′ = {ij1 , . . . , ijd′ }, and choose D ≥ max S. Since Hd ⊆ Hd′ , we have ′
pSS ′ ,D = cd′
is a subsequence of
pS,D = cd . S
′
′
S ,D and pS,D are strings By the choice of the positions j1 , . . . , jd′ , this gives pSS ′ ,D = pS,D S ′ . Since p from the valid family PD , this contradicts the first property in Lemma 4.5, which completes the proof.
5
Statistical and probabilistic extensions
This section proves the statistical and probabilistic extensions stated in Section 1.1.2. We begin with statistical DREs. For distributions µ, ν, let dTV (µ, ν) denote their total variation distance. Definition 5.1 (Statistical decomposable randomized encoding). Let f : {0, 1}n → {0, 1}. A statistical DRE of f consists of possibly correlated random variables (Zib )i∈[n],b∈{0,1} , each taking values in a finite alphabet [K], together with two distributions Pyes , Pno over [K]n . On input x, the encoding is the random vector Z x = (Zixi )i∈[n] ∈ [K]n . 16
The correctness error δ is defined as δ = 1 − dTV (Pyes , Pno ). The privacy error η is defined as (
η = max
)
max dTV (µx , Pyes ), max dTV (µx , Pno ) ,
x∈f −1 (1)
x∈f −1 (0)
where µx is the distribution of Z x . The size of the DRE is n log K as in Definition 1.2. A statistical DRE is perfect exactly when δ = η = 0. Remark 5.2. The definitions in [AIK06, AIKPC15] use a decoder and a simulator. Ignoring computational efficiency, let δdec be the minimum worst-case decoding error and ηsim the minimum simulator-based privacy error. For nonconstant f and any fixed reference distributions in Definition 5.1, max{0, δ/2 − η} ≤ δdec ≤ δ + η. For the upper bound, the likelihood-ratio test on Pyes , Pno has the sum of its two reference errors equal to δ; replacing a reference distribution by µx increases the corresponding error by at most η. Conversely, a decoder with worst-case error e on the actual encodings has error at most e + η on each reference distribution, so δ ≤ 2(e + η). For constant f , δdec = 0. The reference distributions themselves define a simulator with error η, so ηsim ≤ η; minimizing η over the references gives exactly ηsim . This optimization can change δ. We use Definition 5.1 because the reference distributions Pyes , Pno simplify the proofs.
5.1
Average-case lower bounds for general Boolean functions
We now prove Theorem 1.8, a robust, high-probability version of Theorem 1.5. Theorem 1.8. For every δ̄, η̄ ∈ [0, 1] with δ̄ + 2 · η̄ < 1/2, there is cδ̄,η̄ > 0 such that the following holds. For a uniformly random Boolean function f : {0, 1}n → {0, 1}, except with probability at most n
2
2−cδ̄,η̄ ·2 /n , every statistical DRE of f with correctness error δ ≤ δ̄ and privacy error η ≤ η̄ has size at least cδ̄,η̄ · n2 . Proof. The proof largely follows the structure of the proof of Theorem 1.5. First, assume n ≥ 1/cδ̄,η̄ , where we set cδ̄,η̄ ∈ (0, 1/2] later. If n < 1/cδ̄,η̄ , then the target lower bound is less than n, so any DRE violating the target bound must have a singleton alphabet. Such a DRE can encode only a constant n n 2 n n function, and the two constant functions constitute a 2 · 2−2 ≤ 2−2 /2 ≤ 2−cδ̄,η̄ ·2 ≤ 2−cδ̄,η̄ ·2 /n fraction of all Boolean functions, as claimed. 1 Define θ = δ̄ + 2η̄ < 1/2 and its binary entropy H(θ) = θ log 1θ + (1 − θ) log 1−θ , with n H(0) = 0 by continuity. Choose 0 < c < 1/2 such that H(θ) + 2c < 1. Fix sets W, R ⊆ {0, 1} as in the proof of Theorem 1.5 such that every point of R has a unique representation x ⊕ J with x ∈ W and |J| = 2. In addition, ! n 2 n |W | = Ω and |R| = |W | . (5.1) n4 2 17
Fix a function f having a statistical DRE with the stated error bounds and size at most c · n2 . We again use Λ for its probability space; the encoding Z(λ) = (Zib (λ))i∈[n],b∈{0,1} is deterministic once λ ∈ Λ is fixed. By padding, we assume its alphabet is [K], where K = ⌈2cn ⌉. Let A = {z : Pyes (z) > Pno (z)} ⊆ [K]n , which witnesses the total variation distance between Pyes and Pno . Sample Y1 ∼ Pyes and Y0 ∼ Pno . For every x ∈ W , the definition of η allows us to couple λx ∼ Λ with Yf (x) such that Pr[Z x (λx ) ̸= Yf (x) ] ≤ η̄. All these couplings can be realized simultaneously: after sampling Y0 , Y1 , sample each λx from its coupling’s conditional distribution given Yf (x) . Each λx retains the original randomness distribution as its marginal. Define Li (x) = Zi1−xi (λx ). For each J ⊆ [n] with |J| = 2 and b ∈ {0, 1}, define DJ,b : [K]J → {0, 1} by letting DJ,b (uJ ) = 1 ((Yb )[n]\J , uJ ) is in A . h
i
In Theorem 1.5, we always have DJ,f (x) ((Li (x))i∈J ) = f (x ⊕ J). Here, because of the statistical error, the prediction DJ,f (x) ((Li (x))i∈J ) for f (x ⊕ J) can be wrong only 1. if Z x (λx ) ̸= Yf (x) , which has probability at most η̄; 2. if Z x⊕J (λx ) lies on the wrong side of A. This has probability at most δ̄ + η̄, where δ̄ comes from the definition of A and η̄ comes from the distance between Z x⊕J and the corresponding Pyes , Pno . Thus for each x and J, we have h
i
Pr DJ,f (x) ((Li (x))i∈J ) ̸= f (x ⊕ J) ≤ δ̄ + 2 · η̄ = θ < 1/2, which means the average fraction of decoding errors over R, using W and DJ,b ’s, is at most θ. Fix all random choices so that this bound holds. We then need only record a correction pattern affecting at most a θ fraction of R; the number of such patterns is at most |R| ≤ θ|R|
!
≤ 2H(θ)·|R|
possibilities. As in the proof of Theorem 1.5, the total number of possible descriptions is at most
2K
2
2(n) 2
· K |W |
n
· 2|W | · 2H(θ)|R| = 2|R|·β ,
where 2K 2 n2 |W | n|W | log K β = H(θ) + + + |R| |R| |R| 2 n log K 2K 1 = H(θ) + n + + n |W | 2 2
= H(θ) + 2c + o(1).
(by Equation (5.1))
(since K = ⌈2cn ⌉, c < 1/2, and |W | = Ω
n 2 n4
)
Since H(θ) + 2c < 1, for n ≥ n⋆ sufficiently large, we have β < 1 and the fraction of truth tables on n 2 R admitting such a description is therefore at most 2−(1−β)·|R| ≤ 2−γ·2 /n , where γ is a constant depending on θ and c. Since both γ and n⋆ depend only on θ, c, which in turn depend only on δ̄, η̄, it suffices to define cδ̄,η̄ = min {1/2, γ, c, 1/n⋆ } and this completes the proof. 18
5.2
Symmetric classification with statistical error
We next prove Theorem 1.6, the robust version of Theorem 1.3. Theorem 1.6. For every integer K ≥ 1, there exist εK ∈ (0, 1] and integers NK , aK ≥ 1 such that the following holds. Assume n ≥ NK and a symmetric function f : {0, 1}n → {0, 1} has a statistical DRE with alphabet [K], correctness error δ, and privacy error η. If δ + η ≤ εK , then f has period aK . The proof follows the same roadmap as the perfect case, with robust substitutes for its two structural lemmas. Lemma 5.3 (Statistical version of Lemma 4.2). Assume f : {0, 1}n → {0, 1} has a statistical DRE with alphabet [K], correctness error δ, and privacy error η. The following transformations from Lemma 4.2 remain valid: • The Rearranging, Reverse, Negation, and Projection rules preserve both error bounds. • The Restriction rule preserves both error bounds at the cost of a larger alphabet: fixing any s < n input bits yields a statistical DRE with alphabet [K s+1 ]. Proof. The proof is almost identical to that of Lemma 4.2. For Restriction, append the encoding of the s fixed input bits to an unrestricted input bit, which now has alphabet [K]s+1 ∼ = [K s+1 ]. The new encoding is an injective rewriting of the original one on the restricted subcube. Lemma 5.4 (Statistical version of Lemma 3.1). Fix an arbitrary f : {0, 1}n → {0, 1} and a statistical DRE of f with alphabet [K], correctness error δ, and privacy error η. For any X ⊆ {0, 1}n and J ⊆ 2[n] , if |X| · (1 + |J |) · (δ + η) < 1, then there exist functions • DJ,b : [K]J → {0, 1}, where J ∈ J and b ∈ {0, 1}, • Li : {0, 1}n → [K], where i ∈ [n], such that f (x ⊕ J) = DJ,f (x) ((Li (x))i∈J ) holds for all J ∈ J and x ∈ X. Proof. The proof is essentially contained in the proof of Theorem 1.8 above. Using the constructions of DJ,b ’s and Li ’s there, we have h
i
Pr ∃x ∈ X, J ∈ J , DJ,f (x) ((Li (x))i∈J ) ̸= f (x ⊕ J)
≤ Pr [one of the events in Items 1 and 2 occurs for some x ∈ X, J ∈ J ] ≤ |X| · η + |X| · |J | · (δ + η) ≤ |X| · (1 + |J |) · (δ + η) < 1. Hence there exists a choice that establishes the statement. We can now prove Theorem 1.6. Proof of Theorem 1.6. We only highlight the necessary changes to the proof of Theorem 1.3. We first argue that f must have period aK between Hamming weights BK and n − BK , where aK , BK are properly chosen as in Lemma 4.1. This part uses the same proof strategy of gluing short periodic intervals together. The only change lies in the proof of Lemma 4.4: we will replace 19
Lemma 3.1 with Lemma 5.4 and need only ensure Equation (4.4) for all subsets J of6 OK (1) coordinates. The key point is that the proof of Lemma 4.1 only needs the local intervals in Lemma 4.4 to have length at least aK + 1, so they can overlap on an interval of length aK to transfer the periodic pattern. The next step is to embed a large OR function, witnessing the mismatch from boundary Hamming weights. We simply use Lemma 5.3 in place of Lemma 4.2 for the reduction. The key observation is that, although the Restriction rule in Lemma 5.3 now blows up the alphabet size, we only need to restrict OK (1) input bits, since we have already established periodicity between weights BK and n − BK . Finally we need a lower bound for OR: a statistical version of Theorem 4.3. For this purpose, we simply use Lemma 5.4 to mimic the proof of Lemma 4.5 and obtain a local anti-embedding family of dimension OK (1). By ensuring that this dimension is sufficiently large, the desired lower bound follows from Lemma 4.6.
6
Tight structured lower bound for OR
This section proves Theorem 1.9, providing evidence toward Conjecture 1.10 under a structural assumption. Fix a perfect DRE Z = (Zib )i∈[n],b∈{0,1} of ORn with alphabet [K]. Let Pyes denote the distribution n of Z x for any x = ̸ 0n , and let Pno denote the distribution of Z 0 . We say that the DRE has symmetric support on input 0n if, whenever z ∈ [K]n lies in the support of Pno , every coordinate permutation of z also lies in the support. Theorem 1.9. Every perfect DRE of ORn with symmetric support on input 0n has size Ω(n log n). We first record an elementary consequence of privacy. Lemma 6.1. If I ⊊ [n], then (Ziyi )i∈I has the same distribution for every y ∈ {0, 1}I . Proof. Extend each y to some x ∈ {0, 1}n by setting the remaining bits to 1. Hence each Z x has the same distribution Pyes , which remains the same by taking the marginal on I. For z ∈ [K]∗ and c ∈ [K], let hc (z) be the number of occurrences of c in z, and write h(z) = (hc (z))c∈[K] for the histogram of z. Proof of Theorem 1.9. We will prove a quantitative bound K = Ω(n1/3 ), which translates to the size lower bound n log K = Ω(n log n). We may assume n is even. Indeed, if n is odd, fix the last input to zero and condition on any positive-probability value q of its encoding, as in the restriction proof of Lemma 4.2. Deleting that coordinate gives a perfect DRE of ORn−1 over the same alphabet. Its zero-input support is symmetric: any permutation of the remaining coordinates extends to a permutation fixing the last coordinate, so it preserves both the original zero-input support and the conditioning event. Replacing n by n − 1 does not affect the asymptotic bound. Choose a uniformly random S ⊂ [n] of size n/2 and write S̄ = [n] \ S. For each c ∈ [K], let tc = hc ((Zi1 )i∈[n] ), 6
and
Dc = hc ((Zi1 )i∈S ) − hc ((Zi1 )i∈S̄ ).
We use OK (1) to denote any constant depending only on K.
20
A simple calculation shows, for fixed Z and random S, we have E[Dc ] = 0, which means ES |Dc | ≤ E S
√
tc (n − tc ) ≤ tc , n−1
tc and
h((Zi1 )i∈S ) − h((Zi1 )i∈S̄ )
Hence
Var(Dc ) =
1
=
X
X √
E |Dc | ≤
c∈[K]
S
s
tc ≤
K
Z,S
1
≤
tc =
√ Kn.
c
c∈[K]
E h((Zi1 )i∈S ) − h((Zi1 )i∈S̄ )
X
√ Kn.
n
For every fixed S, we know that Z eS̄ and Z 1 have the same distribution Pyes . Hence the above analysis also shows √ E h((Zi0 )i∈S ) − h((Zi1 )i∈S̄ ) ≤ Kn. 1
Z,S
By the triangle inequality, we have E h((Zi0 )i∈S ) − h((Zi1 )i∈S )
Z,S
1
√ ≤ 2 Kn.
(6.1)
√ Fix Z and S for which the norm inside the expectation in Equation (6.1) is at most 2 Kn. Construct a directed multigraph G on [K] with n/2 edges: for each i ∈ S, we add an edge from Zi0 to Zi1 . By Lemma 4.7, G has no self-loops. Since our DRE has symmetric support on input 0n , G cannot have a directed cycle. To see this, a directed cycle indexed by T ⊆ S has equal source and n target multisets, which means Z eT is equivalent to Z 0 up to permutation. The assumed symmetry also puts Z eT in the support of Pno , which contradicts the correctness property in Definition 1.2. The acyclicity of G defines a topological order ρ : [K] −→ {0, 1, . . . , K − 1} that strictly increases along every edge. Hence n X ≤ ρ(Zi1 ) − ρ(Zi0 ) . 2 i∈S On the other hand, since 0 ≤ ρ(c) ≤ K − 1 for every c ∈ [K], (ρ(Zi1 ) − ρ(Zi0 )) =
X
X
i∈S
c∈[K]
ρ(c) · hc ((Zi1 )i∈S ) − hc ((Zi0 )i∈S )
≤ K · h((Zi1 )i∈S ) − h((Zi0 )i∈S ) 1 3/2 √ ≤ 2K n.
(by Equation (6.1))
This gives K = Ω(n1/3 ) by rearranging.
References [AHMS20] Benny Applebaum, Thomas Holenstein, Manoj Mishra, and Ofer Shayevitz. The communication complexity of private simultaneous messages, revisited. Journal of Cryptology, 33(3):917–953, 2020. doi:10.1007/s00145-019-09334-y. [AIK06]
Benny Applebaum, Yuval Ishai, and Eyal Kushilevitz. Cryptography in NC0 . SIAM Journal on Computing, 36(4):845–888, 2006. doi:10.1137/S0097539705446950. 21
[AIKPC15] Shweta Agrawal, Yuval Ishai, Dakshita Khurana, and Anat Paskin-Cherniavsky. Statistical randomized encodings: A complexity theoretic view. In 42nd International Colloquium on Automata, Languages, and Programming (ICALP), Part I, volume 9134 of Lecture Notes in Computer Science, pages 1–13, 2015. doi: 10.1007/978-3-662-47672-7_1. [AL21]
Léonard Assouline and Tianren Liu. Multi-party PSM, revisited: Improved communication and unbalanced communication. In Theory of Cryptography Conference (TCC), Part III, volume 13043 of Lecture Notes in Computer Science, pages 194–223, 2021. doi:10.1007/978-3-030-90453-1_7.
[App17]
Benny Applebaum. Garbled circuits as randomized encodings of functions: a primer. In Yehuda Lindell, editor, Tutorials on the Foundations of Cryptography, pages 1–44. Springer International Publishing, 2017. doi:10.1007/978-3-319-57048-8_1.
[Bar89]
David A. Mix Barrington. Bounded-width polynomial-size branching programs recognize exactly those languages in NC1 . Journal of Computer and System Sciences, 38(1):150– 164, 1989. doi:10.1016/0022-0000(89)90037-8.
[BGI+ 14]
Amos Beimel, Ariel Gabizon, Yuval Ishai, Eyal Kushilevitz, Sigurd Meldgaard, and Anat Paskin-Cherniavsky. Non-interactive secure multiparty computation. In Advances in Cryptology—CRYPTO 2014, Part II, volume 8617 of Lecture Notes in Computer Science, pages 387–404, 2014. Full version: Cryptology ePrint Archive, Report 2014/960. URL: https://eprint.iacr.org/2014/960, doi:10.1007/978-3-662-44381-1_22.
[BHI+ 20]
Marshall Ball, Justin Holmgren, Yuval Ishai, Tianren Liu, and Tal Malkin. On the complexity of decomposable randomized encodings, or: How friendly can a garblingfriendly PRF be? In 11th Innovations in Theoretical Computer Science Conference (ITCS 2020), volume 151 of Leibniz International Proceedings in Informatics (LIPIcs), pages 86:1–86:22, 2020. doi:10.4230/LIPIcs.ITCS.2020.86.
[BHR12]
Mihir Bellare, Viet Tung Hoang, and Phillip Rogaway. Foundations of garbled circuits. In Proceedings of the 2012 ACM Conference on Computer and Communications Security, CCS ’12, pages 784–796, New York, NY, USA, 2012. Association for Computing Machinery. doi:10.1145/2382196.2382279.
[BKN18]
Amos Beimel, Eyal Kushilevitz, and Pnina Nissim. The complexity of multiparty PSM protocols and related models. In Advances in Cryptology—EUROCRYPT 2018, Part II, volume 10821 of Lecture Notes in Computer Science, pages 287–318, 2018. doi:10.1007/978-3-319-78375-8_10.
[CL94]
Jin-Yi Cai and Richard J. Lipton. Subquadratic simulations of balanced formulae by branching programs. SIAM Journal on Computing, 23(3):563–572, 1994. doi: 10.1137/S0097539790181336.
[ER52]
Paul Erdős and Richard Rado. Combinatorial theorems on classifications of subsets of a given set. Proceedings of the London Mathematical Society, 2(1):417–439, 1952. Series 3. doi:10.1112/plms/s3-2.1.417.
[FKN94]
Uriel Feige, Joe Kilian, and Moni Naor. A minimal model for secure computation (extended abstract). In Proceedings of the 26th Annual ACM Symposium on Theory of Computing (STOC), pages 554–563, 1994. doi:10.1145/195058.195408. 22
[GKM+ 26] Daniel Grier, Daniel M. Kane, Jackson Morris, Anthony Ostuni, and Kewen Wu. Quantum advantage from sampling shallow circuits: Beyond hardness of marginals. In 17th Innovations in Theoretical Computer Science Conference (ITCS 2026), volume 362 of Leibniz International Proceedings in Informatics (LIPIcs), 2026. Article 73. doi:10.4230/LIPIcs.ITCS.2026.73. [Hås14]
Johan Håstad. On the correlation of parity and small-depth circuits. SIAM J. Comput., 43(5):1699–1708, 2014. doi:10.1137/14095610X.
[HE26]
Keitaro Hiwatashi and Reo Eriguchi. Ideal private simultaneous messages schemes and their applications. In 17th Innovations in Theoretical Computer Science Conference (ITCS 2026), volume 362 of Leibniz International Proceedings in Informatics (LIPIcs), 2026. Article 76. doi:10.4230/LIPIcs.ITCS.2026.76.
[Hig52]
Graham Higman. Ordering by divisibility in abstract algebras. Proceedings of the London Mathematical Society, 2(1):326–336, 1952. Series 3. doi:10.1112/plms/s3-2.1.326.
[IK97]
Yuval Ishai and Eyal Kushilevitz. Private simultaneous messages protocols with applications. In Proceedings of the 5th Israel Symposium on Theory of Computing and Systems (ISTCS), pages 174–184, 1997. doi:10.1109/ISTCS.1997.595170.
[Ish13]
Yuval Ishai. Randomization techniques for secure computation. In Manoj Prabhakaran and Amit Sahai, editors, Secure Multi-Party Computation, volume 10 of Cryptology and Information Security Series, pages 222–248. IOS Press, 2013. doi:10.3233/ 978-1-61499-169-4-222.
[Kil88]
Joe Kilian. Founding cryptography on oblivious transfer. In Proceedings of the 20th Annual ACM Symposium on Theory of Computing (STOC), pages 20–31, 1988. doi: 10.1145/62212.62215.
[Kőn27]
Dénes Kőnig. Über eine schlussweise aus dem endlichen ins unendliche. Acta Litterarum ac Scientiarum Regiae Universitatis Hungaricae Francisco-Josephinae, Sectio Scientiarum Mathematicarum, 3:121–130, 1927.
[KOW25]
Daniel M. Kane, Anthony Ostuni, and Kewen Wu. Locally sampleable uniform symmetric distributions. In Proceedings of the 57th Annual ACM Symposium on Theory of Computing (STOC), pages 1807–1816, 2025. doi:10.1145/3717823.3718243.
[Ram30]
Frank P. Ramsey. On a problem of formal logic. Proceedings of the London Mathematical Society, 30(1):264–286, 1930. Series 2. doi:10.1112/plms/s2-30.1.264.
[Sim82]
Hans-Ulrich Simon. A tight Ω(log log n)-bound on the time for parallel RAM’s to compute nondegenerated Boolean functions. Information and Control, 55(1–3):102–106, 1982. doi:10.1016/S0019-9958(82)90477-6.
[SN24]
Kazumasa Shinagawa and Koji Nuida. Explicit lower bounds for communication complexity of PSM for concrete functions. In Progress in Cryptology—INDOCRYPT 2023, Part II, volume 14460 of Lecture Notes in Computer Science, pages 45–61. Springer, 2024. doi:10.1007/978-3-031-56235-8_3.
[SS11]
Sylvain Schmitz and Philippe Schnoebelen. Multiply-recursive upper bounds with Higman’s lemma. In 38th International Colloquium on Automata, Languages and 23
Programming (ICALP), Part II, volume 6756 of Lecture Notes in Computer Science, pages 441–452, 2011. doi:10.1007/978-3-642-22012-8_35. [SSW+ 20]
Xiaoming Sun, Yuan Sun, Jiaheng Wang, Kewen Wu, Zhiyu Xia, and Yufan Zheng. On the degree of Boolean functions as polynomials over Zm . In 47th International Colloquium on Automata, Languages, and Programming (ICALP), volume 168 of Leibniz International Proceedings in Informatics (LIPIcs), 2020. Article 100. doi: 10.4230/LIPIcs.ICALP.2020.100.
[Yao86]
Andrew Chi-Chih Yao. How to generate and exchange secrets. In 27th Annual Symposium on Foundations of Computer Science (FOCS 1986), pages 162–167. IEEE, 1986. doi: 10.1109/SFCS.1986.25.
[Yos24]
Maki Yoshida. Towards optimal non-interactive secure multiparty computation for Abelian programs. In IEEE International Symposium on Information Theory (ISIT), pages 1878–1882, 2024. doi:10.1109/ISIT57864.2024.10619511.
24