Suna Bensch

Markus Holzer

Martin Kutrib

Andreas Malcher

Input-Driven Stack Automata

We introduce and investigate input-driven stack automata, which are a generalization of input-driven pushdown automata that recently became popular under the name visibly pushdown automata. Basically, the idea is that the input letters uniquely determine the operations on the pushdown store. This can nicely be generalized to stack automata by further types of input letters which are responsible for moving the stack pointer up or down. While visibly pushdown languages share many desirable properties with regular languages, input-driven stack automata languages do not necessarily so. We prove that deterministic and nondeterministic input-driven stack automata have different computational power, which shows in passing that one cannot construct a deterministic input-driven stack automaton from a nondeterministic one. We study the computational capacity of these devices. Moreover, it is shown that the membership problem for nondeterministic input-driven stack automata languages is NP-complete.

Introduction

Finite automata have intensively been studied and, moreover, have been extended in several different ways. Typical extensions in the view of [START_REF] Ginsburg | Algebraic and Automata-Theoretic Properties of Formal Languages[END_REF] are pushdown tapes [START_REF] Chomsky | Handbook of Mathematic Psychology[END_REF], stack tapes [START_REF] Ginsburg | One-way stack automata[END_REF], or Turing tapes. The investigations in [START_REF] Ginsburg | Algebraic and Automata-Theoretic Properties of Formal Languages[END_REF] led to a rich theory of abstract families of automata, which is the equivalent to the theory of abstract families of languages (see, for example, [START_REF] Salomaa | Formal Languages[END_REF]). On the other hand, slight extensions to finite automata such as a one-turn pushdown tape lead to machine models that can no longer be determinized, that is, the nondeterministic machine model is more powerful than the deterministic one. Moreover, fundamental problems such as membership become more complicated than for languages accepted by finite automata. For example, the equivalence problem turns out to be undecidable, while for regular languages this problem is decidable, and its complexity depends on the machine type used (deterministic or nondeterministic finite automata).

Recently a pushdown automaton model, called visibly pushdown automaton, was popularized by [START_REF] Alur | Adding nesting structure to words[END_REF], which shares many desirable properties with regular languages, but still is powerful enough to describe important context-free-like behavior. The idea on visibly pushdown automata is that the input letters uniquely determine whether the automaton pushes a symbol, pops a symbol, or leaves the pushdown unchanged. Such devices date back to the seminal paper [START_REF] Mehlhorn | Pebbling mountain ranges and its application of DCFL-recongnition[END_REF] and its follow-ups [START_REF] Von Braunmühl | Input-driven languages are recognized in log n space[END_REF] and [START_REF] Dymond | Input-driven languages are in log n depth[END_REF], where this machine model is called input-driven pushdown automaton. One of the most important properties on visibly pushdown automata languages or, equivalently, input-driven pushdown automata languages is that deterministic and nondeterministic automata are equally powerful. Moreover, the language class accepted is closed under almost all basic operations in formal language theory. Since the recent paper [START_REF] Alur | Adding nesting structure to words[END_REF], visibly pushdown automata are a vivid area of research, which can be seen by the amount of literature, for example, [START_REF] Alur | Adding nesting structure to words[END_REF][START_REF] Chervet | Minimizing variants of visibly pushdown automata[END_REF][START_REF] Crespi-Reghizzi | Operator precedence and the visibly pushdown property[END_REF][START_REF] Han | Nondeterministic state complexity of nested word automata[END_REF][START_REF] Okhotin | State complexity of operations on input-driven pushdown automata[END_REF][START_REF] Piao | Operational state complexity of nested word automata[END_REF]. In some of these papers yet another name is used for visibly pushdown automata, namely nested word automata, which may lead to some confusion.

Here we generalize the idea of input-driven pushdown automata to inputdriven stack automata. Since the main difference between a pushdown and a stack is that the latter storage type is also allowed to read information from the inside of the stack and not only from the top, the idea that input letters control the stack behavior easily applies. Hence, in addition to the letters that make the automaton push, pop, or leave the stack unchanged, two new types of letters that allow the movement of the stack pointer up or down are introduced. This leads us to the strong version of a input-driven stack automaton. Relaxing the condition on being input-driven when reading the stack contents, gives the basic idea of a weak input-driven stack automaton. We compare both automata models and show that the strong version is strictly less powerful than the corresponding weak version for deterministic devices. Moreover, when staying with the same model, nondeterminism turns out to be more powerful than determinism, which shows in passing that in both cases determinization is not possible. This sharply contrasts the situation for input-driven pushdown automata. Concerning decidability questions, we would like to note that the results in [START_REF] Ginsburg | One-way stack automata[END_REF] imply that emptiness is decidable for nondeterministic input-driven stack automata and equivalence with regular languages is decidable for deterministic input-driven stack automata. Finally, we also show that the fixed membership problem for input-driven stack automata languages, even for the strong automaton model, has the same complexity as for languages accepted by ordinary stack automata, namely it is NP-complete, and therefore intractable. This again is in sharp contrast to the situation on input-driven pushdown automata languages, whose membership problem is NC 1 -complete [START_REF] Dymond | Input-driven languages are in log n depth[END_REF] while ordinary pushdown automata languages are LOGCFL-complete [START_REF] Sudborough | On the tape complexity of deterministic context-free languages[END_REF].

Preliminaries and Definitions

We write Σ * for the set of all words over the finite alphabet Σ. The empty word is denoted by λ, and we set Σ + = Σ * \ {λ}. The reversal of a word w is denoted by w R and for the length of w we write |w|. We use ⊆ for inclusions and ⊂ for strict inclusions.

A nondeterministic one-way stack automaton is a classical nondeterministic pushdown automaton which is enhanced with an additional pointer that is allowed to move inside the stack without altering the stack contents. In this way it is possible to read but not to change information which is stored on the stack. Such a stack automaton is called input-driven, if the next input symbol defines the next action on the stack, that is, pushing a symbol onto the stack, popping a symbol from the stack, changing the internal state without changing the stack, or moving inside the stack by going up or down. To this end, we assume that the input alphabet Σ is partitioned into the sets Σ c , Σ r , Σ i , Σ u , and Σ d , that control the actions push (call), pop (return), state change without changing the stack (internal), and up and down movement of the stack pointer. A formal definition reads as follows.

Definition 1. A strong nondeterministic one-way input-driven stack automaton (1sNVSA) is a system M = Q, Σ, Γ, ⊥, q 0 , F, δ c , δ r , δ i , δ u , δ d , where 1. Q is the finite set of internal states, 2. Σ is the finite set of input symbols consisting of the disjoint union of sets Σ c , Σ r , Σ i , Σ u , and Σ d , 3. Γ is the finite set of stack symbols, 4. ⊥ ∈ Γ is the initial stack or bottom-of-stack symbol, 5. Γ is a marked copy of Γ , that is Γ = { a | a ∈ Γ }, where the symbol ⊥ is denoted by ⊥, 6. q 0 ∈ Q is the initial state, 7. F ⊆ Q is the set of accepting states, and 8. δ c is the partial transition function mapping Q × Σ c into the subsets of Q × (Γ \ {⊥}), 9. δ r is the partial transition function mapping Q × Σ r × Γ into the subsets of Q, 10. δ i is the partial transition function mapping Q × Σ i into the subsets of Q, 11. δ d is the partial transition function mapping

Q × Σ d × (Γ ∪ Γ ) into the subsets of Q, 12. δ u is the partial transition function mapping Q × Σ u × (Γ ∪ Γ ) into the subsets of Q.
A configuration of a 1sNVSA M = Q, Σ, Γ, ⊥, q 0 , F, δ c , δ r , δ i , δ u , δ d at some time t ≥ 0 is a quadruple c t = (q, w, s, p), where q ∈ Q is the current state, w ∈ Σ * is the unread part of the input, s ∈ Γ Γ * ⊥ ∪ {⊥} gives the current stack contents, and 1 ≤ p ≤ |s| gives the current position of the stack pointer. Let s = s n s n-1 • • • s 1 denote the stack contents. Consider the projection [•] : (Γ ∪ Γ ) + → (Γ ∪ Γ ) such that s[p] = s p , for 1 ≤ p ≤ n. Furthermore, let ϕ be a mapping which marks the first letter of a string in Γ + , that is,

ϕ : Γ + → Γ Γ * such that ϕ(a 1 a 2 • • • a n ) = a 1 a 2 • • • a n . By definition, ϕ(⊥) = ⊥.
The initial configuration for input w is set to (q 0 , w, ⊥, 1). During its course of computation, M runs through a sequence of configurations. One step from a configuration to its successor configuration is denoted by . Let a ∈ Σ, w ∈ Σ * , s ∈ Γ Γ * ⊥ ∪ {⊥}, t ∈ Γ * ⊥, 1 ≤ p ≤ |s|, and Z ∈ Γ . We set 1. (q, aw, s, p) (q , w, Z ϕ -1 (s), |s| + 1), if a ∈ Σ c and (q , Z) ∈ δ c (q, a), 2. (q, aw, Z t, p) (q , w, ϕ(t), |t|), if a ∈ Σ r and q ∈ δ r (q, a, Z ), 3. (q, aw, ⊥, 1) (q , w, ⊥, 1), if a ∈ Σ r and q ∈ δ r (q, a, ⊥), 4. (q, aw, s, p) (q , w, s, p), if a ∈ Σ i and q ∈ δ i (q, a), 5. (q, aw, s, p) (q , w, s, p + 1), if a ∈ Σ u , q ∈ δ u (q, a, s[p]), and s[p] ∈ Γ , 6. (q, aw, s, p) (q , w, s, p), if a ∈ Σ u , q ∈ δ u (q, a, s[p]), and s[p] ∈ Γ , 7. (q, aw, s, p) (q , w, s, p -1), if a ∈ Σ d , q ∈ δ d (q, a, s[p]), and s[p] = ⊥, 8. (q, aw, s, p) (q , w, s, p), if a ∈ Σ d , q ∈ δ d (q, a, s[p]), and s[p] = ⊥.

As usual, we define the reflexive, transitive closure of by * .

So, the pushing of a symbol onto the stack is described by Σ c and δ c , and the popping of a symbol is described by Σ r and δ r . With the help of the mappings ϕ and ϕ -1 it is possible to mark the new topmost symbol suitably. The internal change of the state without altering the stack contents is described by Σ i and δ i . We remark that δ c and δ i do not depend on the topmost stack symbol, but only on the current state and input symbol. This is not a serious restriction since every automaton can be modified in such a way that the topmost stack symbol is additionally stored in the state set. In this context, the question may arise of how a state can store the new topmost stack symbol in case of popping. This can be solved by a similar construction as given in [START_REF] Kutrib | Reversible pushdown automata[END_REF], where every pushdown automaton is converted to an equivalent pushdown automaton such that every stack symbol is a pair of stack symbols consisting of the symbol on the stack and its immediate predecessor.

