Oblivious Transfer with Complex Attribute-Based Access Control - Information Security and Cryptology-ICISC 2010 - page 373

2 Preliminaries

Notation. We denote by κ the security parameter and by PPT the property of
an algorithm of running in probabilistic polynomial-time. A function negl ( · )is

negligible in κ if for every polynomial p ( · ) there exists a value N such that for

all n>N it holds that negl ( · ) < 1 /p ( n ).

2.1 Bilinear Maps

Let G, G T = p ,

where p is a large prime. Let g be a generator of G ,and e be an admissible
bilinear map: G

be two (multiplicative) cyclic groups such that | G | = | G T |

× G → G T , satisfying that (1) for all a, b ∈ Z p it holds that

e ( g a ,g b )= e ( g, g ) ab ;(2) e ( g, g ) = 1; and (3) it is eciently computable.

2.2 Complexity Assumptions

Definition 1. (Computational Di e-Hellman(CDH) Assumption.) Suppose a
challenger chooses a, b, c, z

Z p at random. The DBDH assumption is that no
polynomial-time adversary is to be able to distinguish the tuple ( g a ,g b ,g c ,e ( g, g ) abc )
from ( g a ,g b ,g c ,e ( g, g ) z )) with more than a negligible advantage.

∈

Definition 2. (Decision Bilinear Die-Hellman(DBDH) Assumption[6].) Sup-
pose a challenger chooses a, b, c, z Z p at random. The DBDH assump-

tion is that no polynomial-time adversary is to be able to distinguish the tu-
ple ( g a ,g b ,g c ,e ( g, g ) abc ) from ( g a ,g b ,g c ,e ( g, g ) z )) with more than a negligible
advantage.

∈

Definition 3. (q-Strong Die-Hellman(q-SDH) Assumption[4]). Suppose a
challenger chooses x Z p at random. The q -SDH assumption is that no

polynomial-time adversary is to be able to output a pair ( c, g 1 / ( x + c ) ) where c

∈

∈ Z p

from the tuple ( g, g x ,...,g x q ) with more than a negligible advantage.

2.3 Zero-Knowledge Proof

Throughout the paper, we use known techniques for proving statements about
discrete logarithms such as (1) proof of knowledge of a discrete logarithm modulo
a prime [30,16], (2) proof of knowledge of a pairing preimage [16], (3) proof of
the disjunction or conjunction of any ones of the previous [11,16]. According to
Cramer et al. [11], this class of zero-knowledge (ZK) proof systems (1)(2) can be
combined into ZK proof systems (3) for any disjunctive and conjunctive formula.
Furthermore, using the Fiat-Sahmir heuristic, this class of ZK proof systems can
be converted to non-interactive ZKs at no extra cost. We will use the notation,
for example PoK ( x, r ): y = g x h r y = g x [18] to denote a ZK proof of

knowledge of integers x and r such that both y = g x h r and y = g x hold. All
values not enclosed in ()'s are assumed to be known to the verifier.

{ ∧ }