Cryptography Reference
In-Depth Information
∈
Z
p
,wehave
e
(
u
a
,v
b
)=
e
(
u, v
)
ab
.
- bilinear: for all
u, v
∈
G
and all
a, b
- non-degeneracy:
e
(
g, g
)
=1
G
T
.
- computable: there is an ecient algorithm to compute
e
(
u, v
) for all
u, v
∈
G
.
2.1 The BDHI Assumption
We recall that the bilinear Die-Hellman inversion (BDHI) problem, denoted by
q
-BDHI, is defined [6] as follows: given the
q
+ 1 tuple (
g, g
x
,...,g
x
q
)
G
∗
)
q
+1
∈
(
as input, compute
e
(
g, g
)
1
/x
∈
G
T
. More formally, we explain this problem by
using the following BDHI function:
q
+1
bdhi:
G
→
G
T
(
g, g
x
,...,g
x
q
)
e
(
g, g
)
1
/x
→
We also use a predicate
bdhip(
g, g
x
,...,g
x
q
, T
):=
e
(
g, g
)
1
/x
=
T
to denote the corresponding
decisional
BDHI problem.
Definition 2.1.
We say that the (decisional)
(
t, q,
)
-
BDHI
assumption holds
in
G
if no
t
-time algorithm has advantage at least
in solving the (decisional)
q
-
BDHI
problem in
G
.
2.2 The Twin BDHI Assumption
We define the
twin
q
-BDHI function as
G
∗
)
2(
q
+1)
2
T
→
G
2bdhi:
(
(
g
1
,g
1
,...,g
x
1
;
g
2
,g
2
,...,g
y
2
)
(bdhi(
g
1
,g
1
,...,g
x
1
)
,
bdhi(
g
2
,g
2
,...,g
y
2
))
.
→
We also define a corresponding
twin
q
-BDHI predicate:
2bdhip(
g
1
,g
1
,...,g
x
1
, T
x
;
g
2
,g
2
,...,g
y
2
, T
y
):=
2bdhi(
g
1
,g
1
,...,g
x
1
;
g
2
,g
2
,...,g
y
2
)
?
=(
T
x
, T
y
)
.
The
twin
q
-BDHI assumption states that given random
g
1
,g
2
∈
G
∗
and
x, y
∈
Z
p
it is hard to compute 2bdhi(
g
1
,g
1
,...,g
x
1
;
g
2
,g
2
,...,g
y
2
). The
strong twin
q
-
BDHI assumption states that given random
g
1
,g
2
∈
G
∗
and
x, y
∈
Z
p
it is hard
to compute 2bdhi(
g
1
,g
1
,...,g
x
1
,g
2
,g
2
,...,g
y
2
), along with access to a decision
oracle for the predicate 2bdhip(
g
1
,g
1
,...,g
x
1
, ·
;
g
2
,g
2
,...,g
y
2
, ·
), which on input
(
T
x
, T
y
), returns 2bdhip(
g
1
,g
1
,...,g
x
1
, T
x
;
g
2
,g
2
,...,g
y
2
, T
y
).
We have the following result to address the relation between the BDHI as-
sumption and the strong twin BDHI assumption:
Search WWH ::
Custom Search