Questions tagged [privacy]

Theoretical questions related to Privacy

Filter by
Sorted by
Tagged with
3 votes
1 answer
205 views

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
114 views

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
147 views

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
255 views

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
958 views

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
807 views

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
81 views

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
157 views

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
2k views

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
136 views

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
203 views

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
597 views

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
434 views

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
693 views

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