Definition of Good and Bad Views. In the real world, all tuples in νp define exactly one input-output pair for P. Likewise, the tuples in νk are input-output pairs for P. Using these tuples, one can observe that any tuple (ji, a¯i, Mi, Ci) νc also defines an input-output pair for P, namely Mi ⊕ ϕ¯a¯i (Lj ), Ci ⊕ ϕ¯a¯i (Lj ) , see (7), where we define ϕ¯a¯i := ϕazi ◦ ··· ◦ ϕa1 i for brevity. If among all these q + p + μ input-output pairs defined by ν, there are two that have colliding input or output values, we consider ν to be a bad view. Formally, ν is called “bad” if one of the following conditions is satisfied, where we recall that the user index j in a tuple in νc determines which key tuple from νk has to be used: badc,c : for some distinct (j, a¯, M, C), (j′, a¯′,M′,C′) ∈ νc: ϕ¯a¯(Lj) ⊕ ϕ¯a¯' (Lj' ) ∈ {M ⊕ M′,C ⊕ C′}, badc,p : for some (j, a¯, M, C) ∈ νc and (X, Y ) ∈ νp: ϕ¯a¯(Lj) ∈ {M ⊕ X, C ⊕ Y }, badc,k : for some (j, a¯, M, C) ∈ νc and (K, L) ∈ νk: ϕ¯a¯(Lj) ∈ {M ⊕ K 0n−k,C ⊕ L}, badp,k : for some (X, Y ) ∈ νp and (K, L) ∈ νk: X = K 0n−k or Y = L, badk,k : for some distinct (K, L), (K′, L′) ∈ νk: K = K′ or L = L′. We write bad = badc,c badc,p badc,k badp,k badk,k. The definition of bad events differs from the single-user analysis of Xxxxx et al. [9] in the adjustment of bad events badc,k and badp,k and the addition of the bad event badk,k. The events badc,k and badp,k have been adjusted as construction or permutation queries may now collide with μ different key tuples. The addition of the new bad event badk,k come from the fact that different key tuples might collide.
