Cryptography Reference
In-Depth Information
All-But-One Trapdoor Functions.
In an ABO collection, each function has
an extra input called its
branch
. All of the branches are injective trapdoor func-
tions (having the same trapdoor value), except for one branch which is lossy.
The lossy branch is specified as a parameter to the function sampler, and its
value is hidden by the resulting function description.
Let
B
λ
}
λ∈
N
be a collection of sets whose elements represent the branches.
A collection of (
n,
)-all-but-one trapdoor functions with branch collection
B
is
a triplet of PPT algorithms (
S
abo
,G,G
−
1
) such that:
B
{
=
1. For any
b
∗
∈
B
λ
,
S
abo
(
λ, b
∗
) outputs (
s, td
)
n
n
.
∈{
0
,
1
}
×{
0
,
1
}
=
b
∗
,
G
(
s, b,
n
,
For any
b
·
) computes an injective function
g
s,b
(
·
)over
{
0
,
1
}
and
G
−
1
(
td, b,
) computes
g
−
1
). Additionally,
G
(
s, b
∗
,
·
s,b
(
·
·
) computes a func-
n
whose image has size at most 2
n−
.
tion
g
s,b
∗
(
·
)over
{
0
,
1
}
2. For any
b
0
,b
1
∈
B
λ
, the first output
s
0
of
S
abo
(
λ, b
0
) and the first output
s
1
of
S
abo
(
λ, b
1
) are computationally indistinguishable.
Hash Functions.
A family of functions
H
=
{
h
:
D
→
R
}
is called pair-
wise independent [30] if, for every distinct
x, x
D
and every
y, y
∈
∈
R
,
h
(
x
)=
y
]=1
/
2
.
Pr
h←H
[
h
(
x
)=
y
∧
|
R
|
Extracting Randomness.
The min-entropy of a random variable
X
over a
domain
S
is defined as
H
∞
(
X
)=
lg(max
s∈S
Pr[
X
=
s
])
.
In many natural
settings, the variable
X
is correlated with another variable
Y
whose value is
known to a an adversary. We use the notion of average min-entropy [11], which
captures the remaining unpredictability of
X
conditioned on the value of
Y
:
−
lg
E
y←Y
2
H
∞
(
X|Y
=
y
)
=
lg
E
y←Y
max
s∈S
Pr[
X
=
s
]
.
H
∞
(
X
|
Y
)=
−
−
The average min-entropy is the negative logarithm of the average predictability
of
X
conditioned on the random choice of
Y
; that is, the average maximum
probability of predicting
X
given
Y
. We review the following useful lemmas.
2
r
Lemma 4.
([11], Lemma 2.2).
If
Y
takes at most
possible values and
Z
is
any random variable, then
H
∞
(
X
|
(
Y,Z
))
≥
H
∞
(
X
|
Z
)
−
r.
Lemma 5.
([11], Lemma 2.4).
Let
X
,
Y
be random variables such that
X
∈
and
H
∞
(
X
n
{
0
,
1
}
|
Y
)
≥
k
.Let
H
be a family of pairwise independent hash func-
←H
, we have
Δ
(
Y,h,h
(
x
))
,
(
Y,h,U
ρ
)
n
ρ
tion from
{
0
,
1
}
to
{
0
,
1
}
. Then for
h
≤
as long as
ρ
≤
k
−
2lg(1
/
)
.
We show the scheme presented in [23] in the manner of TBE as follows: Let
(
S
ltf
,F,F
−
1
) give a collection of (
n,
)-lossy trapdoor functions, and let (
S
abo
,G,
G
−
1
) give a collection of (
n,
)-ABO trapdoor functions having branches
B
λ
=
{
v
. We use the branch space as the tag space in the tag-based encryption
scheme.
0
,
1
}
