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, \mathcal{A})$ is $t(n)$-non-private if for every constant $\epsilon > 0$ there exists a probabilistic Turing Machine $\mathcal{M}$ with time complexity $t(n)$ so that Pr[$\mathcal{M}^{\mathcal{A}}(1^n)$ outputs $c$ s.t. $dist(c, d) < \epsilon n$] $\geq 1 - neg(n)$. The probability is taken over the coin tosses of $\mathcal{A}$ and $\mathcal{M}$.

As I understand it, this basically means that with high probability, we can always find some algorithm that essentially outputs the database (or a version of the database that differs on an arbitrarily small fraction of rows) in $t(n)$ time.

But I am having trouble understanding the part about $\mathcal{M}^{\mathcal{A}}(1^n)$. Is $1^n$ just the number $1$ repeated $n$ times? Why would we want to use $1^n$ as the input to the algorithm?



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.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.