<p>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.</p>

CC BY-SA 3.0
2016-04-05T18:34:28.260Z
2016-04-05T18:34:28.260Z
Jessica
<p>I am reading a paper called "Revealing Information while Preserving Privacy", by Dinur and Nissim.  There is a definition in the paper called</p>

<p>Definition 3 (Non-Privacy).  A database $\mathcal{D} = (d, \mathcal{A})$ is $t(n)$-non-private if for every constant $\epsilon &gt; 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) &lt; \epsilon n$] $\geq 1 - neg(n)$.  The probability is taken over the coin tosses of $\mathcal{A}$ and $\mathcal{M}$.</p>

<p>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.</p>

<p>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?</p>

<p>Thanks.</p>

CC BY-SA 3.0
2016-03-30T20:47:20.547Z
https://en.wikipedia.org/wiki/Security_parameter
Huck Bennett
<privacy>
Question about non-private databases and $1^n$
Jessica
# Question about non-private databases and $1^n$

(Asked by: username_0 on 2016-03-30)

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?

Thanks.

**Tags:** privacy
> **Comments:**
> **username_1**: https://en.wikipedia.org/wiki/Security_parameter  

---

## 1 answers

### Answer by username_0 on 2016-04-05. Score: 2 | Accepted answer

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.


---