The moves inside the stack are described by Σ d , δ d and Σ u , δ u , respectively. Up-moves at the top of the stack and down-moves at the bottom of the stack can only change the state, but do not affect the position of the stack pointer. So, the pointer can never go below the bottom and beyond the top of the stack. To ensure the latter the topmost stack symbol is suitably marked. By definition, transition functions δ c and δ r can only be applied if the stack pointer is at the topmost stack symbol. Thus, we stipulate the following behavior: if δ c or δ r have to be applied and the stack pointer is inside the stack, then the stack pointer is set to the topmost symbol, and the new symbol is pushed onto the stack or the topmost symbol is popped off the stack. The bottom-of-stack symbol ⊥ can neither be pushed onto nor be popped from the stack.

The language accepted by a 1sNVSA is precisely the set of words w such that there is some computation beginning with the initial configuration and ending in a configuration in which the whole input is read and an accepting state is entered:

L(M ) = { w ∈ Σ * | (q 0 , w, ⊥, 1) * (q, λ, s, p) with q ∈ F, s ∈ Γ Γ * ⊥ ∪ {⊥}, and 1 ≤ p ≤ |s| }.
If in any case each δ r , δ c , δ i , δ u , and δ d is either undefined or a singleton, then the stack automaton is said to be deterministic. Strong deterministic stack automata are denoted by 1sDVSA. In case that no symbol is ever popped from the stack, that is, δ r = ∅, the stack automaton is said to be non-erasing. Strong nondeterministic and deterministic non-erasing stack automata are denoted by 1sNENVSA and 1sNEDVSA. The family of all languages accepted by an inputdriven stack automaton of some type X is denoted by L (X).

In order to clarify our notion we continue with an example.

Example 2. The non-context-free language { a n b n c n+1 | n ≥ 1 } is accepted by the 1sNEDVSA M = {q 0 , q 1 , q 2 , q 3 }, Σ, {A, ⊥}, ⊥, q 0 , {q 3 }, δ c , δ r , δ i , δ u , δ d , where Σ c = {a}, Σ u = {c}, Σ d = {b}, and Σ r = Σ i = ∅.
The transition functions δ r and δ i are undefined, and δ c , δ u , and δ d are as follows.

(1)

δ c (q 0 , a) = (q 0 , A ) (2) δ d (q 0 , b, A ) = q 1 (3) δ d (q 1 , b, A) = q 1 (4) δ u (q 1 , c, ⊥) = q 2 (5) δ u (q 2 , c, A) = q 2 (6) δ u (q 2 , c, A ) = q 3
Since δ r is undefined, M is non-erasing. An input is accepted only if M eventually enters state q 3 . To this end, it must be in state q 2 . Similarly, to get into state q 2 it must be in state q 1 , and the only possibility to change into state q 1 is from q 0 . If the input does not begin with an a, the computation blocks and rejects immediately. So, any accepting computation starts with a sequence of transitions (1) reading a prefix of the form a n , for n ≥ 1. This yields a configuration (q 0 , w 1 , A A n-1 ⊥, n + 1). Since for input symbol c no transition is defined from q 0 , the remaining input w 1 must have a prefix of the form b m , for m ≥ 1. Therefore, M applies one transition (2) and, subsequently, tries to apply m -1 transitions (3). If m < n, this yields a configuration (q 1 , w 2 , A A n-1 ⊥, p), where 2 ≤ p ≤ n, and M blocks and rejects if an a or a c follows. Similarly, if m > n, after reading b n a configuration (q 1 , w 2 , A A n-1 ⊥, 1) is reached, on which M blocks and rejects when trying to read the next b. Therefore, in any accepting computation w 1 must begin with exactly n copies of b. Since for input symbol a no transition is defined from q 1 , the remaining input w 2 must have a prefix of the form c , for ≥ 1. Therefore, M applies one transition (4) and, subsequently, applies transitions [START_REF] Crespi-Reghizzi | Operator precedence and the visibly pushdown property[END_REF]. If < n, this yields a configuration (q 2 , w 3 , A A n-1 ⊥, p), where 2 ≤ p ≤ n, and M blocks and rejects if an a or a b follows, and does not accept if the input has been consumed. If ≥ n, a configuration (q 2 , w 3 , A A n-1 ⊥, n + 1) is reached. Next, if = n + 1 then M applies transition [START_REF] Dymond | Input-driven languages are in log n depth[END_REF] and accepts the input a n b b c n+1 . For > n + 1 the computation blocks.

Next, we introduce weak variants of input-driven stack automata, for which moves inside the stack are not necessarily input-driven. To this end, we have to extend the domain of δ d and δ u appropriately and to adapt the derivation relation accordingly. First we explain how to modify the transition functions in the definition of input-driven stack automata, where items 11 and 12 are changed to 11 . δ d is the partial transition function mapping Q×Σ ×(Γ ∪Γ ) into the subsets of Q,

. δ u is the partial transition function mapping Q×Σ ×(Γ ∪Γ ) into the subsets of Q.

In the weak mode, the stack can only by entered by reading an input symbol from Σ d . Being inside the stack, the pointer may move up and down for any input symbol. When the top of the stack is reached, the stack is left and any new entering needs another input symbol from Σ d . So, Σ u is not necessary, but we keep it for the sake of compatibility. For the weak mode, the relation is adapted by replacing items 5 to 8 by the following ones:

5 . (q, aw, s, p) (q , w, s, p + 1), if a ∈ Σ, q ∈ δ u (q, a, s[p]), and s[p] ∈ Γ , 6 . (q, aw, s, p) (q , w, s, p), if a ∈ Σ u , q ∈ δ u (q, a, s[p]), and s[p] ∈ Γ , a. (q, aw, s, p) (q , w, s, p -1), if a ∈ Σ d , q ∈ δ d (q, a, s[p]), s[p] ∈ Γ , and ands[p] = ⊥. b. (q, aw, s, p) (q , w, s, p), if |s| ≥ 2, a ∈ Σ, q ∈ δ d (q, a, s[p]), and s[p] = ⊥.

s[p] = ⊥, b. (q, aw, s, p) (q , w, s, p -1), if a ∈ Σ, q ∈ δ d (q, a, s[p]), s[p] ∈ Γ , and s[p] = ⊥, a. (q, aw, s, p) (q , w, s, p), if |s| = 1, a ∈ Σ d , q ∈ δ d (q, a, s[p]),
If for every q ∈ Q, a ∈ Σ, and Z ∈ Γ ∪Γ each of the three sums |δ r (q, a, Z)|+ |δ u (q, a, Z)| + |δ d (q, a, Z)|, |δ c (q, a)| + |δ u (q, a, Z)| + |δ d (q, a, Z)|, and |δ i (q, a)| + |δ u (q, a, Z)|+|δ d (q, a, Z)| is at most one, then the weak stack automaton is said to be deterministic. Weak deterministic stack automata are denoted by 1wDVSA. Moreover, weak nondeterministic and deterministic non-erasing stack automata are denoted by 1wNENVSA and 1wNEDVSA, respectively.

Computational Capacity

We investigate the computational capacity of input-driven stack automata working in strong and weak mode, and prove that these machines induce a strict hierarchy of language families with respect to the following three features: (i) strong and weak mode, (ii) determinism and nondeterminism, and (iii) non-erasing and erasing stack. First we consider deterministic machines and compare weak nonerasing mode with strong erasing mode.

Lemma 3. L 1 = { a n ba n-1 c | n ≥ 1 } ∈ L (1wNEDVSA) \ L (1sDVSA).
Proof. The main idea for a 1wNEDVSA accepting L 1 is to push some symbol on the stack for every input symbol a. When the b appears in the input the stack pointer is moved one position down, that is, to position n. At the same time a certain state is entered which ensures that the stack pointer moves down for subsequent symbols a. In this way, the pointer reaches the bottom of the stack after reading a n-1 . If in this situation a c follows, the input is accepted with an up move, otherwise the input is rejected. Clearly, the automaton constructed is deterministic and non-erasing.

To show that L 1 ∈ L (1sDVSA), we assume in contrast to the assertion that L 1 is accepted by a 1sDVSA M = Q, Σ, Γ, ⊥, q 0 , F, δ c , δ r , δ i , δ u , δ d . Suppose that a ∈ Σ c . Since the stack is initially empty up to ⊥, any application of δ i , δ u , δ d , or δ r can only alter the current state. Therefore, there are two sufficiently large natural numbers n 1 = n 2 and a state q ∈ Q, so that (q 0 , a n1 ba n1-1 c, ⊥, 1) * (q, ba n1-1 c, ⊥, 1) * (f 1 , λ, s 1 , p 1 ) and

(q 0 , a n2 ba n2-1 c, ⊥, 1) * (q, ba n2-1 c, ⊥, 1)

* (f 2 , λ, s 2 , p 2 ), for f 1 , f 2 ∈ F , s 1 , s 2 ∈ Γ Γ * ⊥ ∪ {⊥}, and 1 ≤ p i ≤ |s i |, for i = 1, 2. This implies (q 0 , a n1 ba n2-1 c, ⊥, 1) * (q, ba n2-1 c, ⊥, 1) * (f 2 , λ, s 2 , p 2 )
and, thus, a n1 ba n2-1 c ∈ L 1 , which is a contradiction. Now suppose that a ∈ Σ c . Then for every symbol a, some stack symbol is pushed onto the stack. Since Q is finite, the sequence of states passed through while reading a large number of a's is eventually periodic. Therefore, the sequence of symbols pushed onto the the stack is also eventually periodic. Say, it is of the form uv * w, where u is a suffix of v, v ∈ Γ + , w ∈ Γ * ⊥, and |w|, |v| ≤ |Q|. Therefore, there are two sufficiently large natural numbers n 1 = n 2 , a state q ∈ Q, strings u, v, w, where u is a suffix of v, v ∈ Γ + , w ∈ Γ * ⊥, and natural numbers k 2 > k 1 > 0 so that (q 0 , a n1 ba n1-1 c, ⊥, 1) * (q, ba n1-1 c, ϕ(u)v k1 w, n 1 + 1) * (f 1 , λ, s 1 , p 1 ) and (q 0 , a n2 ba n2-1 c, ⊥, 1)

