Cryptography Reference
In-Depth Information
a function in ({0,1}
w×`
→{0,1}
`
); we denote σ
i
(X) the i-th symbol of σ(X).
Based on the marking assumption, the strategy σ must satisfy the following
constraints (i) if x
i
= 0 it holds that σ
i
(X) = 0, (ii) if x
i
= w it holds that
σ
i
(X) = 1.
In the analysis we will use the notation C
p
(w,x) = x·C
p
(1)+(w−x)·C
p
(0)
with w ∈ N,x ∈ {0,...,w}. We next determine the random variable that
corresponds to the cumulative score assigned to a coalition of w users. We
have
`
X
S
σ
=
(2·σ
i
(X) −1) ·C
p
i
(w,x
i
)
i=1
Consider now some parameter α ∈ R
+
; we are interested in an upper bound
of the expectation
h
e
−α(2·σ
i
(X)−1)·C
p
i
(w,x
i
)
i
`
Y
E[e
−αS
σ
] = E
i=1
X
`
Y
E[p
x
i
(1−p)
w−x
i
e
−α(2·σ
i
(X)−1)·C
p
(w,x
i
)
]
=
i=1
X∈{0,1}
w×`
where the above follows from the fact that the columns are selected indepen-
dently.
We next provide a simplification on the domain of possible adversarial
strategies. Consider the equivalence class over the set of all matrices X ∈
{0,1}
w×`
such that X ∼ X
0
if and only if X and X
0
share the same column
Hamming weights. Consider now two matrices X 6= X
0
that satisfy X ∼ X
0
and a strategy σ for which it holds that σ
i
(X) 6= σ
i
(X
0
) for some location
i ∈ {1,...,`}. We call such strategies “unorthodox.” On the other hand if
σ
i
(X) = σ
i
(X
0
) for all X,X
0
with X ∼ X
0
and all locations i ∈{1,...,`} we
call the strategy “orthodox.”
Given a possibly unorthodox strategy σ we construct an orthodox strategy
σ
0
as follows: for each equivalence class Q of ∼ we consider the value:
n
o
`
Y
E[p
x
i
(1−p)
w−x
i
e
−α(2·σ
i
(X)−1)·C
p
(w,x
i
)
]
max
X∈Q
i=1
If X
ma
Q
is a class representative that matches the above maximal value, we
define for all X ∈ {0,1}
w×`
the new strategy σ
0
(X) = σ(X
max
Q
) where Q is
the equivalence class of X.
Lemma 1.22. For any α ∈ R
+
, given any coalition strategy σ, the strategy
σ
0
defined above is an orthodox strategy that satisfies E[e
−αS
σ
] ≤ E[e
−αS
σ
0
].
Proof. It is easy to see that σ
0
is orthodox as for any X it returns σ evaluated
on a single representative of the class of X. The bound on the expectation
follows easily from the choice of the class representative made.
