Towards Separating Computational and Statistical Differential Privacy

Badih Ghazi Google Research
[email protected] Rahul Ilango MIT^∗
[email protected] ^∗Part of the work done during an internship at Google Research. Pritish Kamath Google Research
[email protected] Ravi Kumar Google Research
[email protected] Pasin Manurangsi Google Research
[email protected]

Abstract

Computational differential privacy (CDP) is a natural relaxation of the standard notion of (statistical) differential privacy (SDP) proposed by Beimel, Nissim, and Omri (CRYPTO 2008) and Mironov, Pandey, Reingold, and Vadhan (CRYPTO 2009). In contrast to SDP, CDP only requires privacy guarantees to hold against computationally-bounded adversaries rather than computationally-unbounded statistical adversaries. Despite the question being raised explicitly in several works (e.g., Bun, Chen, and Vadhan, TCC 2016), it has remained tantalizingly open whether there is any task achievable with the CDP notion but not the SDP notion. Even a candidate such task is unknown. Indeed, it is even unclear what the truth could be!

In this work, we give the first construction of a task achievable with the CDP notion but not the SDP notion, under the following strong but plausible cryptographic assumptions:

$\triangleright$

Non-Interactive Witness Indistinguishable Proofs,
$\triangleright$

Laconic Collision-Resistant Keyless Hash Functions,
$\triangleright$

Differing-Inputs Obfuscation for Public-Coin Samplers.

In particular, we construct a task for which there exists an $\varepsilon$ -CDP mechanism with $\varepsilon=O(1)$ achieving $1-o(1)$ utility, but any $(\varepsilon,\delta)$ -SDP mechanism, including computationally-unbounded ones, that achieves a constant utility must use either a super-constant $\varepsilon$ or an inverse-polynomially large $\delta$ .

To prove this, we introduce a new approach for showing that a mechanism satisfies CDP: first we show that a mechanism is “private” against a certain class of decision tree adversaries, and then we use cryptographic constructions to “lift” this into privacy against computationally bounded adversaries. We believe this approach could be useful to devise further tasks separating CDP from SDP.

Index Terms:

differential privacy, computational differential privacy, indistinguishability obfuscation

I Introduction

The framework of differential privacy (DP) [DMNS06, DKM⁺06] gives formal privacy guarantees on the outputs of randomized algorithms. It has been the subject of a significant body of research, leading to numerous practical deployments including the US census [Abo18], and industrial applications [EPK14, Sha14, Gre16, App17, DKY17, KT18, RSP⁺21].

The definition of DP requires privacy against computationally unbounded, i.e., statistical, adversaries. A natural modification is to instead only require privacy against computationally bounded adversaries. In cryptography, considering computationally bounded adversaries instead of statistical ones enables a vast array of applications, like public-key cryptography. Could the same be true for DP? Despite Beimel, Nissim, and Omri [BNO08] defining computational differential privacy (CDP) in 2008 (definitions that were further extended by Mironov, Pandey, Reingold, and Vadhan [MPRV09]), the central question of separating it from statistical differential privacy (SDP)¹¹1See Section III for the formal definitions of CDP and SDP. A good survey of the area can be found in [Vad17, Section 10]., in the standard client-server model, remains open:

Question 1.

[Vad17, Open Problem 10.6] Is there a computational task solvable by a single curator with computational differential privacy but is impossible to achieve with information-theoretic differential privacy?

There have been several positive and negative results towards resolving this question. In the positive direction, it is known that in the multi-party setting, CDP is stronger than SDP [MMP⁺10, MPRV09]. Roughly speaking, this is because secure multi-party computation enables many data curators to simulate acting as a single central curator, without compromising privacy. Still, the multi-party setting seems very different than the single-curator (aka central) setting. Indeed, [MMP⁺10] remark²²2This remark is also quoted by Groce, Katz, and Yerukhimovich [GKY11]. that their “strong separation between (information-theoretic) differential privacy and computational differential privacy … stands in sharp contrast with the client-server setting where … there are not even candidates for a separation.”

In the central setting, Bun, Chen, and Vadhan [BCV16] show there is a task for which there is a CDP mechanism, but any SDP mechanism for this task must be inefficient (modulo certain cryptographic assumptions). We stress that the task they consider does have an inefficient SDP mechanism (with parameters that match their CDP mechanism), so it does not resolve 1. While this may seem like a minor technical point, we emphasize that it is of crucial importance. Perhaps the main practical motivation behind studying CDP is the hope that there are CDP mechanisms for natural tasks with parameters that beat the lower bounds against SDP mechanisms. But if, as in the case of the result in [BCV16], there exists (even an inefficient) SDP mechanism matching the parameters of the CDP mechanism, then there is no hope of the CDP mechanism’s parameters beating SDP lower bounds.

In the negative direction, Mironov, Pandey, Reingold, and Vadhan [MPRV09] (building on Green and Tao [GT08], Tao and Ziegler [TZ08], and Reingold, Trevisan, Tulsiani, and Vadhan [RTTV08]) show a “dense model theorem” for pairs of random variables with “pseudodensity” with each other. Mironov et al. [MPRV09] note that (roughly speaking) extending this dense model theorem to handle multiple pairs of random variables would prove that any CDP mechanism could be converted into an SDP mechanism; such an extension is still open [Vad17, Open Problem 10.8].

Groce, Katz, and Yerukhimovich [GKY11] show that CDP mechanisms for certain tasks where the output is low-dimensional imply SDP mechanisms. Many natural statistical tasks fall into this category, and consequently, such tasks cannot separate CDP from SDP. (This result was further strengthened by [BCV16].) Furthermore, [GKY11] show that CDP mechanisms constructed in a black-box way from a variety of cryptographic objects, such as one-way functions, random oracles, trapdoor permutations, and cryptographic hash functions, cannot separate CDP from SDP.

In summary, there are at least two barriers to separate CDP from SDP:

1.

High-dimensionality: One needs to consider (perhaps non-natural) tasks with high dimensional outputs;
2.

Exotic cryptography: One needs to use cryptography somewhat specially (perhaps either an exotic primitive or in a non-black-box manner).

In light of these both positive and negative results as well as the lack of a candidate separation, it is not even clear what the truth could be: is there any task for which there is a CDP mechanism but no SDP mechanism?

Our Contributions. We show, under plausible cryptographic hypotheses, that there are indeed tasks for which there exist CDP mechanisms but no SDP mechanisms. This not only positively answers 1 but also negatively answers the dense model extension question [Vad17, Open Problem 10.8]. We state this result now informally and formalize it later in Section II. We also delay discussing our precise cryptographic assumptions to Section II-E, where we discuss their plausibility in detail.

Theorem 2.

[Informal version of Theorem 5] Under cryptographic assumptions, there exists a task for which there is a $\mathsf{CDP}$ mechanism but no $\mathsf{SDP}$ mechanism.

Let us take a step back to discuss the implications of Theorem 2. Although (as we will see in a moment) our task is specifically constructed for the purpose of separating CDP and SDP, the fact that we can separate them at all opens up a possibility that such a separation even holds for some “natural” tasks. Indeed, some of the current lower bound techniques for SDP—such as the ubiquitous “packing lower bounds”³³3Specifically, when the packing lower bound requires the use of super-polynomially many datasets, the corresponding adversary does not necessarily run in polynomial time. (see [HT10])—do not necessarily rule out CDP mechanisms. It seems prudent to carefully reexamine the current lower bound techniques to see whether they also apply to CDP. The ultimate hope for this program would be to employ CDP to overcome the known SDP lower bounds for some more “natural” tasks. (Of course, such tasks would also give a more “natural” separation of CDP and SDP.)

In fact, the technical approach we use in our construction already suggests a general approach for constructing non-trivial CDP mechanisms that could apply to more tasks. We discuss this in more detail in Section II, but the idea is as follows. In order to show a task has a CDP mechanism, first show there is a mechanism for that task that is “private” against a certain class of decision tree adversaries. Then, second, use cryptographic assumptions to “lift” this into privacy against computational adversaries.

Organization. The rest of the paper is organized as follows. Section II provides a high-level overview of our techniques as well as a discussion of our cryptographic assumptions and their plausibility. Section III contains the background material and Section IV formally defines the problems. We provide our CDP mechanism in Section V, and prove lower bounds against SDP mechanisms in Section VI. These two components are put together to prove the main result in Section VII. Finally, we discuss the open problems and future directions in Section VIII.

II Overview of the Results

We will next discuss the high-level overview of our results and techniques. We will sometimes have to be informal here, but all details are formalized later. We first recall how a “task” is defined.⁴⁴4Refer to Section III-B for a more formal definition. Following [GKY11, BCV16], a task is defined by an efficiently computable utility function $u$ that takes in an input dataset $D$ and a response $y$ such that $u(D,y)=1$ if $y$ is considered “useful” for $D$ and $u(D,y)=0$ otherwise. A mechanism $M$ is said to be $\alpha$ -useful for $u$ iff $\operatorname{\mathbb{E}}[u(D,M(D))]\geq\alpha$ for all input datasets $D$ ; we will refer to $\alpha$ as the usefulness of $M$ . We remark that many well-studied problems—such as linear queries with various error metrics—can be written in this form.

One of our main conceptual contributions is to define a class of tasks that seems to naturally circumvent the two earlier-mentioned barriers—tasks where one needs to output a circuit.

II-A The Low Diameter Set Problem

Before we detail why tasks that output a circuit might evade the two barriers, let us describe a concrete example. We call the following the low diameter set $\mathsf{LDS}_{\tau}$ problem (defined for some parameter $\tau\in\mathbb{N}$ ):

$\triangleright$

Given: dataset $D$ represented as $n$ bits (adjacent datasets differ on a single bit)⁵⁵5Refer to Section IV for formal details.
$\triangleright$

Output: circuit $C$ mapping $n$ bits to $1$ bit
$\triangleright$
Utility: $C$ is considered useful if it outputs
- $\triangleright$
  
  $1$ on $D$ , and
- $\triangleright$
  
  $0$ on all points at distance greater than $\tau$ from $D$ .

Informally, this problem asks to output a circuit $C$ such that $C^{-1}(1)\subseteq\{0,1\}^{n}$ contains $D$ and has diameter at most $\tau$ . While this utility function is not efficiently computable, we will address this in Section II-C2. Looking ahead, we will ultimately separate CDP from SDP under cryptographic assumptions by considering a “verifiable” version of this problem where we only care about datasets in a cryptographically special set.

We now revisit the two barriers and discuss how the distance problem might circumvent them.

1.

High-dimensionality: The output of this task is a circuit, which is high-dimensional.
2.

Exotic cryptography: Because the output of the task is a circuit, it lends itself to a powerful class of cryptographic objects: circuit obfuscators [BGI⁺12]. Roughly speaking, circuit obfuscators take as input a circuit $C$ and output a scrambled, obfuscated circuit $C^{\prime}$ that computes the same function as $C$ but which, ideally, has the property that “anything you could do with access to the circuit $C^{\prime}$ , you could do with only black-box access to the function the circuit computes.” Importantly, obfuscation is not in the list of primitives ruled out by the barrier in [GKY11].

II-B SDP Lower Bound

Our starting point for separating CDP from SDP is the low diameter set problem described above. Indeed, we show that there is no SDP mechanism for this problem for any $\tau$ that is essentially sub-linear in $n$ .

Lemma 3.

For all $0<\tau\leq n^{0.9}$ and constant $\varepsilon,\alpha>0$ and $\delta=1/n^{c}$ (for some $c>1$ ), there is no $(\varepsilon,\delta)$ -SDP mechanism for $\mathsf{LDS}_{\tau}$ that is $\alpha$ -useful.

In fact, this lower bound is straightforward (Lemma 15) from the well-known blatant non-privacy notion (see, e.g., [De12]): no DP algorithm can output a dataset that is (with large probability) close to the input dataset. Crucially, our lower bounds are non-constructive, and do not yield an efficient adversary (which would imply a similar lower bound against CDP mechanisms). Thus, to separate CDP from SDP it suffices to come up with a CDP mechanism for, say, $\mathsf{LDS}_{n^{0.9}}$ .

II-C A CDP Mechanism

By Lemma 3, a positive answer to the following question would demonstrate a separation between CDP and SDP.

Question 4.

For constant $\varepsilon=O(1)$ , does there exist an $\varepsilon$ - $\mathsf{CDP}$ mechanism for $\mathsf{LDS}_{n^{0.9}}$ with constant usefulness?

A key step in our approach is to reduce the above question to whether there is a mechanism for $\mathsf{LDS}_{n^{0.9}}$ that is differentially private against query (a.k.a. decision-tree) adversaries. In order to construct such a CDP mechanism $M$ , our main idea is to use obfuscation. In particular, we will consider mechanisms where the returned circuit is obfuscated. Recall that in order to prove a mechanism $M$ that outputs a circuit $C$ is CDP, one needs to argue that no efficient adversary that gets $C$ as input can break the privacy guarantee. By considering mechanisms that return obfuscated circuits, we can drastically simplify the type of adversaries we need to prove privacy against. Instead of proving privacy against adversaries that see the circuit $C$ (i.e., white-box setting), sufficiently strong obfuscation means we only need to prove privacy against decision tree adversaries that can query the function computed by the circuit (i.e., black-box setting). In other words, if we have a mechanism that satisfies DP against black-box adversaries (decision trees) with a polynomial number of queries, we can then hope to use sufficiently strong obfuscation to “lift” this into a mechanism that is secure against (white-box) computational adversaries with polynomial running time.

Of course, one needs to be careful about whether such “sufficiently strong obfuscation” is even possible, but, putting that aside for the moment, the question of whether there is a CDP mechanism for $\mathsf{LDS}_{n^{0.9}}$ (4 above) appears to reduce to whether there is a mechanism for $\mathsf{LDS}_{n^{0.9}}$ that is DP against query (a.k.a. decision-tree) adversaries.

While we do not resolve 4, we (roughly speaking) show that there is a mechanism that is DP against non-adaptive decision tree adversaries, whose queries are fixed a priori. It turns out a relatively simple mechanism based on randomized response [War65] works for these less powerful adversaries.

II-C1 From Non-Adaptive Lower Bound to Computational Lower Bound

This switch from the usual adaptive query adversaries to non-adaptive query adversaries comes at a price however. It is not clear how to use obfuscation to lift a mechanism that is private against non-adaptive queries into one that is private against computational adversaries. Indeed, a polynomial-time algorithm with even black-box access to a function seems to be an inherently adaptive adversary!

Surprisingly, we get around this by using another cryptographic object introduced by Bitansky, Kalai, and Paneth [BKP18]: collision-resistant keyless hash functions. Informally speaking, a hash function being collision-resistant and keyless means that “any efficient adversary can only generate a number of hash collisions that is at most polynomially larger than the advice the adversary gets.”

We then modify the $\mathsf{LDS}_{\tau}$ problem to only consider datasets that belong to a specific set $\mathcal{R}\subseteq\{0,1\}^{n}$ ; in particular, we will specify it the as set of all strings that hash to, say the all zeroes string. Formally, $\mathsf{LDS}_{\tau,\mathcal{R}}$ is the following problem (defined for parameters $\tau\in\mathbb{N}$ and $\mathcal{R}\subseteq\{0,1\}^{n}$ ).

$\triangleright$

Given: dataset $D$ that consists of $n$ bits
$\triangleright$

Output: circuit $C$ mapping $n$ bits to $1$ bit
$\triangleright$
Utility: $C$ is considered useful if $D\notin\mathcal{R}$ or both of the following hold:
- $\triangleright$
  
  it outputs 1 on $D$
- $\triangleright$
  
  it outputs 0 on all points in $\mathcal{R}$ at distance greater than $\tau$ from $D$

In other words, the utility function now completely ignores all points outside of $\mathcal{R}$ .

The high-level intuition behind this change is the following:

1.

Our CDP mechanism can output a circuit $C$ such that the only inputs where $C(x)$ reveals information are those $x$ in the set $\mathcal{R}$ .
2.

Any polynomial-time adversary $\mathcal{A}$ can only generate fixed polynomial number of elements of $\mathcal{R}$ by the collision-resistance property of the hash function.
3.

Combining the above makes the inputs $\mathcal{A}$ can query $C$ on, effectively “non-adaptive”.

Finally, in order to “lift” the query separation into the computational realm we use another cryptographic tool: differing-inputs obfuscation ( $\mathsf{di}\mathcal{O}$ ) [BGI⁺01, BGI⁺12, ABG⁺13]. Roughly speaking, $\mathsf{di}\mathcal{O}$ is an obfuscator with the following guarantee: if any efficient adversary can distinguish the obfuscation of two circuits $C_{1}$ and $C_{2}$ , then an efficient adversary can find an input $x$ on which $C_{1}(x)\neq C_{2}(x)$ . In particular, the specific assumption we use is even weaker than public-coin $\mathsf{di}\mathcal{O}$ [IPS15], which is already considered to more plausible than general $\mathsf{di}\mathcal{O}$ .⁶⁶6See Assumption 22 for formal statement of the assumption and Appendix A for comparison with other $\mathsf{di}\mathcal{O}$ assumptions in literature.

In summary, $\mathsf{di}\mathcal{O}$ allows us to reduce computational adversaries to adaptive query adversaries and collision-resistant keyless hash functions allows us to reduce adaptive query adversaries to non-adaptive query adversaries. Interestingly, to the best of our knowledge, this is the first time collision-resistant keyless hash functions are being used together with any obfuscation assumption.

II-C2 Making the Utility Function Efficiently Computable

We need to address one final issue: utility functions that we have considered so far are not necessarily efficiently computable. Specifically, a trivial way to implement the utility function would be to enumerate all points at distance at least $\tau$ , feed it into the circuit, and check that the output is as expected; this would take $2^{n^{\Omega(1)}}$ time.