* (q, ba n2-1 c, ϕ(u)v k2 w, n 2 + 1) * (f 2 , λ, s 2 , p 2 )
for f 1 , f 2 ∈ F , s 1 , s 2 ∈ Γ Γ * ⊥, and 1 ≤ p i ≤ |s i | for i = 1, 2. Since the input symbol b forces M to push or to pop a symbol, or to leave the stack as it is, the stack is decreased by at most one symbol when the b is read. The subsequent input symbols a increase the stack again. So, the bottommost n 1 (n 2 ) stack symbols are not touched again. Since ϕ(u)v k1 w and ϕ(u)v k2 w have a common prefix of length at most 2, we derive (q 0 , a n1 ba n2-1 c, ⊥, 1) * (q, ba n2-1 c, ϕ(u)v k1 w, n 1 + 1) * (f 2 , λ, s 3 , p 3 ) for some s 3 ∈ Γ Γ * ⊥ and p 3 = |s 3 |. This implies that a n1 ba n2-1 c ∈ L 1 which is a contradiction and, hence, L 1 ∈ L (1sDVSA). Now we turn to show how input-driven stack automata languages are related to some important context-free language families. Let CFL refer to the family of context-free languages. Then Example 2 shows the following result.

Lemma 4. L 2 = { a n b n c n+1 | n ≥ 1 } ∈ L (1sNEDVSA) \ CFL.
The next lemma proves a converse relation, namely that a deterministic and linear context-free language is not accepted by any deterministic weak inputdriven stack automaton. Let DCFL refer to the family of deterministic contextfree and LIN to the family of linear context-free languages, which are both strict sub-families of CFL.

Lemma 5. Let L 3 = { a n b m ab m a n | n, m ≥ 1 } ∪ { b n a n | n ≥ 1 }. Then, L 3 ∈ (DCFL ∩ LIN) \ L (1wDVSA).
Proof. Clearly, L 3 belongs to DCFL ∩ LIN. Now assume that L 3 is accepted by some 1wDVSA M = Q, Σ, Γ, ⊥, q 0 , F, δ c , δ r , δ i , δ u , δ d . Similarly as in the proof of Lemma 3, we conclude a ∈ Σ c and b ∈ Σ c , since otherwise the words from L 3 of the form b + a + could not be accepted. Thus, every input from {a, b} + forces M to only push symbols onto the stack. Continuing similar as in the second part of the proof of Lemma 3 shows that then words not belonging to L 3 are accepted. This contradiction shows the lemma.

For the proof of the following lemma that compares deterministic weak and strong input-driven stack automata (conversely to Lemma 3), we use an incompressibility argument. General information on Kolmogorov complexity and the incompressibility method can be found in [START_REF] Li | An Introduction to Kolmogorov Complexity and its Applications[END_REF]. Let w ∈ {0, 1} + be an arbitrary binary string of length n. Then the plain Kolmogorov complexity C(w|n) of w denotes the minimal size of a program that knows n and describes w. It is well known that there exist binary strings w of arbitrary length n such that C(w|n) ≥ n (see [START_REF] Li | An Introduction to Kolmogorov Complexity and its Applications[END_REF], Theorem 2.2.1). Similarly, for any natural number n, C(n) denotes the minimal size of a program that describes n. It is known that there exist infinitely many natural numbers n such that C(n) ≥ log(n). Lemma 6. Let ˆ: {0, 1} * → { 0, 1} * be the homomorphism that maps 0 to 0

and 1 to 1. L 4 = { a n+m b m w ŵR b n | m, n ≥ 1, w ∈ {0, 1} + } ∪ { a n b n | n ≥ 1 } ∈ L (1sDVSA) \ L (1wNEDVSA).
Proof. The rough idea of a 1sDVSA M for L 4 is to push a symbol A onto the stack for every input symbol a, and to pop symbol A from the stack for every input symbol b read. In order to check the infix w ŵR , M pushes a Z for every 0 and an O for every 1 while reading w. Subsequently, it pops a Z for every 0 and an O for every 1 while reading ŵ. If eventually the stack is empty up to ⊥, the input is to be accepted and otherwise rejected. The concrete construction on M is straightforward except for one detail. The machine must be able to recognize when the stack is empty. To be more precise, it must know when the stack pointer is moved at the bottom-of-stack symbol even if there are no more moves, as for accepting computations. In order to implement this detail, M marks the first symbol on the stack. When this symbol is popped again, M knows that the stack is empty even without reading ⊥.

Next, we show that L 4 ∈ L (1wNEDVSA). Contrarily, assume that L 4 is accepted by a 1wNEDVSA M = Q, Σ, Γ, ⊥, q 0 , F, δ c , δ r , δ i , δ u , δ d . Similar as in the proof of Lemma 3, we conclude that a

∈ Σ c . Moreover, since { a n b n | n ≥ 1 } is a subset of L 4 , we conclude that b ∈ Σ d . Otherwise, b ∈ Σ c or b ∈ Σ i
which leads to a contradiction as shown before. Now we consider an accepting computation K on an input of the form z = a n+m b m w ŵR b n , for w ∈ {0, 1} + , n ≥ 2, k = log(n) , and m = 2 2 k -n. We distinguish two cases.

1. First, we assume that in K nothing is pushed onto the stack while reading the infix w, and consider the configuration c = (q, ŵR b n , s, p) with s ∈ Γ Γ * ⊥ and 1 ≤ p ≤ |s| after reading a n+m b m w. We claim that the knowledge of M , n, m, |w|, q, and p suffices to write a program that outputs w. This is seen as follows.

Since n and m are known, the stack contents s can be computed by simulating M on input a n+m . Furthermore, due to our assumption that nothing is pushed while reading w, and since q and the pointer position p are known, it is possible to simulate M starting with a situation as configuration c but with arbitrary input. This is done successively on all inputs vb n with |v| = |w|. If v = ŵR , then the simulation ends accepting. On the other hand, if the simulation is accepting, then v = ŵR , since otherwise a n+m b m wvb n with v = ŵR would belong to L 4 which is a contradiction. This suffices to identify and output w. The size of the program is a constant for the code itself plus the sizes of M , n, m, |w|, q, and p. The size of M and, thus, of q is also a constant, while p ≤ n + m. So, the size of the program is of order O(log(n) + log(m) + log(n + m) + log(|w|)). Fixing n and m and choosing |w| large enough, we obtain C(w||w|) ∈ o(|w|) which is a contradiction to the above-cited result that there exist binary strings w of arbitrary length such that C(w||w|) ≥ |w|. 2. Second, we assume that in K something is pushed onto the stack while reading the infix w, and consider the configuration c = (q, x, s, |s|) with s ∈ Γ Γ * ⊥ and x ∈ {0, 1} * { 0, 1} + b + is the remaining input when the first symbol has been pushed onto the stack while reading w. We claim that the knowledge of M , k, |w|, the length of the prefix w of w which has been already read, q, and the last symbol B pushed suffices to write a program that outputs n.

The stack height |s| is m + n + 1 = 2 2 k + 1. Therefore, the stack contents s can be computed by simulating M on input a |s|-1 using solely the knowledge of k, and adding B on the top. Next the simulation of M beginning in state q while having the stack pointer on the top of the stack contents s is started successively on all inputs uvb i with u ∈ {0, 1} * , |u| = |w| -, |v| = |w|, and 1 ≤ i ≤ 2 2 k . If w uv = w ŵR and i = n, then the simulation ends accepting. On the other hand, if the simulation is accepting, then w uv = w ŵR and i = n. This suffices to identify and output n. Again, the size of the program is a constant for the code itself plus the sizes of M , k, |w|, , q, and |Γ |. The size of M and, thus, of q and |Γ | is also a constant, while ≤ |w|. So, the size of the program is of order

O(log(k) + log(|w|)) = O(log(log(n)) + log(|w|)).
Fixing w and choosing n large enough, we obtain C(n) ∈ o(log(n)) which is a contradiction since there are infinitely many natural numbers n such that

C(n) ≥ log(n).
This proves the lemma.

With the help of the previous four lemmata we can show the following strict inclusion relations and incomparability results. Proof. The inclusions of the language families induced by the input-driven stack automata are clear by definition. Moreover, L (VPDA) ⊆ CFL is immediate and L (VPDA) ⊆ L (1sDVSA) follows since every visibly (deterministic) pushdown automaton is also a deterministic strong input-driven stack automaton (that is not allowed to read the internal contents of the stack). First, we show that these inclusions are strict. The strictness of the inclusion L (1sDVSA) ⊆ L (1wDVSA) as well as the inclusion L (1sNEDVSA) ⊆ L (1wNEDVSA) is ensured by language L 1 of Lemma 3. Furthermore, a language similar to L 1 was used in [START_REF] Alur | Adding nesting structure to words[END_REF] to show that the inclusion L (VPDA) ⊆ CFL is proper. Finally, the strictness of both inclusions L (1sNEDVSA) ⊆ L (1sDVSA) and L (1wNEDVSA) ⊆ L (1wDVSA) follows by language L 4 of Lemma 6. Next, we show the incomparability results. The languages L 2 and L 3 from Lemmata 4 and 5 imply the incomparability of CFL with the all language families of deterministic variants of inputdriven stack automata, namely L (1sNEDVSA), L (1wNEDVSA), L (1sDVSA), and L (1wDVSA). The incomparability of L (VPDA) with both language families L (1sNEDVSA) and L (1wNEDVSA) follows by the languages L 2 from Lemma 4 and L 4 from Lemma 6, and the obvious fact that L 4 is a visibly pushdown language. Finally, L (1sDVSA) and L (1wNEDVSA) are incomparable due to the languages L 1 and L 4 from Lemmata 3 and 6. This proves the stated claim.

In the remainder of this section we investigate the relation between deterministic and nondeterministic input-driven stack automata. To this end consider the language

L 5 = T 1 ∪ T 2 ∪ T 1 ∪ T 2 ∪ T 3 ∪ T 4 with T 1 = { a n d n 1 u n+1 1 | n ≥ 1 } T 2 = { a n d n 2 u n+1 2 | n ≥ 1 } T 1 = { a n u m 1 d n 1 u n+1 1 | m, n ≥ 1 } T 2 = { a n u m 2 d n 2 u n+1 2 | m, n ≥ 1 } T 3 = { a n d n+1 1 | n ≥ 1 } and T 4 = { a n+m d m 1 d n 2 u n+1 2 u m 1 w ŵR d m 1 d n+1 2 | m, n ≥ 1, w ∈ {0, 1} + },
constructions that a, 0, 1 ∈ Σ c , d 1 , d 2 , 0, 1 ∈ Σ d , and u 1 , u 2 ∈ Σ u . Thus, the automaton constructed is non-erasing and works in the strong mode. Next, we show by way of contradiction that L 5 ∈ L (1wDVSA). Assume that L 5 is accepted by a 1wDVSA M = Q, Σ, Γ, ⊥, q 0 , F, δ c , δ r , δ i , δ u , δ d . Similar as in the proof of Lemma 3, we conclude that a ∈ Σ c . Now, we assume that d 1 ∈ Σ c ∪ Σ r . Due to Lemma 9 with R = a + d + 1 u + 1 we obtain that T 1 is accepted by some 1wDVSA having d 1 ∈ Σ c ∪ Σ r . This is a contradiction to Lemma 8. Thus, d 1 ∈ Σ c ∪ Σ r . Similarly, it can be shown that also

