Cryptography Reference
In-Depth Information
It is worth noting in the above description, that there is no functional
dependency between a
0
,...,a
`
and the public-vectors γ, and Γ is attached to
the public-key.
Correctness. We next discuss the correctness of the scheme.
Theorem 3.9. The Boneh-Franklin scheme satisfies the correctness in the
sense of definition
3.1
.
Proof. First note that the Boneh-Franklin scheme is a unary multiuser en-
cryption scheme. Let htk,ek,sk
1
,...sk
n
i be distributed according to the
process KeyDist
BF
`
(1
n
) where tk = ha
0
,a
1
,...,a
`
i and ek = hH,Γi with
H = (g
a
0
,...,g
a
`
). Here Γ is an (`,n,q)-code over an alphabet Z
q
for some k
bit prime number q and g ∈G where G is a group whose description has been
produced by Gen(1
k
). The secret key sk
u
is computed as a vector δ = b
j
·γ
j
with b
j
= a
0
(
P
i=1
a
i
γ
i
)
−1
for j = 1,...,n.
We will now prove that for any m ∈M = hgi and any user u ∈ [n] it holds
that
Prob[Receive
BF
`
(Transmit
BF
k
(ek,m),sk
u
) = m] = 1
Let the transmission hh
0
· m,h
1
,...,h
`
i sampled by the distribution
Transmit
BF
k
(ek,m) for some r randomly chosen from Z
q
−{0}. The re-
ceiver with index u has access to the key material sk
u
= δ which is equal to
b
u
·γ
u
. Denoting the vector by hδ
1
,...,δ
`
i, the receiver outputs
h
0
·m· (h
rδ
1
...h
rδ
`
)
−1
`
We will prove that δ = b
u
·γ
u
is a representation of h
0
base h
1
,...,h
`
for
any u ∈ [n]. In other terms, we will show that h
0
= h
δ
1
h
δ
2
...h
δ
`
. Indeed, by
substituting δ
i
= b
u
·γ
i
and h
i
= g
a
i
for any i ∈{1,...,`} we obtain:
h
0
=
g
a
1
γ
1
·g
a
2
γ
2
...g
a
`
γ
`
b
u
=
g
a
1
γ
1
·g
a
2
γ
2
...g
a
`
γ
`
a
0
(
P
i=1
a
i
γ
i
)
−1
= g
a
0
Hence the output of the receiving algorithm for any user with index u ∈ [n]
is the message m. This proves the correctness of the Boneh-Franklin scheme.
Security. We, next, show that the Boneh-Franklin scheme is CPA insecure in
the sense of Definition
3.2
. The security proof is based on the DDH assumption
which we state below:
Definition 3.10. DDH. Let G,g,q be a description of a group, and an el-
ement g ∈ G of order q as produced by Gen(1
k
) for some k ∈ N. Con-
sider now the random variable
R
that equals to hG,q,g,g
a
,g
b
,g
c
i where a,b,c