Cryptography Reference
In-Depth Information
Just as [23] described, we require that the total residual leakage over the lossy
and ABO collections is
≤
n
−
+
n
−
n
−
κ
(1)
for some
κ
=
κ
(
λ
)=
ω
(log
λ
), which guarantees the one-wayness of injective
functions as in [23]. Let
H
be a family of pairwise independent hash functions
{
0
,
1
}
n
ρ
,where0
from
to
{
0
,
1
}
≤
ρ
≤
κ
−
2lg(1
/
) for some negligible
=
ρ
.
negl(
λ
). The cryptosystem has message space
{
0
,
1
}
TGen
:
This algorithm generates an injective trapdoor function via (
s, td
)
←
S
ltf
(
λ,
injective
), an ABO trapdoor function having lossy branch 0
v
via
(
s
,td
)
S
abo
(
λ,
0
v
), and a hash function
h
. The public key consists
of the two function indices and the hash function:
pk
=(
s, s
,h
)
.
The secret
decryption key consists of
td
(
td
is for the proof), along with the public key:
dk
=(
td, pk
)
.
It Outputs (
pk, dk
).
TEnc
:
This algorithm takes as input (
pk, m
)where
pk
=(
s, s
,h
) is a public key
and
m
←
←H
ρ
is the message. It chooses a branch
τ
∈{
0
,
1
}
∈
B
λ
at random,
n
uniformly at random. It
and use it as a tag. Then it chooses
x
←{
0
,
1
}
computes
c
1
=
F
(
s, x
)
,c
2
=
G
(
s
,τ,x
)
,c
3
=
m
⊕
h
(
x
)
.
The ciphertext is
output as (
c, τ
)=
(
c
1
,c
2
,c
3
)
,τ
.
TDec
:
This algorithm takes as input
dk,
(
c, τ
)
where
dk
=(
td, pk
)isthe
secret key, and (
c, τ
)=
(
c
1
,c
2
,c
3
)
,τ
is a ciphertext. It first computes
x
=
F
−
1
(
td, c
1
), and checks that
c
1
=
F
(
s, x
)and
c
2
=
G
(
s
,τ,x
); if not, it
outputs
⊥
. Otherwise, it outputs
m
=
c
3
⊕
h
(
x
).
Theorem 2.
The algorithms
(
TGen
,
TEnc
,
TDec
)
described above is a selective-
tag CCA secure tag-based encryption scheme.
We prove the theorem by defining a sequence of experiments Game
0
,...,Game
4
,
where Game
0
is identical to the selective-tag CCA experiment. Then for 1
≤
i
≤
3, the adversary's view in Gamei
i
and Game
i
+1
are statistically or computa-
tionally indistinguishable. Finally it follows immediately from the definition of
Game
4
that the adversary's view is identical for either value of
b
.Bythe
transitivity we get that Game
0
and Game
4
are computationally indistinguish-
able, hence the theorem is proved. We describe the games between a simulator
and an adversary
∈{
0
,
1
}
A
as follows:
Game
0
:
This game is identical to the selective-tag CCA game for TBE. Specif-
ically, at the beginning
outputs a challenge tag
τ
∗
. Then the simulator runs
TGen
to get (
pk, dk
), and gives
pk
to
A
A
. After obtaining
pk
,
A
can query a or-
acle
DEC
(
dk,
submits
two challenge plaintext (
m
0
,m
1
) to the simulator, and the simulator chooses
b
·
) with ciphertext
c
,tag
τ
, and receives the plaintext.
A
uniformly at random, and return
c
∗
←
TEnc
(
pk, τ
∗
,m
b
). Upon receiv-
ing the ciphertext
∈{
0
,
1
}
A
can still query the decryption oracle
DEC
(
c, τ
). The only
restriction of
A
to query decryption oracle is
A
is not allowed to make query