# Tag Info

1

The simplest way to prove a function $f$ is negligible if it is obviously negligible is to show that it is "more negligible" than some other function $g$ which you have already proven negligble, e.g. $g(n)=2^{-n}$. Because $g$ is negligble, there exists $n_{g_0}$ such that for all $n>n_{g_0}$ it holds that $g(n)<1/{n^c}$ for any fixed choice of $c$. ...

0

It would be pretty useful if you would describe particularly what you're doing. This is because it can be easy to use more context to design more efficient DP algorithms. Consider a database $D$ where each user has some number in $[k]$ associated with them, and you want to return a differentially private estimate of: $$p_k = \Pr_{x\in D}[x = k]$$ You're ...

0

A simulator $S$ might work as follows: it generates a random $(c,z)$ and calculates $R=g^{z}X^{-c}$ and $R^{'}=X^{z}(X^{'})^{-c}$. Clearly, $((R,R^{'}),c,z)$ have the same distribution as in a real run. Namely, random values satisfying $g^{z}=RX^{c}$ and $X^{z}=R^{'}(X^{'})^{c}$.

4

They mention $H(nonce, key)$ is modeled as a random oracle. Then, $H(nonce, key) \oplus M\cong U\oplus M$ where $U$ is uniformly random, so the encryption scheme (essentially) becomes the one time pad. This is a fairly standard construction. One "flaw" with the one-time pad is that everything has a valid decryption. Given that this is the case, how can you ...

Top 50 recent answers are included