To overcome the above problem, we restrict circuits to only those that are relatively simple, so that there is a small “witness” $w$ that certifies that the circuit outputs zero at all points that are $\tau$ -far from $D$ . A naive idea is then to let the CDP mechanism output the circuit $C$ together with such a witness $w$ . The utility function can then just efficiently check that $w$ is a valid witness (and that $C(D)=0$ or $x\in\mathcal{R}$ ). This makes the utility function efficient but unfortunately compromises privacy because the witness $w$ itself can leak additional information. To avoid this, we instead use non-interactive witness indistinguishable (NIWI) proofs (e.g., [BOV07]). Roughly speaking, this allows us to produce a proof $\pi$ from $w$ (and $C$ and $\mathsf{di}\mathcal{O}$ ), which does not leak any information about $w$ (against computationally bounded adversaries), but at the same time still allows us to verify that the underlying witness $w$ is valid. The former is sufficient for CDP, while the latter ensures that the utility function can be computed efficiently.

This completes the high-level overview of the constructed task and our $\mathsf{CDP}$ mechanism. The cryptographic primitives needed for our mechanism are formalized in Assumptions 18, 22 and 26.

II-D Final Steps

Finally, since our problem is now not exactly the original $\mathsf{LDS}_{\tau}$ problem anymore, as the utility guarantees are only now meaningful for datasets in $\mathcal{R}$ , we cannot use the lower bound in Lemma 3 for $\mathsf{LDS}_{\tau}$ directly. Fortunately, we can still adapt its proof—a “packing-style” lower bound on each coordinate—to one which applies a packing-style argument on each block of coordinates instead. With this, we can prove the lower bound for $\mathsf{LDS}_{\tau,\mathcal{R}}$ as long as the set $\mathcal{R}$ has sufficiently large density ( $\approx 1/n^{-o(\log n)}$ ).

Putting all the ingredients together, we arrive at the following⁷⁷7We remark that $({\bm{\varepsilon}}_{\mathsf{SDP}},{\bm{\delta}}_{\mathsf{SDP}})$ - $\mathsf{SDP}$ mechanism here refers to an ensemble of mechanisms $\left\{M_{n}\right\}$ that are $({{\bm{\varepsilon}}_{\mathsf{SDP}}}_{n},{{\bm{\delta}}_{\mathsf{SDP}}}_{n})$ - $\mathsf{SDP}$ . (See Definition 7.):

Theorem 5 (Main Result).

Under Assumptions 18, 22 and 26, for any constant ${\bm{\varepsilon}}_{\mathsf{CDP}}>0$ , there exists an ensemble ${\bm{u}}=\left\{u_{n}\right\}_{n\in\mathbb{N}}$ of polynomial time computable utility functions such that

$\triangleright$

There is an ${\bm{\varepsilon}}_{\mathsf{CDP}}$ - $\mathsf{CDP}$ mechanism that is $(1-o_{n}(1))$ -useful for ${\bm{u}}$ .
$\triangleright$

For any constants ${\bm{\varepsilon}}_{\mathsf{SDP}},{\bm{\alpha}}>0$ and ${\bm{\delta}}_{\mathsf{SDP}}=1/n^{27}$ , no $({\bm{\varepsilon}}_{\mathsf{SDP}},{\bm{\delta}}_{\mathsf{SDP}})$ - $\mathsf{SDP}$ mechanism is ${\bm{\alpha}}$ -useful for ${\bm{u}}$ .

The task underlying the separation is an instantiation of the “verifiable low diameter set problem” $\mathsf{VLDS}_{\tau,\mathcal{R},V}$ defined in Definition 14.

II-E On the Plausiblility of the Cryptographic Assumptions

We now discuss the plausiblility of the three cryptographic assumptions we use for our result:

(i)

NIWI: Non-interactive Witness Indistinguishable Proofs (formally, Assumption 26)
(ii)

CRKHF: Laconic Collision-Resistant Keyless Hash Functions (formally, Assumption 18)
(iii)

$\mathsf{di}\mathcal{O}\text{-}\mathsf{for}\text{-}\mathsf{pcS}$ : Differing-Inputs Obfuscation for Public-Coin Samplers (formally, Assumption 22)

Regarding (i), NIWI. Bitansky and Paneth [BP15a] show that NIWIs exist assuming one-way permutations and indistinguishability obfuscation (iO) exists. Recently, Jain, Lin, and Sahai [JLS21] show that the existence of $\mathsf{i}\mathcal{O}$ follows from well-founded assumptions; consequently, NIWIs exist based on widely-believed assumptions. (We note that other previous works have also constructed NIWIs based on other more specific assumptions [BOV07, GOS12].)

Regarding (ii), CRKHF. Bitansky, Kalai, and Paneth [BKP18] defined CRKHFs to model the properties of existing hash functions like SHA-2 used in practice. They suggest several candidates for CRKHFs, such as hash functions based on AES and Goldreich’s one-way functions. They also note that CRKHFs exist in the Random Oracle model, as a random function is a CRKHF. Still, it is an open question to base the security of a CRKHF on a standard cryptographic assumption. Part of the difficulty of doing this, as [BKP18] describe, is that most cryptographic assumptions involve some sort of structure that is useful for constructing cryptographic objects. In contrast, the goal of a CRKHF is to have no structure at all. In summary, given the various CRKHF candidates, the existence in the Random Oracle model, and the fact that CRKHFs exist “in practice,” this assumption is quite plausible. For our specific construction, we need a different hash length (equivalently, different compression rate) than that used in [BKP18]; please refer to the discussion preceding Assumption 18 for the parameters and justification.

Finally, we remark that, even though the existence of CRKHFs is not known to reduce to any “well-founded” assumption, even refuting their existence would answer a longstanding question in cryptography: giving non-contrived separations between the Random Oracle model [BR93] and the standard model. In the words of Bitansky, Kalai, and Paneth [BKP18],

“Any attack on the multi-collision resistance of a [keyless] cryptographic hash function would constitute a strong and natural separation between the hash and random oracles. For several cryptographic hash functions used in practice, the only known separations from random oracles are highly contrived [CGH04].”

Regarding (iii), $\mathsf{di}\mathcal{O}\text{-}\mathsf{for}\text{-}\mathsf{pcS}$ . One can think of $\mathsf{di}\mathcal{O}$ [BGI⁺01, BGI⁺12] as an “extractable” strengthening of $\mathsf{i}\mathcal{O}$ . While $\mathsf{i}\mathcal{O}$ has now become a widely-believed assumption [JLS21], the existence of $\mathsf{di}\mathcal{O}$ is controversial. Several papers (e.g., [BP15b, GGHW17, BSW16]) cast doubt on the existence of $\mathsf{di}\mathcal{O}$ , especially in the case where an arbitrary auxillary input is allowed; we stress that all the negative results for $\mathsf{di}\mathcal{O}$ hold for contrived auxillary inputs and/or distributions. On the positive side, [BCP14] show that $\mathsf{di}\mathcal{O}$ reduces to $\mathsf{i}\mathcal{O}$ in special cases, such as when the number of differing-inputs is bounded by a polynomial. More related to our result, [IPS15] gives a definition of public-coin $\mathsf{di}\mathcal{O}$ that avoids the difficulties presented by earlier negative results regarding auxiliary inputs, although [BP15b] presented some evidence against this definition in special cases. Our specific assumption of $\mathsf{di}\mathcal{O}\text{-}\mathsf{for}\text{-}\mathsf{pcS}$ is in fact weaker than the assumption of public-coin $\mathsf{di}\mathcal{O}$ . In the definition of public-coin $\mathsf{di}\mathcal{O}$ , as in [IPS15], we start with any public-coin sampler ( $\mathsf{pcS}$ ), for which it is hard to find an input on which two circuits differ, even given the knowledge of all the randomness that underlies the circuits. The security of the obfuscation is required to hold even against adversaries that know all the randomness that underlies the generation of the two circuits. However, in our definition, the security of the obfuscation is required to hold only against adversaries that observes a single obfuscated circuit, which makes the assumption weaker. See Appendix A for a more detailed discussion on comparison of this assumption with other $\mathsf{di}\mathcal{O}$ assumptions in literature. Finally, we only use the existence of $\mathsf{di}\mathcal{O}\text{-}\mathsf{for}\text{-}\mathsf{pcS}$ for a simple circuit family for our result, so even if general purpose $\mathsf{di}\mathcal{O}\text{-}\mathsf{for}\text{-}\mathsf{pcS}$ does not exist, we think it is plausible that $\mathsf{di}\mathcal{O}\text{-}\mathsf{for}\text{-}\mathsf{pcS}$ exists for the specific family of circuits we need for our result. (See Assumption 22 for the exact $\mathsf{pcS}$ family for which we require a $\mathsf{di}\mathcal{O}$ .)

Final thoughts on our assumptions.

In conclusion, we view each of our three assumptions as plausible. Moreover, each of assumptions has at least some evidence that is hard to refute: NIWIs exist based on a widely-believed assumption, refuting CRKHFs would require giving the first non-contrived separation between the standard and the Random Oracle model, and despite many attempts (e.g., [BP15b, GGHW17, BSW16]) to refute $\mathsf{di}\mathcal{O}$ , the question is still open, especially for the particular $\mathsf{di}\mathcal{O}\text{-}\mathsf{for}\text{-}\mathsf{pcS}$ version. Thus, refuting any of the assumptions would constitute a breakthrough in cryptography.

III Preliminaries

A function $g:\mathbb{N}\to\mathbb{R}_{\geq 0}$ is said to be negligible if $g(n)=n^{-\omega(1)}$ . Let PPT be an abbreviation for probabilistic polynomial-time Turing machine.

For $x\in\{0,1\}^{n}$ and $r\in\mathbb{N}$ , we use $B_{r}(x)$ to denote the (Hamming) ball of radius $r$ around $x$ , i.e., $\{z\in\{0,1\}^{n}\mid\|x-z\|_{1}\leq r\}$ . Furthermore, we use $\operatorname{diam}(S)$ for a set $S\subseteq\{0,1\}^{n}$ to denote the (Hamming) diameter of $S$ , i.e., $\max_{x,x^{\prime}\,\in S}\|x-x^{\prime}\|_{1}$ .

III-A Dataset and Adjacency

For a domain $\mathcal{X}$ , we view a dataset $D$ as a histogram over the domain $\mathcal{X}$ , i.e., $D\in\mathbb{Z}_{\geq 0}^{\mathcal{X}}$ where $D_{x}$ denotes the number of times $x\in\mathcal{X}$ appears in the dataset. The size of the dataset is defined as $\|D\|_{1}:=\sum_{x\in\mathcal{X}}D_{x}$ . We write $\mathcal{X}^{m}$ as a shorthand for the set of all datasets of size $m$ , and $\mathcal{X}^{*}$ for the set of all datasets over domain $\mathcal{X}$ . Two datasets are adjacent iff $\|D-D^{\prime}\|_{1}=1$ , i.e., one of the datasets is a result of adding or removing a single row from the other dataset.

III-B Mechanism, Utility Function, and Usefulness

A mechanism $M$ is a randomized algorithm that takes in a dataset $D\in\mathcal{X}^{*}$ and outputs an element from a set $\mathcal{Y}$ . The utility of a mechanism is measured by a utility function $u$ , which is a polynomial-time deterministic algorithm that takes in a dataset $D\in\mathcal{X}^{*}$ together with a response $y\in\mathcal{Y}$ and outputs 0 or 1 (whether the response is good for the dataset). We say that the mechanism $M$ is $\alpha$ -useful for utility $u$ iff $\Pr[u(D,M(D))=1]\geq\alpha$ .

Below, we will often discuss an ensemble ${\bm{M}}=\{M_{n}\}_{n\in\mathbb{N}}$ of mechanisms where⁸⁸8It is always implicitly assumed that $\mathcal{X}_{n},\mathcal{Y}_{n}$ are of size $\operatorname{poly}(n)$ . $M_{n}:\mathcal{X}_{n}^{*}\to\mathcal{Y}_{n}$ . We say that an ensemble of mechanisms is efficient if $M_{n}$ on input $D\in\mathcal{X}_{n}^{m}$ runs in time $\operatorname{poly}(n,m)$ . For an ensemble ${\bm{u}}=\left\{u_{n}\right\}_{n\in\mathbb{N}}$ of utility functions and ${\bm{\alpha}}=\left\{\alpha_{n}\in[0,1]\right\}_{n\in\mathbb{N}}$ , we say that ${\bm{M}}$ is ${\bm{\alpha}}$ -useful with respect to ${\bm{u}}$ iff $M_{n}$ is $\alpha_{n}$ -useful with respect to $u_{n}$ for all $n\in\mathbb{N}$ .

For brevity, we will sometimes refer to “ensemble of mechanisms” simply as “mechanism” and “ensemble of utility functions” simply as “utility function” when there is no ambiguity.

III-C Notions of Differential Privacy

We now define the notions of DP that will be used throughout the paper.

(Statistical) Differential Privacy. The standard (statistical) notion of DP can be defined in terms of the following notion of indistinguishability.

Definition 6 (Statistical Indistinguishability).

Distributions $P$ , $Q$ are said to be $(\varepsilon,\delta)$ -indistinguishable, denoted $P\approx_{\varepsilon,\delta}Q$ , if for all events (measurable sets) $\mathcal{E}$ , it holds for $(\mathcal{D}_{0},\mathcal{D}_{1})=(P,Q)$ and $(Q,P)$ that

\displaystyle\Pr_{X\sim\mathcal{D}_{0}}[X\in\mathcal{E}]

\displaystyle~{}\leq~{}e^{\varepsilon}\cdot\Pr_{X\sim\mathcal{D}_{1}}[X\in\mathcal{E}]+\delta\,.

For simplicity, we use $\approx_{\varepsilon}$ to denote $\approx_{\varepsilon,0}$ .

Definition 7 (Statistical Differential Privacy (SDP) [DMNS06, DKM⁺06]).

For $\varepsilon,\delta>0$ , a mechanism $M$ is said to be $(\varepsilon,\delta)$ - $\mathsf{SDP}$ if and only if for every pair $D,D^{\prime}$ of adjacent datasets, we have that $M(D)\approx_{\varepsilon,\delta}M(D^{\prime})$ . We say that an ensemble ${\bm{M}}=\{M_{n}\}_{n\in\mathbb{N}}$ is $({\bm{\varepsilon}},{\bm{\delta}})$ - $\mathsf{SDP}$ for sequences ${\bm{\varepsilon}}=\left\{\varepsilon_{n}\right\}_{n\in\mathbb{N}}$ and ${\bm{\delta}}=\left\{\delta_{n}\right\}_{n\in\mathbb{N}}$ if $M_{n}$ is $(\varepsilon_{n},\delta_{n})$ - $\mathsf{SDP}$ for all $n\in\mathbb{N}$ .

Computational Differential Privacy. The notion of computational DP relaxes the notion of indistinguishability to a computational version, where the privacy holds only with respect to computationally bounded adversaries.

Definition 8 (Computational Indistinguishability).

Two ensembles of distributions ${\bm{P}}=\left\{P_{n}\right\}_{n\in\mathbb{N}}$ and ${\bm{Q}}=\left\{Q_{n}\right\}_{n\in\mathbb{N}}$ , where $P_{n}$ and $Q_{n}$ are supported over $\{0,1\}^{p(n)}$ for some polynomial $p(\cdot)$ , are said to be ${\bm{\varepsilon}}$ -computationally-indistinguishable for a sequence ${\bm{\varepsilon}}=\left\{\varepsilon_{n}\right\}_{n\in\mathbb{N}}$ , denoted ${\bm{P}}\approx^{c}_{{\bm{\varepsilon}}}{\bm{Q}}$ , if there exists a negligible function $\operatorname{negl}(\cdot)$ such that for any PPT adversary $\mathcal{A}$ , it holds for $(\mathcal{D}_{0},\mathcal{D}_{1})=(P_{n},Q_{n})$ and $(Q_{n},P_{n})$ that

\displaystyle\Pr_{X\sim\mathcal{D}_{0}}[\mathcal{A}(X)=1]

\displaystyle~{}\leq~{}e^{\varepsilon_{n}}\Pr_{X\sim\mathcal{D}_{1}}[\mathcal{A}(X)=1]+\operatorname{negl}(n)

In the special case of ${\bm{\varepsilon}}=0$ , we suppress the subscript and simply write ${\bm{P}}\approx^{c}{\bm{Q}}$ .

Throughout, when we refer to a sequence $\{(D_{n},D^{\prime}_{n})\}_{n\in\mathbb{N}}$ of adjacent datasets, it is always assumed that $D_{n}\in\mathcal{X}_{n}^{m_{n}},D^{\prime}_{n}\in\mathcal{X}_{n}^{m^{\prime}_{n}}$ are of sizes $m_{n},m^{\prime}_{n}=\operatorname{poly}(n)$ .

Definition 9 (Computational Differential Privacy ( $\mathsf{CDP}$ ) [MPRV09]).

An ensemble ${\bm{M}}=\left\{M_{n}\right\}_{n\in\mathbb{N}}$ of mechanisms is said to be ${\bm{\varepsilon}}$ - $\mathsf{CDP}$ for a sequence ${\bm{\varepsilon}}=\left\{\varepsilon_{n}\right\}_{n\in\mathbb{N}}$ , if for any sequence $\left\{(D_{n},D^{\prime}_{n})\right\}_{n\in\mathbb{N}}$ of adjacent datasets, it holds that $\left\{M_{n}(D_{n})\right\}_{n\in\mathbb{N}}\approx^{c}_{\varepsilon_{n}}\left\{M_{n}(D_{n}^{\prime})\right\}_{n\in\mathbb{N}}$ .

This definition is often referred to as indistinguishability-based CDP ( $\mathsf{IND}$ - $\mathsf{CDP}$ ) in previous works [MPRV09, GKY11, BCV16]. Since we only use this notion for our main result, we refer to it simply as CDP. The other definition of CDP used in previous works is simulation-based:

Definition 10 ( $\mathsf{SIM}$ - $\mathsf{CDP}$ [MPRV09]).

