Hot answers tagged

14

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 \in \{1,\cdots,n\}$ and all $(x_1,\cdots,x_{i-1})$ in the support of $(X_1, \cdots, X_{i-1})$, we have $\mathbb{E}[X_i | X_1=x_1, \cdots, X_{i-1}=x_{i-1}] \...


10

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)$ is an $\varepsilon$-DP algorithm, and for any $a$ in the range of $A$, $A'(\cdot, a)$ is an $\varepsilon'$-DP algorithm, then the composed algorithm $A' \circ ...


5

If you read the paper carefully, you will find a discussion about using entropy as a metric for the degree of anonymity (see Section 3). In particular, if the conditional entropy of a certain random variable is too low (conditioned on the information available to the adversary), then the adversary has narrowed down the value of the supposedly-anonymized ...


5

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 (the best upper bound is $\sqrt{T} N$ samples). This is true but not an issue for the planted clique paper you mentioned. That paper is concerned with proving a ...


4

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 subdistribution is a function $\delta:Y\to[0,1]$ such that $\sum_{y\in Y}\delta(y)\leq 1$. In other words, a probabilistic function $X\to Y$ is a function $f:...


4

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} \sum_{i=1}^n y_i -\epsilon q(x_i) - \frac{1-\epsilon}2\right| \geq \lambda\right] \leq 2 \cdot e^{-2\lambda^2 n}$$ for all $\lambda>0$. Multiply through by $...


3

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 precision; thus $x$ is represented as $x = x'/2^d$ where $x'$ is an integer. Then $x \cdot y = x' \cdot y' / 2^{2d}$, so the problem is equivalent to computing $x \...


2

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 theorems about time complexity, resource requirements, etc, that are all supposed to be expressed in terms of the size of the input, instead of its value.


1

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 exponential in the min-entropy), a random function will be a good extractor with high probability. It will cost you a factor of something like log m in the min-...


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