Questions tagged [privacy]

Theoretical questions related to Privacy

Filter by
Sorted by
Tagged with
3 votes
1 answer

Proof and interpretation of the No Free Lunch theorem in data privacy

This question relates to a supposed counterexample to the No Free Lunch theorem governing data privacy mechanisms, as stated by Kifer et al (Section 2.1). Colloquially, the theorem states that no ...
Jnov's user avatar
  • 39
0 votes
1 answer

Differential privacy definition: subset of range of values vs. equals a value in the range

Consider only $\epsilon$-differential privacy. The textbook definition for this is: Definition 1: "A randomized algorithm $\mathcal{M}$ with domain $\mathbb{N}^{|\chi|}$ is $\epsilon$-...
user1246462's user avatar
3 votes
1 answer

Fast private computation of dot product

Consider two paranoid parties Alice and Bob. Say Alice owns a secret vector $x=(x_1,\ldots,x_n) \in \mathbb R^n$ and Bob owns a secret vector $y=(y_1,\ldots,y_n) \in \mathbb R^n$. Question. How can ...
dohmatob's user avatar
  • 291
4 votes
1 answer

Why is differential privacy defined over the exponential function?

For adjacent database $D,D'$, a randomized algorithm $A$ is $\varepsilon$-differential private when the following satisfies $$\frac{\Pr(A(D) \in S)}{\Pr(A(D') \in S)} \leq e^\varepsilon,$$ where $S$ ...
user9414424's user avatar
13 votes
2 answers

What is the proof of this nonstandard version of Azuma's inequality?

In Appendix B of Boosting and Differential Privacy by Dwork et al., the authors state the following result without proof and refer to it as Azuma's inequality: Let $C_1, \dots, C_k$ be real-valued ...
William Hoza's user avatar
  • 1,733
1 vote
1 answer

Differential Privacy and Randomized Responses for Counting Queries

I'm trying to understand a basic randomized response mechanism for differential privacy (concrete definition not relevant for the question), but I have some trouble understanding the last step in the ...
Cryptonaut's user avatar
1 vote
1 answer

Question about non-private databases and $1^n$

I am reading a paper called "Revealing Information while Preserving Privacy", by Dinur and Nissim. There is a definition in the paper called Definition 3 (Non-Privacy). A database $\mathcal{D} = (d,...
Jessica's user avatar
  • 151
2 votes
1 answer

Tolerance parameter of statistical query model and adaptivity

It seems that the reasonable assumption for the tolerance parameter of statistical query model is roughly $1/\sqrt{n}$, which is obtained from concentration inequalities (see, e.g., Definition 2.3 of ...
Minkov's user avatar
  • 842
4 votes
1 answer

What is a probabilistic function and where can I learn more about them?

I am reading a paper on privacy that says we can model something as an arbitrary probabilistic function from $X^M \to X^M$. I'm trying to figure out what exactly that means. I saw another paper that ...
Kristin's user avatar
  • 43
1 vote
1 answer

deterministic randomness extractor and privacy

Suppose $X$ is a message which takes values on the set $\{x_1, \dots, x_m\}$ with probability distribution $P_X$. We transmit the message $X$ over the channel $P_{Y|X}$ which outputs $Y$ taking ...
SAmath's user avatar
  • 425
-2 votes
1 answer

What's the connection between entropy and deanonymization?

I'm reading this article about how personal information that was anonymaized can usually be re identified. In the article at Theorem 3 the writers talk about ...
Ramzi Kahil's user avatar
4 votes
2 answers

To what extent is anonymity through a Chaum mix compromised by using trusted mixes in the cascade?

As I understand it, a fundamental of Chaum's mix-net is that, absent an external adversary who can analyse traffic on links within the network, no mix can link the source and destination of any ...
eggyal's user avatar
  • 41
4 votes
2 answers

Support Vector Machines and privacy-preservation

suppose we have data matrix A m-by-n (m observations and n features) which I want to Apply SVM on it achieving privacy (Privacy-Preserving SVM) the questions are:- 1 - Is applying kernel trick ...
Omar Osama's user avatar
23 votes
1 answer

Estimating a percentile among distributed nodes without revealing values

I have a fairly unique problem to solve and I am hoping somebody here can give me some insight into how to best tackle it. Problem: Suppose a list of N numbers is shared among a set of participants ...
user avatar