An ensemble ${\bm{M}}=(M_{n})_{n\in\mathbb{N}}$ of mechanisms is said to be ${\bm{\varepsilon}}$ - $\mathsf{SIM}$ - $\mathsf{CDP}$ if there exists an $(\varepsilon_{n},0)$ - $\mathsf{SDP}$ ensemble $\{M^{\prime}_{n}\}_{n\in\mathbb{N}}$ of mechanisms such that for any sequence $\{D_{n}\in\mathcal{X}_{n}^{*}\}_{n\in\mathbb{N}}$ of datasets, with size of $D_{n}$ being at most $\operatorname{poly}(n)$ , it holds that $M_{n}(D_{n})\approx^{c}M^{\prime}_{n}(D_{n})$ .

It should be noted that $\mathsf{SIM}$ - $\mathsf{CDP}$ cannot be used for the separation we are looking for. Specifically, if $\{M_{n}\}_{n\in\mathbb{N}}$ is ${\bm{\varepsilon}}$ - $\mathsf{SIM}$ - $\mathsf{CDP}$ , we may use $\{M^{\prime}_{n}\}_{n\in\mathbb{N}}$ as our $({\bm{\varepsilon}},{\bm{0}})$ - $\mathsf{SDP}$ mechanism. Since the utility function runs in polynomial time, it follows immediately that, if $\{M_{n}\}_{n\in\mathbb{N}}$ is $\alpha$ -useful, then $\{M^{\prime}_{n}\}_{n\in\mathbb{N}}$ is also $(\alpha-o(1))$ -useful. Due to this, we will not consider $\mathsf{SIM}$ - $\mathsf{CDP}$ again in this paper.

Another point to note is that unlike prior work (e.g. [BCV16]) we use both $({\bm{\varepsilon}},{\bm{\delta}})$ parameters for $\mathsf{SDP}$ , but only ${\bm{\varepsilon}}$ parameter for $\mathsf{CDP}$ , since ${\bm{\delta}}$ is always assumed to be negligible for $\mathsf{CDP}$ . Our lower bounds for $\mathsf{SDP}$ in fact work for ${\bm{\delta}}$ that is not negligible, which only makes the result stronger.

Calculus of $\approx$ and $\approx^{c}$ . The following properties are well-known.

Fact 11.

The notions of $(\varepsilon,\delta)$ -indistinguishability and $\varepsilon$ -computational-indistinguishability satisfy:

$\triangleright$

Basic Composition: If $P_{0}\approx_{\varepsilon,\delta}P_{1}$ and $P_{1}\approx_{\varepsilon^{\prime},\delta^{\prime}}P_{2}$ , then $P_{0}\approx_{\varepsilon+\varepsilon^{\prime},\delta+\delta^{\prime}}P_{2}$ . Similarly, if ${\bm{P}}_{0}\approx^{c}_{{\bm{\varepsilon}}}{\bm{P}}_{1}$ and ${\bm{P}}_{1}\approx^{c}_{{\bm{\varepsilon}}^{\prime}}{\bm{P}}_{2}$ , then ${\bm{P}}_{0}\approx^{c}_{\varepsilon+\varepsilon^{\prime}}{\bm{P}}_{2}$ .
$\triangleright$

Post-processing: If $P\approx_{\varepsilon,\delta}Q$ , then for all (randomized) functions $f$ , it holds that $f(P)\approx_{\varepsilon,\delta}f(Q)$ . Similarly, if ${\bm{P}}\approx^{c}_{{\bm{\varepsilon}}}{\bm{Q}}$ , then for all PPT algorithms $\mathcal{A}$ , it holds that $\mathcal{A}({\bm{P}})\approx^{c}_{{\bm{\varepsilon}}}\mathcal{A}({\bm{Q}})$ .

IV Low Diameter Set Problem and Nearby Point Problem

In this section, we introduce the problems that we will use in our separation. Before that, we will describe a simplifying assumption that we can make about the inputs.

IV-A Simplification of Input Representation

Recall that so far a dataset may contain multiple copies of an element. Below, however, it will be more convenient to only discuss the case where each element appears only once, i.e., $D\in\{0,1\}^{\mathcal{X}}$ .

This is sufficient since if we have a utility function $u:\{0,1\}^{\mathcal{X}}\times\mathcal{Y}\to\{0,1\}$ defined only on $D\in\{0,1\}^{\mathcal{X}}$ , we can easily define the utility function $\overline{u}:\mathbb{N}^{\mathcal{X}}\times\mathcal{Y}\to\{0,1\}$ by

\displaystyle\overline{u}(\overline{D},r)=\begin{cases}u(\overline{D},r)&\text{ if }\overline{D}\in\{0,1\}^{\mathcal{X}},\\ 1&\text{ otherwise.}\end{cases}

In other words, the utility function considers any response good for datasets with repetition. Clearly, if $u$ is efficiently computable, then so is $\overline{u}$ . Furthermore, suppose that we have an $\varepsilon$ - $\mathsf{CDP}$ mechanism ${\bm{M}}=\left\{M_{n}\right\}_{n\in\mathbb{N}}$ for ${\bm{u}}=\left\{u_{n}\right\}_{n\in\mathbb{N}}$ . For every dataset $\overline{D}$ , let $D$ be defined by $D_{i}=\min\left\{\overline{D}_{i},1\right\}$ . Then, we may define $\overline{{\bm{M}}}=\left\{\overline{M}_{n}\right\}_{n\in\mathbb{N}}$ by $\overline{{\bm{M}}}(\overline{D})=M(D)$ . It is easy to see that $\overline{{\bm{M}}}$ remains ${\bm{\varepsilon}}$ -CDP. Furthermore, if ${\bm{M}}$ is ${\bm{\alpha}}$ -useful for ${\bm{u}}$ , then $\overline{{\bm{M}}}$ remains ${\bm{\alpha}}$ -useful for $\overline{{\bm{u}}}$ .

Finally, note that a lower bound for DP algorithms restricted to non-repeated datasets trivially implies a lower bound against all datasets.

Due to this, we will henceforth focus our attention only on the datasets $D\in\{0,1\}^{\mathcal{X}}$ . Furthermore, throughout the remainder of this paper, we will always pick $\mathcal{X}_{n}=[n]$ . This further simplifies the input representation to be just a bit vector $x\in\{0,1\}^{n}$ . We will define an input of our problem in this way. Furthermore, we will henceforth use $x$ instead of $D$ to denote the input dataset.

IV-B Nearby Point Problem

We will start by defining our first problem, which asks to output a point that is close to the input point if the latter belongs to some set $\mathcal{R}$ . As we noted in the introduction, when $\mathcal{R}$ is the set of all points (i.e., $\mathcal{R}_{n}=\{0,1\}^{n}$ ), this is exactly the same as the problem considered in blatant non-privacy [DN03, DMT07]. As we will see later, the presence of the set $\mathcal{R}$ is due to our use of hashing, which is required in our proof for the $\mathsf{CDP}$ mechanism.

Definition 12 ( $\tau$ -Nearby $\mathcal{R}$ -Point Problem).

The nearby point problem parameterized by sequences $\left\{\tau_{n}\in\mathbb{N}\right\}_{n\in\mathbb{N}}$ and $\left\{\mathcal{R}_{n}\subseteq\{0,1\}^{n}\right\}_{n\in\mathbb{N}}$ is denoted by $\mathsf{NBP}_{\tau,\mathcal{R}}$ . For input $x\in\{0,1\}^{n}$ and output $y\in\mathcal{Y}_{n}=\{0,1\}^{n}$ , the utility is defined as:

u^{\mathsf{NBP}}_{\tau_{n},\mathcal{R}_{n}}(x,y):=\mathds{1}\left\{\|x-y\|_{1}\leq\tau_{n}\text{ or }x\notin\mathcal{R}_{n}\right\}

For brevity, we will assume throughout that $\mathcal{R}_{n}$ is efficiently recognizable and henceforth we do not state this explicitly. Note that this assumption implies that the utility function defined above is efficiently computable. The nearby point problem will be primarily used for proving the lower bounds against $\mathsf{SDP}$ .

IV-C Verifiable Low Diameter Set Problem

Next, we define circuit-based tasks for which we will give $\mathsf{CDP}$ mechanisms. To do so, we need to first define a “ $\tau$ -diameter verifier”.

Definition 13 ( $\tau$ -Diameter Verifier).

For a sequence $\tau=\left\{\tau_{n}\right\}_{n\in\mathbb{N}}$ of integers, we say that an efficiently computable (deterministic) verifier $V=\left\{V_{n}\right\}_{n\in\mathbb{N}}$ is a $\tau$ -diameter verifier for circuits of size $s(n)$ if it takes as input a circuit $C:\{0,1\}^{n}\to\{0,1\}$ of (polynomial) size $s(n)$ and a proof $\pi$ of size $\operatorname{poly}(n)$ , and outputs $V_{n}(C,\pi)=1$ only if $\operatorname{diam}(C^{-1}(1))\leq\tau_{n}$ .

We can now define the (verifiable) low diameter set problem as follows:

Definition 14 (Verifiable $\tau$ -Diameter $\mathcal{R}$ -Set Problem).

The verifiable low diameter set problem parameterized by sequences $\tau=\left\{\tau_{n}\right\}_{n\in\mathbb{N}}$ , $\mathcal{R}=\left\{\mathcal{R}_{n}\subseteq\{0,1\}^{n}\right\}_{n\in\mathbb{N}}$ , and $\tau$ -diameter verifier $V=\left\{V_{n}\right\}_{n\in\mathbb{N}}$ is denoted by $\mathsf{VLDS}_{\tau,\mathcal{R},V}$ . The input, output, and utility are defined as follows:

$\triangleright$

Input: $x\in\{0,1\}^{n}$ .
$\triangleright$

Output: circuit $C$ and a proof $\pi$ , both of size $\operatorname{poly}(n)$ .
$\triangleright$

Utility: $u^{\mathsf{VLDS}}_{\tau_{n},\mathcal{R}_{n},V_{n}}(x,(C,\pi)):=$ $\mathds{1}\left\{V_{n}(C,\pi)=1\right\}$ and $\mathds{1}\left\{C(x)=1\mbox{ or }x\notin\mathcal{R}_{n}\right\}$ .

For convenience, we also define the following utility function

\displaystyle u^{\mathsf{eval}}_{\mathcal{R}}(x,C):=\mathds{1}\left\{C(x)=1\mbox{ or }x\notin\mathcal{R}\right\}.

Note that this does not correspond to a hard task, because a circuit that always outputs one is 1-useful. Nonetheless, it will be convenient to state usefulness of some intermediate algorithms via this utility function.

IV-D From Low Diameter Set Problem to Nearby Point Problem

Below we provide a simple observation that reduces the task of proving an $\mathsf{SDP}$ lower bound for the verifiable low diameter set problem to that of the nearby point problem. (Note here that the $\mathsf{SDP}$ mechanisms considered below can be computationally inefficient.)

Lemma 15.

If there is an $({\bm{\varepsilon}},{\bm{\delta}})$ - $\mathsf{SDP}$ ${\bm{\alpha}}$ -useful mechanism for the $\mathsf{VLDS}_{\tau,\mathcal{R},V}$ problem, then there is an $({\bm{\varepsilon}},{\bm{\delta}})$ - $\mathsf{SDP}$ ${\bm{\alpha}}$ -useful mechanism for the $\mathsf{NBP}_{\tau,\mathcal{R}}$ problem.

Proof.

Let $M$ be an $({\bm{\varepsilon}},{\bm{\delta}})$ -SDP ${\bm{\alpha}}$ -useful mechanism for the $\mathsf{VLDS}_{\tau,\mathcal{R},V}$ problem. We will construct an $({\bm{\varepsilon}},{\bm{\delta}})$ -SDP ${\bm{\alpha}}$ -useful mechanism $M^{\prime}$ for the $\mathsf{NBP}_{\tau,\mathcal{R}}$ problem.

The mechanism $M^{\prime}_{n}$ on input dataset $x\in\{0,1\}^{n}$ works as follows. First, let $(C,\pi)\leftarrow M_{n}(x)$ . If $V_{n}(C,\pi)=1$ , then output the lexicographically first element of $C^{-1}(1)$ (else, output $0^{n}$ ). This completes our description of $M^{\prime}$ .

Since $M$ is $({\bm{\varepsilon}},{\bm{\delta}})$ -SDP, we have that $M^{\prime}$ is also $({\bm{\varepsilon}},{\bm{\delta}})$ -SDP by post-processing. It remains to show that $M^{\prime}$ is ${\bm{\alpha}}$ -useful. Fix some input $x\in\{0,1\}^{n}$ . If $x\notin\mathcal{R}_{n}$ , then any output satisfies utility. Thus, it suffices to consider the case where $x\in\mathcal{R}_{n}$ . With probability $\alpha_{n}$ , we have that $V_{n}(C,\pi)=1$ (which implies that $C^{-1}(1)$ has diameter at most $\tau_{n}$ ), and $x\in C^{-1}(1)$ . Consequently, the distance between $x$ and the lexicographically first element of $C^{-1}(1)$ is at most $\tau_{n}$ . So with probability at least $\alpha_{n}$ , the output of $M^{\prime}$ is useful for $x$ , as desired. ∎

V $\mathsf{CDP}$ Mechanism for Verifiable Low Diameter Set Problem

In this section we build a CDP mechanism for the verifiable low diameter set problem. We establish the following result:

Theorem 16.

Suppose that Assumptions 18, 22 and 26 hold. Then, for all constant ${\bm{\varepsilon}}_{\mathsf{CDP}}>0$ and $\tau=\left\{\tau_{n}=n^{0.9}\right\}_{n\in\mathbb{N}}$ , there exists a $\tau$ -diameter verifier $V$ and a sequence $\mathcal{R}=\left\{\mathcal{R}_{n}\right\}_{n\in\mathbb{N}}$ of sets of sizes $|\mathcal{R}_{n}|\geq 2^{n}/n^{o(\log n)}$ , such that there exists an ${\bm{\varepsilon}}_{\mathsf{CDP}}$ - $\mathsf{CDP}$ mechanism that is $(1-o_{n}(1))$ -useful for $u^{\mathsf{VLDS}}_{\tau,\mathcal{R},V}$ .

As discussed in the overview, we first build a mechanism that is $\mathsf{CDP}$ but without verifiability using collision-resistant keyless hash functions and differing-inputs obfuscators (Section V-A). We then turn it into a verifiable one using non-interactive witness indistinguishable proofs (Section V-B).

V-A $\mathsf{CDP}$ Mechanism without Verifiability

In this section, we construct our first $\mathsf{CDP}$ mechanism (Algorithm 3). We depart from the overview in Section II slightly and do not prove a non-adaptive query lower bound explicitly. Instead, we directly show in Section V-A2 how to sample the appropriate differing-inputs circuit family. This can be then easily turned into our $\mathsf{CDP}$ mechanism via $\mathsf{di}\mathcal{O}$ in Section V-A3.

V-A1 Additional Preliminaries: Cryptographic Primitives

Throughout this section, we will repeatedly use the so-called randomized response (RR) mechanism [War65]. Specifically, $\mathsf{RR}_{\varepsilon}$ is an algorithm that takes in $x\in\{0,1\}^{n}$ and outputs $\tilde{x}\in\{0,1\}^{n}$ , where $\tilde{x}_{i}=x_{i}$ with probability $\frac{e^{\varepsilon}}{1+e^{\varepsilon}}$ independently for each $i\in[n]$ . It is well-known (and very simple to verify) that $\mathsf{RR}_{\varepsilon}$ is $\varepsilon$ - $\mathsf{SDP}$ .

Collision-Resistant Keyless Hash Functions. In our construction, we will use the Collision-Resistant Keyless Hash Functions (CRKHFs) [BKP18]. The formal definition is as given below.

Definition 17 (Collision-Resistant Keyless Hash Functions [BKP18]).

A sequence of hash functions $\left\{H_{n}:\{0,1\}^{n}\to\{0,1\}^{\gamma(n)}\right\}_{n\in\mathbb{N}}$ is $K$ -collision resistant for advice length $\zeta$ for sequences $K=\left\{K_{n}\right\}_{n\in\mathbb{N}}$ , $\zeta=\left\{\zeta_{n}\right\}_{n\in\mathbb{N}}$ if, for any PPT $\mathcal{A}$ and a sequence $\{z_{n}\}_{n\in\mathbb{N}}$ of advices where $|z_{n}|=\zeta_{n}$ , it holds for $(Y_{1},\dots,Y_{K_{n}})\leftarrow\mathcal{A}(1^{n};z_{n})$ that

\displaystyle\Pr\begin{bmatrix}Y_{1},\dots,Y_{K_{n}}\text{ are distinct \&}~{}\\ H_{n}(Y_{1})=\cdots=H_{n}(Y_{K_{n}})\end{bmatrix}

\displaystyle\leq\operatorname{negl}(n).

We skip the subscript $n$ when it is clear from context.

In [BKP18], the hash value length $\gamma(n)$ is assumed to be either linear, i.e., $\gamma(n)=\Omega(n)$ , or polynomial, i.e., $\gamma(n)=n^{\Theta(1)}$ . However, we need a collision-resistant hash function with a much smaller $\gamma(n)$ , namely $O(\log^{2}n)$ . We remark that this is still very much plausible: as long as $\gamma(n)$ is $\omega(\log n)$ , the “guess-and-check” algorithm will only produce a collision with only negligible probability. A more precise statement of our assumption is stated below.

Assumption 18.

There is an efficiently computable sequence $H=\left\{H_{n}\right\}_{n\in\mathbb{N}}$ of hash functions with hash value length $\gamma(n)=o(\log^{2}n)$ such that, for any constant $c_{1}>0$ , there exists a constant $c_{2}>0$ such that the hash function sequence is $K$ -collision resistant for advice length $\zeta$ where $K_{n}=n^{c_{2}}$ and $\zeta_{n}=n^{c_{1}}$ .

