Table 3: Computation delays on mobile devices (ms).p=1024-bit p=2048-bit
푛=1 푛=25 푛=50 푛=1 푛=25 푛=50
Exponentiation (1 GHz CPU, 512 MB RAM) 37 452.6 907.8 168.9 3385.4 6762.5
Exponentiation (2.26 GHz CPU, 2 GB RAM) 12.9 192.8 385.3 75.4 1458.8 2917.4(DDDH), which is stronger assumption than the divisible
computational Diffie-Hellman problem (DCDH).
Definition 1.The DCDH problem is as follows: given
(푔, 푔푥,푔푦), where푥, 푦 ∈Z푞,compute푔푦/푥.
Definition 2.The DDDH problem is as follows: given
(푔, 푔푥,푔푦,푔푧), where푥, 푦, 푧 ∈Z푞,decidewhether푧=푦/푥
or a randomly chosen number.
The DDDH problem is weaker than DCDH, since if an
adversary could solve the DCDH problem, he could solve
the DDDH problem by computing푔푥to decide푔푧=푔푦/푥;
thus the DDDH assumption is stronger than the DCDH
assumption.Similarly,theDDHproblemisweakerthan
the computational Diffie-Hellman problem (CDH), which is
weaker than discrete logarithm problem (DL) [ 22 ]. We want
to prove the security of our protocol under the DDH and
DDDH assumptions.
Theorem 3.The DDDH problem is equivalent to the DDH
problem.
Proof.Given the DDDH input (푔, 푔푥,푔푦,푔푧), where푧=
푦/푥,onesubmits(푔, 푔푥,푔푧,푔푦) to DDH to decide whether
푦=푥푧or a randomly chosen number. Similarly, given
the DDH input (푔, 푔푥,푔푦,푔푧), where푧=푥푦,onesubmits
(푔, 푔푥,푔푧,푔푦) to DDDH to decide if푦=푧/푥or a randomly
chosen number.
Therefore, we know that if there is no polynomial time
algorithm to solve the DDH problem, it is hard to solve the
DDDH problem.
Theorem 4.If the DDH problem is hard, it is hard to find a
polynomial time algorithm to recover the group key from the
proposed protocol; in other words, it provides group key secrecy
against passive adversaries under the DDH assumption.
Proof.Letview(푛, 푘) be public information for a group of푛
members to establish a group key푔푘;thusitisaviewof
passive attackers,
V푖푒푤(푛, 푘):=(푔푥^1 ,푔푥^1 푘,푔푥^2 ,푔푥^2 푘,...,푔푥푛,푔푥푛푘). (10)
Suppose we had an algorithmFthat with significant
probability succeeds to distinguish between (view(푛, 푘),
푔푦), where푦is a random number푦∈Z푞,and(view(푛, 푘),
푔푘)where푔푘is the group key; that is,F(V푖푒푤(푛, 푘), 푔푦)=
F(푔푥^1 ,푔푥^1 푘,푔푥^2 ,푔푥^2 푘,...,푔푥푛,푔푥푛푘,푔푦)=1,where푦=푘,
otherwise, returns 0. Then we can query toFwith input
view(푛 − 1, 푘) = (푔푥^1 ,푔푥^1 푘,푔푥^2 ,푔푥^2 푘,...,푔푥푛−1,푔푥푛−1푘)for푛−1
members’ information and additional input((푔푥푖)푟
,(푔푥푖푘)푟
)
for a random number푟∈푅Z푞,where0<푖<푛,thatis,
F(V푖푒푤(푛 − 1, 푘), 푔푥푖푟,푔푥푖푘푟,푔푦).Itfollowsthat
(V푖푒푤(1, 푘), 푔푥푟^1 ,푔푥푘푟^1 ,푔푥푟^2 ,푔푥푘푟^2 ,...,푔푥푟푛−1,푔푥푘푟푛−1,푔푦)=
F(푔푥,푔푥푘,푔푥푟^1 ,푔푥푘푟^1 ,푔푥푟^2 ,푔푥푘푟^2 ,...,푔푥푟푛−1,푔푥푘푟푛−1,푔푦),where
푟푖∈푅Z푞for0<푖<푛.Then퐹can solve the DDDH problem
since it can decide whether푦=푥푘/푥or a random number,
given(V푖푒푤(1, 푘), 푔푦)) = (푔푥,푔푥푘,푔푦).Itmeansthat퐹can
also solve the DDH problem byTheorem 3.Theorem 5.The proposed scheme provides backward secrecy,
forward secrecy, and key independence provided the DDH
problem is intractable.Proof.Whenever membership is changed or the group key
is updated, the group controller alters its own secret푘to푘耠,
where푘耠is an independently random number to푘∈Z푞;
it implies that it is impossible to find an algorithm퐹such
that퐹(푔푘)→푔푘耠
without knowledge of푘and푘耠.We
assume that the secret values are uniformly distributed by a
pseudorandom generator. Therefore, when the group key has
been changed, an adversary must use new public information,
V푖푒푤(푛, 푘耠)=(푔푥^1 ,푔푥^1 푘耠
,푔푥^2 ,푔푥^2 푘耠
,...,푔푥푛,푔푥푛푘耠
),torecover
the group key updated into푔푘耠
and it depends on a solution
to solve the DDH problem byTheorem 4.Itfollowsthatpast
members, future members, or adversaries who know a subset
of previous group keys cannot learn the current group key,
since the broadcast message from the master does not contain
their locker푋푖inview().Theorem 6.The proposed scheme provides implicit key
authentication under the security of certified public key.Proof.Alockerwhichthemasterobtainsfromgroupmem-
bers is what a group member signs with its public key certified
by a CA. Concretely, a locker푋푖is hashed by a one-way
function such as SHA-2, and hash (푋푖)issignedwith푀푖’s
private key using a digital signature algorithm such as RSA,
DSA, and ECDSA. Then, the locker is verified with the public
key bound to푀푖and certified by CA. If there is a locker of
nonmember in the locker list of a group, it must be along with
a forged signature. It means that the problem occurs in a hash
collision attack or a rogue CA certificate [ 23 ]. Once all verified
lockers are transferred to the master, any other nodes which
are not a group member cannot recover the group key under
the DDH assumption (Theorems 4 and 5 ).