d 2 , u 1 , u 2 ∈ Σ c ∪ Σ r .
Finally, we claim that d 1 ∈ Σ d . Otherwise, due to Lemma 9 with R = a + d + 1 , language T 3 would be accepted by some 1wDVSA having d 1 ∈ Σ i ∪ Σ u which is a contradiction.

The rest of the proof is similar to the proof of Lemma 6 and we leave out some details here. We consider an accepting computation K on an input of the form

z = a n+m d m 1 d n 2 u n+1 2 u m 1 w ŵR d m 1 d n 2 , for w ∈ {0, 1} + , n ≥ 2, k = log(n))
, and m = 2 2 k -n. Due to the above considerations, we know that nothing is pushed onto or popped off the stack while reading the infix d m 1 d n 2 u n+1 2 u m 1 . We distinguish now two cases.

1. First, we assume that nothing is pushed onto or popped off the stack while reading the infix w, and consider the configuration c = (q, ŵR d m

1 d n 2 , s, p) with s ∈ Γ Γ * ⊥ and 1 ≤ p ≤ |s| after reading a n+m d m 1 d n 2 u n+1 2 u m 1 w.
Then, the knowledge of M, n, m, |w|, q, and p is sufficient to write a program that outputs w. The size of this program is bounded by O(log(n) + log(m) + log(n + m) + log(|w|)). Hence, C(w||w|) ∈ o(|w|) which is a contradiction for |w| large enough. 2. Second, we assume that something is pushed onto or popped off the stack while reading the infix w. We consider the configuration c = (q, x, s, |s|) with s ∈ Γ Γ * ⊥ and x ∈ {0, 1} * { 0, 1} + d + 1 d + 2 being the remaining input when the first symbol has been pushed onto or popped off the stack while reading w. Again, the knowledge of M , k, |w|, the length of the prefix w of w which has been already read, q, and the last pushed or popped symbol B ∈ Γ is sufficient to write a program that outputs n. The size of this program is bounded by O(log(k) + log(|w|)) = O(log(log(n)) + log(|w|)). Thus, C(n) ∈ o(log(n)) which is a contradiction since there are infinitely natural numbers n such that C(n) ≥ log(n).

Hence, there cannot be any 1wDVSA that accepts the language L 5 .

As an immediate corollary of the previous lemma we obtain the following strict inclusions.

Corollary 11. 1. L (1sNEDVSA) ⊂ L (1sNENVSA). 2. L (1sDVSA) ⊂ L (1sNVSA). 3. L (1wNEDVSA) ⊂ L (1wNENVSA). 4. L (1wDVSA) ⊂ L (1wNVSA).
These strict inclusions show a large difference between input-driven pushdown automata languages or equivalently visibly pushdown languages, where determinism coincides with nondeterminism on the underlying automaton model.

For input-driven stack automata, even for the most restrictive version, the strong machines, nondeterminism is more powerful than determinism. These strictness results are also reflected in the forthcoming result on the complexity of the fixed membership problem. Since the family of languages accepted by ordinary deterministic stack automata belongs to deterministic polynomial time P [START_REF] Lange | A note on the P-completeness of deterministic one-way stack languages[END_REF] it follows that this is also true for every language family induced by a deterministic input-driven stack automaton, regardless whether we have a strong or weak machine, or whether the device is non-erasing or not. On the other hand, when changing from ordinary deterministic stack automata to nondeterministic ones, we obtain an NP-complete language family [START_REF] Hunt | On the complexity of finite, pushdown and stack automata[END_REF][START_REF] Shamir | Checking stacks and context-free programmed grammars accept P-complete languages[END_REF]. This is also the case for the nondeterministic versions of input-driven stack automata, even for strong non-erasing machines, which is shown next.

Theorem 12. Each of the language families L (1sNENVSA), L (1sNVSA), L (1wNENVSA), and L (1wNVSA) has an NP-complete fixed membership problem.