We remark that, for the existence of $\mathsf{CDP}$ mechanism (shown in this section), we will only use the multi-collision-resistance without relying on the assumption on the value of $\gamma$ . The latter is only used to show that no $\mathsf{SDP}$ mechanism exists for the problem (Section VII).

Differing-Inputs Obfuscators for Public-Coin Samplers.

For any two circuits $C_{0}$ and $C_{1}$ , a differing-inputs obfuscator $\mathsf{di}\mathcal{O}$ [BGI⁺12] guarantees that the non-existence of an efficient adversary that can find an input on which $C_{0}$ and $C_{1}$ differ implies that $\mathsf{di}\mathcal{O}(C_{0})$ and $\mathsf{di}\mathcal{O}(C_{1})$ are computationally indistinguishable. For our application, it suffices to assume a weaker notion, namely that of differing-inputs obfuscator for public-coin samplers, as defined below.

Definition 19 (Public-Coin Differing-Inputs Circuit Sampler).

An efficient non-uniform sampling algorithm $\mathsf{Sampler}=\left\{\mathsf{Sampler}_{n}\right\}$ is a public-coin differing-inputs sampler for the parameterized collection $\mathcal{C}=\left\{\mathcal{C}_{n}\right\}$ of circuits if the output of $\mathsf{Sampler}_{n}$ is distributed over $\mathcal{C}_{n}\times\mathcal{C}_{n}$ and for every efficient non-uniform algorithm $\mathcal{A}=\left\{\mathcal{A}_{n}\right\}$ , there exists a negligible function $\operatorname{negl}(\cdot)$ such that for all $n\in\mathbb{N}$ :

\displaystyle\Pr_{\theta}\begin{bmatrix}[l]C_{0}(y)\neq C_{1}(y):\\ (C_{0},C_{1})\leftarrow\mathsf{Sampler}_{n}(\theta),\\ y\leftarrow\mathcal{A}_{n}(\theta)\end{bmatrix}

\displaystyle~{}\leq~{}\operatorname{negl}(n).

Here, $\mathsf{Sampler}_{n}$ is a deterministic algorithm and the only source of randomness is the seed $\theta$ .

Definition 20 (Differing-Inputs Obfuscator for Public-Coin Samplers (cf. [IPS15])).

A uniform PPT $\mathsf{di}\mathcal{O}$ is a differing-inputs obfuscator for public-coin samplers for the parameterized circuit family $\mathcal{C}=\{\mathcal{C}_{n}\}$ if the following conditions are satisfied:

$\triangleright$

Correctness: For all $n\in\mathbb{N}$ , for all $C\in\mathcal{C}_{n}$ , for all inputs $y$ , we have that

$\Pr[C^{\prime}(y)=C(y):C^{\prime}\leftarrow\mathsf{di}\mathcal{O}(1^{n},C)]~{}=~{}1.$
$\triangleright$

Polynomial slowdown: There exists a universal polynomial $p(\cdot)$ such that for all $C\in\mathcal{C}_{n}$ , it holds that

$\Pr[|C^{\prime}|\leq p(|C|):C^{\prime}\leftarrow\mathsf{di}\mathcal{O}(1^{n},C)]~{}=~{}1.$

\triangleright

Differing-inputs: For every public-coin differing inputs sampler $\mathsf{Sampler}=\left\{\mathsf{Sampler}_{n}\right\}$ for $\mathcal{C}$ , and every (not necessarily uniform) PPT distinguisher $\mathcal{D}=\left\{D_{n}\right\}$ , there exists a negligible function $\operatorname{negl}$ such that the following holds for all $n\in\mathbb{N}$ : For $(C_{0},C_{1})\leftarrow\mathsf{Sampler}_{n}(\theta)$

\displaystyle\begin{vmatrix}[l]\Pr_{\theta}\left[D_{n}(\mathsf{di}\mathcal{O}(1^{n},C_{0}))=1\right]\\ -\Pr_{\theta}\left[D_{n}(\mathsf{di}\mathcal{O}(1^{n},C_{1}))=1\right]\end{vmatrix}~{}\leq~{}\operatorname{negl}(n).

We note that the notion of $\mathsf{di}\mathcal{O}\text{-}\mathsf{for}\text{-}\mathsf{pcS}$ is in fact weaker than the notion of general public-coin $\mathsf{di}\mathcal{O}$ as given by [IPS15]. We elaborate on this comparison in Appendix A. Whenever $n$ is clear from context, we use $\mathsf{di}\mathcal{O}(C)$ to denote $\mathsf{di}\mathcal{O}(1^{n},C)$ for simplicity. When we want to be explicit about the randomness $\rho$ (of $\operatorname{poly}(n)$ bit length) used by $\mathsf{di}\mathcal{O}$ we will denote it as $\mathsf{di}\mathcal{O}_{\rho}(C)$ .

We only need the existence of a differing-inputs obfuscator for a specific family of circuits. This circuit family will be defined later and therefore we defer formalizing our assumption to Section V-A3.

V-A2 Public-Coin Differing-Inputs Circuits from CRKHFs

The first step of our proof is to construct a differing-inputs circuit family based on CRKHFs. Our sampler is described in Algorithm 1.

Algorithm 1 Differing-Inputs Circuit Family Sampler

\mathsf{LDS}\text{-}\mathsf{Sampler}_{n}

Parameters: Adjacent datasets

x,x^{\prime}\in\{0,1\}^{n}

, hash value

\upsilon_{n}\in\{0,1\}^{\gamma(n)}

, privacy parameter

\varepsilon>0

, radius

r,\tilde{r}>0

Randomness:

\theta\sim\mathsf{RR}_{\varepsilon}(0^{n})

Output: Circuits

C_{0},C_{1}

\tilde{x}\leftarrow x\oplus\theta

(bit-wise XOR; equivalent to

\mathsf{RR}_{\varepsilon}(x)

)

C_{0}\leftarrow

circuit that on input

z

returns

\mathds{1}\left\{z\in B_{r}(x)\cap B_{\tilde{r}}(\tilde{x})\cap H^{-1}_{n}(\upsilon_{n})\right\}

C_{1}\leftarrow

circuit that on input

z

returns

\mathds{1}\left\{z\in B_{r}(x^{\prime})\cap B_{\tilde{r}}(\tilde{x})\cap H^{-1}_{n}(\upsilon_{n})\right\}

return

(C_{0},C_{1})

We next prove that the above sampler is a public-coin differing-inputs sampler, which means that any efficient adversary, even with the knowledge of $\tilde{x}$ (which is the only source of randomness), cannot find an input on which $C_{0}$ and $C_{1}$ differ. The proof starts by noticing that any input that differentiates $C_{0},C_{1}$ must, by definition of the circuits, have hash value $\upsilon_{n}$ . Therefore, if there were an adversary that can find a differing input, then we could run it multiple times to get $Y_{1},\dots,Y_{K}$ that have the same hash value. (See Algorithm 2 below.) However, our proof is not finished yet, since it is possible that $Y_{1},\dots,Y_{K}$ are not distinct. Indeed, the crux of the construction is that, due to how we select $\tilde{x}$ and define the circuits, a fixed $Y$ will be a differing input with negligible probability⁹⁹9It is also simple to see that this property suffices to prove a non-adaptive query lower bound as discussed in Section II.. It follows that $Y_{1},\dots,Y_{K}$ must be distinct w.h.p. This is formalized below.

Lemma 21.

Let $H$ be as in Assumption 18. For any constant $\varepsilon>0$ , choosing $r=0.5n^{0.9}$ and $\tilde{r}=\frac{1}{1+e^{\varepsilon}}n+n^{0.6}$ makes $\mathsf{LDS}\text{-}\mathsf{Sampler}_{n}$ (Algorithm 1) a public-coin differing-inputs sampler.

Proof.

Suppose for the sake of contradiction that for some adjacent $x,x^{\prime}\in\{0,1\}^{n}$ , there exists a PPT $\mathcal{A}^{\mathrm{DI}}$ such that

\displaystyle\Pr_{\theta}\begin{bmatrix}[l]C_{0}(y)\neq C_{1}(y):\\ (C_{0},C_{1})\leftarrow\mathsf{LDS}\text{-}\mathsf{Sampler}_{n}(\theta),\\ y\leftarrow\mathcal{A}^{\mathrm{DI}}_{n}(\theta)\end{bmatrix}

\displaystyle~{}\geq~{}n^{-c}.

(1)

for some constant $c>0$ . Furthermore, let $c_{1}$ be such that the total size of the descriptions of $\mathcal{A}^{\mathrm{DI}}_{n},\mathsf{LDS}\text{-}\mathsf{Sampler}_{n}$ is at most $n^{c_{1}}$ . Finally, let $c_{2}>0$ be as in Assumption 18 and $K=n^{c_{2}}$ .

Algorithm 2 Collision-Resistant Hash Function Adversary

\mathcal{A}^{\mathrm{CRH}}_{n}

Parameter: The target number of collisions

K\in\mathbb{N}

, constant

c>0

Advice: Descriptions of

\mathcal{A}^{\mathrm{DI}}_{n},\mathsf{LDS}\text{-}\mathsf{Sampler}_{n}

Output:

Y_{1},\dots,Y_{K}\in\{0,1\}^{n}

\perp

i\leftarrow 0

for

j=1,\dots,K\cdot n^{c+1}

\theta^{j}\leftarrow\mathsf{RR}_{\varepsilon}(0^{n})

(C^{j}_{0},C^{j}_{1})\leftarrow\mathsf{LDS}\text{-}\mathsf{Sampler}_{n}(\theta^{j})

y^{j}\leftarrow\mathcal{A}^{\mathrm{DI}}_{n}(\theta^{j})

C^{j}_{0}(y^{j})\neq C^{j}_{1}(y^{j})

then

i\leftarrow i+1

Y_{i}\leftarrow y^{j}

i\geq K

then

break

i<K

then

return

\perp

else

return

Y_{1},\dots,Y_{K}

Consider the adversary $\mathcal{A}^{\mathrm{CRH}}_{n}$ for collision-resistant hash function described in Algorithm 2. First, note that by (1) and a standard concentration inequality, the probability that $\mathcal{A}^{\mathrm{CRH}}_{n}$ outputs $\perp$ is $o_{n}(1)$ . Furthermore, notice that $C_{0},C_{1}$ can differ on $y$ only if $H_{n}(y)=\upsilon_{n}$ , meaning that $H_{n}(Y_{i})=\upsilon_{n}$ always. Therefore, it suffices for us to show that the probability that $Y_{1},\dots,Y_{K}$ are distinct is $1-o_{n}(1)$ . By a union bound, we have that $\mathcal{A}^{\mathrm{CRH}}_{n}$ violates the collision-resistance of $H$ as desired.

Thus, we are only left to show that $Y_{1},\dots,Y_{K}$ are not distinct with probability $o(1)$ . To see that this is the case, notice that

	$\displaystyle\Pr[Y_{1},\dots,Y_{K}\text{ are not distinct}]$
	$\displaystyle~{}\leq~{}\sum_{1\leq i_{1}<i_{2}\leq K}\Pr[Y_{i_{1}}=Y_{i_{2}}].$		(2)

Let us now bound $\Pr[Y_{i_{1}}=Y_{i_{2}}]$ for a fixed pair $i_{1}<i_{2}$ . Suppose that we fix a value of $Y_{i_{1}}$ and suppose that $Y_{i_{1}}$ is assigned at step $j_{1}\in[1,\dots,K\cdot n^{c+1}]$ . Conditioned on these, notice further that

$\displaystyle\Pr[Y_{i_{2}}=Y_{i_{1}}]$	$\displaystyle\leq\Pr[\exists j>j_{1},y^{j}=Y_{i_{1}}]$
	$\displaystyle\leq\Pr[\exists j>j_{1},C^{j}_{0}(Y_{i_{1}})\neq C^{j}_{1}(Y_{i_{1}})]$
	$\displaystyle\leq\sum_{j>j_{1}}\Pr[C^{j}_{0}(Y_{i_{1}})\neq C^{j}_{1}(Y_{i_{1}})].$	(3)

Now, let us bound the RHS probability for a fixed $j>j_{1}$ . To see this, first observe that $Y_{i_{1}}$ must belong to the symmetric difference $B_{r}(x)\triangle B_{r}(x^{\prime})$ ; otherwise, we must have $C^{j_{1}}_{0}(Y_{i_{1}})=C^{j_{1}}_{1}(Y_{i_{1}})$ , a contradiction to our definition of $Y_{i_{1}}$ .

Now, let $\tilde{x}^{j}$ denote the $\tilde{x}$ selected by $\mathsf{LDS}\text{-}\mathsf{Sampler}$ when constructing $C^{j}_{0},C^{j}_{1}$ . We have

\displaystyle\Pr[C^{j}_{0}(Y_{i_{1}})\neq C^{j}_{1}(Y_{i_{1}})]\leq\Pr[Y_{i_{1}}\in B_{\tilde{r}}(\tilde{x}^{j})].

(4)

Let $d:=\|Y_{i_{1}}-x\|_{1}$ and $\tilde{d}:=\|Y_{i_{1}}-\tilde{x}^{j}\|_{1}$ . Since $Y_{i_{1}}\in B_{r}(x)\triangle B_{r}(x^{\prime})$ , it holds that $d\in\{r,r+1\}$ . Thus, $\tilde{d}$ is distributed as $\mathrm{Bin}(d,\frac{e^{\varepsilon}}{1+e^{\varepsilon}})+\mathrm{Bin}(n-d,\frac{1}{1+e^{\varepsilon}})$ . We have $\operatorname{\mathbb{E}}_{\tilde{x}^{j}\sim\mathsf{RR}_{\varepsilon}(x)}\tilde{d}=\frac{1}{1+e^{\varepsilon}}n+\frac{e^{\varepsilon}-1}{e^{\varepsilon}+1}d$ . By Bernstein’s inequality,

	$\displaystyle\Pr[\tilde{d}\leq\tilde{r}]$	$\displaystyle~{}\leq~{}\exp\left(-\frac{t^{2}}{\frac{e^{\varepsilon}}{(1+e^{\varepsilon})^{2}}n+\frac{2}{3}t}\right)$
		$\displaystyle~{}\leq~{}\exp(-\Omega(n^{0.8})),$

where $t=\operatorname{\mathbb{E}}_{\tilde{x}^{j}\sim\mathsf{RR}_{\varepsilon}(x)}\tilde{d}-\tilde{r}\geq\frac{e^{\varepsilon}-1}{e^{\varepsilon}+1}(0.5n^{0.9}-1)-n^{0.6}$ . Plugging into (4), we have

\displaystyle\Pr[C^{j}_{0}(Y_{i_{1}})\neq C^{j}_{1}(Y_{i_{1}})]\leq\exp(-\Omega(n^{0.8})).

(5)

Combing (2), (3), (5), we have

	$\displaystyle\Pr[Y_{1},\dots,Y_{K}\text{ are not distinct}]$
	$\displaystyle~{}\leq~{}K^{3}n^{c+1}\cdot\exp(-\Omega(n^{0.8}))$
	$\displaystyle~{}\leq~{}\exp(-\Omega(n^{0.8})),$

where the last inequality follows from $K=n^{O(1)}$ . ∎

V-A3 From Differing-Inputs Circuits to $\mathsf{CDP}$

We will next construct a $\mathsf{CDP}$ mechanism from the previously constructed differing-inputs circuit family. First, let us state the assumption we need here:

Assumption 22.

For $H$ as in Assumption 18, any constant $\varepsilon>0$ and $r=0.5n^{0.9},\tilde{r}=\frac{1}{1+e^{\varepsilon}}n+n^{0.6}$ , there exists a differing-inputs obfuscator $\mathsf{di}\mathcal{O}$ for the sampler $\mathsf{LDS}\text{-}\mathsf{Sampler}$ .

Our mechanism can then be defined by simply applying the obfuscator to the circuit generated in the same way as $C_{1}$ in $\mathsf{LDS}\text{-}\mathsf{Sampler}_{n}$ . This mechanism $\mathcal{M}_{\mathrm{diO}}$ is described more formally in Algorithm 3. The $\mathsf{CDP}$ property of the mechanism follows rather simply from the definition of $\mathsf{di}\mathcal{O}$ and the fact that $\mathsf{RR}_{\varepsilon}$ is $\varepsilon$ - $\mathsf{SDP}$ .

Algorithm 3

\mathsf{CDP}

mechanism

\mathcal{M}_{\mathrm{diO}}

Parameter: Differing-inputs obfuscator

\mathsf{di}\mathcal{O}

, hash function

H

, parameters

\varepsilon,r,\tilde{r}

(as in Assumption 22), and a hash value

\upsilon_{n}\in\{0,1\}^{\gamma(n)}

Input: Dataset

x\in\{0,1\}^{n}

Output: Circuit

:\{0,1\}^{n}\to\{0,1\}

\tilde{x}\leftarrow\mathsf{RR}_{\varepsilon}(x)

C\leftarrow

circuit that on input

z

returns

\mathds{1}\left\{z\in B_{r}(x)\cap B_{\tilde{r}}(\tilde{x})\cap H^{-1}_{n}(\upsilon_{n})\right\}

\widehat{C}\leftarrow\mathsf{di}\mathcal{O}_{\rho}(C)

for randomness

\rho

return

\widehat{C}

Figure 1: Hybrids in proof of Theorem 23.

H_{0}

is precisely

\mathcal{M}_{\mathrm{diO}}(x)

and

H_{2}

is precisely

\mathcal{M}_{\mathrm{diO}}(x^{\prime})

Theorem 23.

Under Assumptions 18 and 22, $\mathcal{M}_{\mathrm{diO}}$ (Algorithm 3) is $\varepsilon$ - $\mathsf{CDP}$ .

Proof.

For any adjacent datasets $x,x^{\prime}$ , we want to show that $\mathcal{M}_{\mathrm{diO}}(x)\approx^{c}_{\varepsilon}\mathcal{M}_{\mathrm{diO}}(x^{\prime})$ . We show this using an intermediate hybrid, as shown in Figure 1, where changes from one hybrid to next are highlighted in red.

