Cryptography Reference
In-Depth Information
element
s
of
S
uniformly at random. Unless otherwise indicated, algorithms are
randomized. We write
z
←A
O
1
,O
2
,...
(
x, y, ...
) to indicate that
A
is an algorithm
with inputs
x, y, ...
and access to oracles
O
2
, ...
and let
z
be the output.
Let
X
and
Y
be two random variables over some set
S
.The
statistic distance
O
1
,
between
X
and
Y
is defined as
Δ
(
X, Y
)=
2
s∈S
Pr[
X
=
s
]
Pr[
Y
=
s
]
.
We say
X
and
Y
are statistically indistinguishable if
Δ
(
X, Y
) is negligible. It's
routine to see that statistical indistinguishability implies computational indis-
tinguishability.
−
2.1 Tag-Based Encryption
Informally in a tag-based encryption scheme, the encryption and decryption
operations take an additional “tag”. we review selective-tag security against
chosen-ciphertext attacks [19] of tag-based encryption. More formally, a tag-
based encryption scheme
=(
TGen
,
TEnc
,
TDec
) consists of three algorithms.
TGen
takes as input a security parameter
λ
, and outputs a key pair (
pk, dk
);
TEnc
takes as input a public key
pk
,aplaintext
m
,atag
τ
, and outputs a ciphertext
c
;
TDec
takes as input a secret key
dk
, a ciphertext
c
,atag
τ
, and outputs a
plaintext
m
.
For correctness, we require that
TBE
←
TGen
(
λ
), we have
TDec
(
dk, τ,
TEnc
(
pk,τ,m
)) =
m.
We now define the selective-tag CCA security.
Consider the following experiment between a chlangger and an adversary
∀
λ
,
τ
and
m
,(
pk, dk
)
A
:
Experiment Exp
tbe
-
stag
-
cca
TBE,A
(
λ
)
(
τ
∗
,St
0
)
←A
(
λ, init
)
(
pk, dk
)
←
TGen
(
λ
)
(
m
0
,m
1
,St
)
←A
DEC
(
dk,·
)
(
find,pk,St
0
)
,
c
∗
←
TEnc
(
pk, τ
∗
,m
b
)
b
←A
DEC
(
dk,·
)
(
guess, c
∗
,St
)
If
b
=
b
then return 1 else return 0
b
←{
0
,
1
}
where the oracle
DEC
(
dk,
(
c, τ
)) returns
m
←
TDec
(
dk,τ,c
) with the restriction
) for challenge tag
τ
∗
.Bothmes-
sages must be of the same size. We define the advantage of
that
A
is not allowed to query oracle
DEC
(
dk,
·
A
in the above exper-
(
λ
)=
2
iment as
Adv
tbe
-
stag
-
cca
TBE,A
Pr [
Exp
tbe
-
stag
-
cca
TBE,A
1
(
λ
)=1]
−
.
A tag-based en-
cryption scheme
is said to be selective-tag secure against chosen-ciphertext
attacks if the advantage function is negligible for all probabilistic polynomial
time (PPT)
TBE
A
. In the above experiment
A
is allowed to make decryption queries
=
τ
∗
. This includes queries for the challenge ciphertext
c
∗
for any
τ
with tags
=
τ
∗
. The challenge tag
τ
∗
has to be output by
τ
before seeing the public key.
Tags in public key encryption have been considered in [28]. We briefly review
the definition of full-tag CCA security in [28].
Full-tag CCA security
for TBE schemes considered in [28] are almost the same
as selective-tag CCA security, except that
A
is allowed to choose
τ
∗
at the end of
its
find
stage, possibly depending on the public key and its queries. In the
guess
stage,
A
=(
τ
∗
,c
∗
). In particular,
A
is allowed to ask any decryption queries (
τ, c
)