Proof. The containment in NP follows immediately from the fact that ordinary nondeterministic stack automata have an NP-complete fixed membership problem [START_REF] Hunt | On the complexity of finite, pushdown and stack automata[END_REF][START_REF] Shamir | Checking stacks and context-free programmed grammars accept P-complete languages[END_REF]. It remains to show NP-hardness. To this end, it suffices to show that the (with respect to set inclusion) smallest language family L (1sNENVSA) has an NP-hard membership problem. We reduce the well-known NP-complete 3SAT problem [START_REF] Garey | Computers and Intractability, A Guide to the Theory of NP-Completeness[END_REF] to the problem under consideration. We encode a Boolean formula F = c 1 ∧ c 2 ∧ • • • ∧ c m with variables X = {x 1 , x 2 , . . . , x n }, where each clause c i with 1 ≤ i ≤ m is a disjunction of three literals, by a word F ∈ 1 n ({0, +, -} * # * $) * . The prefix encodes the number of input variables. Then each clause c i , for 1 ≤ i ≤ m, of the formula F is encoded by a word w ci in {0, +, -} n # n , where at position j, for 1 ≤ j ≤ n, there is a 0 (+, -), if the variable x j does not appear (positively appears, negatively appears) in c i . These words are separated by $-symbols and are placed in sequence. Then the language L = { F | F is a Boolean formula that evaluates to 1 } is NP-hard. We informally describe how a 1wNENVSA automaton M accepts L. Set Σ c = {1}, Σ r = ∅, Σ i = {$}, Σ u = {#}, and Σ d = {0, +, -}. On prefix 1 n the automaton pushes either the symbol 0 or 1. In this way, the automaton guesses an assignment to the n variables of the formula. Then the sequence that encodes a clause is used to read into the stack in order to determine the assignments of the involved variables. In passing the automaton checks whether this clause evaluates to 1. Then the block of # symbols is used to reset the stack pointer to the top of the stack, and after reading $ the checking procedure for the next clause is restarted. If all clauses evaluate to 1, the whole encoding is accepted, otherwise it is rejected. It is easy to see that the automaton is nonerasing. This shows that already the language family L (1sNENVSA) contains an NP-hard language.

Theorem 7 .Fig. 1 .

 71 Fig. 1. Inclusion structure of deterministic language families. The arrows indicate strict inclusions. All families not linked by a path are pairwise incomparable.

where ˆis the mapping introduced in Lemma 6. Then we can prove the following result, which allows us to categorize the different symbols used in the definition of language L 5 . Lemma 8. Let M = Q, Σ, Γ, ⊥, q 0 , F, δ c , δ r , δ i , δ u , δ d be a 1wDVSA.

Proof. We only prove the first claim. The other claims can be shown by similar arguments. So assume that T 1 is accepted by M . In order to show d 1 ∈ Σ c ∪ Σ r , we assume in contrast to the assertion that d 1 is in Σ c or Σ r . Thus, we distinguish two cases-note that we make no assumption on the containment of the letter a within the sub-alphabets that come from the partition of Σ:

1. Assume that d 1 ∈ Σ r . Note that after reading the word a n d n 1 the stack of M is empty up to the bottom of stack symbol ⊥. This is due to the fact, that M is deterministic and d 1 ∈ Σ r . Since Q is finite, there are two distinct sufficiently large numbers n 1 = n 2 and a state q ∈ Q, such that

and, thus,

Then we argue as follows. Since M is deterministic and d 1 ∈ Σ c , we know that the stack height is at least n + 1 after reading word a n d n 1 and the stack pointer is on the topmost symbol. Then further reading of u n+1 1 -here we make no assumption on letter u 1 and its containment in Σ c Σ r , Σ i , Σ u , or Σ d -may only touch the topmost n + 1 symbols of the stack. Since Q and Γ are finite we find two sufficiently large numbers n 1 = n 2 , a state q ∈ Q and a stack symbol Z ∈ Γ , such that , respectively, we obtain the accepting computation Next we need some notation. Let Σ c , Σ r , Σ i , Σ u , and Σ d be a partitioning of Σ. Then we say that a partitioning Σ c , Σ r , Σ i , Σ u , and

and Σ d ⊆ Σ d . Then the next lemma, which can be shown by an easy adaptation of the well-known Cartesian product construction for pushdown automata, reads as follows: Lemma 9. Let M = Q, Σ, Γ, ⊥, q 0 , F, δ c , δ r , δ i , δ u , δ d be a 1wDVSA (1sDVSA) and R ⊆ Σ * be a regular language. Then the language L(M ) ∩ R is accepted by a 1wDVSA (1sDVSA) with a compatible partitioning of the alphabet Σ. Now we are ready to show that there exists a language that belongs to the class induced by the most restricted form of nondeterministic input-driven automata, namely 1sNENVSA, but is not a member of the larger deterministic class 1wDVSA.

Proof. The idea for a 1sNENVSA accepting L 5 is first to guess whether the input belongs to T 1 , T 2 , T 1 , T 2 , T 3 , or T 4 . The construction to accept inputs from T 1 , T 2 , T 1 , T 2 , and T 3 is similar to the construction in Lemma 4. In the constructions for T 1 and T 2 we observe that u 1 and u 2 belong to Σ u . Since the stack pointer is on the top after reading a n , the processing of u 1 and u 2 only affects the current state, but not the stack or the position of the stack pointer. The construction to accept T 4 is as follows. While reading a's some symbol A is pushed onto the stack up to some moment in which it is nondeterministically decided to push some different symbol B onto the stack for every remaining input symbol a. Then, while reading d 1 's and seeing B's the stack pointer moves down and continues moving down while reading d 2 's and seeing A's. If the bottom of the stack is reached, the stack pointer moves up while reading u 2 's and seeing A's and continues moving up, while reading u 1 's and seeing B's on the stack. If the top of the stack is reached, the processing of the infix w ŵR is done in a similar way as in the proof of Lemma 6. The only difference is that symbols from { 0, 1} now ensure that the stack pointer moves down instead of popping off the topmost symbol. If the first B of the stack is again reached, the stack pointer continues moving down while reading d 1 's and seeing B's and continues to move down while reading d 2 's and seeing A's. The input is accepted if the bottom of the stack is eventually reached and rejected otherwise. We observe from the


Michele Boreale
email: michele.boreale@unifi.it.

Michela Paolini

Worst-and average-case privacy breaches in randomization mechanisms ⋆

Keywords: Foundations of security, quantitative information flow, differential privacy, utility, information theory

In a variety of contexts, randomization is regarded as an effective technique to conceal sensitive information. We model randomization mechanisms as information-theoretic channels. Our starting point is a semantic notion of security that expresses absence of any privacy breach above a given level of seriousness ǫ, irrespective of any background information, represented as a prior probability on the secret inputs. We first examine this notion according to two dimensions: worst vs. average case, single vs. repeated observations. In each case, we characterize the security level achievable by a mechanism in a simple fashion that only depends on the channel matrix, and specifically on certain measures of "distance" between its rows, like norm-1 distance and Chernoff Information. We next clarify the relation between our worst-case security notion and differential privacy (dp): we show that, while the former is in general stronger, the two coincide if one confines to background information that can be factorised into the product of independent priors over individuals. We finally turn our attention to expected utility, in the sense of Ghosh et al., in the case of repeated independent observations. We characterize the exponential growth rate of any reasonable utility function. In the particular case the mechanism provides ǫ-dp, we study the relation of the utility rate with ǫ: we offer either exact expressions or upper-bounds for utility rate that apply to practically interesting cases, such as the (truncated) geometric mechanism.

Introduction

In a variety of contexts, randomization is regarded as an effective means to conceal sensitive information. For example, anonymity protocols like Crowds [START_REF] Reiter | Crowds: Anonymity for Web Transactions[END_REF] or the Dining Cryptographers [START_REF] Chaum | The Dining Cryptographers Problem: Unconditional Sender and Recipient Untraceability[END_REF] rely on randomization to "confound" the adversary as to the true actions undertaken by each participant. In the field of Data Mining, techniques have been proposed by which datasets containing personal information that are released for business or research purposes are perturbed with noise, so as to prevent an adversary from re-identifying individuals or learning sensitive information about them (see e.g. [START_REF] Evfimievski | Limiting Privacy Breaches in Privacy Preserving Data Mining[END_REF] and references therein).

In the last few years, interest in the theoretical principles underlying randomizationbased information protection has been steadily growing. Two major areas have by now clearly emerged: Quantitative Information Flow (qif) [START_REF] Braun | Quantitative Notions of Leakage for One-try Attacks[END_REF][START_REF] Köpf | Vulnerability Bounds and Leakage Resilience of Blinded Cryptography under Timing Attacks[END_REF][START_REF] Boreale | Asymptotic information leakage under one-try attacks[END_REF][START_REF] Boreale | Quantitative Information Flow, with a View[END_REF][START_REF] Chatzikokolakis | Anonymity protocols as noisy channels[END_REF][START_REF] Chatzikokolakis | On the Bayes risk in information-hiding protocols[END_REF][START_REF] Smith | On the Foundations of Quantitative Information Flow[END_REF] and Differential Privacy (dp) [START_REF] Dwork | Differential Privacy[END_REF][START_REF] Dwork | Calibrating Noise to Sensitivity in Private Data Analysis[END_REF][START_REF] Mcsherry | Privacy Integrated Queries[END_REF][START_REF] Mcsherry | Mechanism Design via Differential Privacy[END_REF][START_REF] Friedman | Data Mining with Differential Privacy[END_REF][START_REF] Ganta | Composition Attacks and Auxiliary Information in Data Privacy[END_REF]. As discussed in [START_REF] Barthe | Information-theoretic Bounds for Differentially Private Mechanisms[END_REF], qif is mainly concerned with quantifying the degree of protection offered against an adversary trying to guess the whole secret; dp is rather concerned with protection of individual bits of the secret, possibly in the presence of background information, like knowledge of the remaining bits. The areas of qif and dp have grown separately for some time: only very recently researchers have begun investigating the relations between these two notions [START_REF] Alvim | Differential Privacy: on the trade-off between Utility and Information Leakage[END_REF][START_REF] Alvim | Quantitative Information Flow and Applications to Differential Privacy[END_REF][START_REF] Alvim | On the relation between Differential Privacy and Quantitative Information Flow[END_REF][START_REF] Barthe | Information-theoretic Bounds for Differentially Private Mechanisms[END_REF].

The present paper is an attempt at distilling and systematizing the notions of security breach underlying qif and dp. We view a randomization mechanism as an informationtheoretic channel with inputs in X and outputs in Y. The starting point of our treatment is a semantical notion of breach. Assume X is a finite set of items containing the secret information X, about which the adversary has some background knowledge or belief, modeled as a prior probability distribution p(x). Consider a predicate Q ⊆ X -in a dataset about individuals, one may think of Q as gender, or membership in a given ethnical group etc. The mere fact that X is in Q or not, if ascertained, may convey sensitive information about X. Henceforth, any observation y ∈ Y that causes a significant change in the adversary's posterior belief about X ∈ Q must be regarded as dangerous. In probabilistic terms, Q is a breach if, for some prior probability on X, the posterior probability of Q after interaction with the randomization mechanism exhibits a significant change, compared to its prior probability. We decree a randomization mechanism as secure at level ǫ, if it exhibits no breach of level > ǫ, independently of the prior distribution on the set of secret data X. The smaller ǫ, the more secure the mechanism. This simple idea, or variations thereof, has been proposed elsewhere in the Data Mining literature -see e.g. [START_REF] Evfimievski | Limiting Privacy Breaches in Privacy Preserving Data Mining[END_REF]. Here, we are chiefly interested in analyzing this notion of breach according to the following dimensions.

1. Worst-vs. average-case security. In the worst-case approach, one is interested in bounding the level of any breach, independently of how likely the breach is. In the average-case, one takes into account the probability of the observations leading to the breach. 2. Single vs. repeated, independent executions of the mechanism. 3. Expected utility of the mechanism and its asymptotic behavior, depending on the number of observations and on a user-defined loss function.

To offer some motivations for the above list, we observe that worst-case is the type of breach considered in dp, while average-case is the type considered in qif. In the worstcase scenario, another issue we consider is resistance to background information. In the case of dp, this is often stated in the terms that [START_REF] Dwork | Differential Privacy[END_REF]: Regardless of external knowledge, an adversary with access to the sanitized database draws the same conclusions whether or not my data is included, and formalized as such [START_REF] Ganta | Composition Attacks and Auxiliary Information in Data Privacy[END_REF]. We investigate how this relates to the notion of privacy breach we consider, which also intends to offer protection against arbitrary background knowledge. Concerning the second point, a scenario of repeated observations seems to arise quite naturally in many applications. For instance, an online, randomized data-releasing mechanism might offer users the possibility of asking the same query a number of times. This allows the user to compute more accurate answers, but also poses potential security threats, as an adversary could remove enough noise to learn valuable information about the secret. This is an instance of the composition attacks which are well known in the context of dp, where they are thwarted by allotting each user or group of users a privacy budget that limits the overall number of queries to the mechanism; see e.g. [START_REF] Mcsherry | Privacy Integrated Queries[END_REF][START_REF] Friedman | Data Mining with Differential Privacy[END_REF]. For another example, in a de-anonymization scenario similar to [START_REF] Narayanan | Robust De-anonymization of Large Sparse Datasets[END_REF], [START_REF] Boreale | Quantitative Information Flow, with a View[END_REF] shows that gathering information about a target individual can be modeled as collecting multiple observations from a certain randomization mechanism. In general, one would like to assess the security of a mechanism in these situations. In particular, one would like to determine exactly how fast the level of any potential breach grows, as the number n of independent observations grows.

The third point, concerning utility, has been the subject of intensive investigation lately (see related work paragraph). Here, we are interested in studying the growth of expected utility in the model of Ghosh et al. [START_REF] Ghosh | Universally utility-maximizing privacy mechanisms[END_REF] as the number of independent observations grows, and to understand how this is related to security.

In summary, the main results we obtain are the following.

-In the scenario of a single observation, both in the average and in the worst case, we characterize the security level (absence of breach above a certain threshold) of the randomization mechanism in a simple way that only depends on certain rowdistance measures of the underlying matrix. -We prove that our notion of worst-case security is stronger than dp. However, we show the two notions coincide when one confines to background information that factorises as the product of independent measures over all individuals. This, we think, sheds further light on resistance of dp against background knowledge. -In the scenario of repeated, independent observations, we determine the exact asymptotic growth rate of the (in)security level, both in the worst and in the average case. -In the scenario of repeated, independent observations, we determine the exact asymptotic growth rate of any reasonable expected utility. We also give bounds relating this rate to ǫ-dp, and exact expressions in the case of the geometric mechanisms. In this respect, we argue that the geometric mechanism is superior to its truncated version [START_REF] Ghosh | Universally utility-maximizing privacy mechanisms[END_REF].

Related work

There is a large body of recent literature on qif [START_REF] Braun | Quantitative Notions of Leakage for One-try Attacks[END_REF][START_REF] Köpf | Vulnerability Bounds and Leakage Resilience of Blinded Cryptography under Timing Attacks[END_REF][START_REF] Boreale | Asymptotic information leakage under one-try attacks[END_REF][START_REF] Boreale | Quantitative Information Flow, with a View[END_REF] and dp [START_REF] Dwork | Differential Privacy[END_REF][START_REF] Dwork | Calibrating Noise to Sensitivity in Private Data Analysis[END_REF].

The earliest proposal of a worst-case security notion is, to the best of our knowledge, found in [START_REF] Evfimievski | Limiting Privacy Breaches in Privacy Preserving Data Mining[END_REF]. As mentioned, the investigation of the relations between qif and dp has just begun. Both [START_REF] Barthe | Information-theoretic Bounds for Differentially Private Mechanisms[END_REF] and [START_REF] Alvim | Quantitative Information Flow and Applications to Differential Privacy[END_REF][START_REF] Alvim | On the relation between Differential Privacy and Quantitative Information Flow[END_REF] discuss the implication of ǫ-dp on information leakage guarantees, and vice-versa, in the case of a single observation. In the present work, we propose and characterize both worst-and average-case semantic notions of privacy breach, encoding resistance to arbitrary side-information, and clarify their relationships with qif and dp. We also study the asymptotic behavior of privacy breaches depending on the number of observations. The notion of utility has been the subject of intensive investigation in the field of dp, see e.g. [START_REF] Mcsherry | Mechanism Design via Differential Privacy[END_REF][START_REF] Ghosh | Universally utility-maximizing privacy mechanisms[END_REF][START_REF] Alvim | Differential Privacy: on the trade-off between Utility and Information Leakage[END_REF][START_REF] Alvim | Quantitative Information Flow and Applications to Differential Privacy[END_REF][START_REF] Alvim | On the relation between Differential Privacy and Quantitative Information Flow[END_REF] and references therein. A general goal is that of designing mechanisms achieving optimal expected utility given a certain security level ǫ. Ghosh et al. [START_REF] Ghosh | Universally utility-maximizing privacy mechanisms[END_REF] propose a model of expected utility based on user preferences, and show that both the geometric mechanism and its truncated version achieve universal optimality. Here we provide the growth rate of utility, and we highlight a difference between a mechanism and its truncated version, in the presence of repeated observations. Alvim et al. [START_REF] Alvim | Differential Privacy: on the trade-off between Utility and Information Leakage[END_REF] have shown the tight connection between utility and Bayes risk, hence information leakage, in the case of a single observation. A different, somewhat stronger notion of utility, called accuracy, is considered by McSherry and Talwar [START_REF] Mcsherry | Mechanism Design via Differential Privacy[END_REF]. They do not presuppose any user-specific prior over the set of possible answers; rather, they show that, in the exponential mechanism they propose, for any database, the expected score of the answer comes close to the maximum.

Structure of the paper

The rest of the paper is organized as follows. In Section 2 we review some terminology and basic concepts about Bayesian hypothesis testing and information leakage. Section 3 characterizes the semantic security of randomization mechanisms, both in the worst and in the average case, but limited to a single observation on the part of the adversary. Section 4 discusses the relation between dp and our worst-case security. Section 5 discusses the asymptotic behavior of the security level in the case of n independent observations where the secret input remains fixed, again both in the worst and in the average case. In the worst case, we also offer a result characterizing the probability, depending on n, that some sequence of observations causes a breach. In Section 6 we deal with utility in the case of repeated observations. Section 7 discusses further work and draws some concluding remarks. Due to space limitations proofs have been omitted; they can be found in a full version available online [START_REF] Boreale | Worst-and average-case privacy breaches in randomization mechanisms[END_REF].

Preliminaries

We review some notation and basic concepts about Bayesian hypothesis testing and information leakage.

Basic terminology

Let X be a finite nonempty set. A probability distribution on X is a function p : X → [0, 1] such that x∈X p(x) = 1. The support of p is defined as supp(p)

△ = {x ∈ X|p(x) > 0}. For any Q ⊆ X we let p(Q) denote x∈Q p(x). Given n ≥ 0, we let p n : X n → [0, 1]
denote the n-th extension of p, defined as p n (x 1 , . . . , x n ) n i=1 p(x i ); this is in turn a probability distribution on the set X n . When Q ⊆ X n and n is clear from the context, we shall abbreviate p n (Q) as just p(Q). For n = 0, we set p 0 (ǫ) = 1, where ǫ denotes the empty tuple. Pr(•) will generally denote a probability measure defined on some probability space (understood from the context). Given a random variable X taking values in X, we write X ∼ p(x) if X is distributed according to p(x), that is for each x ∈ X, Pr(X = x) = p(x). We shall only consider discrete random variables. Suppose we are given random variables X, Y,... taking values in X, Y,... and defined on the same probability space. We shall use abbreviations such as p(y|x) for Pr(Y = y|X = x), p(y|Q) for Pr(Y = y|X ∈ Q), and so on, whenever no confusion arises about the involved random variables X and Y. Finally, when notationally convenient, we shall denote the conditional probability distribution on Y p(•|x) (x ∈ X) as p x (•). Randomization mechanisms are information-theoretic channels. The use of this concept in the field of qif has been promoted by Chatzikokolakis, Palamidessi and collaborators [START_REF] Chatzikokolakis | Anonymity protocols as noisy channels[END_REF][START_REF] Chatzikokolakis | On the Bayes risk in information-hiding protocols[END_REF][START_REF] Braun | Quantitative Notions of Leakage for One-try Attacks[END_REF]; the systems amenable to this form of representation are sometimes referred to as information hiding systems (see also [START_REF] Boreale | Asymptotic information leakage under one-try attacks[END_REF][START_REF] Boreale | Quantitative Information Flow, with a View[END_REF]). The entry of row x and column y of the channel's matrix will be written as p(y|x), and represents the probability of observing y, given that x is the (secret) input of the system. For each x, the x-th row of the matrix is identified with the probability distribution on Y given by y → p(y|x), which is denoted by p x . We say R is non-degenerate if x x ′ implies p x p x ′ , and strictly positive if p(y|x) > 0 for each x and y. Note that p(•) on X and the conditional probability matrix p(y|x) together induce a probability distribution q on X × Y defined as q(x, y) p(x) • p(y|x), hence a pair of discrete random variables (X, Y) ∼ q(x, y), with X taking values in X and Y taking values in Y. Of course, one has X ∼ p(x) and, for each x ∈ X and y ∈ Y s.t. p(x) > 0, Pr(Y = y|X = x) = p(y|x).

Definition 1 (randomization mechanism)

. A randomization mechanism is a triple R = (X, Y, p(•|•)), composed

Bayesian hypothesis testing, min-entropy, leakage

Assume we are given a randomization mechanism R = (X, Y, p(•|•)) and an a priori distribution p(x) on X. Assume an attacker wants to identify X on the basis of the observation Y, where, as explained above, (X, Y) ∼ p(x) • p(y|x). This scenario can be formalized in terms of Bayesian hypothesis testing, as follows. The attacker's strategy is represented by a guessing function g : Y → X. The success probability after 1 observation (relative to g) is defined as by

P (g) succ △ = Pr(g(Y) = X) . (1)
Correspondingly, the error probability is

P (g) e △ = 1 -P (g) succ .
It is well-known (see e.g. [START_REF] Cover | Elements of Information Theory[END_REF]) that optimal strategies, that is strategies maximizing the success probability, are those obeying the following Maximum A Posteriori (map) criterion: for each y ∈ Y and x ∈ X g(y) = x implies p(y|x)p(x) ≥ p(y|x ′ )p(x ′ ) ∀x ′ ∈ X .In what follows, we shall always assume that g is map and consequently omit the superscript (g) . The quantity P succ admits a number of equivalent formulations. For example, it is straightforward to check that (cf. e.g. [START_REF] Smith | On the Foundations of Quantitative Information Flow[END_REF][START_REF] Boreale | Asymptotic information leakage under one-try attacks[END_REF][START_REF] Boreale | Quantitative Information Flow, with a View[END_REF]; the sums below run over y of positive probability)

P succ = y p(y) max x p(x|y) (2) = y max x p(y|x)p(x) . (3)
Equation ( 2) shows clearly that P succ results from an average over all observations y ∈ Y. This equation also establishes a connection with Rényi's min-entropy [START_REF] Rényi | On Measures of Entropy and Information[END_REF]. This, for a random variable X ∼ p(x), is defined thus (in the following, all the log's are taken with base 2): H ∞ (X) △ =log max x p(x) .Conditional min-entropy of X given Y is defined as: H ∞ (X|Y) △ =log y p(y) max x p(x|y) .Therefore from ( 2)