$\triangleright$

Distribution $H_{0}$ is precisely $\mathcal{M}_{\mathrm{diO}}(x)$ .
$\triangleright$

Distribution $H_{1}$ is a variant of $H_{0}$ , where we change $x$ to $x^{\prime}$ in the definition of $C$ , but continue to sample $\tilde{x}\sim\mathsf{RR}_{\varepsilon}(x)$ .
$\triangleright$

Distribution $H_{2}$ is a variant of $H_{1}$ , where we sample $\tilde{x}\sim\mathsf{RR}_{\varepsilon}(x^{\prime})$ . Note that this is exactly $\mathcal{M}_{\mathrm{diO}}(x^{\prime})$ .

We show that $H_{0}\approx^{c}_{\varepsilon}H_{2}$ by showing that $H_{0}\approx^{c}H_{1}$ and $H_{1}\approx_{\varepsilon,0}H_{2}$ and using basic composition (11). We have from Lemma 21, that under Assumption 18, the joint distribution of $\tilde{x}\sim\mathsf{RR}_{\varepsilon}(x)$ , and circuits $C$ in $H_{0}$ and $H_{1}$ is precisely the output of $\mathsf{LDS}\text{-}\mathsf{Sampler}$ . Thus, from Assumption 22, it follows that $H_{0}\approx^{c}H_{1}$ by post-processing (11). Next, we have that $H_{1}\approx_{(\varepsilon,0)}H_{2}$ , since the only difference between the two is the distribution of $\tilde{x}$ , and $\mathsf{RR}_{\varepsilon}(x)\approx_{(\varepsilon,0)}\mathsf{RR}_{\varepsilon}(x^{\prime})$ (again by post-processing). ∎

Finally, its utility also follows simply from a standard concentration inequality.

Theorem 24.

When choosing $\tilde{r}=\frac{1}{1+e^{\varepsilon}}n+n^{0.6}$ , $\mathcal{M}_{\mathrm{diO}}$ is $(1-o(1))$ -useful for $u^{\mathsf{eval}}_{H^{-1}_{n}(\upsilon_{n})}$ .

Proof.

Consider any dataset $x$ . If $x\notin H^{-1}_{n}(\upsilon_{n})$ , then, by definition of $u^{\mathsf{LDS}}_{H^{-1}_{n}(\upsilon_{n})}$ , the utility is $1$ . Therefore, we may only consider the case where $x\in H^{-1}_{n}(\upsilon_{n})$ .

In this case, $\Pr\left[u^{\mathsf{eval}}_{H^{-1}_{n}(\upsilon_{n})}(x,\mathcal{M}_{\mathrm{diO}}(x))=1\right]$ is equal to $\Pr_{\tilde{x}\sim\mathsf{RR}_{\varepsilon}(x)}[x\in B_{\tilde{r}}(\tilde{x})]$ . Notice that $\|x-\tilde{x}\|_{1}$ is distributed as $\mathrm{Bin}(n,\frac{1}{1+e^{\varepsilon}})$ . Therefore, applying Bernstein’s inequality, we have

	$\displaystyle\Pr_{\tilde{x}\sim\mathsf{RR}_{\varepsilon}(x)}[x\notin B_{\tilde{r}}(\tilde{x})]$	$\displaystyle~{}\leq~{}\exp\left(-\frac{t^{2}}{\frac{e^{\varepsilon}}{(1+e^{\varepsilon})^{2}}n+\frac{2}{3}t}\right)$
		$\displaystyle~{}\leq~{}\exp(-\Omega(n^{0.2})),$

where $t=\tilde{r}-\frac{n}{1+e^{\varepsilon}}=n^{0.6}$ . Thus, we have $\Pr\left[u^{\mathsf{eval}}_{H^{-1}_{n}(\upsilon_{n})}(x,\mathcal{M}_{\mathrm{diO}}(x))=1\right]=1-o(1)$ as desired. ∎

V-B $\mathsf{CDP}$ Mechanism for $\mathsf{VLDS}$

V-B1 Witness-Indistinguishable Proofs

For any $\mathsf{NP}$ language $L$ with associated verifier $V_{L}$ , let $R_{L}$ denote the corresponding relation $\left\{(x,w):x\in L\text{ and }V_{L}(x,w)=1\right\}$ . Let $R_{L}(x):=\left\{w:(x,w)\in R_{L}\right\}$ .

Definition 25 (NIWI Proof System).

A pair $(P,V)$ of PPT algorithms is a non-interactive witness indistinguishable (NIWI) proof system for an $\mathsf{NP}$ relation $R_{L}$ if it satisfies:

Correctness: for every $(x,w)\in R_{L}$

\Pr[V(x,\pi)=1:\pi\leftarrow P(x,w)]=1.

Soundness: there exists a negligible function $\operatorname{negl}$ such that for all $x\notin L$ and $\pi\in\{0,1\}^{*}$ :

\Pr[V(x,\pi)=1]\leq\operatorname{negl}(|x|).

Witness Indistinguishability: There exists a polynomial $\zeta(\cdot)$ and a negligible function $\operatorname{negl}(\cdot)$ , such that for any sequence $I=\left\{(x,w_{0},w_{1}):w_{0},w_{1}\in R_{L}(x)\right\}$ and for all circuits $C$ of size at most $\zeta(|x|)$ :

\displaystyle\begin{vmatrix}[l]\Pr_{\pi_{0}\leftarrow P(x,w_{0})}[C(x,\pi_{0})=1]\\ -\Pr_{\pi_{1}\leftarrow P(x,w_{1})}[C(x,\pi_{1})=1]\end{vmatrix}

\displaystyle~{}\leq\operatorname{negl}(|x|).

Assumption 26 ([BOV07, GOS12, BP15a]).

There exists a NIWI proof system for any language in $\mathsf{NP}$ .

V-B2 Making Utility Function Efficient Using Witness-Indistinguishable Proofs

We consider the $\mathsf{NP}$ language $\widehat{L}$ defined below, and use the corresponding NIWI verifier to define the utility for $\mathsf{VLDS}$ .

Definition 27.

Language $\widehat{L}$ consists of all circuits $\widehat{C}$ with a top AND gate, namely of the form $\widehat{C}_{0}\wedge\widehat{C}_{1}$ such that there exists some $x$ , $\tilde{x}$ and $\rho$ , such that at least one of $\widehat{C}_{0}$ or $\widehat{C}_{1}$ can be obtained as $\mathsf{di}\mathcal{O}_{\rho}(C)$ where $C$ is a circuit that takes in $z$ and computes $\mathds{1}\left\{z\in B_{r}(x)\cap B_{\tilde{r}}(\tilde{x})\cap H^{-1}(\upsilon)\right\}$ .

A “witness” for $\widehat{C}\in\widehat{L}$ is given by $w=(b,x,\tilde{x},\rho)$ , where $b\in\{0,1\}$ indicates whether the witness is provided for $\widehat{C}_{0}$ or for $\widehat{C}_{1}$ . Let $(\widehat{P},\widehat{V})$ denote the NIWI proof system for $L$ (guaranteed to exist by Assumption 26).

We consider the verifiable low diameter set problem $\mathsf{VLDS}_{\tau,H^{-1}(\upsilon),\widehat{V}}$ . Note that $\widehat{C}\in\widehat{L}$ automatically implies that $\widehat{C}$ encodes a $\tau$ -diameter set (since $\widehat{C}=\widehat{C}_{0}\wedge\widehat{C}_{1}$ , it suffices to certify that at least one of $\widehat{C}_{0}$ or $\widehat{C}_{1}$ encodes a $\tau$ -diameter set) where $\tau=2r=n^{0.9}$ .

Algorithm 4 Sub-routine

\mathcal{M}_{\mathrm{diO}}^{\mathrm{aux}}

Parameter: Differing-inputs obfuscator

\mathsf{di}\mathcal{O}

, hash function

H

, parameters

\varepsilon,r,\tilde{r}

(as in Assumption 22), and a hash value

\upsilon\in\{0,1\}^{\gamma(n)}

Input: Dataset

x\in\{0,1\}^{n}

Output: Circuit

:\{0,1\}^{n}\to\{0,1\}

\tilde{x}\leftarrow\mathsf{RR}_{\varepsilon}(x)

C\leftarrow

circuit that on input

z

returns

\mathds{1}\left\{z\in B_{r}(x)\cap B_{\tilde{r}}(\tilde{x})\cap H^{-1}_{n}(\upsilon)\right\}

\widehat{C}\leftarrow\mathsf{di}\mathcal{O}_{\rho}(C)

for randomness

\rho

return

\widehat{C}

\tilde{x}

\rho

Algorithm 5

\mathsf{CDP}

mechanism

\mathcal{M}_{\mathrm{cdp}}

Input: Dataset

x\in\{0,1\}^{n}

, radius parameters

r,\tilde{r}>0

and privacy parameter

\varepsilon

Output: Circuit

C

and a proof string

\pi

\widehat{C}_{0},\tilde{x}_{0},\rho_{0}\leftarrow\mathcal{M}_{\mathrm{diO}}^{\mathrm{aux}}(x)

\widehat{C}_{1},\tilde{x}_{1},\rho_{1}\leftarrow\mathcal{M}_{\mathrm{diO}}^{\mathrm{aux}}(x)

\widehat{C}=\widehat{C}_{0}\wedge\widehat{C}_{1}

\pi\leftarrow\widehat{P}(\widehat{C},(0,x,\tilde{x}_{0},\rho_{0}))

