arXiv:2605.29760v1 [cs.IT] 28 May 2026
Secure Distributed Hypothesis Testing Gowtham R. Kurri
Varun Narayanan
Vinod M. Prabhakaran
K. R. Sahasranand
IIIT Hyderabad [email protected]
CMI, Chennai [email protected]
TIFR, Mumbai [email protected]
IIT Palakkad [email protected]
Abstract—In distributed hypothesis testing, a central server performs hypothesis testing based on information received from distributed sensors/clients. We study a secure variant of this problem in which the central server determines the hypothesis class of an underlying distribution without learning any additional information about the distribution itself. We prove that, in its standard form, this is impossible to achieve, even for simple and highly restricted cases. To bypass this impossibility, we augment the model with a shared secret key available to clients but hidden from the server. We show that a single-bit secret key enables perfectly secure testing for simple classes by reducing the test distributions to a symmetric, canonical instance. Finally, for arbitrary hypothesis classes over finite domains, we establish a reduction to standard hypothesis testing using Private Simultaneous Messages (PSM) protocols, achieving polynomial communication and key lengths.
I. I NTRODUCTION Consider the client-server model in which clients hold individual data and transmit locally computed messages to a central server tasked with evaluating a joint function of their combined data. This computation model is highly practical and has been studied extensively in distributed computing. In this setting, it is often critical to keep client data secure, in that, the server learns the function output but nothing else about client data. This is the privacy notion considered in secure multiparty function computation (MPC) [1], a central primitive in cryptography and distributed computing that ensures that the server learns the function output and little else. Distributed inference [2] is a kind of computation in the client-server model where clients observe independent and identically distributed (i.i.d.) samples from an underlying distribution, and the server wants to learn a statistic of the distribution. Here, individual noisy samples (e.g., collected by distributed environmental sensors) forming the client data often lack sensitive meaning and do not require strict secrecy. Instead, a natural privacy goal is to protect the underlying distribution, ensuring that the server learns nothing about this distribution other than the target statistic. We study this privacy notion in Distributed Hypothesis Testing (DHT) [2] with composite hypotheses. Let the null hypothesis H0 and the alternative H1 represent distinct classes of distributions over a finite domain. In standard DHT, clients receive i.i.d. samples from an unknown test distribution µ ∈ H0 ∪ H1 , and each client sends a local The authors acknowledge the use of Gemini for editing and formatting, as well as for assisting in the development of some of the analytical arguments used to prove Proposition 3 and the reduction that follows. All such instances were critically examined, refined, and verified by the authors.
message to the server to aid detection of the hypothesis class, while optimizing the trade-off between total communication and correctness error. We formulate Secure Distributed Hypothesis Testing (SDHT), which imposes an additional privacy constraint: the server must learn almost nothing about µ beyond its hypothesis class. Formally, the distributions of aggregated messages received by the server must be close in statistical distance for any pair of test distributions originating from the same class. Our Contributions Our first contribution is definitional. SDHT devises the right model to study privacy of distributions during distributed inference. We conduct a systematic study of SDHT, detailing fundamental impossibilities and proposing workarounds. We begin by showing that SDHT is impossible even for the simplest case where H0 = {Ber(p0 ), Ber(p1 )} vs. H1 = {Ber(p2 )} when p0 , p1 , p2 are distinct; in that, both correctness and privacy error cannot be simultaneously made arbitrarily small even with arbitrarily many samples. To bypass this fundamental impossibility, we augment the model with a uniformly distributed shared secret key that is independent of the test distribution, available to all clients, and hidden from the server. Indeed, just a single bit of shared secret key suffices to bypass the impossibility for H0 = {Ber(p), Ber(1 − p)} and H1 = {Ber(1/2)}, when p ̸= 1/2. If the key is 0, each client i sends Yi = Xi , where Xi is the received sample; if the key is 1, they send Yi = 1 − Xi . Under both Ber(p) and Ber(1 − p), the samples Y1 , . . . , Yn are i.i.d. according to Ber(p) with probability 1/2 and Ber(1 − p) with probability 1/2. Conversely, if the test distribution is Ber(1/2), the sequence remains i.i.d. Ber(1/2). This guarantees perfect privacy—(Y1 , . . . , Yn ) are identically distributed for both distributions in H0 —while still allowing the server to correctly identify the hypothesis class using a detector for H0 vs. H1 . We adapt this scheme to achieve perfectly secure hypothesis testing between any two distinct classes containing two distributions and one distribution, respectively, over an arbitrary finite domain. Finally, we address SDHT for arbitrary hypothesis classes. We obtain a reduction from SDHT to standard (nondistributed) hypothesis testing, where the communication cost and secret key length scale polynomially with the number of samples (for a fixed domain size). This is achieved using Perfectly Private Simultaneous Messages (PSM) protocols: a primitive from information-theoretically secure multiparty computation.
Related Work The study of distributed hypothesis testing dates back to the works of Tenney and Sandell [3] and of Ahlswede and Csiszar [4]. The setting where each client/sensor gets a single sample and is rate limited was studied in [5]. DHT has been well-studied [6]–[8], with a focus on various aspects such as error exponents [9], [10], sample complexity [11], communication complexity [12], [13], and shared randomness [14]. Various notions of security are considered for computation in the client server model. Secure multiparty computation [1]—a central notion in cryptography—adopts an indistinguishibility-based notion of security where the messages received by the server are required to be close in statistical distance for any pair of inputs that evaluate to the same value for the pre-agreed function. Most relevant to our work is a primitive in MPC, namely, private simultaneous messages (PSM) protocols [15] where clients share a secret key unknown to the server who wants to compute a function of the client data while maintaining the aforementioned security. A different line of work, in statistics, computer science, and other related fields, concerns differential privacy, introduced in [16], and extensively studied thereafter: see the survey by Dwork [17]. Ensuring differential privacy in the client-server model leads to the study of local differential privacy [18]–[20]. Various other notions of privacy and specialized privacy-preserving tasks have been explored, including Pufferfish privacy [21], maximal leakage [22], [23], privacy against hypothesis-testing adversaries [24], and private mean estimation [25]. These notions are primarily about protecting client-level data, whereas our problem concerns the privacy of the statistic of the distribution. Thus, the setting we consider is fundamentally different from the above line of work. Notation Finite sets are denoted as X , Y, K and so on; a distribution over X by PX , etc; random variables distributed according a PX by X. When there is no room for ambiguity, a sequence (X1 , X2 , . . . , Xn ) will be shortened as X n . We use WY |X ◦ PX to denote P the distribution of Y with probability mass function x∈X PX (x)WY |X (·|x). Total variation distance/statistical distance between two distributions P and Q over a finite domain P X is denoted dTV (P, Q) and given by dTV (P, Q) = 21 x∈X |P (x) − Q(x)|. The Bernoulli distribution with mean p is denoted Ber(p). WLOG, as usual, stands for without loss of generality.
For n ∈ N, ε, δ ≥ 0, an (ε, δ)-secure distributed hypothesis testing (SDHT) scheme for H0 vs. H1 using n samples is defined by randomized functions WYi |Xi with output alphabet function Qn Yi for each i ∈ [n] and a deterministic Qn D : i=1 Yi → {0, 1}. Define PYµn = i=1 WYi |Xi ◦ µ for any µ ∈ H0 ∪ H1 . Then, the following conditions hold: a) (1 − ε)-correctness: When (Y1 , . . . , Yn ) ∼ PY n , P [D (Y1 , . . . , Yn ) = b] ≥ 1 − ε, ∀µ ∈ Hb , b ∈ {0, 1}. b) δ-privacy: For all b ∈ {0, 1} and µ, µ′ ∈ Hb , ′ dTV PYµn , PYµn ≤ δ. Pn The SDHT scheme uses i=1 log |Yi | bits of communication. Remark 1. We will use the following simple observation in our proofs. By standard results (see, for instance, [26]; for completeness, we also include a proof at the end of the appendix), dTV (P, Q) ≥ δ if and only if there exists a deterministic test D that uses sample X and outputs D(X) ∈ {0, 1} such that PP [D(X) = 0] + PQ [D(X) = 1] ≥ 1 + δ. We will also consider SDHT using shared secret key where each client i computes Yi conditioned on Xi and a sampled shared secret key K distributed uniformly over a finite set K. An (ε, δ)-SDHT scheme for H0 vs. H1 using shared secret key over a finite domain K and n samples is defined by randomized functions WYi |Xi ,K Q with output n alphabet Yi and a deterministic function D : i=1 Yi → {0, 1}. When PK is the uniform distribution over K and µ ∈ H0 ∪ H1 , define µ ⊗n PX · PK · n KY n = µ
n Y
WYi |Xi ,K .
i=1
The correctness and privacy properties in Definition 2 hold with respect to PYµn (the marginal distribution of Y n under µ PX n KY n ) for all µ ∈ H0 ∪H1 . The communication incurred P n is i=1 |Yi | bits. The secret key size is log |K| bits. Hypotheses H0 and H1 are securely distinguishable without shared key (respectively, with shared key) if there exists an (ε, δ)-SDHT scheme using shared key (respectively, with shared key) for H0 vs. H1 for any ε, δ > 0 using n samples when n is sufficiently large. III. M AIN R ESULTS
P [D (X1 , . . . , Xn ) = b] ≥ 1 − ε, ∀µ ∈ Hb , b ∈ {0, 1}.
Suppose there is a randomized map (or channel) that maps every distribution in H0 to the same message distribution and every distribution in H1 to the same message distribution (different from the message distribution under H0 ). If each client computes their message by applying this map to their sample, perfect privacy is guaranteed: indeed, messages received by the server are identically distributed for all distributions in H0 ; similarly for H1 . To detect the hypothesis class, the server can perform a simple hypothesis test between the message distribution under H0 vs. that under H1 . This is formalized in the following proposition:
Definition 2. Let H0 and H1 be two classes of distributions over a finite domain X .
Proposition 1. Suppose there exists WY |X and distinct (0) (1) (b) distributions PY and PY such that WY |X ◦ µ = PY
II. P ROBLEM S TATEMENT Definition 1 (Binary Hypothesis Testing). Let H0 and H1 be two classes of distributions over a finite domain X . For n ∈ N, ε ≥ 0, a (1 − ε)-correct hypothesis test for H0 vs. H1 using n samples is a deterministic function D : X n → {0, 1} such that, when X1 , . . . , Xn ∼ µ, i.i.d.,
for every µ ∈ Hb and b ∈ {0, 1}. Then, there exists an (e−Ω(n) , 0)-SDHT scheme for H0 vs. H1 using n samples that incurs n · log |Y| bits of communication and does not use a shared secret key. Unfortunately, such a channel does not exist in general; specifically, even for the simple case of {Ber(p0 ), Ber(p1 )} vs. {Ber(p2 )} for distinct p0 , p1 , p2 , such a channel does not exist. Our main technical contribution is showing that, for this pair of hypotheses, it is impossible to drive both correctness and privacy error arbitrarily small without using a shared secret key no matter how many samples are used. Theorem 1. For any distinct p0 , p1 , p2 ∈ [0, 1], the hypotheses {Ber(p0 ), Ber(p1 )} and {Ber(p2 )} are not securely distinguishable without using shared secret keys. Using Theorem 1 and Proposition 1, we can obtain the following general result. Corollary 1. Let µ0 , µ1 , µ2 be distributions over the same domain. Then, hypotheses {µ0 , µ1 } and {µ2 } are securely distinguishable without shared secret key if and only if there exists no θ ∈ [0, 1] and distinct a, b, c ∈ {0, 1, 2} such that θµa + (1 − θ)µb = µc . We bypass the above impossibility by augmenting the model with a uniformly distributed shared secret key. This key is independent of the test distribution, available to all clients, and hidden from the server. Theorem 2. Let µ0 , µ1 , µ2 be distributions over the same domain. There exists a (e−Ω(n) , 0)-SDHT scheme for {µ0 , µ1 } vs. {µ2 } using n samples and a 1-bit shared secret key. Finally, we address SDHT for arbitrary hypothesis classes in the shared-key setting. We demonstrate a reduction from SDHT to standard (non-distributed) hypothesis testing, where the communication cost and secret key length scale polynomially with the number of samples (for a fixed domain size). This is achieved using Perfectly Private Simultaneous Messages (PSM) protocols: a primitive from informationtheoretically secure multiparty computation. These protocols allow the server to compute a predetermined function of the clients’ inputs while ensuring perfect privacy against the server. Let D : X n → {0, 1} be a detector for the standard hypothesis test between H0 and H1 using n samples. By applying a PSM protocol to D, we obtain a distributed test with correctness and privacy errors upper-bounded by the correctness error of D. Because D is a symmetric function, we utilize Eriguchi and Shinagawa PSM protocol [27] for symmetric functions, yielding exponential communication efficiency compared to general PSM protocols. Qn Theorem 3. Let D : i=1 X n be a symmetric function achieving (1 − ε)-correct hypothesis test for H0 vs. H1 using n samples. There exists an (ε, ε)-SDHT scheme for H0 vs. H1 using n samples, incurring O(n2⌈|X |/3⌉ ) bits of communication and shared keys.
IV. P ROOFS Proof of Theorem 1 Any details omitted from this proof are provided in the Appendix. It suffices to consider the cases p0 < p2 < p1 and p0 < p1 < p2 ; the other cases are similarly handled by relabelling pi . The former is relatively straightforward to establish, while the latter requires a more delicate argument. (a) Case p0 < p2 < p1 : Let p2 = θ · p1 + (1 − θ) · p0 for some θ ∈ (0, 1). Towards a contradiction, suppose there exists an (ε, δ)-SDHT scheme {WYi |Xi }ni=1 , D for this problem using n samples and without using a shared key. Let, (b) (Y1 , . . . , Yn(b) ) ∼
n Y
WYi |Xi ◦ Ber(pb ), ∀b ∈ {0, 1, 2}.
i=1 (b)
(b)
By (1 − ε)-correctness, D(Y1 , . . . , Yn ) = c with probability at least 1 − ε for each (b, c) ∈ {(0, 0), (1, 0), (2, 1)}. We will construct a randomized map D′ such that (b) (b) D′ (Y1 , . . . , Yn ) = b with probability at least 1 − ε for b ∈ {0, 1}. This contradicts δ-privacy for sufficiently small ε > 0 and δ > 0. D′ is defined as follows: On input Y1 , . . . , Yn , for each i ∈ [n], sample Y1′ , . . . , Yn′ i.i.d. according to WYi |Xi ◦ Ber(p0 ) and B1 , . . . , Bn i.i.d. according to Ber(θ). For each i ∈ [n], let Zi = Bi · Yi + (1 − Bi ) · Yi′ , and output D(Z1 , . . . , Zn ). If each Yi is distributed i.i.d. according to WYi |Xi ◦ Ber(p0 ), then each Zi is also distributed i.i.d. according to WYi |Xi ◦ Ber(p0 ). But, if each Yi is distributed i.i.d. according to WYi |Xi ◦ Ber(p1 ), then each Zi is distributed i.i.d. according to WYi |Xi ◦ Ber(p2 ). This follows from the fact that, for any WY |X , WY |X ◦Ber(p2 ) = WY |X ◦(θ · Ber(p1 ) + (1 − θ) · Ber(p0 )) . The properties of D′ follow from the correctness of D. (b) Case p0 < p1 < p2 : There exists θ ∈ [0, 1], such that p1 = θ · p2 + (1 − θ) · p0 . Consider RX|U where RX|U (·|0) = Ber(p0 ) and RX|U (·|1) = Ber(p2 ). Then, RX|U ◦ Ber(0) = Ber(p0 ), RX|U ◦ Ber(1) = Ber(p2 ) and RX|U ◦ Ber(θ) = Ber(p1 ). Thus, if ({WYi |Xi }ni=1 , D) is an (ε, δ)-SDHT scheme for {Ber(p0 ), Ber(p1 )} vs. {Ber(p2 )}, then ({WYi |Xi ◦ RX|U }ni=1 , D) is an (ε, δ)-SDHT scheme for {Ber(0), Ber(θ)} vs. {Ber(1)}. Hence, it suffices to show that theorem holds for p0 = 0, p1 = θ and p2 = 1 for all θ ∈ (0, 1). It suffices to restrict to SDHT schemes ({WYi |Xi }ni=1 , D) where WYi |Xi (·|0) ̸= WYi |Xi (·|1) for all i ∈ [n]. Clearly, Yj is independent of {Yi }i̸=j and identically distributed irrespective of the distribution of Xj . Hence, for all a, b ∈ {0, 1, 2}, denoting (Y1 , . . . , Yj−1 , Yj+1 , . . . , Yn ) as Y −j , (a) (b) (a) (b) dTV PY n , PY n = dTV PY −j , PY −j . In other words, ({WYi |Xi }ni=1 , D) is an (ε, δ)-SDHT scheme (if and) only if ({WYi |Xi }i̸=j , D) is an (ε, δ)-SDHT scheme.
(j)
Proposition 2. Suppose PYi ≡ WYi |Xi ◦ Ber(pj ) for each j ∈ {0, 1, 2} and i ∈ [n]. Suppose (0) (1) H 2 PYi , PYi = λ > 0. (1) inf (1) (2) WYi |Xi : H 2 PYi , PYi WYi |Xi (·|0)̸=WYi |Xi (·|1) (1)
(2)
(0)
(1)
Then, either dTV (PY n , PY n ) ≤ 1/2 or dTV (PY n , PY n ) ≥ √ −( 3/2−1)λ 1−e for all n and all schemes using n samples. Proof. Fix n and a SDHT scheme {{WYi |Xi }ni=1 , D}. Let Qn (j) PY n = i=1 WYi |Xi ◦ Ber(pj ) for j ∈ {0, 1, 2}. Suppose (1) (2) dTV PY n , PY n ≥ 1/2; else we are done. From the relationship between total variation distance and squared Hellinger distance [28, Equation (7.22)], s 2 1 2 dTV (P, Q) ≤ 1 − 1 − H (P, Q) . (2) 2 Hence, r 2 (1) (2) (1) (2) 2 H PY n , PY n ≥ 2 − 2 1 − dTV PY n , PY n p √ ≥ 2(1 − (1 − (1/2)2 )) = 2 − 3. (3)
where a = q1 , c = q0 − q1 , and c′ = (1 − θ)c. Define (1) (2) H 2 PY , PY f (a, c) := (0) (1) H 2 PY , PY p p 1 − a(a + c′ ) − (1 − a)(1 − a − c′ ) p p = . 1 − (a + c′ )(a + c) − (1 − a − c′ )(1 − a − c) The proof is essentially analytical; it entails showing that f (a, c) is non-increasing in a for a fixed c, and showing that f (0, c) is decreasing in c whereby f (a, c) ≤ f (0, c) ≤ lim f (0, c) < ∞. c↓0
□ Finally, we show that for channels with finite output alphabet (|Y| < ∞), the supremum of squared Hellinger distance ratios of the output distributions does not exceed that of the output distributions generated by channels with binary output alphabet. For Y = [k], let WY |X be a channel such that (i)
(i)
WY |X (i|0) = (α0 )ki=1 and WY |X (i|1) = (α1 )ki=1 , where
(i)
(j)
Next,
α0
α0
(1) (0) (0) (1) 2dTV PY n , PY n ≥ H 2 PY n , PY n (4) n Y 1 2 (0) (1) 1 − H PYi , PYi =2−2 2 i=1 (5)
α1
α1
≥ 2 − 2e ≥ 2 − 2e
− 12
Pn
−λ 2
Pn
i=1 H
2
(0)
(1)
i
i
PY ,PY
(1) (2) PY , PY i=1 H
2 −λ 2H
i
(6)
2
(1) (2) PY n , PY n
i
(7)
(9)
(2)
H 2 PYi , PYi < ∞. sup (1) (0) WYi |Xi :WYi |Xi (1|0)̸=WYi |Xi (1|1) H 2 P Yi , PYi Proof sketch. For a channel WY |X with WY |X (1|0) = q0 and WY |X (1|1) = q1 , q0 > q1 , WLOG, we can write (1)
≡ Ber(a), PY
(0)
≡ Ber(a + c′ ), PY
≡ Ber(a + c),
(2)
(1)
(1) (1 − γ) · α1 + γ ∗
Proposition 3. We have
(2)
and prove that there exists γ ∗ ∈ (0, 1) such that (1 − γ) · α0 + γ
Next, we show that the assumption in Proposition 2 is satisfied. WLOG, suppose that H0 = {Ber(0), Ber(θ)} for a fixed θ ∈ (0, 1) and that H1 = {Ber(1)}.
PY
∀i ≤ j.
We do this in three steps: i. We consider the transformation W → W γ for γ ∈ (0, 1) such that, for b ∈ {0, 1}, ( (1) (1 − γ) · αb + γ for i = 1 PW γ (Y = i|b) = (i) (1 − γ) · αb for i = 2, . . . , k
(8)
where (4) follows from [28, Equation (7.22)], (5) follows from the tensorization property for squared Hellinger distance under product distributions [28, Equation (7.26)], (6) follows from 1 − x ≤ e−x , for all x ∈ R, (7) follows from the definition of λ in (1), (8) follows fromQthe tensorization n property together with the identity 1 − i=1 (1 − xi ) ≤ Pn i=1 xi , for all xi ∈ [0, 1], (9) follows from the lower bound in (3).
(1)
(j)
≥ 2 − 2e √ ≥ 2 1 − e−( 3/2−1)λ ,
≤ (i)
≤
α0
(2) α1
; γ ∈ [0, γ ∗ ]
with equality at γ = γ . ii. Next, we show that the squared Hellinger distance ratio for the output distributions generated by W γ is upper bounded by that of the output distribution generated by W . iii. Finally, we show that the squared Hellinger ratio of the output distributions does not change if we “merge” two symbols with the same α0 /α1 ratio. By repeating this process in (i)-(iii), we can reduce the alphabet size to obtain a binary channel. □ Proof sketch of Corollary 1 A detailed proof is provided in Appendix. The “if” direction is shown by presenting a channel WY |X that maps µ0 , µ1 to the same distribution and µ2 to a distinct distribution whenever such λ, a, b, c do not exist, and then appealing to Proposition 1. To see the “only if” direction, suppose θµ2 +(1−θ)µ0 = µ1 for some θ ∈ [0, 1]. By employing the same reduction considered in the beginning of case where p0 < p1 < p2 in the proof of Theorem 1, we can argue that H0 and H1 are securely distinguishable only if so are hypotheses
{Ber(0), Ber(θ)} and {Ber(1)}. The result now follows from Theorem 1. A similar argument can be used when θ, a, b, c exists as stated in the corollary for any distinct a, b, c. □ Proof Sketch of Theorem 2 A detailed proof is provided in Appendix. As discussed in the introduction, such a scheme can be obtained for {Ber(p0 ), Ber(p1 )} vs {Ber(p2 )}, using a single bit of shared key if p0 = 1−p1 and p2 = 1/2. This can be straightforwardly adapted for the case where p1 = 1 − p0 and p2 ∈ / {p0 , p1 }. We build WY |X that maps Ber(p0 ), Ber(p1 ) and Ber(p2 ) to Ber(p), Ber(1−p) and Ber(q), respectively, such that q ∈ / {p, 1 − p} whenever p0 , p1 , p2 are distinct. This reduces testing {Ber(p0 ), Ber(p1 )} vs. {Ber(p2 )} to testing {Ber(p), Ber(1 − p)} vs. {Ber(q)}. For any finite domain X , we build a deterministic map WY |X : X → {0, 1} such that WY |X ◦ µ0 , WY |X ◦ µ1 and WY |X ◦µ2 are distinct Bernoulli distributions whenever µ2 , µ1 , µ2 are distinct distributions over X . Proof of Theorem 3 We will require the following definitions in the proof. Definition 3. A Boolean function f : X n → {0, 1} is symmetric if for any (x1 , . . . , xn ) ∈ X n and any permutation σ on [n], f (x1 , . . . , xn ) = f (xσ(1) , . . . , xσ(n) ). Definition 4. Let f : X n → {0, 1} be an n-variate Boolean function. A private simultaneous messages (PSM) protocol for f using secret key K uniformly distributed over a domain K is a tuple {WYi |Xi ,K }ni=1 , ϕ where each WYi |Xi ,K is a channel withQoutput alphabet Yi , and ϕ is a n deterministic function D : i=1 Yi → {0, 1} satisfying the following properties with respect to PX n KY n =
n Y i=1
PX · P K ·
n Y
WYi |Xi ,K .
i=1
where PK and PX are uniform distributions over K and X , respectively. a) Correctness: For all (x1 , . . . , xn ) ∈ X n and k ∈ K, Pr[D(Y1 , . . . , Yn ) = f (x1 , . . . , xn )|X n = xn , K = k] = 1. b) Privacy: For any (x1 , . . . , xn ), (x̃1 , . . . , x̃n ) ∈ X n such that f (x1 , . . . , xn ) = f (x̃1 , . . . , x̃n ), PY n |X n =xn = PY n |X n =x̃n . Pn The communication incurred is i=1 |Yi | bits. The secret key size is log |K| bits. We will use the following result from [27] on the existence of PSM protocols for symmetric functions. Theorem 4 (Theorem 1 in [27]). For any symmetric function f : X n → {0, 1}, there exists a PSM protocol for f using that incurs O(nδ ) bits of communication and O(nδ ) key length, where δ = 2⌈|X |/3⌉ + 1. There exists a PSM {WYi |Xi ,K }ni=1 , ϕ for D with O(nδ ) bits of communication and O(nδ ) key length, where δ = 2⌈|X |/3⌉ + 1. This follows from Theorem 4 since D
is symmetric. We will argue that {WYi |Xi ,K }ni=1 , ϕ is an (ε, ε)-private distributed hypothesis test for H0 vs. H1 using n samples with the same communication and key length. For any b ∈ {0, 1} and µ ∈ Hb , when X1 , . . . , Xn are i.i.d. according to µ, by the correctness of the PSM protocol, the output of the test is D(X1 , . . . , Xn ). But then, since D is a (1−ε)-correct hypothesis test for H0 vs. H1 , the output of the test is b with probability at least 1−ε. This establishes the correctness of the distributed hypothesis test. Next, when X1 , . . . , Xn are i.i.d. according to µ, define PX n KY n = µ⊗n · PK ·
n Y
WYi |Xi ,K .
(10)
i=1
For any µ, when X1 , . . . , Xn are i.i.d. according to µ, suppose D(X1 , . . . , Xn ) = 0 with probability α. Let PY n and PY n |X n be defined with respect to the distribution PX n KY n in (10). Fix any (x1 , . . . , xn ) ∈ X n such that D(x1 , . . . , xn ) = 0 and any (x̃1 , . . . , x̃n ) ∈ X n such that D(x̃1 , . . . , x̃n ) = 0. Then, ( PY n |X n =xn with probability α, PY n = PY n |X n =x̃n with probability 1 − α. Since D is a (1 − ε)-correct hypothesis test for H0 vs. H1 , for any µ ∈ H0 , α ≥ 1 − ε. Hence, dTV (PY n , PY n |X n =xn ) ≤ ε. Similarly, for any µ ∈ H1 , α ≤ ε. Hence, dTV (PY n , PY n |X n =x̃n ) ≤ ε. This establishes ε-privacy of the distributed hypothesis test. The communication and key length of the distributed hypothesis test are the same as that of the PSM protocol, which are O(nδ ) bits and O(nδ ) bits, respectively. □ V. D ISCUSSION AND F UTURE W ORK For arbitrary hypothesis classes, (i) we need a shared secret key of substantial length, and (ii) it needs to be kept completely secret from the server. When privacy is required only against a computationally bounded server, the former concern can be addressed by using a pseudorandom generator to stretch a short seed into a long pseudorandom string that can be used as the shared secret key. Addressing the latter concern is an interesting and important direction for future work. The impossibility result in Theorem 1 extends to the case where the shared randomness is completely known to the server; this can be shown by a standard averaging argument. A natural way to bypass this impossibility is to provide a key Ki to client i such that (K1 , . . . , Kn ) is distributed according to some publicly known joint distribution PK1 ···Kn , and the server is allowed to collude with up to t clients. This reveals the key and sample of each colluding client i to the server. Since the server gets t independent samples from the test distribution from such collusions, the privacy error is lower bounded by the statistical distance between t samples from any pair of distributions in H0 (or H1 ). Nevertheless, when t is small, it may be possible to design SDHT schemes with desirable correctness and privacy guarantees.
A good candiate for constructing such tests is the notion of non-interactive secure multiparty computation (NIMPC) introduced by Beimel et al. [29]. R EFERENCES [1] Y. Lindell, “Secure multiparty computation,” Commun. ACM, vol. 64, no. 1, p. 86–96, Dec. 2020. [2] J. N. Tsitsiklis, “Decentralized detection,” in Advances in Statistical Signal Processing, H. V. Poor and J. B. Thomas, Eds., vol. 2. JAI Press, 1993, pp. 297–344. [3] R. R. Tenney and N. R. Sandell, “Detection with distributed sensors,” IEEE Transactions on Aerospace and Electronic Systems, vol. AES17, no. 4, pp. 501–510, 1981. [4] R. Ahlswede and I. Csiszar, “Hypothesis testing with communication constraints,” IEEE Transactions on Information Theory, vol. 32, no. 4, pp. 533–542, 1986. [5] J. N. Tsitsiklis, “Decentralized detection by a large number of sensors,” Mathematics of Control, Signals and Systems, vol. 1, no. 2, pp. 167–182, Jun 1988. [6] T. S. Han and S. Amari, “Statistical inference under multiterminal data compression,” IEEE Transactions on Information Theory, vol. 44, no. 6, pp. 2300–2324, 1998. [7] P. K. Varshney, Distributed Detection and Data Fusion, 1st ed. Berlin, Heidelberg: Springer-Verlag, 1996. [8] M. S. Rahman and A. B. Wagner, “Optimality of binning for distributed hypothesis testing,” in 2010 48th Annual Allerton Conference on Communication, Control, and Computing (Allerton), 2010, pp. 828–835. [9] P. Escamilla, M. Wigger, and A. Zaidi, “Distributed hypothesis testing: cooperation and concurrent detection,” IEEE Transactions on Information Theory, vol. 66, no. 12, pp. 7550–7564, 2020. [10] U. Hadar, J. Liu, Y. Polyanskiy, and O. Shayevitz, “Error exponents in distributed hypothesis testing of correlations,” in 2019 IEEE International Symposium on Information Theory (ISIT). IEEE, 2019, pp. 2674–2678. [11] H. Kazemi, A. Pensia, and J. Varun, “The sample complexity of distributed simple binary hypothesis testing under information constraints,” in The Thirty Eighth Annual Conference on Learning Theory. PMLR, 2025, pp. 3213–3214. [12] A. Andoni, T. Malkin, and N. S. Nosatzki, “Two party distribution testing: Communication and security,” in International Colloquium on Automata, Languages, and Programming, 2019. [13] K. R. Sahasranand and H. Tyagi, “Communication complexity of distributed high dimensional correlation testing,” IEEE Transactions on Information Theory, vol. 67, no. 9, pp. 6082–6095, 2021. [14] J. Acharya, C. Canonne, and H. Tyagi, “Communication-constrained inference and the role of shared randomness,” in International Conference on Machine Learning. PMLR, 2019, pp. 30–39. [15] U. Feige, J. Killian, and M. Naor, “A minimal model for secure computation (extended abstract),” in Proceedings of the Twenty-Sixth Annual ACM Symposium on Theory of Computing, ser. STOC ’94. Association for Computing Machinery, 1994, p. 554–563.
[16] C. Dwork, “Differential privacy,” in Automata, Languages and Programming, M. Bugliesi, B. Preneel, V. Sassone, and I. Wegener, Eds. Springer, 2006, pp. 1–12. [17] ——, “Differential privacy: A survey of results,” in Theory and Applications of Models of Computation, M. Agrawal, D. Du, Z. Duan, and A. Li, Eds. Springer, 2008, pp. 1–19. [18] S. P. Kasiviswanathan, H. K. Lee, K. Nissim, S. Raskhodnikova, and A. Smith, “What can we learn privately?” SIAM Journal on Computing, vol. 40, no. 3, pp. 793–826, 2011. [19] J. C. Duchi, M. I. Jordan, and M. J. Wainwright, “Local privacy and statistical minimax rates,” in 2013 IEEE 54th Annual Symposium on Foundations of Computer Science, 2013, pp. 429–438. [20] J. Acharya, G. Kamath, Z. Sun, and H. Zhang, “Inspectre: Privately estimating the unseen,” in International Conference on Machine Learning. PMLR, 2018, pp. 30–39. [21] T. Nuradha and Z. Goldfeld, “Pufferfish privacy: An informationtheoretic study,” IEEE Transactions on Information Theory, vol. 69, no. 11, pp. 7336–7356, 2023. [22] I. Issa, A. B. Wagner, and S. Kamath, “An operational approach to information leakage,” IEEE Transactions on Information Theory, vol. 66, no. 3, pp. 1625–1657, 2019. [23] J. Liao, L. Sankar, F. P. Calmon, and V. Y. F. Tan, “Hypothesis testing under maximal leakage privacy constraints,” in 2017 IEEE International Symposium on Information Theory (ISIT), 2017, pp. 779–783. [24] Z. Li, T. J. Oechtering, and D. Gündüz, “Privacy against a hypothesis testing adversary,” IEEE Transactions on Information Forensics and Security, vol. 14, no. 6, pp. 1567–1581, 2019. [25] S. Agarwal, G. Kamath, M. Majid, A. Mouzakis, R. Silver, and J. Ullman, “Private mean estimation with person-level differential privacy,” in Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). SIAM, 2025, pp. 2819–2880. [26] H. Tyagi and S. Watanabe, Information-theoretic Cryptography. Cambridge University Press, 2023. [27] R. Eriguchi and K. Shinagawa, “Efficient multiparty private simultaneous messages for symmetric functions,” in Advances in Cryptology – EUROCRYPT 2025: 44th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Madrid, Spain, May 4–8, 2025, Proceedings, Part V, 2025, p. 240–269. [28] Y. Polyanskiy and Y. Wu, “Information theory: From coding to learning.” Cambridge University Press, 2024. [29] A. Beimel, A. Gabizon, Y. Ishai, E. Kushilevitz, S. Meldgaard, and A. Paskin-Cherniavsky, “Non-interactive secure multiparty computation,” in Advances in Cryptology – CRYPTO 2014. Springer, 2014, pp. 387–404.
A PPENDIX P ROOF OF P ROPOSITION 1 Qn
Let D : i=1 Yi → {0, 1} be a (1−ϵ)-correct hypothesis (0) (1) test for PY vs. PY using n samples for appropriate ϵ > 0. Then, it is easy to see that {WYi |Xi }ni=1 , D where WXi |Yi = WX|Y for each i is a (ϵ, 0) private distributed hypothesis test for H0 vs. H1 by the property of WY |X . An optimal hypothesis test D will achieve correctness error ϵ = e−Ω(n) . M ISSING D ETAILS IN P ROOF OF T HEOREM 1 We first prove Proposition 3 and formalize the arguments outlined in items (i)-(iii) that appear after it. Proof of Proposition 3 For a channel WY |X with WY |X (1|0) = q0 and WY |X (1|1) = q1 , q0 > q1 , WLOG, we can write (2)
PY
(1)
≡ Ber(a), PY
(0)
≡ Ber(a + c′ ), PY
≡ Ber(a + c),
where a = q1 , c = q0 − q1 , and c′ = (1 − θ)c. Define (1) (2) H 2 PY , PY f (a, c) := (0) (1) H 2 PY , PY p p 1 − a(a + c′ ) − (1 − a)(1 − a − c′ ) p p = 1 − (a + c′ )(a + c) − (1 − a − c′ )(1 − a − c) N := . D We seek to show that for all choices of (non-degenerate) WY |X , the ratio defined by f (a, c) is bounded. We handle a boundary case first. If a+c = 1, then q0 = 1 and c = 1−q1 . For this configuration, we have f (a, c) p p 1 − a(a + c′ ) − (1 − a)(1 − a − c′ ) √ = 1 − a + c′ p p 1 − (1 − c)(1 − c + c′ ) − c(c − c′ ) √ = 1 − 1 − c + c′ p p 1 − (1 − c)(1 − c + (1 − θ)c) − c(c − (1 − θ)c) p = 1 − 1 − c + (1 − θ)c √ p 1 − (1 − c)(1 − θc) − c2 θ √ = 1 − 1 − θc √ √ √ 1− 1−c−c θ √ = 1−c+ 1 − 1 − θc √ √ √ √ (1 − 1 − c − c θ)(1 + 1 − θc) ≤ 1−c+ θc √ √ (c − c θ) · 2 ≤ 1−c+ √ θc 2(1 − θ) ≤1+ θ which is bounded above for a fixed θ ∈ (0, 1). Next, we show that f (a, c) is non-increasing in a ∈ (0, 1 − c) for a fixed c ∈ (0, 1), so that we can bound
f (a, c) by f (0, c). The partial derivatives w.r.t. a are given by ∂f ∂N ∂D = ·D− · N. ∂a ∂a ∂a To show that f (a, c) is non-increasing, we show that ∂N 1 ∂D 1 ∂f ≤ 0 ⇐⇒ · ≤ · . ∂a ∂a N ∂a D Define, for b ̸= c′ , ga,c′ (b)
p p 1 − (a + b)(a + c′ ) − (1 − a − b)(1 − a − c′ ) p p = 1 − (a + b)(a + c′ ) − (1 − a − b)(1 − a − c′ ) −1 p p = 1 − (a + b)(a + c′ ) − (1 − a − b)(1 − a − c′ ) ! 2 − 2a − b − c′ 2a + b + c′ + p . × − p 2 (a + b)(a + c′ ) 2 (1 − a − b)(1 − a − c′ ) ∂ ∂a
Substituting p = a + b and q = a + c′ , the expression simplifies to ga,c′ (b) √ 2−p−q √ − 2p+q pq + 2 (1−p)(1−q) p = √ 1 − pq − (1 − p)(1 − q) p p √ √ ( (1 − p)(1 − q) − pq)(1 + (1 − p)(1 − q) + pq) p = −2 pq(1 − p)(1 − q) (11) := hq (p), where the equality in (11) is proved in Lemma 3 towards the end of this section on page 9. Note that hq (p) is well-defined for the case p = q (that is, b = c′ ) as well. To show ga,c′ (0) ≤ ga,c′ (c), it suffices to prove that hq (p) is monotonically increasing in p for a ∂h fixed q; that is ∂pq ≥ 0. Let p = sin2 α, q = sin2 β where α ∈ [0, π2 ]. The case where α = 0 corresponds to p = a + b = 0 for b ∈ [0, c], in particular, a = 0, and this case is handled separately, later. The case where α = π/2 corresponds to p = a + b = 1 where b ∈ [0, c]. This implies that a + c = 1, a case that has been handled separately earlier. So, we restrict to α ∈ 0, π2 . To show that hq (p) is monotonically increasing in p for a fixed q, it suffices to show that for the function fβ (α) := hsin2 β (sin2 α), ∂f
the partial derivative ∂αβ ≥ 0, since ∂hq ∂fβ ∂α ∂fβ 1 = = ∂p ∂α ∂p ∂α sin 2α π and sin 2α ≥ 0 for α ∈ 0, 2 . We have q p ( (1 − sin2 α)(1 − sin2 β) − sin2 α sin2 β) −1 q fβ (α) = 2 sin2 α sin2 β(1 − sin2 α)(1 − sin2 β) q q · (1 + (1 − sin2 α)(1 − sin2 β) + sin2 α sin2 β) =
−2 cos (α + β)(1 + cos (α − β)) . sin 2α sin 2β
The partial derivative of fβ with respect to α satisfies
where
(i)
(j)
α0 α 1 ∂fβ ≤ 0(j) ∀i ≤ j. (i) sin2 2α sin 2β α1 α1 2 ∂α γ = − sin 2α − sin (α + β) − sin 2α) + 2 cos 2α(cos (α + β) We consider the transformation WY |X → WY |X for γ ∈ (0, 1) such that, for b ∈ {0, 1}, 1 + (cos 2α + cos 2β) 2 WYγ |X (i|b) = 2 ( = sin 2α sin (α + β) + sin 2α + 2 cos 2α cos (α + β) (1) (1 − γ) · αb + γ for i = 1 + cos 2α(cos 2α + cos 2β) (i) (1 − γ) · αb for i = 2, . . . , n = cos (α − β) − cos 2α cos (α + β) + sin2 2α We have the following lemma proved towards the end of + 2 cos 2α cos (α + β) + cos2 2α + cos 2α cos 2β this section on page 10. = cos (α − β) + cos 2α cos (α + β) + sin2 2α (1) (2) α0 α Lemma 1. Suppose (1) < 0(2) ≤ 1. There exists γ ∗ ∈ + cos2 2α + cos 2α cos 2β = (1 + cos 2α cos 2β) + (cos (α − β) + cos 2α cos (α + β)).
cos (α − β) + cos 2α cos (α + β)
= 2 cos3 α cos β + 2 sin3 α sin β ≥ 0, where the last inequality holds because sin α, cos α ≥ 0 for α ∈ (0, π2 ). Thus, we have established that f (a, c) is non-increasing in a ∈ (0, 1 − c) for a fixed c ∈ (0, 1) and hence f (a, c) ≤ f (0, c)
√ √ 1 − c′ − 1 − c′ p √ = 1 − c′ c − (1 − c′ )(1 − c) p p 1 − (1 − θ)c − 1 − (1 − θ)c p p = 1 − (1 − θ)c2 − (1 − (1 − θ)c)(1 − c) p √ k − c + (1 − c)(k − c) √ = √ (12) √ ( k + k − c)( k − 1)2
1 where k = 1−θ > 1. In Lemma 4 towards the end of this section on page 9, we show that f (0, c) is non-increasing in c ∈ (0, 1). Therefore,
2 < ∞. k−1
Formalizing the Arguments in (i)-(iii) (i) Let WY |X be a channel with input alphabet X = {0, 1} and output alphabet Y = {1, 2, . . . , k} such that, for i ∈ [1 : k], (i)
(1)
(1 − γ) · α1 + γ
(2)
, and
α1 (2)
≤
α0
(2)
α1
For the channel W γ , the related ratio H(γ) is given in Equation (13). We show in Lemma 5 towards the end of this section on page 10 that H(γ) is strictly decreasing for γ ∈ [0, γ ∗ ]. (iii) Finally, to show that the squared Hellinger ratio does (i) (j) α0 α not change if two output symbols i, j such that (i) = 0(j) , α1 α1 it suffices to show the following lemma, which is proved towards the end of this section on page 11. Lemma 2. Let X1 ∼ Ber(p) and X2 ∼ Ber(q) be passed through a channel WY |X with output alphabet Y. Let i, j ∈ Y be two distinct output symbols with WY |X (i|0) = α0 ,
(i)
WY |X (i|1) = α1 ,
(j)
WY |X (j|1) = α1 .
WY |X (j|0) = α0 , (1)
1
□
(i)
(1 − γ) · α0 + γ
α0
(ii) We consider input distributions µ0 = Ber(0), µ1 = (j) Ber(λ), µ2 = Ber(1). Let (ai )kj=1 be the output distribution of W when the input distribution is µi , for i = 0, 1, 2. For channel W , we are interested in the ratio q 2 q Pk (j) (j) a − a 2 1 j=1 H= q 2 . q Pk (j) (j) a0 − a1 j=1
= 2 cos3 α cos β + 2 sin α sin β(1 − cos2 α)
WY |X (i|0) = α0 and WY |X (·|1) = α1 ,
(1)
(1 − γ ∗ ) · α1 + γ ∗
(2)
=
for γ ∈ [0, γ ∗ ].
+ (2 cos2 α − 1)(cos α cos β − sin α sin β) = cosα cos β + sin α sin β + 2 cos3 α cos β (( −( cos(α( cos β + sin α sin β − 2 cos2 α sin α sin β( 3 = 2 sin α sin β + 2 cos α cos β − 2 cos2 α sin α sin β
c↓0
(1 − γ ∗ ) · α0 + γ ∗ (1)
ii.
= (cos α cos β + sin α sin β)
α1
(1)
i.
The first term 1 + cos 2α cos 2β ≥ 0, and we show that the second term is also non-negative:
f (a, c) ≤ f (0, c) ≤ lim f (0, c) = √
α1
(0, 1) such that
= 1 + cos (α − β) + cos 2α cos 2β + cos 2α cos (α + β)
(i)
(j)
(2)
Let PY and PY denote the respective output distributions. Suppose a second channel merges symbols i and j into a supersymbol ij, such that the new output Y ′ is defined as ( ij if Y ∈ {i, j} ′ Y = . Y otherwise (1)
(2)
Let PY ′ and PY ′ denote the output distributions after (i) α0 (i) α1
(j)
α0
, then for any p, q ∈ [0, 1], (1) (2) (1) (2) H 2 PY , PY = H 2 PY ′ , PY ′ .
merging. If
=
(j)
α1
2 q 2 q q Pn (1) (j) (j) (1 − γ)a1 + γ + j=2 (1 − γ)a2 − (1 − γ)a1 H(γ) = q q 2 2 q q Pn (1) (1) (j) (j) (1 − γ)a0 + γ − (1 − γ)a1 + γ + j=2 (1 − γ)a0 − (1 − γ)a1 q
(1)
(1 − γ)a2 + γ −
2 q q (j) (j) a − a 2 1 j=2 = q 2 . q q 2 q Pn (1) (1) (j) (j) γ γ − a1 + 1−γ + j=2 a0 + 1−γ a0 − a1 q
(1)
γ a2 + 1−γ −
q
(1)
γ a1 + 1−γ
2
+
Pn
We can repeat the process in (i)-(iii) to merge the symbols in Y until we obtain a channel WY′ |X such that there is a single output symbol a such that WY′ |X (a|0) ≤ WY′ |X (a|1). Relabeling 0 and 1, we can continue this process to obtain a binary channel WY′′ |X . Proofs of the lemmas used in Proof of Theorem 1 Lemma 3. Let 0 < p < 1, 0 < q < 1, and p ̸= q. Define the expression hq (p) as √ 2−p−q √ − 2p+q pq + 2 (1−p)(1−q) p hq (p) = √ 1 − pq − (1 − p)(1 − q)
Substituting these back into the numerator, we get A(2 − p − q) − B(p + q) = (A − B) 1 − AB − (A2 + AB + B 2 ) = (A − B) 1 − A2 − B 2 − 2AB = (A − B) 1 − (A + B)2 = (A − B)(1 − A − B)(1 + A + B). Substituting this back into the expression for hq (p), we have
(14)
The function hq (p) can be simplified to the following form: 1 hq (p) = − p 2 pq(1 − p)(1 − q) p √ × (1 − p)(1 − q) − pq p √ × 1 + (1 − p)(1 − q) + pq (15) p √ Proof. Define A = pq and B = (1 − p)(1 − q). First, we combine the terms in the numerator of hq (p).
(13)
hq (p) =
(A−B)(1−A−B)(1+A+B) 2AB
1−A−B (A − B)(1 + A + B) = (16) 2AB 1 (B − A)(1 + A + B) , =− 2 AB where (16) follows because p ̸= q implies that A + B ̸= 1. Finally, substituting the expressions for A and B back into this yields 1 hq (p) = − p 2 pq(1 − p)(1 − q) p √ × (1 − p)(1 − q) − pq p √ × 1 + (1 − p)(1 − q) + pq .
p+q 2−p−q A(2 − p − q) − B(p + q) + = . 2A 2B 2AB We have −
A2 = pq, B 2 = (1 − p)(1 − q) = 1 − p − q + pq,
Lemma 4. The function f (0, c) in (12) is non-increasing on the interval (0, 1).
which gives 1 − p − q = B 2 − A2 ,
Proof. The derivative of f (0, c) w.r.t. c evaluates to
2 − p − q = 1 + B 2 − A2 ,
f ′ (0, c) =
p + q = 1 − B 2 + A2 . Substituting these into the numerator yields
where √
A(2 − p − q) − B(p + q) 2
−r(q + r)(r2 + 2s − c + 1) + s(q + s − c) , 2rs(q − 1)2 (q + r)2
2
2
2
= A(1 + B − A ) − B(1 − B + A ) = A + AB 2 − A3 − B + B 3 − A2 B = (A − B) + (AB 2 − A2 B) + (B 3 − A3 ). We factor the terms individually. AB 2 − A2 B = AB(B − A) = −(A − B)AB, B 3 − A3 = (B − A)(B 2 + AB + A2 ) = −(A − B)(A2 + AB + B 2 ).
q=
k, r =
√
k − c, s =
p (1 − c)(k − c).
The denominator is positive, and the sign of f ′ (0, c) is determined entirely by its numerator, Num = −r(q + r)(r2 + 2s − c + 1) + s(q + s − c). √ Define t = 1 − c. We have 1) c = 1p− t2 , 2) s = (1 − c)(k − c) = tr, 3) r2 − t2 = (k − c) − (1 − c) = k − 1 = q 2 − 1.
Substituting c = 1 − t2 and s = tr into the components of the terms in the numerator yields r2 + 2s − c + 1 = r2 + 2tr − (1 − t2 ) + 1 = r2 + 2tr + t2 = (r + t)2 , q + s − c = q + tr − (1 − t2 ) = q − 1 + t2 + tr = (q − 1) + t(r + t). Applying these substitutions back into Num gives Num = −r(q + r)(r + t)2 + tr (q − 1) + t(r + t) , which implies Num r = −(q + r)(r + t)2 + t(q − 1) + t2 (r + t) = t(q − 1) − (r + t) (q + r)(r + t) − t2 = t(q − 1) − (r + t) q(r + t) + rt + (r2 − t2 ) = t(q − 1) − (r + t) q(r + t) + rt + (q 2 − 1) 2
This gives
N , M +N where N = a1 b0 − a0 b1 and M = b1 − b0 . We analyze N and M based on the given conditions. 1) Since aa10 < bb01 , cross-multiplying yields a0 b1 < a1 b0 , which means N = a1 b0 − a0 b1 > 0. 2) Since bb10 ≤ 1, we have b0 ≤ b1 , which means M = b1 − b0 ≥ 0. Because N > 0 and M ≥ 0, the denominator M + N is strictly positive and M + N ≥ N . Consequently, the fraction MN +N must lie in the interval (0, 1]. This satisfies the required condition 0 ≤ γ ≤ 1. γ=
Lemma 5. H(γ) in (13) is strictly increasing for γ ∈ [0, γ ∗ ]. γ Proof. Step 1: Let x = 1−γ . Because x is a strictly increasing function for γ ∈ [0, 1), H(γ) is strictly increasing if and only if H(x) is strictly increasing. From Lemma 1, (1)
a0 + x
2
= t(q − 1) − (r + t)(q − 1) − q(r + t) − rt(r + t) = (q − 1) t − (r + t)(q + 1) − q(r + t)2 − rt(r + t) 2
= (q − 1)[t − rq − r − tq − t] − q(r + t) − rt(r + t) = −(q − 1)(rq + r + tq) − q(r + t)2 − rt(r + t). √ Noting that q = k > 1, we have that all the three terms above are negative, and hence f ′ (0, c) ≤ 0. Thus, f (0, c) is non-decreasing in (0, 1). Proof of Lemma 1. For notational simplicity, we denote (1) (2) αi by ai and αi by bi , for i ∈ {0, 1}. First, we show ′ that f (γ) ≥ 0 where f (γ) =
(1 − γ)a0 + γ a0 + γ(1 − a0 ) = . (1 − γ)a1 + γ a1 + γ(1 − a1 )
To determine its monotonicity, we compute f ′ (γ). 1 f ′ (γ) = (1 − a0 )[a1 + γ(1 − a1 )] 2 [a1 + γ(1 − a1 )] − (1 − a1 )[a0 + γ(1 − a0 )] . Expanding the terms inside the numerator yields (a1 + γ − a1 γ − a0 a1 − a0 γ + a0 a1 γ) − (a0 + γ − a0 γ − a1 a0 − a1 γ + a1 a0 γ). Notice that all terms involving γ cancel out, simplifying the numerator to a1 − a0 . Thus, the derivative is a1 − a0 f ′ (γ) = . [a1 + γ(1 − a1 )]2 From the premise aa01 < bb01 ≤ 1, we have aa01 < 1, which implies a0 < a1 (since the variables are nonnegative). Therefore, the numerator a1 − a0 > 0. Since the denominator is strictly positive, f ′ (γ) > 0. This confirms that the ratio strictly increases as γ increases. Next, we show that the γ satisfying f (γ) = bb01 falls in the interval [0, 1]. We set up the equation a0 + γ(1 − a0 ) b0 = . a1 + γ(1 − a1 ) b1
(1)
a2 + x (1)
(2)
≤
a0
(2)
.
a2
(1)
(1)
Because a0 < a2 , the function x 7→ (1) a0 (1) a2
(2) a0 (2) a2
a0 +x (1)
a2 +x
is strictly
increasing in x. If ≥ , the constraint is already tight or violated at x = 0. In this case, the admissible domain is only the singleton {0}, where the theorem holds vacuously. We therefore proceed assuming x∗ > 0, which strictly (1) (2) a0 a requires (1) < 0(2) . Since probabilities are non-negative, a2
a2
(2)
this strictly implies a0 > 0. 2 We rewrite H(x) = G(x)+C F (x)+C0 , where q 2 q (1) (1) • F (x) = a0 + x − a1 + x , 2 q q (1) (1) a2 + x − a1 + x , • G(x) = 2 q q Pn Pn (j) (j) • C0 = a0 − a1 = j=2 c0,j , j=2 2 q q Pn Pn (j) (j) • C2 = a − a = j=2 c2,j . 2 1 j=2 Step 2: We differentiate H(x) to get H ′ (x) =
G′ (x)(F (x) + C0 ) − F ′ (x)(G(x) + C2 ) . (F (x) + C0 )2
Since F (x) and G(x) strictly decrease as x increases, F ′ (x) = −|F ′ (x)| and G′ (x) = −|G′ (x)|. For H ′ (x) ≥ 0 to hold, we require −|G′ (x)|(F (x) + C0 ) + |F ′ (x)|(G(x) + C2 ) ≥ 0, which directly simplifies to the condition |F ′ (x)|(G(x) + C2 ) ≥ |G′ (x)|(F (x) + C0 ). Also, |F ′ (x)| = F (x) · q
1
, (1) (1) (a0 + x)(a1 + x) 1 |G′ (x)| = G(x) · q . (1) (1) (a2 + x)(a1 + x)
(1)
(1)
1 < a2 , it strictly follows that q (1)
Because a0
>
a0 +x
q 1 . So, the following inequality is sufficient to imply (1) a2 +x ′
H (x) > 0.
F (x) C0 ≥ . G(x) C2
Let y = define
t, q = 1 − θ, and w =
(j)
a2
are non-increasing over the active indices j ≥ 2. In particular, t2 ≥ tj for every active j ≥ 2. Recall that, for x ∈ (0, x∗ ], (j) a0
(1)
p
(1)
θ + qy 2 . For y ̸= 1,
(j) (2)
a0 a2 ≤ a0 a2 . (j)
Since a2 > 0, if a0 = 0, then necessarily a2 = 0. Such an index contributes zero to both C0 and C2 , and may be omitted. (j) Thus, for every active index j ≥ 2, we have a0 > 0 and (j)
. (j)
If tj = 1, then a0 = a2 , meaning both c0,j and c2,j vanish. We resolve this by defining K(1) through its continuous extension, 2 1−λ K(1) := lim K(t) = . t→1 λ With this convention, we have
c0,j =
≤ K(t1 (x))
n X
c2,j K(tj )
j=2 n X
c2,j = K(t1 (x))C2 .
j=2
F (x) C0 ≤ K(t1 (x)) = . C2 G(x) From Step 2, this implies that H ′ (x) > 0 for all x ∈ (0, x∗ ]. Because a1 is a strict convex combination of a0 and a2 , (1) (1) (1) (1) the inequality a0 < a2 guarantees that a0 < a1 . q 2 q (1) (1) Consequently, F (0) = a0 − a1 > 0. The denominator of H(x), which is F (x) + C0 , is therefore strictly positive and non-zero. This makes H(x) continuous on the closed interval [0, x∗ ]. Since H(x) is continuous on [0, x∗ ] and strictly increasing on (0, x∗ ], it is strictly increasing on [0, x∗ ]. (i)
α
α
(j)
0 Proof of Lemma 2. The condition (i) = 0(j) implies their α1 α1 reciprocals are also equal. Let r be this common ratio.
(i)
r=
(j)
α1
α1
α0
α0
= (i)
(j)
. (i)
(i)
(1)
a0 + x
(i)
= (1 − p)α0 + pα1 (i)
(i)
= (1 − p)α0 + p(rα0 ) (i)
= α0 (1 − p + pr). By identical reasoning for symbol j, we have
(1)
a2 + x
.
(i)
This allows us to express the probabilities as α1 = rα0 (j) (j) and α1 = rα0 . Then (1)
which remains valid for all active j ≥ 2, including when tj = 1. (1) Step 5: For x ∈ (0, x∗ ], the term a0 + x is strictly positive. Now we identify t1 (x) =
= t2 .
PY (i) = (1 − p)WY |X (i|0) + pWY |X (i|1)
c0,j = c2,j K(tj ),
F (x) = K(t1 (x)), G(x)
(2)
a0
Thus,
for 0 < y < 1 similarly gives the exact same equivalent condition w > θ + qy, proving K(t) is strictly increasing for all t > 0, t ̸= 1. Step 4: (2) Since we are in the case a0 > 0, the monotone likelihood ratio condition implies that, for every j ≥ 2,
(j)
n X j=2
1−w Hence M (y) > 0 for y > 1. Differentiating M (y) = w−y
(j)
(1)
a0 + x
a2
Hence
′
(j)
(2)
≥
K(t1 (x)) ≥ K(tj ).
C0 =
w2 − (θ + qy)2 = λq(y − 1)2 > 0.
a0
a2 + x
Therefore, t1 (x) ≥ tj for every active j ≥ 2. Since K is strictly increasing,
Thus M ′ (y) > 0 is equivalent to w′ (y − w) > (1 − w′ )(w − 1). Using w′ = qy w , this reduces to w > λ + qy. But
may define tj =
.
(2)
a2
(1)
t1 (x) =
M ′ (y) w′ 1 − w′ = − . M (y) w−1 y−w
a2
a0
Since all quantities in this inequality are strictly positive for x > 0 in the nondegenerate case, this is equivalent to
Since K(t) = M (y)2 , it is enough to prove that M (y) w−1 is increasing in y. For y > 1, we have M (y) = y−w . Differentiation gives
(2)
≤
a2 + x
w−1 . M (y) = y−w
(2) (j)
(2)
a0 + x
Step 3: For t > 0, define the function 2 p 1 − θ + (1 − θ)t K(t) = √ 2 . p t − θ + (1 − θ)t √
By the monotone likelihood ratio condition, the ratios tj =
(1)
(j)
PY (j) = α0 (1 − p + pr).
For X2 ∼ Ber(q), substituting q for p yields (2)
(i)
(2)
(j)
PY (i) = α0 (1 − q + qr), PY (j) = α0 (1 − q + qr). When symbols i and j are merged, the probability of observing the supersymbol ij for input X1 is (1)
(1)
(1)
PY ′ (ij) = PY (i) + PY (j) (i)
(j)
(i)
(j)
= (α0 + α0 )(1 − p + pr). Similarly for X2 , (2)
PY ′ (ij) = (α0 + α0 )(1 − q + qr). The squared Hellinger distance is H 2 (P, Q) = 2 p P p P (y) − Q(y) . Because the merge only affects y i and j, the distance change is exactly the difference between the separated symbols and the merged symbol. Let ∆ denote this difference: (1) (2) (1) (2) ∆ = H 2 PY , PY − H 2 PY ′ , PY ′ . The contribution from the distinct symbols i and j is 2 q q (1) (2) PY (i) − PY (i) Torig = q 2 q (1) (2) + PY (j) − PY (j) 2 q q (i) (i) α0 (1 − p + pr) − α0 (1 − q + qr) = q 2 q (j) (j) + α0 (1 − p + pr) − α0 (1 − q + qr) p 2 p (i) (j) = (α0 + α0 ) 1 − p + pr − 1 − q + qr .
WY |X ◦ µ0 (1) − WY |X ◦ µb (1) 1 = ⟨v ′ , ub ⟩ = α · ⟨v, ub ⟩ + · ⟨1, ub ⟩. 2 Clearly, ⟨1, ub ⟩ = 0 for b ∈ {1, 2} since µ0 , µ1 and µ2 are distributions. Moreover, ⟨v, u1 ⟩ = 0 and ⟨v, u2 ⟩ > 0. We conclude that the channel WY |X maps µ0 and µ1 to the same distribution, but maps µ2 to a different distribution. P ROOF OF T HEOREM 2
The contribution from the merged supersymbol ij is 2 q q (1) (2) Tmerged = PY ′ (ij) − PY ′ (ij) q =
−
(i)
(j)
(α0 + α0 )(1 − p + pr) q
(i)
!2 (i) (j) (α0 + α0 )(1 − q + qr) (j)
= (α0 + α0 )
p
1 − p + pr −
p
1 − q + qr
2
Consider RX|U such that RX|0 = µa , RX|1 = µb . When U = {0, 1}, RX|U ◦ Ber(0) = µa , RX|U ◦ Ber(1) = µb and RX|U ◦ Ber(λ) = µc . Let ϕ be a map from {0, 1, 2} to {0, 1, λ} that maps a, b, c to 0, 1, λ, respectively. Then, {{WYi |Xi ◦ RX|U }ni=1 , D} is a (ϵ, δ)-SDHT scheme for {Ber(ϕ(0)), Ber(ϕ(1))} vs. {Ber(ϕ(2))} using n samples and without using shared key. This contradicts Theorem 1 for sufficiently small ϵ > 0 and δ > 0. To prove the “if” direction, we will show that Proposition 1 implies a SDHT scheme using n samples that incurs n bits of communication without using shared secret key when λ, a, b, c satisfying the condition in the corollary do not exist, For this, we will construct WY |X such that WY |X ◦ µ0 = WY |X ◦ µ1 , but WY |X ◦ µ2 ̸= WY |X ◦ µ0 . Interpret µ0 , µ1 and µ2 as |X |-dimensional vectors; define u1 = µ0 −µ1 and u2 = µ0 − µ2 . By non-collinearity, u1 and u2 are linearly independent. Let v be a unit vector such that ⟨v, u1 ⟩ = 0 and ⟨v, u2 ⟩ > 0. When 1 is the all-ones vector, there exists β > 0 such that each coordinate of v ′ = α·v + 12 ·1 belongs to [0, 1]. Define WY |X such that WY |X (x) = Bernoulli(vx′ ) for x ∈ X . Clearly, for any x ∈ X , Pr[WY |X (x) = 1] = vx′ , where vx′ ∈ [0, 1] is the x-th coordinate of v ′ . But then, for b ∈ {1, 2},
.
Since Torig = Tmerged , we have ∆ = 0, proving the squared Hellinger distance is preserved. P ROOF OF C OROLLARY 1 To prove the “only if” direction, suppose there exists λ ∈ [0, 1] such that λµa + (1 − λ)µb = µc for distinct a, b, c ∈ {0, 1, 2}. Further, suppose there exist (ϵ, δ)-SDHT scheme {WYi |Xi }ni=1 , D for H0 vs. H1 using n samples and without using shared key. We will construct a (ϵ, δ)SDHT scheme for {Ber(p0 ), Ber(p1 )} vs. {Ber(p2 )} for some p0 , p1 , p2 ∈ [0, 1] using n samples and without using shared key. This contradicts Theorem 1 for sufficiently small ϵ > 0 and δ > 0.
By Corollary 1, it suffices to construct perfectly private distributed hypothesis test for H0 = {µ0 , µ1 } and H1 = {µ2 } such that µ0 , µ1 and µ2 are collinear. This is shown in two steps. In Claim 1, a perfectly private distributed hypothesis test is constructed for H0 vs. H1 using 1 bit shared key when µ0 , µ1 and µ2 are Bernoulli distributions such that the latter is distinct from the former two. Then we argue that, when µ0 , µ1 and µ2 are collinear distributions such that µ2 is distinct from both µ0 and µ1 , there exists a channel WY |X that maps µ0 , µ1 and µ2 to Bernoulli distributions where the latter is distinct from the former two. By composing the channel WY |X with the perfectly private distributed hypothesis test for Bernoulli distributions, we obtain the required perfectly private distributed hypothesis test for H0 vs. H1 using 1 bit shared key. The latter step is straightforward: let Y = {0, 1}. Let WY |X be the deterministic channel which maps each x ∈ X to 1 if µ0 (x) > µ1 (x) and maps x to 0 otherwise. Since µ0 and µ2 are distinct, WY |X maps µ0 and µ2 to different Bernoulli distributions. Moreover, since µ0 , µ1 and µ2 are collinear, but µ1 and µ2 are distinct, WY |X maps µ1 and µ2 to distinct Bernoulli distributions. Claim 1. Let H0 = {Ber(p0 ), Ber(p1 )} and H1 = {Ber(p2 )} where p2 ∈ / {p0 , p1 }. Then, there exists a perfectly private distributed hypothesis test using 1 bit shared
key for H0 vs. H1 using n samples that is (1 − e−Ω(n) )correct and incurs n bits of communication. Proof. First, consider the case where, for some q ∈ / {p, 1 − p}, µ0 = Ber(p), µ1 = Ber(1 − p) and µ2 = Ber(q). Let the shared key K be a uniformly random bit. For each i, let WYi |Xi ,K = Xi ⊕ K. Let D be a hypothesis test for H0′ = {Ber(p), Ber(1 − p)} vs. H1′ = {Ber(q), Ber(1 − q)} using n samples with correctness error at most ϵ. We will argue that {WYi |Xi ,K }ni=1 , D is a perfectly private distributed hypothesis test for H0 vs. H1 with correctness error at most ϵ. For i ∈ {0, 1, 2}, let ⊗n i · PK · PX n KY n = Ber(pi )
n Y
WYi |Xi ,K
i=1
Clearly, when the test distribution is Ber(pi ), (Y1 , . . . , Yn ) are distributed according to PYi n for i ∈ {0, 1, 2}. Observe, for a, b ∈ {0, 1}, conditioned on K = b, PYa n = Ber(pa⊕b )⊗n . Furthermore, PY2 n = Ber(b·(1−q)+(1−b)· q)⊗n conditioned on K = b. By the first observation, PY0 n and PY1 n are identical distributions—they are distributed according to Ber(p)⊗n with probability 1/2 and according to Ber(1 − p)⊗n with probability 1/2—ensuring perfect privacy. A similar statement holds for PY2 n , but with q in place of p by the second observation. For any realization of the shared key K, (Y1 , . . . , Yn ) are distributed i.i.d. according a distribution in H0′ (resp., H1′ ) when the test distribution is in H0 (resp., H1 ). Thus, the correctness error of the test reduces to the correctness error of D for H0′ vs. H1′ , which is at most ϵ. An optimal test D will achieve correctness error ϵ = e−Ω(n) . The communication incurred by the test D is exactly n bits. In the rest of the proof, we will prove the following:
following constraints on m: −
1 1 ≤m≤ 2 − p 0 − p1 2 − p 0 − p1 1 1 − ≤m≤ p0 + p 1 p0 + p 1
Since 0 < p0 + p1 < 2, we can choose 0 ̸= m that satisfies the above inequalities. With this choice of m, we have f (p0 ) + f (p1 ) = 1, f (p2 ) ∈ / {f (p0 ), f (p1 )}. The latter follows from the fact that f is injective since m ̸= 0, and p2 ∈ / {p0 , p1 }. Since α and β associated with f are in [0, 1], WY |X is a valid channel. This concludes the proof of the claim. M ISSING D ETAILS IN R EMARK 1 Lemma 6. dTV (P, Q) ≥ δ if and only if there exists a deterministic test D that uses sample X and outputs D(X) ∈ {0, 1} such that PP [D(X) = 0] + PQ [D(X) = 1] ≥ 1 + δ. Proof. For any deterministic test D, we have PP [D(X) = 0] + PQ [D(X) = 1] = 1 − PP [D(X) = 1] + PQ [D(X) = 1] = 1 + Q(A) − P (A). where A = {x : D(x) = 1}. Suppose dTV (P, Q) < δ. Then, since dTV (P, Q) = maxA⊆X Q(A) − P (A), we have PP [D(X) = 0] + PQ [D(X) = 1] ≤ 1 + dTV (P, Q) < 1 + δ. Next, suppose that dTV (P, Q) ≥ δ and consider the test D∗ (x) = 1{x∈A∗ } where dTV (P, Q) = Q(A∗ ) − P (A∗ ). Then, from the calculation above, we have PP [D∗ (X) = 0] + PQ [D∗ (X) = 1] = 1 + dTV (P, Q)
Claim 2. There exists WY |X and p, q such that q ∈ / {p, 1 − p}, WY |X ·Ber(p0 ) = Ber(p), WY |X ·Ber(p1 ) = Ber(1−p) and WY |X · Ber(p2 ) = Ber(q) when p2 ∈ / {p0 , p1 } and p0 ̸= p1 . Note, when p0 = p1 , the distributions µ0 and µ1 are identical, and thus, the test is trivial. Otherwise, composing the channel WY |X with the perfectly private distributed hypothesis test for Bernoulli distributions, we obtain the required perfectly private distributed hypothesis test for H0 vs. H1 using 1 bit shared key. This concludes the proof of Theorem 2. We now prove the above claim. To find WY |X , let WY |X (0|0) = α and WY |X (0|1) = β for some α, β ∈ [0, 1]. Define the function f : t 7→ WY |X ◦ Ber(t)(0) for t ∈ [0, 1]. It is easy to see that f (t) = α · t + β · (1 − t); alternatively, f (t) = m · t + k where m = α − β and k = β. We have, f (p0 ) + f (p1 ) = p + 1 − p = 1. Hence, m · (p0 + p1 ) + 2k = 1 =⇒ k =
1 m · (p0 + p1 ) − . 2 2
Forcing the constraints α = m + k ∈ [0, 1] and β = k ∈ [0, 1] and using the above expression for k, we have the
≥ 1 + δ.