Theoretical questions related to Privacy

learn more… | top users | synonyms

1
vote
1answer
71 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} = ...
2
votes
1answer
83 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 ...
4
votes
1answer
169 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 ...
0
votes
1answer
87 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 ...
-2
votes
1answer
111 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 ...
4
votes
2answers
395 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 ...
4
votes
2answers
396 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 ...
23
votes
1answer
665 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 ...