[ Pobierz całość w formacie PDF ]
a random bit c " {0, 1}. The challenger sets kc = ±t and k1-c to be a random element in Zp.
" A receives {Xi,b = ¾(²i,b, 1)}i"[1,n],b"{0,1}, as well as W = ¾(±, n + 1).
19
" A can adaptively make secret key queries for identities u " {0, 1}n. In response, A receives
{Ui(u)}i"[0,n+1] where
(u)
U0 = ¾(ru, 1) for a randomly chosen ru " Zp
Ui(u) = ¾(ru · ²i,1-ui, 1) for i = 1, . . . , n
n
(u)
Un+1 = ¾(± + ru · ²i,ui, n)
i=1
We require that for a particular identity u, A can only make a single key query for u.
" A can also adaptively make queries to Encode, Mult, Pair.
" A makes a challenge query on a set S, subject to the restriction that u " S for any u queried
/
in a secret key query. In response, A receives
n
Hdr = (¾(t, 1), ¾(t · ²i,vi, n))
v"S i=1
In addition, A receives K0 = ¾(k0, n + 1) and K1 = ¾(k1, n + 1).
" A can continue making secret key queries for identities u " S.
/
" A produces a guess c for c.
Now consider an algorithm B that plays the above game with A. Rather than choose values for
²i,b, ±, t, ru, k0, k1, algorithm B treats them as formal variables. B maintains a list
L = {(pj, ij, ¾j)}
where pj is a polynomial in the variables {²i,b}i"[1,n],b"{0,1}, ±, t, k0, k1, {ru}, the integer ij indexes
the groups, and ¾j is a string in {0, 1}m. The list is initialized with the tuples (²i,b, 1, ¾2i+b-1)
for randomly generated strings ¾2i+b-1 " {0, 1}m, as well as (±, n + 1, ¾2n+1) for a random string
¾2n+1 " {0, 1}m. Initially, L contains 2n + 1 entries.
The game starts with B giving A the tuple of strings {¾i}i"[1,2n+1]. Now, A is allowed to make
the following queries:
Encode(x, i): If x " Zp and 1 d" i d" n + 1, then B looks for a tuple (p, i, ¾) " L, where p is the
constant polynomial equal to x. If such a tuple exists, then B responds with ¾. Otherwise, B
generates a random string ¾ " {0, 1}m, adds the tuple (p, i, ¾) (again, where p is a constant
polynomial equal to x) to L,and responds with ¾.
Mult(¾k, ¾ , b): B looks for tuples (pk, ik, ¾k), (p , i , ¾ ) " L. If one or both tuples do not exist, then
B responds with ¥". If both tuples are found, but ik = i , then B responds with ¥". Otherwise,
B lets i a" ik = i , computes the polynomial p = pk +(-1)bp , and looks for a tuple (p, i, ¾) " L.
If the tuple is found, then B responds with ¾. Otherwise, B generates a random string ¾, adds
the tuple (p, i, ¾) to L, and resonds with ¾.
20
Pair(¾k, ¾ ): B looks for tuples (pk, ik, ¾k), (p , i , ¾ ) " L. If one or both tuples do not exist, then B
responds with ¥". If both tuples are found, but i a" ik + i > n + 1, then B responds with ¥".
Otherwise, B computes the polynomial p = pk · p , and looks for a tuple (p, i, ¾) " L. If the
tuple is found, then B responds with ¾. Otherwise, B generates a random string ¾, adds the
tuple (p, i, ¾) to L, and responds with ¾.
KeyGen(u): B creates a new formal variable ru. It adds the tuple (ru, 1, ¾) to L for a randomly
generated ¾ " {0, 1}m. It also adds tuples (ru²i,1-ui, 1, ¾i) for i = 1, . . . , n, where the ¾i are
n
generated at random in {0, 1}m. Finally, it adds the tuple (± + ru · ²i,ui, n, ¾) for another
i=1
randomly generated ¾ " {0, 1}m. B responds with the list of ¾ values generated in this step.
Enc(S): B creates new formal variables t, k0, k1. It adds several tuples to L:
n
(t, 1, ¾1) , (t · ²i,vi , n , ¾2) , (k0 , n + 1 , ¾3) , (k1 , n + 1 , ¾4)
v"S i=1
Where the ¾i are randomly generated. B gives A the strings ¾1, ¾2, ¾3, ¾4.
B can increase m arbitrarily, thus making strings ¾ hard to guess. Therefore, we can assume
without loss of generality that A only makes Mult and Pair queries on strings obtained from B.
After a polynomial number of queries, A returns a guess c " {0, 1}. Now, B chooses a random
c " {0, 1}. If also chooses random values for ²i,b, ±, t " Zp, ru. It also chooses a random k " Zp. B
sets kc = ±t and k1-c = k.
The simulation provided by B is perfect unless out choices for the variables ²i,b, ±, t, k0, k1 results
[ Pobierz całość w formacie PDF ]