P succ = 2 -H ∞ (X|Y) . ( 4
)
Success probability is the key to defining information leakage of X given Y. This quantity expresses, in bits, how much, on the average, one observation increases the success probability of the attacker. The intuition is that a gain of one bit of leakage corresponds to doubling the a priori success probability:

L(X; Y) △ = H ∞ (X)-H ∞ (X|Y) = log P succ max x p(x) .

Asymptotic behavior

The scenario of a single observation generalizes to the case of several, say n, independent observations as follows. Given a prior p(x) and fixed any n ≥ 0, the adversary gets to know the observations corresponding to n independent executions of the mechanism R, say y n = (y 1 , ..., y n ) ∈ Y n , throughout which the secret state x is kept fixed. Formally, the adversary knows a random vector of observations

Y n = (Y 1 , ..., Y n ) such that, for each i = 1, ..., n, Y i is distributed like Y and the individual Y i are conditionally indepen- dent given X.
That is, the following equality holds true for each

y n ∈ Y n and x ∈ X s.t. p(x) > 0 Pr Y n = (y 1 , . . . , y n ) | X = x = n i=1 p(y i |x)
.We will often abbreviate the right-hand side of the last expression as p(y n |x). Again, for any n, the attacker's strategy is modeled by a guessing function g : Y n → X; the optimal strategy, that we will assume throughout the paper, is when g is map. The corresponding success and error probabilities, which depend on n, will be denoted by P n succ and P n e , respectively 1 . It is quite expected that, as n → +∞, P n succ → 1, and this is indeed the case, under very mild conditions. What is important, though, is to characterize how fast the probability of success approaches 1. Intuitively, we want be able to determine an exponent ρ ≥ 0 such that, for large n, P n succ ≈ 1 -2 -nρ . To this purpose, we introduce some concepts in what follows.

Let {a n } n≥0 be a sequence of nonnegative reals. Assume that τ = lim n→+∞ a n exists and that a n ≤ τ for each n. We define the rate of {a n } n≥0 as follows:

rate({a n }) △ = lim n→+∞ - 1 n log(τ -a n ) (5)
provided this limit exists 2 . When rate({a n }) = ρ we also say that a n reaches τ at rate ρ, and write this as a n τ -2 -nρ .Intuitively, for large values on of n, this can be interpreted as ≈. The above definition is modified as expected for the case when a n ≥ τ for each n: we set rate({a n })

△ = lim n→+∞ -1
n log(a nτ) and write a n τ + 2 -nρ if ρ = rate({a n }). Note that we do allow rate({a n }) = +∞, a case that arises for example when {a n } n≥0 is a constant sequence. 1 For the case n = 0, we set for uniformity y n △ = ǫ (empty tuple) and p(ǫ|x)

△ = 1.
With this choice, P 0 succ = max x p(x). 2 More generally, we define the upper-rate (resp. lower-rate) rate({a n }) (resp. rate({a n })) by replacing the lim in (5) by lim sup (resp. lim inf).

The rate of growth of P n succ is given by Chernoff Information. Given two probability distributions p, q on Y, we let their Chernoff Information be

C(p, q) △ = -min 0≤λ≤1 log( y∈supp(p)∩supp(q) p λ (y)q 1-λ (y)) (6)
where we stipulate that C(p, q) = +∞ if supp(p) ∩ supp(q) = ∅. Here C(p, q) can be thought of as a sort of distance 3 between p and q: the more p and q are far apart, the the less observations are needed to discriminate between them. More precisely, assume we are in the binary case X = {x 1 , x 2 } (binary hypothesis testing) and let

p i = p(•|x i ) for i = 1, 2.
Then a well-known result gives us the rate of convergence for the probabilities of success and error, with the proviso that p(x 1 ) > 0 and p(x 2 ) > 0 (cf. [START_REF] Cover | Elements of Information Theory[END_REF]): P n succ 1-2 -nC(p 1 ,p 2 ) and P n e 2 -nC(p 1 ,p 2 ) (here we stipulate 2 -∞ = 0). Note that this rate does not depend on the prior distribution p(x) on {x 1 , x 2 }, but only on the probability distributions p 1 and p 2 . This result extends to the general case |X| ≥ 2. Provided R is non-degenerate, it is enough to replace C(p 1 , p 2 ) by min x x ′ C(p x , p x ′ ), thus (see [START_REF] Boreale | Asymptotic information leakage under one-try attacks[END_REF][START_REF] Leang | On the asymptotics of M-hypothesis Bayesian detection[END_REF]):

