Cryptography Reference
In-Depth Information
The essential difference is that the success probability of the case v = 0 is
not guaranteed to be related in a predictable manner to the overall probability
of success. In particular what we may argue is that in each conditional space
A
i
the success probability of the adversary in the experiment p
v
satisfies that
p
0
= 1/2+α
i
for some α
i
(this is without loss of generality as if an adversary
drops below 1/2 in its prediction capability in a certain conditional space
there exists another adversary that by flipping its answer does better than
1/2) and p
q
= 1/2. The latter statement follows from the fact that when v = q
no information about the plaintext is transmitted to the adversary. Regarding
the former, we use α
i
to denote the success of the adversary in the conditional
space A
i
. Regarding the α
i
values we know that
`
·
P
i=1
(1/2+α
i
) = 1/2+.
Based on this there must be an i
0
such that α
i
0
≥ /`. Indeed, if α
i
< /`
for all i = 1,...,` we have that the success probability would be less than
1/2 + , a contradiction. As a result we can find some v
0
for which it holds
that |p
i
v
0
−1
−p
i
v
0
| ≥ /(`q). Now the proof can be completed with identical
arguments to those of theorem
3.3
while operating in the conditional A
i
0
space.
1
3.2.3 Boneh-Franklin Multiuser Encryption Scheme
The scheme works in conjunction to a multiplicative cyclic group G of large
prime order over which solving the Decisional Di
e Hellman (DDH) Problem
is hard (a definition will be given shortly). Vectors in Z
q
will be denoted by
δ = hδ
1
,...,δ
`
i.
A possible example for G can be the subgroup of order q of Z
p
, where
q | p−1 and p,q are large primes. It is helpful to keep in mind that arithmetic
in the exponents is performed in the finite field Z
q
, i.e., g
x+y
= g
x+y mod q
and similarly for exponentiation g
a·b
= g
a·b mod q
.
For some ` ∈ N, let h
0
,h
1
,...,h
`
be random elements of G so that h
j
=
df
g
r
j
for j = 0,...,` and define the vector r =
df
hr
1
,...,r
`
i. A representation
of h
0
with respect to the base h
1
,...,h
`
is an `-vector δ =
df
hδ
1
,...,δ
`
i such
that h
0
= h
δ
1
...h
δ
`
, or equivalently δ · r = r
0
where · denotes the inner
product between two vectors.
Let Gen be a polynomial-time algorithm that receives 1
k
as input (where
k is a security parameter) and it samples the description of a multiplicative
group as well as of an element g inside this group. While we will avoid making
the group description explicit we assume that it contains su
cient information
to perform the multiplication operation as well as it contains a membership
test for the group; the value q is the prime order of the cyclic subgroup gen-
erated by g. We further require that k < log q < k+1 something that implies
that the group G cannot be specified as a list of elements.
Based on Gen, we define the Boneh-Franklin multiuser encryption scheme
with parameters k,`N as follows
