Hot answers tagged

15 votes
Accepted

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

I can't find a reference, so I'll just sketch the proof here. Theorem. Let $X_1, \cdots, X_n$ be real random variables. Let $a_1, \cdots, a_n, b_1, \cdots, b_n$ be constants. Suppose that, for all $i ...
  • 2,783
10 votes
Accepted

Why is differential privacy defined over the exponential function?

This answer may be disappointing, but working on a log scale really mostly just makes the formulas nicer. The definition, as written, has the following important properties: Composition: If $A(\cdot)$...
5 votes
Accepted

Tolerance parameter of statistical query model and adaptivity

What you are saying is that given $N$ random samples one cannot simulate an algorithm that makes $T$ queries to VSTAT$(N)$. If the $T$ queries are chosen adaptively then one might need more samples (...
  • 881
4 votes
Accepted

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

The definition you give is essentially the one you need. A probabilistic function from $X$ to $Y$ assigns to each $x\in X$ a subdistribution of elements of $Y$ (rather than a single $y\in Y$). Such a ...
4 votes
Accepted

Differential Privacy and Randomized Responses for Counting Queries

You have $\mathbb{E}[y_i]=\epsilon q(x_i) + (1-\epsilon)/2$ and $0 \leq y_i \leq 1$, with all they $y_i$s being independent. Thus the Chernoff-Hoeffding bound gives $$\mathbb{P}\left[\left|\frac{1}{n} ...
  • 2,783
3 votes
Accepted

Fast private computation of dot product

I will assume you are in the honest-but-curious model. You can't represent real numbers in finite space, so I will assume all values are represented in fixed-point arithmetic, to $d$ bits of ...
  • 10.5k
3 votes

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

As mentioned by Thomas in a comment, indeed, there appears to be an issue with the definition (or the theorem; depending on how you look at it), specifically regarding the quantifiers. This is also ...
  • 4,361
2 votes
Accepted

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

As Huck Bennett pointed out, $1^n$ is the "security parameter", which is a cryptographer's way of expressing that the input has length n. They express the input this way to make it easier to prove ...
  • 151
1 vote
Accepted

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

If you are working with discrete probability distributions, then for any subset $S$ of the range, you have $$ \Pr[\mathcal{M}(x)\in S] = \sum_{s\in S} \Pr[\mathcal{M}(x)=s] \leq \sum_{s\in S} e^\...
  • 4,361
1 vote

deterministic randomness extractor and privacy

I came across this late. Don't know if this question still matters. I am posting this as an answer since it is too long for a comment. If n can be 1 but m is not too large (say, at most a small ...

Only top scored, non community-wiki answers of a minimum length are eligible