(NIWI proof for

\widehat{C}\in\widehat{L}

using witness

(0,x,\tilde{x}_{0},\rho_{0})

return

\widehat{C}

\pi

Theorem 28.

Under Assumptions 18, 22 and 26, $\mathcal{M}_{\mathrm{cdp}}$ (Algorithm 5) is $2\varepsilon$ - $\mathsf{CDP}$ .

Proof.

For any adjacent datasets $x$ , $x^{\prime}$ , we want to show that $\mathcal{M}_{\mathrm{cdp}}(x)\approx^{c}_{2\varepsilon}\mathcal{M}_{\mathrm{cdp}}(x^{\prime})$ . We show this through the means of intermediate hybrids, as shown in Figure 2, where changes from one hybrid to next are highlighted in red.

Figure 2: Hybrids in proof of Theorem 28.

H_{0}

is precisely

\mathcal{M}_{\mathrm{cdp}}(x)

and

H_{4}

is precisely

\mathcal{M}_{\mathrm{cdp}}(x^{\prime})

$\triangleright$

Distribution $H_{0}$ is precisely $\mathcal{M}_{\mathrm{cdp}}(x)$ .
$\triangleright$

Distribution $H_{1}$ is a variant of $H_{0}$ , where $\widehat{C}_{1}$ is generated through $x^{\prime}$ instead of $x$ .
$\triangleright$

Distribution $H_{2}$ is a variant of $H_{1}$ , where we switch $\pi$ from corresponding to witness $(0,x,\tilde{x}_{0},\rho_{0})$ to the witness $(1,x^{\prime},\tilde{x}_{1},\rho_{1})$ .
$\triangleright$

Distribution $H_{3}$ is a variant of $H_{2}$ , where $\widehat{C}_{0}$ is also generated through $x^{\prime}$ instead of $x$ .
$\triangleright$

Distribution $H_{4}$ is a variant of $H_{3}$ , where we switch $\pi$ from corresponding to witness $(1,x^{\prime},\tilde{x}_{1},\rho_{1})$ to the witness $(0,x^{\prime},\tilde{x}_{0},\rho_{0})$ . Note that this is exactly $\mathcal{M}_{\mathrm{cdp}}(x^{\prime})$ .

From Assumption 26 and post-processing (11), we have that $H_{1}\approx^{c}H_{2}$ , and similarly $H_{3}\approx^{c}H_{4}$ .

Next, we show that $H_{0}\approx^{c}_{\varepsilon}H_{1}$ . Note that the output of $H_{0}$ and $H_{1}$ do not depend on $\tilde{x}_{1}$ and $\rho_{1}$ . Thus the only material change between $H_{0}$ and $H_{1}$ is that $\widehat{C}_{1}\sim\mathcal{M}_{\mathrm{diO}}(x)$ in $H_{0}$ versus $\widehat{C}_{1}\sim\mathcal{M}_{\mathrm{diO}}(x^{\prime})$ in $H_{1}$ . From Theorem 23, we have that $\mathcal{M}_{\mathrm{diO}}(x)\approx^{c}_{\varepsilon}\mathcal{M}_{\mathrm{diO}}(x^{\prime})$ . Thus, it follows that $H_{0}\approx^{c}_{\varepsilon}H_{1}$ by post-processing (11). Similarly, it follows that $H_{2}\approx^{c}_{\varepsilon}H_{3}$ (here we use that $\tilde{x}_{0}$ and $\rho_{0}$ are immaterial to the final output of $H_{2}$ and $H_{3}$ ).

Combining these using basic composition (11), we get that $H_{0}\approx^{c}_{2\varepsilon}H_{4}$ , thus implying that $\mathcal{M}_{\mathrm{cdp}}$ is $2\varepsilon$ - $\mathsf{CDP}$ . ∎

Corollary 29.

$\mathcal{M}_{\mathrm{cdp}}$ is $(1-o(1))$ -useful for $u^{\mathsf{VLDS}}_{\tau,H^{-1}(\upsilon),\widehat{V}}$ .

Proof.

The utility for $x\notin H^{-1}(\upsilon)$ is trivially $1$ . Consider $x\in H^{-1}(\upsilon)$ . Suppose the mechanism $\mathcal{M}_{\mathrm{diO}}$ is $(1-\eta)$ -useful for $u^{\mathsf{eval}}_{H^{-1}(\upsilon)}$ . Since we sample $\widehat{C}_{0}$ and $\widehat{C}_{1}$ from $\mathcal{M}_{\mathrm{diO}}$ independently we have that $\widehat{C}(x)=1$ with probability at least $1-2\eta$ . Finally, note that the proof $\pi$ in the output of $\mathcal{M}_{\mathrm{cdp}}$ is always accepted by $\widehat{V}$ . From Theorem 24, we have that $\eta=o(1)$ , and hence $\mathcal{M}_{\mathrm{cdp}}$ is $1-2\eta=1-o(1)$ useful for $u^{\mathsf{VLDS}}_{\tau,H^{-1}(\upsilon),\widehat{V}}$ . ∎

We end this section by proving Theorem 16. The proof is essentially a straightforward combination of the previous two results. The only choice left to make is to select the hash value $\upsilon$ ; we select it so that the size of the preimage $H^{-1}(\upsilon)$ is maximized. This ensures that the set $\mathcal{R}=H^{-1}(\upsilon)$ has enough density as required in Theorem 16. (Note: the density requirement in Theorem 16 is not important for showing the existence of a $\mathsf{CDP}$ mechanism, but instead is later used to show the non-existence of $\mathsf{SDP}$ mechanisms.)

Proof of Theorem 16.

Let $H,\tau,\widehat{V}$ be as defined above. Furthermore, let $\upsilon$ be such that $H^{-1}(\upsilon)$ is maximized and $\varepsilon=\varepsilon_{\mathsf{CDP}}/2$ . The fact that there exists an $\varepsilon_{\mathsf{CDP}}$ - $\mathsf{CDP}$ mechanism that is $(1-o(1))$ -useful for $u^{\mathsf{VLDS}}_{\tau,\mathcal{R},\widehat{V}}$ follows immediately from Theorem 28 and Corollary 29. Furthermore, by our choice of $\upsilon$ , notice that $|\mathcal{R}|=|H^{-1}(\upsilon)|\geq 2^{n}/2^{\gamma(n)}\geq 2^{n}/n^{o(\log n)}$ , where the latter comes from our assumption on $\gamma$ in Assumption 18. ∎

VI $\mathsf{SDP}$ Lower Bounds for the Nearby Point Problem

In this section, we will show that there is no $O(1)$ - $\mathsf{SDP}$ algorithm for the nearby point problem with target threshold $n^{0.9}$ as long as the set $\mathcal{R}_{n}$ is fairly dense, as formalized below.

Theorem 30.

For $\tau=\left\{\tau_{n}\right\}_{n\in\mathbb{N}}$ and $\mathcal{R}=\left\{\mathcal{R}_{n}\subseteq\{0,1\}^{n}\right\}_{n\in\mathbb{N}}$ such that $\tau_{n}\leq n^{0.9}$ and $|\mathcal{R}_{n}|\geq 2^{n}/n^{o(\log n)}$ and for any constant ${\bm{\varepsilon}},{\bm{\alpha}}>0$ and ${\bm{\delta}}=1/n^{27}$ , no $({\bm{\varepsilon}},{\bm{\delta}})$ - $\mathsf{SDP}$ mechanism is ${\bm{\alpha}}$ -useful for $u^{\mathsf{NBP}}_{\tau,\mathcal{R}}$ .

To prove Theorem 30, let us first recall the standard “blatant non-privacy implies non-DP” proof¹⁰¹⁰10Here we follow the proofs in [Sur19, Man22]., which corresponds to the case $\mathcal{R}_{n}=\{0,1\}^{n}$ . At a high-level, these proofs proceed by showing that the error in each coordinate is large by “matching” each $x\in\{0,1\}^{n}$ with another point $x^{\prime}$ which is the same as $x$ except with the $i$ -th bit flipped; a basic calculation then shows that (on average) the $i$ -th bit is predicted incorrectly with large probability. Summing this up over all the coordinates yield the desired bound.

As we are in the case where $\mathcal{R}_{n}\neq\{0,1\}^{n}$ , we cannot use the proof above directly. Nonetheless, we can still adapt the above proof. More specifically, instead of looking at each coordinate at a time, we look at a block of coordinates. For each block, we try to find a matching in the same spirit as above, but we now allow the $x,x^{\prime}$ to have a larger distance; simple calculations give us a lower bound on being incorrect in this block (Section VI-B). We then “sum up” across all blocks to get a large distance (Section VI-C). Even though we get a large distance $\tau$ via this approach, the error probability (i.e. one minus usefulness) is small (i.e. $o(1)$ ). Fortunately, we can overcome this using the so-called DP hyperparameter tuning algorithm [LT19, PS21] (Section VI-D). This concludes our proof overview.

VI-A Additional Preliminaries: Tools from Differential Privacy

We will require several additional tools from DP literature, which we list below for completeness.

Laplace Mechanism. The Laplace distribution with scale parameter $b>0$ , denoted by $\operatorname{Lap}(b)$ , is the probability distribution over $\mathbb{R}$ with probability mass function $z\mapsto\frac{1}{2b}\exp(-|z|/b)$ .

Given a function $f:\mathcal{X}^{*}\to\mathbb{R}$ , its sensitivity is defined as $\Delta(f):=\max_{D,D^{\prime}}|f(D)-f(D^{\prime})|$ , where the maximum is over all pair $D,D^{\prime}$ of adjacent datasets.

The Laplace mechanism [DMNS06] is an $\varepsilon$ - $\mathsf{SDP}$ mechanism that simply outputs $f(X)+\operatorname{Lap}(\Delta(f)/\varepsilon)$ .

Group Privacy. The following fact is well-known and is often referred to as group privacy.

Fact 31 (Group Privacy (e.g., [Vad17])).

Let $M:\mathcal{X}^{*}\to\mathcal{Y}$ be an $(\varepsilon,\delta)$ - $\mathsf{SDP}$ mechanism and let $D,D^{\prime}\in\mathbb{N}^{\mathcal{X}}$ be such that $\|D-D^{\prime}\|\leq t$ , then, we have $M(D)\approx_{\varepsilon^{\prime},\delta^{\prime}}M(D^{\prime})$ where $\varepsilon^{\prime}=t\varepsilon$ and $\delta^{\prime}=\frac{e^{\varepsilon^{\prime}}-1}{e^{\varepsilon}-1}\cdot\delta$ .

DP Hyperparameter Tuning. We will also use the following result of Liu and Talwar [LT19] on DP hyperparameter tuning. We remark that some improvements in the constants has been made in [PS21], by using a different distribution of the number of repetitions. Nonetheless, since we are only interested in an asymptotic bound, we choose to work with the slightly simpler hyperparameter tuning algorithm from [LT19].

The hyperparameter tuning algorithm from [LT19] allows us to take any DP “base” mechanism $\mathcal{M}_{\mathrm{base}}$ , which outputs a candidate $y$ and a score $q\in\mathbb{R}$ , run it multiple times and output a candidate with score that is below a certain threshold.¹¹¹¹11While DP Hyperparameter tuning is typically stated for choosing based on score above a threshold, the formulations are equivalent. The precise description is in Algorithm 6.

Algorithm 6 DP Hyperparameter Tuning

\mathcal{M}_{\mathrm{tuning}}

Parameters: Mechanism

\mathcal{M}_{\mathrm{base}}

, Threshold

s

, Number of Steps

T

, Stopping Probability

\gamma

Input: Dataset

D

for

j=1,\dots,T

Let

(y,q)\leftarrow\mathcal{M}_{\mathrm{base}}(D)

q\leq s

then

return

y

(and halt)

With probability

\gamma

return

\perp

(and halt)

We will use the following DP guarantee of $\mathcal{M}_{\mathrm{tuning}}$ , which was shown in [LT19]¹²¹²12Note that this is a simplified version of [LT19, Theorem 3.1] where we simply set $\varepsilon_{0}=1$ ..

Theorem 32 (DP Hyperparameter Tuning [LT19]).

For all $\varepsilon>0$ , $\delta,\gamma\in[0,1]$ and $T\geq 2/\gamma$ , if $\mathcal{M}_{\mathrm{base}}$ is $(\varepsilon,\delta)$ - $\mathsf{SDP}$ , then $\mathcal{M}_{\mathrm{tuning}}$ (Algorithm 6) is $(2\varepsilon+1,10e^{2\varepsilon}\cdot\delta/\gamma)$ .

VI-B Weak Hardness

We start with a relatively weak hardness for the case of $\tau=0$ , i.e., the answer is considered correct iff it is the same as the input. To prove this, we recall a couple of facts.

The first is a simple relation between independent set and maximum matching. Let $\operatorname{ind}(G)$ denote the size of the maximum independent set of $G$ .

Fact 33.

For any graph $G=(V,E)$ , there exists matching of size at least $(|V|-\operatorname{ind}(G))/2$ .

Let $\mathbb{H}^{d}$ denote the distance- $d$ graph on the hypercube, i.e., $\mathbb{H}^{d}=(\{0,1\}^{n},E)$ where $({\bm{x}},{\bm{x}}^{\prime})\in E$ iff $\|{\bm{x}}-{\bm{x}}^{\prime}\|_{1}\leq d$ . Let $\binom{n}{\leq d}=\sum_{i=0}^{d}\binom{n}{i}$ . The following standard lower bound follows from a “packing argument”.

Fact 34.

For any $d\in\mathbb{N}$ , $\operatorname{ind}(\mathbb{H}^{2d+1})\leq 2^{n}/\binom{n}{\leq d}$ .

We are now ready to prove a lower bound for the nearby problem.

Theorem 35.

For any $\mathcal{R}\subseteq\{0,1\}^{n},d,\varepsilon,\delta$ , let $\varepsilon^{\prime}=(2d+1)\varepsilon$ and $\delta^{\prime}=\frac{e^{\varepsilon^{\prime}}-1}{e^{\varepsilon}-1}\delta$ . Then, for any $(\varepsilon,\delta)$ - $\mathsf{SDP}$ algorithm $M$ , we have

\displaystyle\sum_{x\in\mathcal{R}}\Pr[M(x)\neq x]\geq 0.5e^{-\varepsilon^{\prime}}(1-\delta^{\prime})\left(|\mathcal{R}|-\frac{2^{n}}{\binom{n}{\leq d}}\right).

Proof.

Let $\mathbb{H}^{2d+1}[\mathcal{R}]$ denote the subgraph of $\mathbb{H}^{2d+1}$ induced on $\mathcal{R}$ . Notice that $\operatorname{ind}(\mathbb{H}^{2d+1}[\mathcal{R}])\leq\operatorname{ind}(\mathbb{H}^{2d+1})$ . Therefore, by 33 and 34, we can conclude $\mathbb{H}^{2d+1}[\mathcal{R}]$ contains a matching of size at least $m\geq\left(|\mathcal{R}|-2^{n}/\binom{n}{\leq d}\right)/2$ . Let the matching be $(x^{1},\tilde{x}^{1}),\dots,(x^{m},\tilde{x}^{m})$ .

For each $i\in[m]$ , we have

	$\displaystyle\Pr[M(x^{i})\neq x^{i}]+\Pr[M(\tilde{x}^{i})\neq\tilde{x}^{i}]$
	$\displaystyle~{}\geq~{}\Pr[M(x^{i})=\tilde{x}^{i}]+\Pr[M(\tilde{x}^{i})\neq\tilde{x}^{i}]$
	$\displaystyle~{}\geq~{}e^{-\varepsilon^{\prime}}(\Pr[M(\tilde{x}^{i})=\tilde{x}^{i}]-\delta^{\prime})+\Pr[M(\tilde{x}^{i})\neq\tilde{x}^{i}]$
	$\displaystyle~{}\geq~{}e^{-\varepsilon^{\prime}}(\Pr[\mathcal{M}(\tilde{x}^{i})=\tilde{x}^{i}]+\Pr[\mathcal{M}(\tilde{x}^{i})\neq\tilde{x}^{i}]-\delta^{\prime})$
	$\displaystyle~{}=~{}e^{-\varepsilon^{\prime}}(1-\delta^{\prime}).$

Adding this over all $i\in[m]$ yields the claimed bound. ∎

VI-C Boosting the Distance

We can now prove a hardness for larger $\tau$ by dividing the coordinates into groups and applying the previously derived weak hardness result on each group. We note that the “non-usefulness” we get on the right hand side is still insufficient for Theorem 30; this will be dealt with in Section VI-D.

Theorem 36.

Let $n=n^{\prime}\cdot b^{\prime}$ for some $n^{\prime},b^{\prime}\in\mathbb{N}$ . For any $\mathcal{R}\subseteq\{0,1\}^{n},d,\varepsilon,\delta,\zeta$ , let $\varepsilon^{\prime}=(2d+1)\varepsilon$ and $\delta^{\prime}=\frac{e^{\varepsilon^{\prime}}-1}{e^{\varepsilon}-1}\delta$ . Then, for any $(\varepsilon,\delta)$ - $\mathsf{SDP}$ algorithm $M$ , there exists $x\in\mathcal{R}$ such that

	$\displaystyle\Pr[u^{\mathsf{NBP}}_{\zeta\cdot b^{\prime},\mathcal{R}}(M(x),x)=0]$
	$\displaystyle\textstyle~{}\geq\left(0.5e^{-\varepsilon^{\prime}}(1-\delta^{\prime})\left(1-\frac{2^{n}}{\|\mathcal{R}\|\cdot\binom{n^{\prime}}{\leq d}}\right)\right)-\zeta.$

Proof.

Let $B_{i}:=\{(i-1)n^{\prime}+1,\dots,in^{\prime}\}$ for all $i\in[b^{\prime}]$ . Furthermore, let $\mathcal{R}_{(B_{i},z_{-B_{i}})}$ denote the set of all $x\in\mathcal{R}$ such that $x_{-B_{i}}=z_{-B_{i}}$ .

First, notice that

	$\displaystyle\sum_{x\in\mathcal{R}}\Pr[u^{\mathsf{NBP}}_{\zeta\cdot b^{\prime},\mathcal{R}}(M(x),x)=0]$
	$\displaystyle\textstyle=~{}\sum_{x\in\mathcal{R}}\operatorname{\mathbb{E}}_{y\leftarrow M(x)}\mathds{1}\left\{\frac{\|\{i\in[n]\mid y_{i}\neq x_{i}\}\|}{b^{\prime}}>\zeta\right\}$
	$\displaystyle\textstyle~{}\geq~{}\sum_{x\in\mathcal{R}}\operatorname{\mathbb{E}}_{y\leftarrow M(x)}\mathds{1}\left\{\frac{\|\{i\in[b^{\prime}]\mid y_{B_{i}}\neq x_{B_{i}}\}\|}{b^{\prime}}>\zeta\right\}$
	$\displaystyle\textstyle~{}\geq~{}\sum_{x\in\mathcal{R}}\operatorname{\mathbb{E}}_{y\leftarrow M(x)}\left[\Pr_{i\in[b^{\prime}]}[y_{B_{i}}\neq x_{B_{i}}]-\zeta\right]$
	$\displaystyle\textstyle~{}=~{}\left(\frac{1}{b^{\prime}}\sum_{i\in[b^{\prime}]}\sum_{x\in\mathcal{R}}\Pr[M(x)_{B_{i}}\neq x_{B_{i}}]\right)-\zeta\|\mathcal{R}\|$
	$\displaystyle\textstyle~{}\geq~{}\frac{1}{b^{\prime}}\sum\limits_{\begin{subarray}{c}i\in[b^{\prime}]\\ z_{-B_{i}}\in\{0,1\}^{[n]\setminus B_{i}}\\ x\in\mathcal{R}_{(B_{i},z_{-B_{i}})}\end{subarray}}\Pr[M(x)_{B_{i}}\neq x_{B_{i}}]-\zeta\|\mathcal{R}\|.$

For each fixed $z_{-B_{i}}\in\{0,1\}^{[n]\setminus B_{i}}$ , consider the mechanism $M^{\prime}:\{0,1\}^{B_{i}}\to\{0,1\}^{B_{i}}$ defined by $M^{\prime}(x_{B_{i}}):=M_{i}(x_{B_{i}}\circ z_{-B_{i}})|_{B_{i}}$ . It is clear that $M^{\prime}$ is $(\varepsilon,\delta)$ - $\mathsf{SDP}$ . Furthermore, observe that $\Pr[M(x)_{B_{i}}\neq x_{B_{i}}]=\Pr[M^{\prime}(x)\neq x_{B_{i}}]$ for all $x\in\mathcal{R}_{(B_{i},z_{-B_{i}})}$ . Therefore, by applying Theorem 35 and plugging it back into the above, we get

	$\displaystyle\sum_{x\in\mathcal{R}}\Pr[u^{\mathsf{NBP}}_{\zeta\cdot b^{\prime},\mathcal{R}}(M(x),x)=0]$
	$\displaystyle\textstyle~{}\geq~{}\frac{1}{b^{\prime}}\sum\limits_{\begin{subarray}{c}i\in[b^{\prime}]\\ z_{-B_{i}}\end{subarray}}0.5e^{-\varepsilon^{\prime}}(1-\delta^{\prime})\left(\|\mathcal{R}_{(B_{i},z_{-B_{i}})}\|-\frac{2^{n^{\prime}}}{\binom{n^{\prime}}{\leq d}}\right)$
	$\displaystyle\qquad-\zeta\|\mathcal{R}\|$
	$\displaystyle\textstyle~{}=~{}\frac{1}{b^{\prime}}\sum_{i\in[b^{\prime}]}0.5e^{-\varepsilon^{\prime}}(1-\delta^{\prime})\left(\|\mathcal{R}\|-\frac{2^{n-n^{\prime}}\cdot 2^{n^{\prime}}}{\binom{n^{\prime}}{\leq d}}\right)$
	$\displaystyle\qquad-\zeta\|\mathcal{R}\|$
	$\displaystyle\textstyle~{}=~{}\left(0.5e^{-\varepsilon^{\prime}}(1-\delta^{\prime})\left(\|\mathcal{R}\|-\frac{2^{n}}{\binom{n^{\prime}}{\leq d}}\right)\right)-\zeta\|\mathcal{R}\|.$

Dividing by $|\mathcal{R}|$ then gives us the claimed bound. ∎

VI-D Boosting the Failure Probability

We will now prove the last part of the lower bound, which is to show that the existence of even slightly useful mechanism also leads to an existence of a highly useful mechanism, albeit at a slight increase in the distance threshold. The formal statement and its proof are given below; the proof uses the DP hyperparameter tuning algorithm (Theorem 32).

Theorem 37.

Suppose that there exists an $(\varepsilon,\delta)$ - $\mathsf{SDP}$ mechanism $M:\{0,1\}^{n}\to\{0,1\}^{n}$ that is $\alpha$ -useful for $u^{\mathsf{NBP}}_{\tau,\mathcal{R}}$ . Then, for all $C>0$ , there exists an $(\varepsilon^{\prime},\delta^{\prime})$ - $\mathsf{SDP}$ mechanism $\widehat{M}:\{0,1\}^{n}\to\{0,1\}^{n}$ that is $(1-1/n^{C})$ -useful for $u^{\mathsf{NBP}}_{\tau^{\prime},\mathcal{R}}$ where $\varepsilon^{\prime}=4\varepsilon+1,\delta^{\prime}=O\left(\frac{e^{4\varepsilon}n^{C}\ln n}{\alpha}\cdot\delta\right)$ and $\tau^{\prime}=\tau+O\left(\frac{\ln n}{\alpha}\right)$ .

Proof.

First, let us construct the mechanism $\mathcal{M}_{\mathrm{base}}:\{0,1\}^{n}\to\{0,1\}^{n}\times\mathbb{R}$ as follows:

$\triangleright$

On input $x\in\{0,1\}^{n}$ , first let $y\leftarrow M(x)$ .
$\triangleright$

Then, let $q=\|x-y\|_{1}+z$ where $z\sim\operatorname{Lap}(1/\varepsilon)$ .
$\triangleright$

Output $(y,q)$ .

Since $M$ is $(\varepsilon,\delta)$ - $\mathsf{SDP}$ and the Laplace mechanism is $\varepsilon$ - $\mathsf{SDP}$ , the basic composition theorem implies that the entire $\mathcal{M}_{\mathrm{base}}$ mechanism is $(2\varepsilon,\delta)$ - $\mathsf{SDP}$ .

Let $\widehat{T}=\ln(5n^{C})/\alpha$ . Let $\tau^{\prime}=\tau+2\log(10n^{C}\widehat{T})/\varepsilon$ . We now apply Algorithm 6 with $\gamma=0.5/(n^{C}\widehat{T}),T=2/\gamma$ and threshold $s=\tau^{\prime}-\log(10n^{C}\widehat{T})/\varepsilon$ . Theorem 32 ensures that the resulting algorithm $\mathcal{M}_{\mathrm{tuning}}$ is $(4\varepsilon+1,10e^{4\varepsilon}\delta/\gamma)$ - $\mathsf{SDP}$ . Our final mechanism $\widehat{M}$ is the mechanism that runs $\mathcal{M}_{\mathrm{tuning}}$ . If the output is not $\perp$ , $\widehat{M}$ returns that output. Otherwise, $\widehat{M}$ returns an arbitrary element of $\{0,1\}^{n}$ . Since $\widehat{M}$ is a post-processing of $\mathcal{M}_{\mathrm{tuning}}$ , we have $\widehat{M}$ is also $(4\varepsilon+1,10e^{4\varepsilon}\delta/\gamma)$ - $\mathsf{SDP}$ .

We will next show that $\mathcal{M}_{\mathrm{tuning}}$ is $(1-1/n^{C})$ -useful for $u^{\mathsf{NBP}}_{\tau^{\prime},\mathcal{R}}$ . By definition of the utility function, this immediately holds for any $x\notin\mathcal{R}$ . Therefore, we may only consider any $x\in\mathcal{R}$ . Consider $\mathcal{M}_{\mathrm{tuning}}$ on such an $x$ . Let $y^{i},z^{i},q^{i}$ denote the corresponding values of $y,z,q$ in the $i$ -th run of $\mathcal{M}_{\mathrm{base}}$ . We consider the following three events:

$\triangleright$

Let $\mathcal{E}_{1}$ denote the event that $|\|x^{i}-y^{i}\|_{1}-q^{i}|>\log(10n^{C}\widehat{T})/\varepsilon$ for some $i\in[\widehat{T}]$ .
$\triangleright$

Let $\mathcal{E}_{2}$ denote the event that $u_{\tau,\mathcal{R}}(y_{i})=0$ for all $i\in[\widehat{T}]$ .
$\triangleright$

Let $\mathcal{E}_{3}$ denote the event that $\mathcal{M}_{\mathrm{tuning}}$ halts and returns $\bot$ in the first $\widehat{T}$ steps.

Before we bound the probability of each event, notice that, if none of $\mathcal{E}_{1},\mathcal{E}_{2},\mathcal{E}_{3}$ occurs, we must have $u^{\mathsf{NBP}}_{\tau^{\prime},\mathcal{R}}(y)=1$ (where $y$ denotes the output of $\widehat{M}$ ), since $s-\tau,\tau^{\prime}-s\geq\log(10n^{C}\widehat{T})/\varepsilon$ . That is,

	$\displaystyle\Pr_{y\leftarrow\widehat{M}(x)}[u^{\mathsf{NBP}}_{\tau^{\prime},\mathcal{R}}(y)=0]$	$\displaystyle\leq\Pr[\mathcal{E}_{1}\vee\mathcal{E}_{2}\vee\mathcal{E}_{3}]$
		$\displaystyle\leq\Pr[\mathcal{E}_{1}]+\Pr[\mathcal{E}_{2}]+\Pr[\mathcal{E}_{3}].$

We will now bound the probability for each event. For $\mathcal{E}_{1}$ , it immediately follows from the Laplace tail bound together with a union bound that

\displaystyle\Pr[\mathcal{E}_{1}]\leq\widehat{T}\cdot 2/(10n^{C}\widehat{T})=0.2/n^{C}.

For $\mathcal{E}_{2}$ , the $\alpha$ -usefulness of $M$ implies that

\displaystyle\Pr[\mathcal{E}_{2}]\leq(1-\alpha)^{\widehat{T}}\leq 0.2/n^{C}.

Finally, for $\mathcal{E}_{3}$ , a simple union bound gives

\displaystyle\Pr[\mathcal{E}_{3}]\leq\gamma\cdot\widehat{T}\leq 0.5/n^{C}.

By combining the four inequalities above, we have

\displaystyle\Pr_{y\leftarrow\widehat{M}(x)}[u^{\mathsf{NBP}}_{\tau^{\prime},\mathcal{R}}(y)=0]<1/n^{C},

as desired. ∎

VI-E Putting Things Together: Proof of Theorem 30

Proof of Theorem 30.

Suppose for the sake of contradiction that, for some constant ${\bm{\varepsilon}}>0$ and ${\bm{\delta}}=1/n^{-27}$ there exists an $({\bm{\varepsilon}},{\bm{\delta}})$ - $\mathsf{SDP}$ mechanism ${\bm{M}}$ that is $0.01$ -useful for $u^{\mathsf{NBP}}_{\tau,\mathcal{R}}$ for every $n\in\mathbb{N}$ ; recall $\tau_{n}\leq n^{0.9}$ .

Using Theorem 37 with $C=26$ , there is a $(\hat{{\bm{\varepsilon}}},\hat{{\bm{\delta}}})$ mechanism $M^{\prime}_{n}$ for $\hat{{\bm{\varepsilon}}}=4{\bm{\varepsilon}}+1$ and $\hat{{\bm{\delta}}}=O(n^{26}\log n\cdot{\bm{\delta}})=O(\log n/n)$ that is $(1-1/n^{26})$ -useful for $u^{\mathsf{NBP}}_{\tau^{\prime}_{n},\mathcal{R}_{n}}$ where $\tau^{\prime}_{n}=\tau_{n}+O(\log n)=O(n^{0.9})$ . Plugging this into Theorem 36 with $\mathcal{R}=\mathcal{R}_{n},n^{\prime}=n^{0.05},b^{\prime}=n^{0.95},\zeta=\tau^{\prime}_{n}/b^{\prime}\leq O(n^{-0.05}),{\bm{\varepsilon}}=\hat{{\bm{\varepsilon}}},{\bm{\delta}}=\hat{{\bm{\delta}}},d=(\log n^{0.04})/3\varepsilon$ (which gives ${\bm{\varepsilon}}^{\prime}\leq\log(2n^{0.04})$ and ${\bm{\delta}}^{\prime}=O(\log n/n^{0.96})=o_{n}(1)$ in Theorem 36), we have

	$\displaystyle\frac{1}{n^{26}}\geq$	$\displaystyle~{}\left(0.5\cdot e^{-\log(2n^{0.04})}(1-o_{n}(1))\left(1-o_{n}(1)\right)\right)$
		$\displaystyle~{}\quad-O(n^{-0.05})$
	$\displaystyle=$	$\displaystyle~{}O(n^{-0.04})\cdot(1-o(1))-O(n^{-0.05}),$

which is a contradiction for any sufficiently large $n$ .

∎

VII Putting Things Together: Proof of Theorem 5

Our main theorem follows from combining the main results from the previous two sections.

Proof of Theorem 5.

Let $u=u^{\mathsf{VLDS}}_{\tau,\mathcal{R},V}$ be as given in Theorem 16, which immediately yields the existence of an ${\bm{\varepsilon}}_{\mathsf{CDP}}$ - $\mathsf{CDP}$ mechanism that is $(1-o(1))$ -useful. Furthermore, since $|\mathcal{R}|\geq 2^{n}/n^{o(\log n)}$ , Theorem 30 implies that for any constant ${\bm{\varepsilon}}_{\mathsf{SDP}},{\bm{\alpha}}>0$ , there is ${\bm{\delta}}_{\mathsf{SDP}}=1/n^{27}$ such that no $({\bm{\varepsilon}}_{\mathsf{SDP}},{\bm{\delta}}_{\mathsf{SDP}})$ - $\mathsf{SDP}$ mechanism is ${\bm{\alpha}}$ -useful for $u^{\mathsf{NBP}}_{\tau,\mathcal{R}}$ . Finally, applying Lemma 15, we can conclude that no $({\bm{\varepsilon}}_{\mathsf{SDP}},{\bm{\delta}}_{\mathsf{SDP}})$ - $\mathsf{SDP}$ mechanism is ${\bm{\alpha}}$ -useful for $u^{\mathsf{VLDS}}_{\tau,\mathcal{R},V}$ . This concludes our proof. ∎

VIII Conclusion and Discussion

In this work, we give a first task that, under certain assumptions, admits an efficient CDP algorithm but does not admit an SDP algorithm (even inefficient ones). As mentioned in Section I, perhaps the most intriguing next direction would be to see if there are more “natural” tasks for which $\mathsf{CDP}$ algorithms can go beyond known $\mathsf{SDP}$ lower bounds.

On the technical front, there are also a few interesting directions. For example, it would be interesting to see if the three assumptions in our paper can be removed, relaxed, or replaced (by perhaps more widely believed assumptions). Alternatively, we can ask the opposite question: what are the (cryptographic) assumptions necessary for separating $\mathsf{CDP}$ and $\mathsf{SDP}$ ? Such a question has been extensively studied in the multiparty model [HMST22, GMPS13, GKM⁺16, HMSS19, HNO⁺18]; for example, it is known that key-agreement is necessary and sufficient to get better-than-local-DP protocol for inner product in the two-party setting [HMST22]. Achieving such a result in our setting would significantly deepen our understanding of the $\mathsf{CDP}$ -vs- $\mathsf{SDP}$ question in the central model.

Another possible improvement is to strengthen the hardness of the adversary. In this paper, we only consider polynomial-time adversaries. Indeed, our $\mathsf{CDP}$ mechanism does not remain $\mathsf{CDP}$ against quasi-polynomial adversary. The reason is that we choose the hash value length to be only $o(\log^{2}\lambda)$ in Assumption 18, so a trivial “guess-and-check” algorithm can break this assumption in time $\lambda^{O(\log\lambda)}$ . However, as far as we are aware, there is no inherent barrier in proving a separation with $\mathsf{CDP}$ that holds even against, e.g., sub-exponential time adversaries. Achieving such a result (potentially under stronger or different assumptions) would definitely be interesting.

Furthermore, our task (or more precisely the utility function) is non-uniform (through the choice of $\upsilon_{n}$ ). It would also be interesting to have a uniform task.

Acknowledgments

We thank Prabhanjan Ananth for helpful discussions about differing-inputs obfuscation, and anonymous reviewers for helpful comments.

References

[ABG⁺13] Prabhanjan Ananth, Dan Boneh, Sanjam Garg, Amit Sahai, and Mark Zhandry. Differing-inputs obfuscation and applications. IACR Cryptol. ePrint Arch., page 689, 2013.
[Abo18] John M Abowd. The US Census Bureau adopts differential privacy. In KDD, pages 2867–2867, 2018.
[App17] Apple Differential Privacy Team. Learning with privacy at scale. Apple Machine Learning Journal, 2017.
[BCP14] Elette Boyle, Kai-Min Chung, and Rafael Pass. On extractability obfuscation. In TCC, pages 52–73, 2014.
[BCV16] Mark Bun, Yi-Hsiu Chen, and Salil P. Vadhan. Separating computational and statistical differential privacy in the client-server model. In TCC, pages 607–634, 2016.
[BGI⁺01] Boaz Barak, Oded Goldreich, Russell Impagliazzo, Steven Rudich, Amit Sahai, Salil P. Vadhan, and Ke Yang. On the (im)possibility of obfuscating programs. In CRYPTO, pages 1–18, 2001.
[BGI⁺12] Boaz Barak, Oded Goldreich, Russell Impagliazzo, Steven Rudich, Amit Sahai, Salil P. Vadhan, and Ke Yang. On the (im)possibility of obfuscating programs. J. ACM, 59(2):6:1–6:48, 2012.
[BKP18] Nir Bitansky, Yael Tauman Kalai, and Omer Paneth. Multi-collision resistance: a paradigm for keyless hash functions. In STOC, pages 671–684, 2018.
[BNO08] Amos Beimel, Kobbi Nissim, and Eran Omri. Distributed private data analysis: Simultaneously solving how and what. In CRYPTO, pages 451–468, 2008.
[BOV07] Boaz Barak, Shien Jin Ong, and Salil P. Vadhan. Derandomization in cryptography. SIAM J. Comput., 37(2):380–400, 2007.
[BP15a] Nir Bitansky and Omer Paneth. Zaps and non-interactive witness indistinguishability from indistinguishability obfuscation. In TCC, pages 401–427, 2015.
[BP15b] Elette Boyle and Rafael Pass. Limits of extractability assumptions with distributional auxiliary input. In ASIACRYPT, pages 236–261, 2015.
[BR93] Mihir Bellare and Phillip Rogaway. Ccs. pages 62–73, 1993.
[BSW16] Mihir Bellare, Igors Stepanovs, and Brent Waters. New negative results on differing-inputs obfuscation. In EUROCRYPT, pages 792–821, 2016.
[CGH04] Ran Canetti, Oded Goldreich, and Shai Halevi. The random oracle methodology, revisited. J. ACM, 51(4):557–594, 2004.
[De12] Anindya De. Lower bounds in differential privacy. In TCC, pages 321–338, 2012.
[DKM⁺06] Cynthia Dwork, Krishnaram Kenthapadi, Frank McSherry, Ilya Mironov, and Moni Naor. Our data, ourselves: Privacy via distributed noise generation. In EUROCRYPT, pages 486–503, 2006.
[DKY17] Bolin Ding, Janardhan Kulkarni, and Sergey Yekhanin. Collecting telemetry data privately. In NeurIPS, pages 3571–3580, 2017.
[DMNS06] Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam D. Smith. Calibrating noise to sensitivity in private data analysis. In TCC, pages 265–284, 2006.
[DMT07] Cynthia Dwork, Frank McSherry, and Kunal Talwar. The price of privacy and the limits of LP decoding. In STOC, pages 85–94, 2007.
[DN03] Irit Dinur and Kobbi Nissim. Revealing information while preserving privacy. In PODS, pages 202–210, 2003.
[EPK14] Úlfar Erlingsson, Vasyl Pihur, and Aleksandra Korolova. RAPPOR: Randomized aggregatable privacy-preserving ordinal response. In CCS, pages 1054–1067, 2014.
[GGHW17] Sanjam Garg, Craig Gentry, Shai Halevi, and Daniel Wichs. On the implausibility of differing-inputs obfuscation and extractable witness encryption with auxiliary input. Algorithmica, 79(4):1353–1373, 2017.
[GKM⁺16] Vipul Goyal, Dakshita Khurana, Ilya Mironov, Omkant Pandey, and Amit Sahai. Do distributed differentially-private protocols require oblivious transfer? In ICALP, pages 29:1–29:15, 2016.
[GKY11] Adam Groce, Jonathan Katz, and Arkady Yerukhimovich. Limits of computational differential privacy in the client/server setting. In TCC, pages 417–431, 2011.
[GMPS13] Vipul Goyal, Ilya Mironov, Omkant Pandey, and Amit Sahai. Accuracy-privacy tradeoffs for two-party differentially private protocols. In CRYPTO, pages 298–315, 2013.
[GOS12] Jens Groth, Rafail Ostrovsky, and Amit Sahai. New techniques for noninteractive zero-knowledge. J. ACM, 59(3):11:1–11:35, 2012.
[Gre16] Andy Greenberg. Apple’s “differential privacy” is about collecting your data – but not your data. Wired, June, 13, 2016.
[GT08] Ben Green and Terence Tao. The primes contain arbitrarily long arithmetic progressions. Annals of Mathematics, 167(2):481–547, 2008.
[HMSS19] Iftach Haitner, Noam Mazor, Ronen Shaltiel, and Jad Silbak. Channels of small log-ratio leakage and characterization of two-party differentially private computation. In TCC, pages 531–560, 2019.
[HMST22] Iftach Haitner, Noam Mazor, Jad Silbak, and Eliad Tsfadia. On the complexity of two-party differential privacy. In STOC, pages 1392–1405, 2022.
[HNO⁺18] Iftach Haitner, Kobbi Nissim, Eran Omri, Ronen Shaltiel, and Jad Silbak. Computational two-party correlation: A dichotomy for key-agreement protocols. In FOCS, pages 136–147, 2018.
[HT10] Moritz Hardt and Kunal Talwar. On the geometry of differential privacy. In STOC, pages 705–714, 2010.
[IPS15] Yuval Ishai, Omkant Pandey, and Amit Sahai. Public-coin differing-inputs obfuscation and its applications. In TCC, pages 668–697, 2015.
[JLS21] Aayush Jain, Huijia Lin, and Amit Sahai. Indistinguishability obfuscation from well-founded assumptions. In STOC, pages 60–73, 2021.
[KT18] Krishnaram Kenthapadi and Thanh T. L. Tran. PriPeARL: A framework for privacy-preserving analytics and reporting at LinkedIn. In CIKM, pages 2183–2191, 2018.
[LT19] Jingcheng Liu and Kunal Talwar. Private selection from private candidates. In STOC, pages 298–309, 2019.
[Man22] Pasin Manurangsi. Tight bounds for differentially private anonymized histograms. In SOSA, pages 203–213, 2022.
[MMP⁺10] Andrew McGregor, Ilya Mironov, Toniann Pitassi, Omer Reingold, Kunal Talwar, and Salil P. Vadhan. The limits of two-party differential privacy. In FOCS, pages 81–90, 2010.
[MPRV09] Ilya Mironov, Omkant Pandey, Omer Reingold, and Salil P. Vadhan. Computational differential privacy. In CRYPTO, pages 126–142, 2009.
[PS21] Nicolas Papernot and Thomas Steinke. Hyperparameter tuning with renyi differential privacy. CoRR, abs/2110.03620, 2021.
[RSP⁺21] Ryan Rogers, Subbu Subramaniam, Sean Peng, David Durfee, Seunghyun Lee, Santosh Kumar Kancha, Shraddha Sahay, and Parvez Ahammad. LinkedIn’s audience engagements API: A privacy preserving data analytics system at scale. J. Priv. Confiden., 11(3), 2021.
[RTTV08] Omer Reingold, Luca Trevisan, Madhur Tulsiani, and Salil P. Vadhan. Dense subsets of pseudorandom sets. In FOCS, pages 76–85, 2008.
[Sha14] Stephen Shankland. How Google tricks itself to protect Chrome user privacy. CNET, October, 2014.
[Sur19] Ananda Theertha Suresh. Differentially private anonymized histograms. In NeurIPS, pages 7969–7979, 2019.
[TZ08] Terence Tao and Tamar Ziegler. The primes contain arbitrarily long polynomial progressions. Acta Mathematica, 201(2):213 – 305, 2008.
[Vad17] Salil P. Vadhan. The complexity of differential privacy. In Tutorials on the Foundations of Cryptography, pages 347–450. Springer International Publishing, 2017.
[War65] Stanley L Warner. Randomized response: A survey technique for eliminating evasive answer bias. JASA, 60(309):63–69, 1965.

Appendix A Comparison of various $\mathsf{di}\mathcal{O}$ assumptions

We review and compare the various notions of differing inputs obfuscation, showing that the notion of $\mathsf{di}\mathcal{O}\text{-}\mathsf{for}\text{-}\mathsf{pcS}$ (Definition 20) is in fact weaker (or at least, no stronger) than all notions of differing inputs obfuscation studied in literature.

The definition of $\mathsf{di}\mathcal{O}$ as given by [BGI⁺12] did not include the notion of a sampler. Informally speaking, it requires that for all efficient adversaries $A$ there is an efficient adversary $A^{\prime}$ such that if $A$ can distinguish the obfuscation of a circuit $C_{0}$ from the obfuscation of $C_{1}$ , then for any circuits $C_{0}^{\prime}$ and $C_{1}^{\prime}$ that are functionally equivalent to $C_{0}$ and $C_{1}$ respectively, $A^{\prime}$ can find an input on which $C_{0}$ and $C_{1}$ disagree.

This notion is stronger than the corresponding notion involving samplers. Since most applications of differing-inputs obfuscation in literature are stated using differing-inputs samplers, we will only refer to $\mathsf{di}\mathcal{O}$ notions that involve these.

Definition 38 (Differing-Inputs Circuit Sampler [ABG⁺13]).

An efficient non-uniform sampling algorithm $\mathsf{Sampler}=\left\{\mathsf{Sampler}_{n}\right\}$ is a differing-inputs sampler for the parameterized collection $\mathcal{C}=\left\{\mathcal{C}_{n}\right\}$ of circuits if the output of $\mathsf{Sampler}_{n}$ is distributed over $\mathcal{C}_{n}\times\mathcal{C}_{n}\times\{0,1\}^{*}$ and for every efficient non-uniform algorithm $\mathcal{A}=\left\{\mathcal{A}_{n}\right\}$ , there exists a negligible function $\operatorname{negl}(\cdot)$ such that for all $n\in\mathbb{N}$ :

\Pr_{\theta}\begin{bmatrix}[l]C_{0}(y)\neq C_{1}(y):\\ (C_{0},C_{1},\mathsf{aux})\leftarrow\mathsf{Sampler}_{n}(\theta),\\ y\leftarrow\mathcal{A}_{n}(C_{0},C_{1},\mathsf{aux})\end{bmatrix}~{}\leq~{}\operatorname{negl}(n).

Plain Sampler.: We call a differing-inputs sampler as a Plain Sampler if $\mathsf{aux}$ is always $\bot$ .
Public-Coin Sampler.: We call a differing-inputs sampler as Public-Coin Sampler if $\mathsf{aux}$ is equal to $\theta$ (precisely Definition 19).
General Sampler.: We call a differing-inputs sampler as a General Sampler whenever we want to emphasize that $\mathsf{aux}$ is allowed to be any function of $\theta$ . In particular, plain and public-coin samplers are special cases of general samplers.

Note that, the more information that $\mathsf{aux}$ is allowed to contain, the more restricted the distribution over circuit pairs $(C_{0},C_{1})$ gets. In particular, any public-coin Sampler remains a differing-inputs Sampler if we set $\mathsf{aux}$ to be some function of $\theta$ (instead of being all of $\theta$ ), and similarly, any general differing-inputs Sampler can be converted to a plain-Sampler by simply setting $\mathsf{aux}=\bot$ .

We can consider two notions of security of differing inputs obfuscators, depending on whether or not the distinguisher has access to $\mathsf{aux}$ . Recall that the “differing-inputs” condition in Definition 20 was

\displaystyle\begin{vmatrix}[l]\Pr_{\theta}\left[D_{n}(\mathsf{di}\mathcal{O}(1^{n},C_{0}))=1\right]\\ -\Pr_{\theta}\left[D_{n}(\mathsf{di}\mathcal{O}(1^{n},C_{1}))=1\right]\end{vmatrix}

\displaystyle~{}\leq~{}\operatorname{negl}(n).

(6)

On the other hand, we could consider a different notion where for any general sampler $\mathsf{Sampler}$ , for $(C_{0},C_{1},\mathsf{aux})\leftarrow\mathsf{Sampler}_{n}(\theta)$ , we replace the “differing-inputs” condition with

\displaystyle\begin{vmatrix}[l]\Pr_{\theta}\left[D_{n}(\mathsf{di}\mathcal{O}(1^{n},C_{0}),\mathsf{aux})=1\right]\\ -\Pr_{\theta}\left[D_{n}(\mathsf{di}\mathcal{O}(1^{n},C_{1}),\mathsf{aux})=1\right]\end{vmatrix}

\displaystyle~{}\leq~{}\operatorname{negl}(n).

(7)

Depending on the type of sampler (plain or public-coin or general) and the notion of security for differing inputs obfuscators ((6) or (7)), we get various kinds of $\mathsf{di}\mathcal{O}$ assumptions, which we list below.

Plain $\mathsf{di}\mathcal{O}$ .: We refer to $\mathsf{plain}\text{-}\mathsf{di}\mathcal{O}$ as the notion of $\mathsf{di}\mathcal{O}$ that holds only against plain samplers. Note, there is no difference here between the security notions of (6) and (7), since $\mathsf{aux}=\bot$ anyway.
Public-Coin $\mathsf{di}\mathcal{O}$ .: We refer to $\mathsf{pc}\text{-}\mathsf{di}\mathcal{O}$ , as the notion of public-coin $\mathsf{di}\mathcal{O}$ defined by [IPS15], corresponding to the notion of $\mathsf{di}\mathcal{O}$ that holds only against public-coin samplers, where the distinguisher also has access to $\mathsf{aux}=\theta$ , as in (7).
General $\mathsf{di}\mathcal{O}$ .: We refer to $\mathsf{gen}\text{-}\mathsf{di}\mathcal{O}$ , as the notion of general $\mathsf{di}\mathcal{O}$ defined by [ABG⁺13], corresponding to the notion of $\mathsf{di}\mathcal{O}$ that holds for general samplers, and where the distinguisher also has access to $\mathsf{aux}$ , as in (7).
$\mathsf{di}\mathcal{O}$ for General Samplers.: We define $\mathsf{di}\mathcal{O}\text{-}\mathsf{for}\text{-}\mathsf{genS}$ as the notion of $\mathsf{di}\mathcal{O}$ that holds only against general samplers, but where the distinguisher does not have access to $\mathsf{aux}$ , as in (6).
$\mathsf{di}\mathcal{O}$ for Public-Coin Samplers.: This is precisely Definition 20, where the security of $\mathsf{di}\mathcal{O}$ holds only for public-coin samplers, where the distinguisher does not have access to $\mathsf{aux}=\theta$ , as in (6).

Figure 3: Comparisons between different

\mathsf{di}\mathcal{O}

assumptions, where

\mathsf{A}\to\mathsf{B}

denotes that existence of

\mathsf{A}

implies existence of

\mathsf{B}

, or in other words, existence of

\mathsf{A}

is a stronger assumption than existence of

\mathsf{B}

. Existence of

\mathsf{di}\mathcal{O}\text{-}\mathsf{for}\text{-}\mathsf{pcS}

(assumption used in this paper) is the weakest among all the notions.

Comparison between different $\mathsf{di}\mathcal{O}$ assumptions. The comparison between the assumptions asserting existence of each type of $\mathsf{di}\mathcal{O}$ is illustrated in Figure 3, with justification for each arrow given as follows:

$\triangleright$

Existence of $\mathsf{gen}\text{-}\mathsf{di}\mathcal{O}$ implies existence of $\mathsf{plain}\text{-}\mathsf{di}\mathcal{O}$ and $\mathsf{pc}\text{-}\mathsf{di}\mathcal{O}$ , since both are special cases corresponding to plain samplers and public-coin samplers respectively.
$\triangleright$

To the best of knowledge, it is unknown whether the assumptions of existence of $\mathsf{plain}\text{-}\mathsf{di}\mathcal{O}$ and the existence of $\mathsf{pc}\text{-}\mathsf{di}\mathcal{O}$ are comparable or not.
$\triangleright$

Existence of $\mathsf{plain}\text{-}\mathsf{di}\mathcal{O}$ implies existence of $\mathsf{di}\mathcal{O}\text{-}\mathsf{for}\text{-}\mathsf{genS}$ since any general sampler can be converted to a plain sampler by simply setting $\mathsf{aux}=\bot$ ; note that the distinguisher (in the definition of $\mathsf{di}\mathcal{O}$ ) does not have access to $\mathsf{aux}$ in either case.
$\triangleright$

Existence of $\mathsf{di}\mathcal{O}\text{-}\mathsf{for}\text{-}\mathsf{genS}$ implies existence of $\mathsf{plain}\text{-}\mathsf{di}\mathcal{O}$ and $\mathsf{di}\mathcal{O}\text{-}\mathsf{for}\text{-}\mathsf{pcS}$ since both are special cases corresponding to plain samplers and public-coin samplers respectively.
$\triangleright$

Existence of $\mathsf{pc}\text{-}\mathsf{di}\mathcal{O}$ implies existence of $\mathsf{di}\mathcal{O}\text{-}\mathsf{for}\text{-}\mathsf{pcS}$ , since the distinguisher in the definition of $\mathsf{di}\mathcal{O}\text{-}\mathsf{for}\text{-}\mathsf{pcS}$ does not have access to $\theta$ and hence is less powerful.

Finally, one may wonder, what was special about the application of $\mathsf{di}\mathcal{O}$ in this paper that only required $\mathsf{di}\mathcal{O}\text{-}\mathsf{for}\text{-}\mathsf{pcS}$ and not $\mathsf{gen}\text{-}\mathsf{di}\mathcal{O}$ or $\mathsf{pc}\text{-}\mathsf{di}\mathcal{O}$ as in prior work in cryptography. The main reason is that, in cryptographic applications, an $\mathsf{aux}$ is provided to adversaries to enable certain cryptographic functionality (such as by revealing some public key parameters), and thus, it is required that the $\mathsf{di}\mathcal{O}$ is secure even given knowledge of this $\mathsf{aux}$ information. In applications of $\mathsf{pc}\text{-}\mathsf{di}\mathcal{O}$ , the distinguisher typically does not have access to all of $\theta$ (such as some secret key parameters may be hidden), but security given knowledge of entire $\theta$ implies security given partial knowledge of $\theta$ . In the setting of this paper, there wasn’t any particular functionality that needed to be enabled, other than basic circuit evaluation, and the particular circuit samplers of interest were public-coin differing inputs samplers, which is why it suffices to only assume $\mathsf{di}\mathcal{O}\text{-}\mathsf{for}\text{-}\mathsf{pcS}$ .

	$\displaystyle\sum_{x\in\mathcal{R}}\Pr[u^{\mathsf{NBP}}_{\zeta\cdot b^{\prime},\mathcal{R}}(M(x),x)=0]$
	$\displaystyle\textstyle=~{}\sum_{x\in\mathcal{R}}\operatorname{\mathbb{E}}_{y\leftarrow M(x)}\mathds{1}\left\{\frac{\|\{i\in[n]\mid y_{i}\neq x_{i}\}\|}{b^{\prime}}>\zeta\right\}$
	$\displaystyle\textstyle~{}\geq~{}\sum_{x\in\mathcal{R}}\operatorname{\mathbb{E}}_{y\leftarrow M(x)}\mathds{1}\left\{\frac{\|\{i\in[b^{\prime}]\mid y_{B_{i}}\neq x_{B_{i}}\}\|}{b^{\prime}}>\zeta\right\}$
	$\displaystyle\textstyle~{}\geq~{}\sum_{x\in\mathcal{R}}\operatorname{\mathbb{E}}_{y\leftarrow M(x)}\left[\Pr_{i\in[b^{\prime}]}[y_{B_{i}}\neq x_{B_{i}}]-\zeta\right]$
	$\displaystyle\textstyle~{}=~{}\left(\frac{1}{b^{\prime}}\sum_{i\in[b^{\prime}]}\sum_{x\in\mathcal{R}}\Pr[M(x)_{B_{i}}\neq x_{B_{i}}]\right)-\zeta\|\mathcal{R}\|$
	$\displaystyle\textstyle~{}\geq~{}\frac{1}{b^{\prime}}\sum\limits_{\begin{subarray}{c}i\in[b^{\prime}]\\ z_{-B_{i}}\in\{0,1\}^{[n]\setminus B_{i}}\\ x\in\mathcal{R}_{(B_{i},z_{-B_{i}})}\end{subarray}}\Pr[M(x)_{B_{i}}\neq x_{B_{i}}]-\zeta\|\mathcal{R}\|.$

	$\displaystyle\sum_{x\in\mathcal{R}}\Pr[u^{\mathsf{NBP}}_{\zeta\cdot b^{\prime},\mathcal{R}}(M(x),x)=0]$
	$\displaystyle\textstyle~{}\geq~{}\frac{1}{b^{\prime}}\sum\limits_{\begin{subarray}{c}i\in[b^{\prime}]\\ z_{-B_{i}}\end{subarray}}0.5e^{-\varepsilon^{\prime}}(1-\delta^{\prime})\left(\|\mathcal{R}_{(B_{i},z_{-B_{i}})}\|-\frac{2^{n^{\prime}}}{\binom{n^{\prime}}{\leq d}}\right)$
	$\displaystyle\qquad-\zeta\|\mathcal{R}\|$
	$\displaystyle\textstyle~{}=~{}\frac{1}{b^{\prime}}\sum_{i\in[b^{\prime}]}0.5e^{-\varepsilon^{\prime}}(1-\delta^{\prime})\left(\|\mathcal{R}\|-\frac{2^{n-n^{\prime}}\cdot 2^{n^{\prime}}}{\binom{n^{\prime}}{\leq d}}\right)$
	$\displaystyle\qquad-\zeta\|\mathcal{R}\|$
	$\displaystyle\textstyle~{}=~{}\left(0.5e^{-\varepsilon^{\prime}}(1-\delta^{\prime})\left(\|\mathcal{R}\|-\frac{2^{n}}{\binom{n^{\prime}}{\leq d}}\right)\right)-\zeta\|\mathcal{R}\|.$

Towards Separating Computational and Statistical Differential Privacy

Abstract

Index Terms:

I Introduction

Question 1.

Theorem 2.

II Overview of the Results

II-A The Low Diameter Set Problem

II-B SDP Lower Bound

Lemma 3.

II-C A CDP Mechanism

Question 4.

II-C1 From Non-Adaptive Lower Bound to Computational Lower Bound

II-C2 Making the Utility Function Efficiently Computable

II-D Final Steps

Theorem 5 (Main Result).

II-E On the Plausiblility of the Cryptographic Assumptions

Final thoughts on our assumptions.

III Preliminaries

III-A Dataset and Adjacency

III-B Mechanism, Utility Function, and Usefulness

III-C Notions of Differential Privacy

Definition 6 (Statistical Indistinguishability).

Definition 7 (Statistical Differential Privacy (SDP) [DMNS06, DKM+06]).

Definition 8 (Computational Indistinguishability).

Definition 9 (Computational Differential Privacy (𝖢𝖣𝖯\mathsf{CDP}) [MPRV09]).

Definition 10 (𝖲𝖨𝖬\mathsf{SIM}-𝖢𝖣𝖯\mathsf{CDP} [MPRV09]).

Fact 11.

IV Low Diameter Set Problem and Nearby Point Problem

IV-A Simplification of Input Representation

IV-B Nearby Point Problem

Definition 12 (τ\tau-Nearby ℛ\mathcal{R}-Point Problem).

IV-C Verifiable Low Diameter Set Problem

Definition 13 (τ\tau-Diameter Verifier).

Definition 14 (Verifiable τ\tau-Diameter ℛ\mathcal{R}-Set Problem).

IV-D From Low Diameter Set Problem to Nearby Point Problem

Lemma 15.

Proof.

V 𝖢𝖣𝖯\mathsf{CDP} Mechanism for Verifiable Low Diameter Set Problem

Theorem 16.

V-A 𝖢𝖣𝖯\mathsf{CDP} Mechanism without Verifiability

V-A1 Additional Preliminaries: Cryptographic Primitives

Definition 17 (Collision-Resistant Keyless Hash Functions [BKP18]).

Assumption 18.

Differing-Inputs Obfuscators for Public-Coin Samplers.

Definition 19 (Public-Coin Differing-Inputs Circuit Sampler).

Definition 20 (Differing-Inputs Obfuscator for Public-Coin Samplers (cf. [IPS15])).

V-A2 Public-Coin Differing-Inputs Circuits from CRKHFs

Lemma 21.

Proof.

V-A3 From Differing-Inputs Circuits to 𝗖𝗗𝗣\mathsf{CDP}

Assumption 22.

Theorem 23.

Proof.

Theorem 24.

Proof.

V-B 𝖢𝖣𝖯\mathsf{CDP} Mechanism for 𝖵𝖫𝖣𝖲\mathsf{VLDS}

V-B1 Witness-Indistinguishable Proofs

Definition 25 (NIWI Proof System).

Assumption 26 ([BOV07, GOS12, BP15a]).

V-B2 Making Utility Function Efficient Using Witness-Indistinguishable Proofs

Definition 27.

Theorem 28.

Proof.

Corollary 29.

Proof.

Proof of Theorem 16.

VI 𝖲𝖣𝖯\mathsf{SDP} Lower Bounds for the Nearby Point Problem

Theorem 30.

VI-A Additional Preliminaries: Tools from Differential Privacy

Fact 31 (Group Privacy (e.g., [Vad17])).

Theorem 32 (DP Hyperparameter Tuning [LT19]).

VI-B Weak Hardness

Fact 33.

Fact 34.

Theorem 35.

Proof.

VI-C Boosting the Distance

Theorem 36.

Proof.

Definition 7 (Statistical Differential Privacy (SDP) [DMNS06, DKM⁺06]).

Definition 9 (Computational Differential Privacy ( $\mathsf{CDP}$ ) [MPRV09]).

Definition 10 ( $\mathsf{SIM}$ - $\mathsf{CDP}$ [MPRV09]).

Definition 12 ( $\tau$ -Nearby $\mathcal{R}$ -Point Problem).

Definition 13 ( $\tau$ -Diameter Verifier).

Definition 14 (Verifiable $\tau$ -Diameter $\mathcal{R}$ -Set Problem).

V $\mathsf{CDP}$ Mechanism for Verifiable Low Diameter Set Problem

V-A $\mathsf{CDP}$ Mechanism without Verifiability

V-A3 From Differing-Inputs Circuits to $\mathsf{CDP}$

V-B $\mathsf{CDP}$ Mechanism for $\mathsf{VLDS}$

VI $\mathsf{SDP}$ Lower Bounds for the Nearby Point Problem

Appendix A Comparison of various $\mathsf{di}\mathcal{O}$ assumptions

Definition 38 (Differing-Inputs Circuit Sampler [ABG⁺13]).