P n succ 1 -2 -n min x x ′ C(p x ,p x ′ ) ( 7
)
P n e 2 -n min x x ′ C(p x ,p x ′ ) (8)
(with the understanding that, in the min, p(x) > 0 and p(x ′ ) > 0).

Semantic security of randomization mechanisms

We shall consider two scenarios. In the worst-case scenario, one is interested in the seriousness of a breach, independently of how much the breach is likely; this is also the scenario underlying differential privacy, which we will examine in Section 6. In the average-case scenario, one considers, so to speak, the seriousness of the breach averaged on the probability of the observed Y. In each scenario, our aim is to characterize when a randomization mechanism can be considered secure both in a semantic and in an operational fashion. We fix a generic randomization mechanism R for the rest of the section.

The worst-case scenario

In the worst-case definition, we compare the probability of predicates Q ⊆ X of the inputs, prior and posterior to one observation y ∈ Y: a large variation in the posterior probability relative to any y implies a breach. Note that even the situation when the posterior probability is small compared to the prior is considered as dangerous, as it tells the adversary that X ∈ Q c is likely.

Definition 2 (worst-case breach).

Let ǫ ≥ 0. A ǫ-breach (privacy breach of level ǫ) for R is a subset Q ⊆ X such that for some a priori probability distribution p(x) on X, we have p(Q) > 0 and

max p(y)>0 | log p(Q|y) p(Q) | > ǫ . R is ǫ-secure if it has no breach of level ǫ. The security level of R is defined as ǫ R △ = inf{ǫ ≥ 0 : R is ǫ-secure}. If | log p(Q|y) p(Q) | > ǫ,
we say y causes a Q-breach of level ǫ.

Remark 1. Note that the condition max y | log p(Q|y) p(Q) | > ǫ can be equivalently reformulated as max y max{ p(Q|y) p(Q) , p(Q) p(Q|y) } > 2 ǫ . For each y ∈ Y, let π M,y and π m,y be the maximum and the minimum in the column y of the matrix p(•|•), respectively. We give the following operational characterization of ǫ-security. A similar property (amplification) was considered as a sufficient condition for the absence of breaches in [START_REF] Evfimievski | Limiting Privacy Breaches in Privacy Preserving Data Mining[END_REF]. In the theorem below, we stipulate that

π M,y π m,y = +∞ if π M,y > 0 and π m,y = 0. Theorem 1. R is ǫ-secure iff log max y π M,y π m,y ≤ ǫ. Example 1.
The following example is inspired by [START_REF] Evfimievski | Limiting Privacy Breaches in Privacy Preserving Data Mining[END_REF]. The private information is represented by the set of integers X = {0, ..., 5}, and Y = X. We consider a mechanism that replaces any x ∈ X by a number y that retains some information about the original x. More precisely, we let Y = ⌊X + ξ⌋ mod 6, where with probability 0.5 ξ is a chosen uniformly at random in {- 1 2 , 1 2 }, and with probability 0.5 it is chosen uniformly at random in X. We can easily compute the resulting conditional probability matrix.

                                    
0.2500 0.2500 0.0833 0.0833 0.0833 0.2500 0.2500 0.2500 0.2500 0.0833 0.0833 0.0833 0.0833 0.2500 0.2500 0.2500 0.0833 0.0833 0.0833 0.0833 0.2500 0.2500 0.2500 0.0833 0.0833 0.0833 0.0833 0.2500 0.2500 0.2500 0.2500 0.0833 0.0833 0.0833 0.2500 0.2500

                                     .
The security level of this mechanism is ǫ R = log 0.25 0.083 = 3.0012.

The average-case scenario

We want to asses the security of R by comparing the prior and posterior success probability for an adversary wanting to infer whether the secret is in Q or not after observing Y. This will give us an average measure of the seriousness of the breach induced by Q. Fix a prior probability distribution p(x) on X. For every nonempty Q ⊆ X, we shall denote by Q the binary random variable I Q (X), where I Q : X → {0, 1} is the indicator function of Q -in this notation, the dependence from p(x) is left implicit, as p(x) will always be clear from the context. An adversary, after observing Y, wants to determine whether it holds Q or Qc . This is a binary Bayesian hypothesis testing problem, which, as seen in Section 2, can be formulated in terms of min-entropy.

Definition 3 (Average-case breach). Let

ǫ ≥ 0. A ǫ-A-breach (average case breach of level ǫ) of R is a Q ⊆ X s.t. for some a priori distribution p(x) on X, we have that p(Q) > 0 and L( Q; Y) = H ∞ ( Q) -H ∞ ( Q|Y) > ǫ. R is ǫ-A-secure if it has no average case breach of level ǫ. The A-security level of R is defined as ǫ A R △ = inf{ǫ ≥ 0 : R is ǫ-A-secure}.
Of course, Y leaks at most one bit about the truth of Q: 0 ≤ L( Q; Y) ≤ 1. In the next theorem, recall that for each x ∈ X, p x (•) denotes the distribution p(•|x).

Theorem 2. Let l △ = max x,x ′ ||p x -p x ′ || 1 and ǫ ≥ 0. Then R is ǫ-A-secure iff log( l 2 + 1) ≤ ǫ.

Worst-case security vs. differential privacy

We first introduce dp, then discuss its relation to worst-case security. The definition of differential privacy relies on a notion of "neighborhood" between inputs of an underlying randomization mechanism. In the original formulation, two neighbors x and x ′ are two database instances that only differ by one entry. More generally, one can rely upon a notion of adjacency. An undirected graph is a pair (V, E) where V is a set of nodes and E is a set of unordered pairs {u, v} with u, v ∈ V and u v. We also say that E is an adjacency relation on V and if v ∼ v ′ say v and v ′ are adjacent.

Definition 4 (differential privacy). A differentially private mechanism

D is a pair (R, ∼) where R = (X, Y, p(•|•)
) is a randomization mechanism and ∼ is an adjacency relation on X, that is, (X, ∼) forms an undirected graph. Let ǫ > 0. We say D provides ǫ-differential privacy if for each x, x ′ ∈ X s.t. x ∼ x ′ , it holds that for each y ∈ Y:

max y | log p(y|x) p(y|x ′ ) | ≤ ǫ . (9)
Note that condition ( 9) is exactly that given in Theorem 1 to characterize worstcase privacy breaches, but limited to pairs of adjacent rows x and x ′ . This prompts the question of the exact relationship between the two notions. In the rest of the section, we will consider the standard domain X = {0, 1} n of databases, corresponding to subsets of a given set of individuals {1, ..., n}. We deem two databases x, x ′ adjacent if they differ for the value of exactly one individual, that is if their Hamming distance is 1 [START_REF] Dwork | Calibrating Noise to Sensitivity in Private Data Analysis[END_REF][START_REF] Alvim | On the relation between Differential Privacy and Quantitative Information Flow[END_REF][START_REF] Alvim | Differential Privacy: on the trade-off between Utility and Information Leakage[END_REF]. Throughout the section, we let D = (R, ∼) be a generic mechanism equipped with this X and this adjacency relation. Moreover, we will denote by Q i (i ∈ {1, ..., n}) the set of databases {x ∈ X | x i = 1}, that is databases containing individual i.

The following theorem provides a precise characterization of (worst-case) ǫ-security in terms of privacy of individuals: interaction with the mechanism does not significantly change the belief about the participation of any individual to the database. Theorem 3. R satisfies ǫ-security iff for each i ∈ {1, ..., n} and prior p(•), Q i is not an ǫ-breach.

Remark 2. The above theorem is of course still valid if one strengthens the "only if" part by requiring that both Q i and Q c i are not ǫ-breach. We proceed now by linking (worst-case) ǫ-security to ǫ-dp. The next result sets limits to the "arbitrariness" of background information against which dp offers guarantees: for example, it fails in some cases where an adversary has sufficient background information to rule out all possible databases but two, which are substantially different from each other. Theorem 4. If R satisfies ǫ-security then D = (R, ∼) provides ǫ-dp. On the contrary, for each n there exist mechanisms providing ǫ-dp but not ǫ-security; in particular, these mechanisms exhibit Q i -breaches (i ∈ {1, ..., n}) of level arbitrarily close to nǫ > ǫ.

Example 2. Let us consider the mechanism with input domain X = {0, 1} 2 , corresponding to the following matrix:

                     
                      .
This mechanism provides ǫ-dp with ǫ = 1. However, it is not ǫ-secure, as e.g. 2/3 1/12 = 8 > 2 ǫ .

We recover coincidence between ǫ-security and ǫ-dp if we confine ourselves to background knowledge that can be factorised as the product of independent measures over individuals. This provides another characterization of ǫ-dp. In what follows, for any x ∈ X, we denote by x \i the element of {0, 1} n-1 obtained by removing the i-th component from x.

Theorem 5. The following statements are equivalent:

1. D satisfies ǫ-dp; 2. for each i ∈ {1, ..., n} and p(x) of the form p i (x i )q(x \i ), Q i is not an ǫ-breach; 3. for each p(x) of the form n j=1 p j (x j ) and for each i ∈ {1, ..., n}, Q i is not an ǫbreach.

Asymptotic security

We assume that the attacker collects a tuple y n = (y 1 , y 2 , . . . , y n ) ∈ Y n of observations generated i.i.d from the mechanism R. We expect that, given Q, as n grows, the breach level approaches a threshold value. In order to the characterize synthetically the security of the randomization mechanism, though, it is important to characterize how fast this threshold is approached. Again, we distinguish a worst-from an average-case scenario and, for the rest of the section, fix a generic randomization mechanism R.

Worst-case scenario

We begin with an obvious generalization of the notion of breach.

Definition 5 (n-breach of level ǫ)

. A (n, ǫ)-privacy breach is a subset Q ⊆ X s.t. for some prior distribution p(x) on X, we have that p(Q) > 0 and

max p(y n )>0 | log p(Q|y n ) p(Q) | > ǫ .
The next proposition says that a notion of security based on bounding the level of n-breaches is not achievable. For the sake of simplicity, we shall discuss some of the following results in the case R is non-degenerate (all rows of the matrix are distinct). Proposition 1. Assume R is non-degenerate. For n large enough, R has n-breaches of arbitrary level. More explicitly, for any nonempty Q ⊆ X and any ǫ ≥ 0 there is a prior distribution p(x) s.t. for any n large enough there is y n (p(y n ) > 0) such that log p(Q|y n ) p(Q) > ǫ.

