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 1 ...h `
) −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
Search WWH ::




Custom Search