Upper Bounds for Symmetric Approximate Bounded Indistinguishability

Christopher Williamson · 2026

Read Upper Bounds for Symmetric Approximate Bounded Indistinguishability by Christopher Williamson (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-13771.txt.

Introduction

Christopher Williamson studies even bounded match via hyper smoothing and Hahn polys. Two spreads over binary strings are (k,delta)-wise matching when all size-k parts sit within chance gap delta. Prior work left open whether (c n,0)-wise matching pairs could have c-prime n-wise parts staying far apart. His upper bound shows those parts must be fast close for all c and c-prime, joining and lifting prior bounds across wider settings. The approach uses Hahn poly ways under hyper sampling and trimming.

Catalog record

CREATORChristopher Williamson
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE31350
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2605.13771

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Upper Bounds for Symmetric Approximate Bounded Indistinguishability Christopher Williamson Abstract A pair of probability distributions over { 0 , 1 } n \{0,1\}^{n} is said to be ( k , δ ) (k,\delta) -wise indistinguishable if all of the size k k marginals are within statistical distance at most δ \delta . Previous works introduced this concept and study when and how well one can distinguish between such a pair of symmetric distributions by observing t t bits. We use a simple hypergeometric smoothing approach and Hahn polynomials to obtain new upper bounds that apply across a wider range of parameters and improve previously available bounds in several regimes. In particular, prior works left open the basic question of whether there exist constants 0 < c 1 < c 2 < 1 0<c_{1}<c_{2}<1 and a pair of ( c 1 ​ n , 0 ) (c_{1}n,0) -wise indistinguishable distributions such that the c 2 ​ n c_{2}n -wise marginals have statistical distance Ω ⁡ ( 1 ) \Omega(1) . One application of our new bounds is to rule this out for all c 1 , c 2 c_{1},c_{2} and to show that the c 2 ​ n c_{2}n -wise marginals must in fact be exponentially close. Another application in this setting is to show that the c 2 ​ n c_{2}n -wise marginals must be super-polynomially close even if the c 1 ​ n c_{1}n -wise marginals are allowed to have statistical distance δ \delta for any δ ≤ exp ⁡ ( − ω ⁡ ( n ​ log ⁡ n ) ) \delta\leq\exp\left({-\omega(\sqrt{n\log{n}})}\right) . Our bounds also yield new results in other regimes, for example when k k is sublinear or when t / n t/n tends to 1. 1 Introduction We consider pairs of distributions ( \mu,\nu ) over \{0,1\}^{n} . The distributions \mu and \nu are said to be (k,\delta) -wise indistinguishable if for any subset S\subseteq[n] of size at most k , the marginal distributions \mu_{S} and \nu_{S} over indices in S are of statistical distance at most \delta . The distributions are t -wise reconstructible with advantage \epsilon if there exists a set S\subseteq[n] of indices of size t and a statistical test T:\{0,1\}^{t}\to\{0,1\} such that \left|\mathbb{E}_{X\sim\mu}[T(X_{S})]-\mathbb{E}_{Y\sim\nu}[T(Y_{S})]\right|\geq\epsilon, where X_{S} is the restriction of random variable X to the bits located at the indices in S . The distributions are symmetric if \mu and \nu are invariant under permutation (see Section 2.2 ); for such distributions the size of S is relevant but not the choice of indices. Cryptographic motivation. Work of Bogdanov et al. [ 1 , 3 ] considered this notion of indistinguishability as a way to capture cryptographic secret sharing schemes in a minimal setting. Their observation was that a single bit secret can be shared by sampling n bits from \mu or from \nu , depending on the secret: (k,0) -wise indistinguishability of the distributions provides a security guarantee that any size \leq k coalition of colluding parties learns nothing about the secret from their joint shares. The secret reconstruction function for the scheme is a test T applied over the shares of sufficiently many (possibly all) parties. Their work proves the existence of distributions over \Sigma^{n} where \Sigma consists of bit strings of length polynomial in n . In this work we only consider distributions over \{0,1\}^{n} . The special case of T=\mathrm{OR} captures the notion of visual cryptography, introduced by Naor and Shamir [ 7 ] in 1994. Their work considered (k,0) -wise indistinguishable distributions and attempted to maximise the reconstruction advantage of \mathrm{OR} taken over k+1 bits. They gave a tight bound for all k in the special case k=n-1 ; they also derived a non-tight result for general k and n . Krause and Simon [ 6 ] gave improved upper and lower bounds for general k and n , but these bounds are exponentially far apart when k=\Omega(n) . In this work, we consider the statistical distance between the distributions, which must capture the power of general tests T . Prior work. Bogdanov et al. [ 2 ] and Huang and Viola [ 5 ] considered the extent to which symmetric k -wise indistinguishable distributions must have statistically close t -wise marginals for t>k . In particular, [ 2 ] shows that if \mu and \nu are symmetric over n -bit strings and perfectly k -wise indistinguishable, then the statistical distance between t -wise marginals is at most O(k^{3/2})\cdot e^{-k^{2}/1156t} for all k<t\leq n/64 . The analogous result in [ 5 ] gives a similar bound and also applies to t at most some (unspecified) constant fraction of n . In the sharp reconstruction setting where t=k+1 , [ 8 ] gives the upper bound n^{O(1)}\cdot\frac{(n-t)^{(n-t)/2}(n+t)^{(n+t)/2}}{2^{t}\,n^{n}}. We observe that these results leave open the question of whether there exist constants 0<c_{1}<c_{2}<1 and a pair of symmetric distributions \mu,\nu over \{0,1\}^{n} that are c_{1}n -wise indistinguishable yet c_{2}n -wise reconstructible with advantage e^{-o(n)} or even \Omega(1) . Our contribution. We study both the regimes of (k,\delta) -wise indistinguishability for \delta\neq 0 and without requiring that reconstruction parameter t=k+1 . We extend prior results, which do not provide upper bounds on the reconstruction advantage of distributions for all t and k . Our bound is strong enough to answer the question above in the negative. Our main contribution is the following theorem, from which more easily interpretable corollaries easily follow. Theorem 1 . Let \mu,\nu be symmetric distributions over \{0,1\}^{n} which are (k,\delta) -wise indistinguishable. Then, for integers 0\leq s\leq k<t<n , the reconstruction advantage over t bits is at most \sqrt{n+1}\,\exp{\left(-\frac{(n-t)(s+1)(s+2)}{2n(t+s+2)}\right)}+\delta\,\sqrt{2(s+1)}\cdot 2^{s}. (1) By setting \delta=0 and s=k we immediately obtain: Corollary 1 . Let \mu,\nu be symmetric distributions over \{0,1\}^{n} which are (k,0) -wise indistinguishable. Set integers 0\leq k<t\leq n . Then, the reconstruction advantage over t bits is at most \sqrt{n+1}\exp\!\left(-\frac{(n-t)(k+1)(k+2)}{2n(t+k+2)}\right). This is already a more general result than previously known. In the parameter regime in which t is at most some fixed constant fraction of n , we recover the bound as in [ 2 ] in which the rate of decay in the exponent is governed (ignoring constants) by -k^{2}/t . In the case that k is at least some fixed constant fraction of n , we see that the behaviour is governed (ignoring constants) by the exponent -(n-t) . In the setting that \delta\neq 0 , we are interested in fixing k and then maximising \delta so that the statistical distance over t -wise marginals still must be superpolynomially small. We select two different choices of s and apply Theorem 1 to obtain two upper bounds for approximate bounded indistinguishability. These corollaries extend results in [ 5 ] , which only consider reconstruction by all n bits and require \delta to be smaller than our bounds. Our two corollaries are stated in Section 5 and handle the cases in which t is at most a fixed constant fraction of n and in which t approaches n , respectively. To gain intuition for now, we state just one result which is less general than what we prove in Section 5 . Corollary 2 . Fix constants 0<c_{1}<c_{2}<1 and let k=\lfloor c_{1}n\rfloor and t=\lfloor c_{2}n\rfloor

Read the complete text