The above proposition suggests that, in the case of a large number of observations, worst-case analysis should focus on how fast p(Q|y n ) can grow, rather than looking at the maximum level of a breach. Definition 6 (rate of a breach). Let ρ ≥ 0. A breach of rate ρ is a subset Q ⊆ X such that there exist a prior distribution p(x) on X with p(Q) > 0 and a sequence of n-tuples, {y n } n≥0 , with p(y n ) > 0, such that p(Q|y n ) 1 -2 -nρ ′ with ρ ′ > ρ. A randomization mechanism is ρ-rate secure if it has no privacy breach of rate ρ. The rate security level is defined as ρ R △ = inf{ρ ≥ 0 : R is ρ-rate secure}.

Theorem 6. R is ρ-rate secure iff ρ ≥ log max y π M,y π m,y .
The above theorem says that, for large n, the seriousness of the breach, for certain y n , can be as bad as

≈ log 1 -( π m π M ) n p(Q)
. The result, however, does not tell us how likely a serious breach is depending on n. The next result shows that the probability that some observable y n causes a Q-breach grows exponentially fast. We premise some notation. Fix a prior p(x) over X. Recall that we let X ∼ p(x) denote a random variable representing the secret information, and Y n = (Y 1 , ..., Y n ) be the corresponding random vector of n observations, which are i.i.d. given X. Let us fix Q ⊆ X s.t. p(Q) > 0. Then p(Q|Y n ) is a random variable. For any fixed ǫ > 0, let us consider the two events

Breach ǫ n △ = p(Q|Y n ) p(Q) > 2 ǫ and Breach ǫ n △ = p(Q) p(Q|Y n ) > 2 ǫ .
Clearly, the event Breach ǫ n ∪ Breach ǫ n is the event that Y n causes a Q-breach of level ǫ. As n grows, we expect that the probability of this event approaches 1 quite fast. The next theorem tells us exactly how fast. Theorem 7. Assume R is non-degenerate and strictly positive. Then, with the notation introduced above

Pr(Breach ǫ n |X ∈ Q) 1 -2 -nC and Pr(Breach ǫ n |X ∈ Q c ) 1 -2 -nC
where C = min x∈Q,x ′ ∈Q c C(p x , p x ′ ), with the understanding that x and x ′ in the min are taken of positive probability. As a consequence, the probability that Y n causes a Q-breach reaches 1 at rate at least C.

Average-case scenario

It is straightforward to extend the definition of average-case breach to the case with multiple observations. For any nonempty subset Q ⊆ X, and random variable X ∼ p(x), s.t. p(Q) > 0, we consider Q = I Q (X) and define the leakage imputable to Q after n observations as

L n ( Q; Y n ) H ∞ ( Q) -H ∞ ( Q|Y n ). An n-breach of level ǫ ≥ 0 is a Q such that L n ( Q; Y n ) > ǫ.
Recall from (4) that ), [START_REF] Boreale | Worst-and average-case privacy breaches in randomization mechanisms[END_REF] implies that, as n → +∞ we have

P n succ = 2 -H ∞ ( Q|Y n ) is
P n succ → 1, hence L n ( Q; Y n ) → -log max{p(Q), 1 -p(Q)} . If p(•|Q) = p(•|Q c ) then P n
succ is constantly max{p(Q), 1p(Q)}, so that the observations give no advantage to the attacker. These remarks suggest that, in the case of repeated observations, it is again important to characterize how fast P n succ → 1.

Definition 7 (rate of a breach -average case). Let ρ ≥ 0. An A-breach of rate ρ is a subset Q ⊆ X such that for some prior distribution p(x) on X with p(Q) > 0 one has that P n succ 1 -2 -nρ ′ , for some ρ ′ > ρ. A randomization mechanism is ρ-rate A-secure if it has no privacy breach of rate ρ. The rate A-security level is defined as

ρ A R △ = inf{ρ ≥ 0 : R is ρ-rate A-secure}.
Now we can proceed with the following theorem.

Theorem 8. R is ρ-rate A-secure iff max x,x ′ C(p x , p x ′ ) ≤ ρ.

Utility

We next turn to the study of utility. In the rest of the section, we fix a mechanism R and a prior distribution p(•). Without any significant loss of generality, we shall assume that R is strictly positive and that supp(p) = X. Moreover, in this section, we shall work under the more general assumption that Y is finite or denumerable.

For any n ≥ 1, we are now going to define the expected utility of R, depending on user-specific belief, modeled as a prior p(•) on X, and on function loss : X × X → R + . Here, loss(x, x ′ ) represents the loss of a user who interprets the result of an observation of R as x ′ , given that the real answer is x. For the sake of simplicity, we shall assume that loss achieves a proper minimum when x = x ′ : for each x x ′ , loss(x, x) < loss(x, x ′ ). We also presuppose a guessing function g : Y n → X. The expected utility of Drelative to g -after n observations is in fact defined as an expected loss (the lower the better), thus

U n △ = x p(x) y n p(y n |x)loss(x, g(y n )) . (10)
Note that this definition coincides with that of Ghosh et al. [START_REF] Ghosh | Universally utility-maximizing privacy mechanisms[END_REF] when one interprets our guessing function g as the remap considered in [START_REF] Ghosh | Universally utility-maximizing privacy mechanisms[END_REF]. This is also the utility model of Alvim et al. [START_REF] Alvim | On the relation between Differential Privacy and Quantitative Information Flow[END_REF], modulo the fact they only consider the 0/1-loss, or better, the complementary gain.

Example 3. When Y is a subset of the reals, legal loss functions include the absolute value error loss(x, x ′ ) = |x ′ -x| and the squared error loss(x, x ′ ) = (x ′x) 2 . The binary loss function defined as 0 if x = x ′ and 1 otherwise is another example: the resulting expected loss is just error probability, U n = P n e .

It is quite easy to argue that, since a proper minimum in loss(x, x ′ ) is reached when x = x ′ , the utility is maximized asymptotically when g respects the map criterion: p(g(y n )|y n ) ≥ p(x|y n ) for each x ∈ X. In what follows, we just assume that g is a fixed map function. Below, we study the behavior of utility in relation to differential privacy. The crucial quantity is

ρ R △ = min x,x ′ ∈X,p x p x ′ C(p x , p x ′ ) . (11)
We will show that the the asymptotic rate of utility is determined solely by ρ R . Note that this quantity does not depend on the user-defined loss function, nor on the prior p(•). For the sake of simplicity, below we discuss the result only in the case when R is non-degenerate4 .

Remark 3. We note that the formula [START_REF] Boreale | Quantitative Information Flow, with a View[END_REF] for Chernoff Information extends to the case when p(•) and q(•) have the same denumerable support.

Theorem 9. Assume R is non-degenerate. Then U n U R + 2 -nρ R , where U R △ = x p(x)loss(x, x).
Having established the centrality of ρ R in the asymptotic behavior of utility, we now discuss the relationship of this quantity with the worst-case security level ǫ provided by the mechanism. The first result provides us with a simple, general bound relating ρ R and ǫ. In what follows, we will obtain more precise results relating ǫ to the utility rate ρ R in the case of a class of mechanisms providing ǫ-dp. Specifically, we will consider mechanisms with a finite input domain X = {0, 1, . . . , N}, a denumerable Y = Z and a conditional probability matrix of the form p i ( j) = Mc |i-j| , for some positive c < 1. This class of mechanisms includes the geometric mechanism (a discrete variant of the Laplacian mechanism, see [START_REF] Ghosh | Universally utility-maximizing privacy mechanisms[END_REF]) and also a version extended to Z of the optimal mechanism considered by Alvim et al. [START_REF] Alvim | On the relation between Differential Privacy and Quantitative Information Flow[END_REF].

Theorem 11. Let R be a mechanism as described above. Then ρ R = log(1+c)-1 2 log c-1 .

Remark 4. The geometric mechanism is obtained by equipping the above described mechanism with the the line topology over X = {0, ..., N}: i ∼ j iff d i j △ = |i -j| = 1. This is the topology for counting queries in "oblivious" mechanisms, for example. If we set c = 2 -ǫ , then this mechanism provides ǫ-dp. The above theorem tells us that in this case ρ R = ǫ 2 + log 1+2 -ǫ 2 . By setting e.g. ǫ = 1, one gets ρ R ≈ 0.085. For any mechanism R with input X = {0, ..., N} and output Y = Z, we can consider the corresponding truncated mechanism R ′ : it has X = Y = {0, 1, . . . , N} and its matrix is obtained from R's by summing all the columns y < 0 to column y = 0, and all the columns y > N to column y = N. Corollary 1. Assume R ′ is the truncated version of a mechanism R. Then ρ R ′ < ρ R .

In the case of a single observation case, treated by Ghosh et al. [START_REF] Ghosh | Universally utility-maximizing privacy mechanisms[END_REF], there is no substantial difference between the geometric mechanism and the truncated geometric one. Corollary 1 shows that the situation is different in the case with repeated observations.

Conclusion and further work

We have analyzed security of randomization mechanisms against privacy breaches with respect to various dimensions (worst vs. average case, single vs. repeated observations, utility). Whenever appropriate, we have characterized the resulting security measures in terms of simple row-distance properties of the underlying channel matrix. We have clarified the relation our worst-case measure with dp.

A problem left open by our study is the exact relationship between our average-case security notion and the maximum leakage considered in qif -see e.g. [START_REF] Köpf | Vulnerability Bounds and Leakage Resilience of Blinded Cryptography under Timing Attacks[END_REF]. We would also like to apply and possibly extend the results of the present paper to the setting of de-anonymization attacks on dataset containing micro-data. [START_REF] Narayanan | Robust De-anonymization of Large Sparse Datasets[END_REF] has shown that the effectiveness of these attacks depends on certain features of sparsity and similarity of the dataset, which roughly quantify how difficult it is to find two rows of the dataset that are similar. The problem can be formalized in terms of randomization mechanisms with repeated observations -see [START_REF] Boreale | Quantitative Information Flow, with a View[END_REF] for some preliminary results on this aspect. Then the row-distance measures considered in the present paper appear to be strongly related to the notion of similarity, and might play a crucial in the formulation of a robust definition of dataset security.

  by a finite set of inputs X representing the secret information, a finite set of observables Y representing the observable values, and a conditional probability matrix, p(•|•) ∈ [0, 1] X×Y , where each row sums up to 1.

Theorem 10 .

 10 Assume R is worst-case ǫ-secure. Then ρ R ≤ ǫ. The same conclusion holds if D = (R, ∼) provides ǫ-dp.

Note that C(p, q) = 0 iff p = q and that C(p, q) = C(q, p). However C(•, •) fails to satisfy the triangle inequality.

The result carries over to the general case, at the cost of some notational burden: one has to replace U R with a more complicated expression.

Work partially supported by the eu funded project Ascens.