Delegatable pseudorandom functions and applications

Abstract

Techniques are provided for delegating evaluation of pseudorandom functions to a proxy. A delegator delegates evaluation of a pseudorandom function to a proxy, by providing a trapdoor to the proxy based on a secret key k and a predicate P using an algorithm T, wherein the predicate P defines a plurality of values for which the proxy will evaluate the pseudorandom function, wherein the plurality of values comprise a subset of a larger domain of values, and wherein the trapdoor provides an indication to the proxy of the plurality of values. A proxy evaluates a pseudorandom function delegated by a delegator by receiving a trapdoor from the delegator that provides an indication of a plurality of values to be evaluated, wherein the plurality of values comprise a subset of a larger domain of values; and evaluating an algorithm C on the trapdoor to obtain the pseudorandom function value for each of the plurality of values. The trapdoor can be provided to the proxy using a Gordreich, Goldwasser, Micali (GGM) binary tree representation.

Claims

1. An apparatus for delegating by a delegator evaluation of a pseudorandom function to a proxy, comprising: a memory; and at least one processing device, coupled to the memory, operative to: compute, using said at least one processing device, a trapdoor based on a secret key and a predicate, wherein said predicate defines a plurality of values for which the proxy is authorized to evaluate said pseudorandom function, wherein said plurality of values comprise a subset of a larger domain of values; and provide, using said at least one processing device, said trapdoor to said proxy for said proxy to evaluate said pseudorandom function on behalf of said delegator, wherein said trapdoor provides an indication to said proxy of said plurality of values for which the proxy is authorized to evaluate said pseudorandom function.

2. The apparatus of claim 1 wherein said pseudorandom function that is delegated to said proxy generates a pseudorandom function value for at least one of said plurality of values conforming to said predicate.

3. The apparatus of claim 1 wherein said pseudorandom function generates a pseudorandom function value for at least one value in said larger domain and wherein said pseudorandom function values for any value that is not within said plurality of values is unpredictable for said proxy.

4. The apparatus of claim 1 wherein said trapdoor is provided to said proxy using a Gordreich, Goldwasser, Micali (GGM) binary tree comprising a plurality of nodes that are labelled by a binary representation induced by said GGM tree.

5. The apparatus of claim 4 wherein labels of leaf nodes of said GGM tree comprise said larger domain and every leaf node of said GGM tree is associated with a pseudorandom function value for its label.

6. The apparatus of claim 5 wherein said trapdoor is represented by root nodes of one or more sub-trees in said GGM tree that cover a given range of said predicate and said proxy is authorized to evaluate, using said trapdoor, the pseudorandom function values for all leaves within one or more sub-trees.

7. The apparatus of claim 4 wherein said at least one processing device is further configured to determine one or more sub-trees in said GGM tree that cover a given range of said predicate.

8. The apparatus of claim 7 wherein said at least one processing device is further configured to determine two or more of second sub-trees in said GGM tree, wherein a number of said second sub-trees and a level in said GGM tree of root nodes of said second sub-trees depend only on a size of a given range of said predicate, and wherein the root nodes of said second sub-trees are descendants in said GGM tree of the root nodes of said minimum number of sub-trees.

9. The apparatus of claim 4 wherein said at least one processing device is further configured to determine at least two sub-trees in the GGM tree that cover a given range of said predicate, wherein at least two of said sub-trees are anchored on a same level of said GGM tree.

10. The apparatus of claim 4 wherein said plurality of nodes are further associated with pseudorandom values that are based on said binary representation, wherein said pseudorandom value of a given node of said plurality of nodes is based on recursively applying a pseudorandom generator on the pseudorandom value of a parent node of said given node, and wherein said pseudorandom generator is indexed by the label of said given node.

11. The apparatus of claim 10 wherein labels of leaf nodes of said GGM tree comprise said larger domain and said pseudorandom values of said leaf nodes comprise pseudorandom function values defined over said larger domain, and wherein the pseudorandom value of a given leaf node comprises a pseudorandom function value for the label of said given leaf node.

12. The apparatus of claim 4 wherein said trapdoor is represented by a leaf node in said GGM tree wherein said leaf node covers a given singleton range of said predicate.

13. The apparatus of claim 1 wherein said delegator comprises a trusted center and said proxy comprises a radio frequency identification reader and said delegation apparatus is performed for one or more of authentication and access control.

14. The apparatus of claim 1 wherein said delegator comprises a symmetric searchable encryption (SSE) client and said proxy comprises an SSE server and said delegation apparatus is performed to generate one or more query tokens.

15. The apparatus of claim 1 wherein said delegation comprises a key assignment mechanism for a broadcast encryption scheme.

16. An apparatus for evaluating by a proxy a pseudorandom function delegated by a delegator, comprising: a memory; and at least one processing device, coupled to the memory, operative to: receive, using said at least one processing device, a trapdoor from said delegator for said proxy to evaluate said pseudorandom function on behalf of said delegator, wherein said trapdoor provides an indication of a plurality of values for which said proxy is authorized to evaluate said pseudorandom function, wherein said plurality of values comprise a subset of a larger domain of values; and evaluate, using said at least one processing device, an algorithm on said trapdoor to obtain at least one pseudorandom function value for at least one of said plurality of values.

17. The apparatus of claim 16, wherein said algorithm using said trapdoor, executes a number of steps to compute said at least one pseudorandom function value for each of said plurality of values and terminates when said algorithm reaches a final state.

18. The apparatus of claim 16 wherein said pseudorandom function that is delegated to said proxy generates a pseudorandom function value for at least one of said plurality of values conforming to a predicate, wherein said predicate defines said plurality of values for which the proxy is authorized to evaluate said pseudorandom function.

19. The apparatus of claim 18 wherein said proxy can only infer information about said predicate using said trapdoor that is inferred directly by said generated pseudorandom function values.

20. The apparatus of claim 18 wherein said trapdoor is provided to said proxy using a Gordreich, Goldwasser, Micali (GGM) binary tree comprising a plurality of nodes that are labelled by a binary representation induced by said GGM tree.

21. The apparatus of claim 20 wherein labels of leaf nodes of said GGM tree comprise said larger domain and every leaf node of said GGM tree is associated with a pseudorandom function value for its label.

22. The apparatus of claim 21 wherein said trapdoor is represented by the root nodes of one or more sub-trees in said GGM tree that cover a given range of said predicate and said proxy is authorized to evaluate, using said trapdoor, the pseudorandom function values for all leaves within said one or more sub-trees.

23. The apparatus of claim 20 wherein said at least one processing device is further configured to determine one or more sub-trees in said GGM tree that cover a given range of said predicate.

24. The apparatus of claim 20 wherein said at least one processing device is further configured to determine at least two sub-trees in the GGM tree that cover a given range of said predicate, wherein at least two of said sub-trees are anchored on the same level of said GGM tree.

25. The apparatus of claim 20 wherein said plurality of nodes are further associated with pseudorandom values that are based on said binary representation, wherein said pseudorandom value of a given node of said plurality of nodes is based on recursively applying a pseudorandom generator on the pseudorandom value of a parent node of said given node, and wherein said pseudorandom generator is indexed by the label of said given node.

26. The apparatus of claim 25 wherein said trapdoor comprises a level and a pseudorandom value associated with a root node of one or more sub-trees in said GGM tree that cover a given range of said predicate, wherein said proxy is authorized to evaluate, using said trapdoor, the pseudorandom function values for all leaf nodes within said one or more sub-trees.

27. The apparatus of claim 25 wherein said trapdoor comprises a level and a pseudorandom value associated with a root node of two or more sub-trees in said GGM tree that cover a given range of said predicate, wherein a number of said sub-trees and a level in said GGM tree of the root nodes of said sub-trees depend only on a size of a given range of said predicate, and wherein said proxy is authorized to evaluate, using said trapdoor, the pseudorandom function values for all leaf nodes within said two or more sub-trees.

28. The apparatus of claim 16 wherein said pseudorandom function generates a pseudorandom function value for at least one value in said larger domain and wherein said pseudorandom function values for any value that is not within said plurality of values is unpredictable for said proxy.

29. The apparatus of claim 16 wherein said proxy can only infer information about said larger domain of values that are within said plurality of values using said trapdoor.

30. The apparatus of claim 16 wherein said delegator comprises a trusted center and said proxy comprises a radio frequency identification reader and said delegation apparatus is performed for one or more of authentication and access control.

31. The apparatus of claim 16 wherein said delegator comprises a symmetric searchable encryption (SSE) client and said proxy comprises an SSE server and said delegation apparatus is performed to generate one or more query tokens.

32. The apparatus of claim 16 wherein said delegation comprises a key assignment mechanism for a broadcast encryption scheme.

33. A method by a delegator for delegating evaluation of a pseudorandom function to a proxy, comprising: computing, using at least one processing device, a trapdoor based on a secret key and a predicate, wherein said predicate defines a plurality of values for which the proxy is authorized to evaluate said pseudorandom function, wherein said plurality of values comprise a subset of a larger domain of values; and providing, using said at least one processing device, said trapdoor to said proxy for said proxy to evaluate said pseudorandom function on behalf of said delegator, wherein said trapdoor provides an indication to said proxy of said plurality of values for which the proxy is authorized to evaluate said pseudorandom function.

34. A computer program product comprising a non-transitory machine-readable storage medium having encoded therein executable code of one or more software programs, wherein the one or more software programs when executed by a delegator for delegating evaluation of a pseudorandom function to a proxy perform the following steps: computing, using at least one processing device, a trapdoor based on a secret key and a predicate, wherein said predicate defines a plurality of values for which the proxy is authorized to evaluate said pseudorandom function, wherein said plurality of values comprise a subset of a larger domain of values; and providing, using said at least one processing device, said trapdoor to said proxy for said proxy to evaluate said pseudorandom function on behalf of said delegator, wherein said trapdoor provides an indication to said proxy of said plurality of values for which the proxy is authorized to evaluate said pseudorandom function.

35. A method by a proxy for evaluating a pseudorandom function delegated by a delegator, comprising: receiving, using at least one processing device, a trapdoor from said delegator for said proxy to evaluate said pseudorandom function on behalf of said delegator, wherein said trapdoor provides an indication of a plurality of values for which said proxy is authorized to evaluate said pseudorandom function, wherein said plurality of values comprise a subset of a larger domain of values; and evaluating, using said at least one processing device, an algorithm on said trapdoor to obtain at least one pseudorandom function value for at least one of said plurality of values.

36. A computer program product comprising a non-transitory machine-readable storage medium having encoded therein executable code of one or more software programs, wherein the one or more software programs when executed by a proxy for evaluating a pseudorandom function delegated by a delegator perform the following steps: receiving, using at least one processing device, a trapdoor from said delegator for said proxy to evaluate said pseudorandom function on behalf of said delegator, wherein said trapdoor provides an indication of a plurality of values for which said proxy is authorized to evaluate said pseudorandom function, wherein said plurality of values comprise a subset of a larger domain of values; and evaluating, using said at least one processing device, an algorithm on said trapdoor to obtain at least one pseudorandom function value for at least one of said plurality of values.

Description

BRIEF DESCRIPTION OF THE DRAWINGS

(1) FIG. 1 illustrates a delegator that delegates evaluation of pseudorandom functions to a proxy in accordance with aspects of the present invention;

(2) FIGS. 2 and 3 illustrate security games between attacker A and a challenger C indexed by parameter ;

(3) FIG. 4 illustrates a Gordreich, Goldwasser, Micali (GGM) binary tree on the PRF domain along with trapdoor information computed by aspects of the presented invention;

(4) FIGS. 5 and 6 illustrate exemplary pseudo code for the trapdoor generation algorithm T for best range cover and uniform range cover implementations, respectively;

(5) FIG. 7A illustrates a conventional Symmetric searchable encryption scheme between a client and a server;

(6) FIG. 7B illustrates a Symmetric searchable encryption scheme between a client and a server augmented with DPRFs in accordance with aspects of the present invention; and

(7) FIG. 8 shows one possible implementation of a given one of the processing devices of FIG. 1.

DETAILED DESCRIPTION

(8) The present invention provides methods and apparatus for delegating evaluation of pseudorandom functions to a proxy. Furthermore, aspects of the present invention provide a delegatable pseudorandom function (DPRF) cryptographic primitive that enables the delegation of the evaluation of a pseudorandom function (PRF) to an untrusted proxy according to a given predicate that defines the inputs on which the proxy will evaluate the PRF.

(9) Specifically, let F be a PRF family, and P a set of predicates, called the delegation policy, defined over the domain of F. A DPRF is a triplet (F,T,C) constructed with respect to P, that provides the elementary functionality shown in FIG. 1. For any secret key k and a predicate P, a delegator 110 computes a trapdoor via algorithm T, and is transmitted to a proxy 120. The latter then runs algorithm C on to finally derive exactly the set of PRF values V.sub.P={f.sub.k(x)|P(x)}, where f.sub.k, i.e., the PRF value on every input x satisfying predicate P, overall correctly enabling the evaluation of PRF f.sub.k subject to predicate P without explicit knowledge of secret key k (or even the input values A.sub.P={x|P(x))}).

(10) The above scheme is motivated by efficiency. As long as the trapdoor is sublinear in the size n=|{x|P(x)}| of delegated PRF values, the delegation is meaningful as the delegator 110 conserves resources (or otherwise the proxy 120 could be provided directly with the n PRF values in the delegated set V.sub.P={f.sub.k(x)|P(x)}).

(11) At the same time, the DPRF must retain the security properties of the underlying PRF, namely, (i) pseudorandomness for any value x conforming to the delegation predicate P, i.e., P(x), and (ii) unpredictability for any nonconforming value x such that P(x). In addition, a DPRF can optionally satisfy a policy privacy property that prevents the proxy 120 from inferring information about P or the delegated set {x|P(x)} from the trapdoor .

(12) An exemplary formal definitional framework is provided for the new primitive of DPRFs, capturing the above technical requirements. Correctness captures the ability of the proxy 120 to successfully evaluate the PRF on exactly those inputs specified by predicate P. Security captures the requirement that the delegation capabilities of the PRF do not compromise its core pseudorandomness property, but this condition goes beyond the standard security definition of PRFs since the pseudorandomness attacker may now adaptively query a trapdoor delegation oracle with policies of its choice.

(13) Equally important is also a policy privacy property that a DPRF may optionally satisfy, intuitively capturing the inability of a malicious proxy 120 to learn any (non-trivial) property about the delegation set A.sub.P={(x|P(x)} (that is not implied by set V.sub.P). The security notion postulates that any two policies P, P are indistinguishable provided that |A.sub.P|=|A.sub.P|, and no PRF queries are obtained in the symmetric difference of A.sub.P,A.sub.P (a necessary condition).

(14) GGM-Based Realization for Range Predicates

(15) Two efficient and secure DPRF constructions are provided for the case where the delegation policy contains predicates described by one-dimensional ranges. Range-based policy predicates is an interesting use case as many applications maintain an ordering over the PRF inputs and delegation rights are defined with respect to ranges of such inputs.

(16) A first DPRF scheme is referred to as a best range cover (BRC), and relies on the well-known Gordreich, Goldwasser, Micali (GGM) PRF family. See, e.g., O. Goldreich et al., How to Construct Random Functions, J. ACM, 33(4):792-807 (1986). This family defines a PRF based on the hierarchical application of any length-doubling pseudorandom generator (PRG) according to the structure induced by a tree, where input values are uniquely mapped to root-to-leaf paths. By leveraging the above characteristics, the disclosed BRC scheme features logarithmic delegation size in the number of values conforming to the policy predicate simply by having the trapdoor comprising a subset G.sub.P of PRG values that (almost optimally) cover the target range V.sub.P of PRF values.

(17) The disclosed BRC scheme may not satisfy policy privacy as the structure of intermediate PRG values in G.sub.P leaks information about predicate P. This motivates a second construction, referred to as uniform range cover (URC). This URC scheme augments BRC in a way that renders all trapdoors corresponding to ranges of the same size indistinguishable. This is achieved by having comprising a subset G.sub.P of PRG values that cover the target range V.sub.P of PRF values less optimally: G.sub.P contains PRG values that are descendants of those values in G.sub.P at a tree height that depends solely on |V.sub.P| (which by definition leaks to the adversary). More interestingly, by adopting the above change, URC retains both the asymptotic logarithmic communication complexity of BRC and its DPRF security, but it achieves a policy privacy notion appropriately relaxed to the current setting of range predicates. Inherently, no tree-based DPRF scheme can satisfy the initial version of policy privacy, thus a sufficient relaxation is employed, referred to as a union policy privacy.

(18) Main Applications

(19) Finally, the disclosed DPRF schemes, equipped with efficiency, security and policy privacy, lend themselves to new schemes that provide scalable solutions to a wide range of information security and applied cryptography settings that involve the controlled authorization of PRF-based computations. Generally, DPRFs are particularly useful in applications that rely on the evaluation of (secret) key-based cryptographic primitives on specific inputs (according to an underlying policy): Using a DPRF scheme then allows a cost-efficient, yet secure and private, key management for an untrusted proxy 120 who is otherwise capable in executing a particular computational task of interest.

(20) There are a number of applications in which DPRFs are useful, including authentication and access control in RFIDs, efficient batch querying in searchable encryption as well as broadcast encryption. Due to the underlying GGM building component, the disclosed DPRFs are extremely lightweight, as their practical implementation entails a few repeated applications of any efficient candidate instantiation of a PRG (e.g., HMAC or block ciphers).

(21) According to one aspect of the invention, delegatable PRFs (DPRFs) are provided. A definitional framework is provided for the new DPRF primitive, capturing properties such as efficiency, correctness, security and policy privacy, and also offering a relaxed union policy privacy that is arguably necessary for a wide DPRF class with range-based policies.

(22) According to another aspect of the invention, a framework is provided for constructing DPRF schemes for the important case where the delegation policy is governed by range predicates over inputs. The disclosed framework augments the generic GGM construction framework discussed above to provide two concrete DPRF schemes, namely schemes BRC and URC.

DEFINITIONS

(23) A pseudorandom function family (PRF) is a family of functions {f.sub.k:A.fwdarw.B|k} so that is efficiently samplable and all ,,A,B are indexed by a security parameter . The security property of a PRF is as follows: for any probabilistic polynomial-time (PPT) A running in time polynomial in it holds that
|Pr[==1 ]Pr[=1 ]|=negl(),
where negl denotes a negligible function and the probability above is taken over the coins of and the random variables k and R which are uniform over the domains and (A.fwdarw.B) respectively.

(24) Delegatable PRFs

(25) The notion of delegation for PRFs is defined with respect to a delegation policy , i.e. is a set of predicates defined over A, also indexed by , where each predicate P has an efficient public encoding, so that the set of elements in A that satisfy P, denoted as A.sub.P={xA|P(x)}, is efficiently derived.

(26) Definition 1 (Delegatable PRF) A triple (,T,C) is called a delegatable PRF (DPRF) with respect to policy provided it satisfies two properties, correctness and security, that are defined individually below.

(27) CorrectnessT is a PPT algorithm such that given a description of P and a key k, it outputs a trapdoor intended to be used along with the deterministic PT algorithm C for the computation of every element of A that satisfies the predicate P. For fixed P,k, the algorithm C can be considered as a function
C:St.sub.P,k.fwdarw.BSt.sub.P,k,
where St.sub.P,k is a set of states and the output C(s) is a pair that consists of a PRF value and a (new) state. The domain and range of C are augmented with a special value that will be used to denote the final state. C(s)=C.sub.L(s),C.sub.R(s) and define recursively the set of reachable states from a subset S of St.sub.P,c as
(S)S(C.sub.R(S)).

(28) The elements of the DPRF that are produced given an initial state s will be defined using the complete set of reachable states given s. A set S is -closed provided it holds (S)=S. For a singleton S={s}, (s) is written instead of ({s}), and (s) denotes the closure of s under , i.e., the fixpoint of the recursive equation for that also contains s.

(29) Definition 2 (Correctness) The DPRF scheme (,T,C) is correct for a policy if for every P,k:

(30) 1. {|T(P,k)}{}St.sub.P,k.

(31) 2. C.sub.R()= (termination condition).

(32) 3. There exists a polynomial p.sub.1 s.t. |A.sub.P|p.sub.1().

(33) 4. There exists a polynomial p.sub.2 s.t. for every T(P,k): [(i)] (a) () (termination guarantee). (b) |()|p.sub.2(|A.sub.P|) (efficiency). (c) {f.sub.k(x)|P(x)}=f.sub.k(A.sub.P)={C.sub.L(s)|s()} (completeness).

(34) According to the above exemplary conditions, all possible trapdoors corresponding to a certain policy predicate P are valid initial inputs for C. Starting from an arbitrary trapdoor for P, the proxy 120 can execute a number of steps, compute the DPRF image of every argument x that fulfills P), and terminate when it reaches the final state , where no further useful information can be derived.

(35) The condition 3 of correctness stems from the fact that the setting is considered where the proxy 120 wishes to eventually compute all the delegated PRF values. If this is not necessary (or desirable) for the DPRF application, the condition can be relaxed to any size of A.sub.P (including super-polynomial sizes). In this case, completeness (item 4(iii) above) will have to be relaxed as well since the proxy 120 cannot hope to be able to compute all the delegated PRF values. There are a number of ways to capture this by suitably modifying the way C works; for instance: (i) C may produce a random sample of f.sub.k(A.sub.P), (ii) C may be given the value x as input and return f.sub.k(x) provided that xA.sub.P, (iii) C may be given the lexicographic rank of an element x within A.sub.P and return f.sub.k(x).

(36) SecurityFor security, consider the case where the server is malicious and model DPRF security as a game G.sub.SEC.sup. 200, shown in FIG. 2, between an attacker and a challenger indexed by parameter . Due to the delegation capabilities of DPRFs the security game 200 is more elaborate than the definition of a plain PRF, as shown in FIG. 2.

(37) Definition 3 (Security) The DPRF scheme (,T,C) is secure for a policy if for any PPT , it holds that

(38) $\mathrm{Pr}\left[G_{\mathrm{SEC}}^A\left(1^{}\right)=1\right]\frac{1}{2}+\mathrm{neg}1\left(\right).$

(39) First, a delegatable PRF is a PRF. Specifically, any PRF attacker against f.sub.k can be turned into an attacker that wins the DPRF game described above. Fix some PPT and let be its non-negligible distinguishing advantage. There will be some polynomial q so that, for any , q() is an upper bound on the number of queries submitted to 's oracle by . Given such q and for fixed , hybrid oracle (f.sub.k/R).sub.j is defined for any j{0, . . . , q()} that operates as follows: (f.sub.k/R).sub.j responds as f.sub.k() in the first q()j queries and as R() in the last j queries. Taking such sequence of oracles into account, by triangular inequality, it follows that there exists some value j{0, . . . , q()1} for which the distinguishing probability will be at least /q() for to distinguish between two successive hybrid oracles (f.sub.k/R).sub.j and (f.sub.k/R).sub.j+1 when R is a random function. This follows from the fact that distinguishes the extreme hybrids f.sub.k() and R() with probability . is constructed as follows out of : plays the DPRF game and queries the DPRF function for the q(s)j first queries of . Then it submits the (j+1)-th query of as the challenge. Finally it completes the simulation of by answering any remaining queries of with random values drawn from B. It is easy to see that the distinguishing advantage of is /q(), i.e., non-negligible in .

(40) Second, observe that there is a trivial construction of a delegatable PRF from any PRF: Consider an ordering over A, e.g. the lexicographical order. For fixed P,k set T(P,k)=f.sub.k(x), . . . , f.sub.k(x.sub.n), where x.sub.i is the i-th element of A.sub.P according to . Given , the set of states is St.sub.P,k={,(2,), . . . , (n,),)} and the reconstruction function C can be simply defined to be a table-lookup. It is straightforward to show that (,T,C) is a DPRF as long as the underlying family is a PRF, since any delegation query can be interpreted as a series of polynomially many PRF queries.

(41) The existence of a trivial DPRF construction with respect to arbitrary policies from any given PRF motivates the disclosed primitive: Interesting DPRF constructions will be those that are communication efficient, i.e., they allow trapdoors with size that is sublinear in the number of elements that satisfy the corresponding policy predicate.

(42) (General) Policy Privacy

(43) Consider an additional policy privacy property that goes beyond the standard (D)PRF security and is quite relevant in the context of a delegatable PRF. In order to model this privacy condition, an indistinguishability game G.sub.PP.sup. 300 is used, carried out between an attacker and a challenger indexed by a security parameter . The game 300 proceeds as shown in FIG. 3.

(44) Definition 4 (Policy privacy)The DPRF scheme (,T,C) for a policy satisfies policy privacy if for any PPT , it holds that

(45) $\mathrm{Pr}\left[G_{\mathrm{SEC}}^A\left(1^{}\right)=1\right]\frac{1}{2}+\mathrm{neg}1\left(\right).$

(46) The above definition suggests that the trapdoor that corresponds to a certain policy predicate hides the predicate itself, at least among all policy predicates that enable the same number of elements and when the adversary does not know the PRF value of any element that satisfies one of them but not the other. Observe that all the restrictions stated are necessary: if |A.sub.P.sub.0||A.sub.P.sub.1|, then the adversary can distinguish P.sub.0 from P.sub.1 by counting the number of new PRF values it computes starting from state * and ending in . In addition, if the adversary learns any PRF value of an argument x within A.sub.P.sub.0A.sub.P.sub.1, either by making a PRF query or a delegation query, then it can quess b by computing {C.sub.L(s)|s()} and running the equality test C.sub.L(s)f.sub.k(x) at each execution step.

(47) It is submitted that even though desirable, the above property conflicts with efficiency (sublinear trapdoors) for a wide class of schemes. This will motivate relaxing the property as discussed below.

(48) Assume that the policy predicates are ranges [a,b] that lie in an interval [0,2.sup.1]. Then, no efficient and policy private DPRF scheme exists, if the trapdoor generation algorithm T(P,k) is deterministic and public and the delegated computation is tree-wise, i.e., for each range the trapdoor is a specific array of keys that enable in a deterministic way the calculation of the final set of values through a tree-like derivation. Indeed, for every 0<jba the delegated computation of the intersection [a+j,b] must be identical for [a,b] and [a+j,b+j]. Otherwise, an adversary can make PRF queries for all the values in [a+j,b] and, since it knows the way that each unique trapdoor of [a,b] and [a+j,b+j] computes the PRF values of the range [a+j,b], can thus distinguish the two range predicates by making the corresponding equality tests. By induction, this implies that for any j<ab, in the trapdoor of [a,b] there exist keys d.sub.0, . . . , d.sub.j that allow the computation of f.sub.k(a), . . . , f.sub.k(a+j) respectively. Thus, the size of the trapdoor of the range [a,b] consists of r=ba+1=#[a,b] keys which means that the DPRF cannot be efficient (i.e., delegate the range with a trapdoor size less than the set of values being delegated).

(49) The above argument suggests that if policy privacy is to be attained, trapdoors are needed at least as long as the delegated values. However, the trivial construction for ranges, i.e., when the trapdoor of [a,b] is the f.sub.k(a),f.sub.k(a+1), . . . , f.sub.k(b) does not satisfy policy privacy. For instance, when delegating [1,3] and [3,5] the attacker can easily distinguish them by obtaining the value f.sub.t(3) (it belongs in the intersection hence the attacker is allowed to have it) and checking its location within the trapdoor vector. Nevertheless, arranging the PRF values of [a,b] as so that f.sub.k(x) is placed in position x mod(r) is a solution that works. Policy privacy follows from the fact that elements that belong in two overlapping ranges will be placed in the same fixed location in the two corresponding vector trapdoors, as shown below for exemplary ranges [0, 3], [1, 4], [2, 5], [3, 6], [4, 7] of size 4:

(50) TABLE-US-00001 f.sub.k(0) f.sub.k(1) f.sub.k(2) f.sub.k(3) f.sub.k(4) f.sub.k(1) f.sub.k(2) f.sub.k(3) f.sub.k(4) f.sub.k(5) f.sub.k(2) f.sub.k(3) f.sub.k(4) f.sub.k(5) f.sub.k(6) f.sub.k(3) f.sub.k(4) f.sub.k(5) f.sub.k(6) f.sub.k(7)

(51) Efficient DPRFs are obtained out of tree-based PRFs where the values computed are at the leaves of a full binary tree, and the policy predicates are ranges covered by proper subtrees. In this case, even allowing a probabilistic trapdoor generator does not suffice to provide policy privacy for a very efficient scheme. To see this, let [a,b] be a range of size and be a trapdoor for [a,b] of size g(r)O(log.sup.c r), i.e., g(r) is polylogarithmic in r, hence also in . By the Pigeonhole principle, there exists a delegation key y in that computes all the values corresponding to a set T[a,b] of size at least r/g(r), that is, a subtree T of depth at least dlog(r)log(g(r))=(1). Assuming without loss of generality that r/g(r) is an integer, the latter implies that there exists a value x[a,b] with a zero suffix of length d that is computed by this key y. Since, there are g(r) such possible values x[a,b], an adversary has significant probability 1/g(r) of guessing x. Then it can make a query x, receive f.sub.k(x) and submit as the challenge the two policies P.sub.0=[a,b] and P.sub.1=[x,b+(xa)]. After it receives the challenge trapdoor *, it can locate all keys that correspond to subtrees of size d and check if there is minimum leaf value (an all-zero path) in some of these subtrees that equals to f.sub.k(x). Then, the adversary can distinguish effectively P.sub.0,P.sub.1 since x cannot be covered by any subtree of size d in a trapdoor for [a+x,b+(xa)]. This argument can be extended to more general tree-like delegation schemes.

(52) Union Policy Privacy

(53) Under the notion of union policy privacy, the adversary is restricted from making queries in the intersection of the challenge policy predicates (but is allowed to query at arbitrary locations outside the targeted policy set). This property is modeled by a game G.sub.UPP.sup.A(1.sup.) that proceeds identically as G.sub.PP(1.sup.) but terminates with 1 provided that all the following relaxed conditions are met: b={tilde over (b)}, |A.sub.P.sub.0|=|A.sub.P.sub.1|, A.sub.P.sub.0A.sub.P.sub.1, aL.sub.que:a.Math.(A.sub.P.sub.0A.sub.P.sub.1) and ^PL.sub.pol:A.sub.P(A.sub.P.sub.0A.sub.P.sub.1)=. For policies consisting of disjoint predicates, games G.sub.PP(1.sup.) and G.sub.UPP(1.sup.) are equivalent.

Constructions

(54) DPRF schemes are now presented for range policy predicates. In a section entitled The BRC Construction, a first construction is described, called best range cover (BRC), which satisfies the correctness and security properties of DPRFs, achieving trapdoor size logarithmic in the range size. However, BRC lacks the policy privacy property. In a section entitled The URC Construction. the BRC is built upon to obtain a policy-private DPRF scheme, called uniform range cover (URC), that retains the trapdoor size complexity of BRC.

(55) It is noted that both of the following constructions operate also in the special case where the policy predicate specifies a singleton set of values over which the evaluation of a pseudorandom function is delegated, as would be apparent to a person of ordinary skill in the art. In some instantiations of these constructions for this use case, a trapdoor may degenerate to the pseudorandom function value computed over the actual singleton value specified by the corresponding singleton policy predicate. Therefore, in what follows, constructions for policy predicates specifying ranges of two or more values are described.

(56) BRC Construction

(57) Let G:{0,1}.sup..fwdarw.{0,1}.sup.2 be a pseudorandom generator and G.sub.0(k),G.sub.1(k) be the first and second half of the string G(k), where the specification of G is public and k is a secret random seed. The GGM pseudorandom function family is defined as ={f.sub.k:{0,1}.sup.n.fwdarw.{0,1}.sup.}.sub.k{0,1}.sub., such that f.sub.k(x.sub.n-1, . . . x.sub.0)=G.sub.x.sub.0( . . . (G.sub.x.sub.n-1(k))), where n is polynomial in and x.sub.n-1 . . . x.sub.0 is the input bitstring of size n.

(58) FIG. 4 illustrates a GGM binary tree 400 on the PRF domain with 4 levels, along with trapdoor information computed by aspects of the presented invention. The leaves in FIG. 4 are labeled with a decimal number from 0 to 15, sorted in ascending order. Every edge is labeled with 0 (1) if it connects a left (resp. right) child. Every internal node is labeled with the binary string determined by the labels of the edges along the path from the root to this node. Suppose that the PRF domain is (0,1).sup.4. Then, the PRF value of 0010 is f.sub.k(0010)=G.sub.0(G.sub.1(G.sub.0(G.sub.0(k)))). Observe that the composition of G is performed according to the edge labels in the path from the root to leaf 2=(0010).sub.2, selecting the first (second) half of the output of G when the label of the visited edge is 0 (resp. 1). Based on the above, the binary representation of the leaf labels constitute the PRF domain, and every leaf is associated with the PRF value of its label.

(59) Every internal node of the GGM tree can be associated with a partial PRF value, by performing the composition of G as determined by the path from the root to that node. For example, node 00 in FIG. 4 is associated with partial PRF G.sub.0(G.sub.0(k)). Henceforth, for simplicity, f.sub.k(x.sub.n-1 . . . x.sub.j) denotes the partial PRF G.sub.x.sub.j( . . . (G.sub.x.sub.n-1(k))). Observe that if a party has the partial PRF f.sub.k(x.sub.n-1 . . . x.sub.j), then it can compute the PRF values of all 2.sup.j inputs that have prefix x.sub.n-1 . . . x.sub.j, simply by following a DFS traversal in the subtree with root x.sub.n-1 . . . x.sub.j and composing with seed f.sub.k(x.sub.n-1 . . . x.sub.j). In one example, using the partial PRF value at node 00, the PRF values of the inputs in (decimal) range [0,3] can be derived as f.sub.k(0000)=G.sub.0(G.sub.0(f.sub.k(00))), f.sub.k(0001)=G.sub.1(G.sub.0(f.sub.k(00))), f.sub.k(0010)=G.sub.0(G.sub.1(f.sub.k(00))), and f.sub.k(0011)=G.sub.1(G.sub.1(f.sub.k(00))).

(60) For any range [a,b] of leaf labels, there is a (non-unique) set of subtrees in the GGM tree that cover exactly the corresponding leaves. For instance, [2,7] is covered by the subtrees rooted at nodes 001 and 01 (colored in grey). As indicated above, a party having the partial PRF values of these subtree roots and the subtree depths, it can derive all the PRF values of the leaves with labels in [a,b]. In the current example, having (f.sub.k(001),1) and (f.sub.k(01),2), it can derive the PRF values of the leaves with labels in [2,7]. The first construction is based on the above observations. In particular, given a range policy predicate [a,b] with size |A.sub.P|=ba+1, it finds the minimum number of subtrees that cover [a,b], which is similar to finding the canonical subsets for 1-dimensional range queries. As such, this scheme is referred to as best range cover (BRC).

(61) The BRC DPRF construction is a triplet (,T,C), where F is the GGM PRF family described above with tree depth n. The delegation policy is ={([a,b]|0a<ba+.sup.2.sup.n1}, where is a constant integer.

(62) FIG. 5 illustrates exemplary pseudo code 500 for the trapdoor generation algorithm T of BRC. This algorithm takes as input secret key k and a range predicate [a,b]. It outputs a delegation trapdoor that enables the computation of f.sub.k(x) for every x whose decimal representation is in [a,b] (i.e., the PRF values of the leaves in the GGM tree with labels in [a,b]). T initially finds the first bit in which a and b differ (Line 2), which determines the common path from the root to leaves a and b. Suppose that this common path ends at node u. T then traverses the left and right subtree of u separately (Lines 3-10 and 1-18, respectively). The left traversal is described and the right one is performed symmetrically. T continues the path from the left child of u, denoted by v, to a. It checks whether a is the leftmost leaf of v's subtree. In this case the PRF value of v is included in along with the depth of v's subtree, and the traversal terminates (Lines 3-4). Otherwise, it includes the PRF value of the right child of v and the depth of the subtree rooted at that child, and continues the traversal in the left child of v iteratively (Lines 5-10).

(63) In the example of FIG. 4, for input [2,7], T outputs trapdoor =(f.sub.k(001),1),(f.sub.k(01),2. By its description, it can be seen that the algorithm of FIG. 5 covers the input range with maximal subtrees. However, there is one exception; if the input range is exactly covered by a single subtree (e.g., [4,7]), then T covers it with two subtrees (rooted at 010 and 011, respectively). In general, T in BRC covers the input range with at least two subtrees.

(64) The PRF computation algorithm C of BRC is now described. For fixed P=[a,b] of size r and key k, the set of states are defined as St.sub.P,k={(,(1,), . . . , (r1,),}, where =(y.sub.1,d.sub.1), . . . , (y.sub.m,d.sub.m) is the trapdoor produced by algorithm T. Note that, every y value corresponds to a partial PRF value associated with the root of a GGM subtree. Therefore, there is a natural ordering of PRF values for a given , starting from the leftmost leaf of the subtree of y.sub.1 to the rightmost leaf of the subtree of y.sub.m. Note that this order is not necessarily the same as the order of the leaves in the GGM tree. Starting from the PRF value of the leftmost leaf of the y.sub.1 subtree, C computes in every next step the PRF value of the next leaf in the ordering discussed above. Specifically, C starts with state and computes C()=G.sub.0( . . . (G.sub.0(y.sub.1))),(1,), where the composition is performed d.sub.1 times. Next, given state (i,), C locates the unique subtree that covers the (i+1)-th leaf x in the ordering of . Specifically, it finds the pair (y.sub.i,d.sub.i) in , where t is such that .sub.=1.sup.t-12.sup.d.sup.i<.sub.=1.sup.t2.sup.d.sup.. Then, the suffix x.sub.d.sub.t . . . x.sub.0 is the binary representation of i.sub.=1.sup.t-12.sup.d.sup.[0,2.sup.d.sup.t1]. Given this suffix, C can compute

(65) $f_k\left(x\right)=G_{x_0}\left(\mathrm{.Math.}\left(G_{x_{d_t}}\left(y_i\right)\right)\right)$
and output

(66) $C\left(\left(i,\right)\right)=.Math.G_{x_0}\left(\mathrm{.Math.}\left(G_{x_{d_t}}\left(y_i\right)\right)\right),\left(i+1,\right).Math..$
Note that, for input state (r1,), C outputs C((r1,))=, G.sub.1( . . . G.sub.1(y.sub.m))),, where the composition is performed d.sub.m times.

(67) In the example of FIG. 4, the trapdoor for range [2,14] is (f.sub.k(01),2),(f.sub.k(001),1),(f.sub.k(10),2),(f.sub.k(110),2),(f.sub.k(1110),0). Algorithm C computes the PRF values for leaves 4, 5, 6, 7, 2, 3, 8, 9, 10, 11, 12, 13, 14 in this order, i.e.,
C()=G.sub.0(G.sub.0(f.sub.k(01))),(1,)=f.sub.k(0100),(1,).fwdarw.
C((1,))=G.sub.1(G.sub.0(f.sub.k(01))),(2,)=f.sub.k(0101),(2,).fwdarw.

C((12,))=f.sub.k(1110),.

(68) Based on the above description, some partial PRF values are computed multiple times in C, e.g., f.sub.k(011) is computed twice; once during calculating f.sub.k(0110) and once for f.sub.k(0111). Note that this can be easily avoided by employing an external data structure of size O(r); every PRF value is computed once, stored in the data structure, and retrieved in a next step if necessary. In this manner, the computational cost of C can become O(r), since one PRF value is computed for every node in the subtrees covering the range (of size r).

(69) The correctness of BRC is stated in the following theorem.

(70) Theorem 1 The BRC DPRF construction (,T,C) with respect to delegation policy ={[a,b]0a<ba+.sup.2.sup.n1}, where n is the depth of the underlying GGM tree, is a constant integer, and .sup. is the maximum range size, is correct.

(71) The trapdoor size complexity in BRC is now discussed. Let V.sub.1, V.sub.2 be the sets of arguments of the PRF values computed by Lines 3-10 and 11-18 of algorithm T, respectively. Then, |V.sub.1|+|V.sub.2|=r.Math.|V.sub.1| is analyzed and the analysis for V.sub.2 is similar. Observe that, in every step in Lines 3-10, the algorithm covers more than |V.sub.1|/2 values of V.sub.1 with a maximal subtree of the sub-range defined by V.sub.1. Iteratively, this means that the algorithm needs no more than log(r) maximal subtrees to cover the entire sub-range of V.sub.1. Consequently, the total number of elements in is O(log(r)).

(72) BRC does not satisfy policy privacy, even for non-intersecting policy predicates, as shown in FIG. 4. Consider ranges [2,7] and [9,14], both with size 6. The trapdoors generated for these ranges are ((f.sub.k(001),1),(f.sub.k(01),2) and (f.sub.k(101),1),(f.sub.k(1001),0),(f.sub.k(110),1),(f.sub.k(1110),0), respectively. Clearly, these trapdoors are distinguishable due to their different sizes. This motivates the second DPRF construction presented in the next section.

(73) URC Construction

(74) Consider again the ranges [2,7] and [9,14], for which BRC generates two distinguishable trapdoors, ((f.sub.k(001),1), (f.sub.k(01),2) and (f.sub.k(101),1),(f.sub.k(1001),0), (f.sub.k(110),1), (f.sub.k(1110),0), respectively. Instead of computing the trapdoor of [2,7] as above, assume that an alternative trapdoor is generated equal to

(75) (f.sub.k(010),1),(f.sub.k(0010),0),(f.sub.k(011),1),(f.sub.k(0011),0)

(76) Observe that this trapdoor appears to be indistinguishable to that of [9,14]; the two trapdoors have the same number of elements, the first parts of their elements are all partial PRFs, whereas their second pans (i.e., the depths) are pairwise equal. This suggests that, policy privacy could be achieved, if a trapdoor algorithm T is devised such that, for any range predicate of a fixed size r, it always generates a trapdoor with a fixed number of elements and a fixed sequence of depths. More simply stated, the algorithm should produce uniform trapdoors for ranges of the same size. The challenge is to design such an algorithm retaining the logarithmic trapdoor size of BRC. Next, the second DPRF construction is presented, called uniform range cover (URC), which enjoys the efficiency of BRC and the union policy privacy property.

(77) URC builds upon BRC. In particular, URC starts by producing a trapdoor as in BRC, and then modifies it to generate a uniform trapdoor for the given range r. Recall that a trapdoor in BRC is a sequence of elements, where the first part is a (full or partial) PRF value, and the second is a depth value. Moreover, the depths have some useful structure, referred to as decomposition, formalized as follows:

(78) Definition 5 Let r be an integer greater than 1. A pair of non-negative integral sequences D=((k.sub.1, . . . , k.sub.c), (l.sub.1, . . . , l.sub.d)) is called a decomposition of r if the following hold: 1. .sub.i=1.sup.c2.sup.k.sup.i+.sub.j=1.sup.d2.sup.l.sup.j=r 2. k.sub.1> . . . >k.sub.c and l.sub.1> . . . >l.sub.d

(79) A decomposition of r D=((k.sub.1, . . . , k),(l.sub.1, . . . , l.sub.d)) is a worst-case decomposition (w.c.d.) of r if it is of maximum size, i.e., for every decomposition of r D=((k.sub.1, . . . , k.sub.c), (l.sub.1, . . . , l.sub.d)), c+dc+d. M.sub.Dmax{k.sub.1,l.sub.1} is defined as the maximum integer that appears in D.

(80) By the description of algorithm T in BRC, for fixed range size r, the depths in the trapdoor can be separated into two sequences that form a decomposition of r. Each sequence corresponds to a set of full binary subtrees of decreasing size that cover leaves in the range predicate. The usage of the worst case decomposition will become clear soon.

(81) The following lemma shows that the maximum integer that appears in any decomposition of r and, hence, the maximum depth of a subtree in a cover of a range of size r, can have just one of two consecutive values that depend only on r.

(82) Lemma 1 Let D=((k.sub.1, . . . , k.sub.c),(l.sub.1, . . . , l.sub.d)) be a decomposition of r. Define B(r)log(r+22. Then M.sub.D{B(r),B(r)+1}. In addition, if M.sub.D=B(r)+1 then the second largest value is less than M.sub.D.

(83) By Lemma 1, the trapdoor that is generated by BRC for a range P=[a,b] of size |A.sub.P|=r, even if this trapdoor corresponds to a w.c.d. of r, consists of at most |{0, . . . , B(r)}|+|{0, . . . , B(r)+1}|=2B(r)+3 pairs. Hence, the trapdoor size is O(log(r)), which complies with the bound described in the BRC Section. Moreover, since |A.sub.P|.sup., every trapdoor has no more than 2log(.sup.+2)1 pairs.

(84) Observe that two trapdoors that correspond to the same w.c.d. (i.e., the two sequences in the decomposition are identical pairwise) appear indistinguishable. Moreover, it can be shown that a trapdoor following a w.c.d. retains the logarithmic size in r. Therefore, the trapdoor algorithm T in URC employs a converter that takes as input a BRC trapdoor, and produces an alternative trapdoor that complies with a fixed w.c.d.

(85) Theorem 2 Let D=((k.sub.1, . . . , k.sub.c),(l.sub.1, . . . , l.sub.d)) be a decomposition of r. Then all the elements in {0, . . . , M.sub.D} appear in D iff D is a w.c.d. of r.

(86) A consequence of Theorem 2 and Lemma 1 is that, for every integer r>1, a w.c.d. of r is a proper rearrangement of the integers that appear in the w.c.d. r where the first sequence is (B(r), . . . , 0) and the second sequence is the remaining integers in the decomposition in decreasing order. This unique w.c.d. is referred to as a uniform decomposition of r. The main idea in URC is to always generate a trapdoor that complies with the uniform decomposition of r.

(87) FIG. 6 illustrates exemplary pseudo code 600 for the algorithm T in URC. The process starts with invoking the T algorithm of BRC to get an initial trapdoor (Line 1). Let D be the decomposition implied by (Line 2). The loop in Lines 3-5 utilizes Theorem 2 and works as follows. It finds the highest depth x that does not exist in D, and splits the partial PRF value y, in the rightmost pair in with depth x+1, producing two new partial PRF values with depth x, i.e., y.sub.i.sup.0=G.sub.0(y.sub.i) and y.sub.i.sup.1=G.sub.1(y.sub.i) (Line 4). Note that these values correspond to the two children of the subtree of y.sub.i. Thus, if element (y.sub.i,x+1) is substituted by (y.sub.i.sup.0,x),(y.sub.i.sup.1,x) in , then the trapdoor can still produce the same leaf PRF values as before. However, at all times the sequence of depths in should form a decomposition. Hence, after removing (y.sub.i,x+1), (y.sub.i.sup.0,x) is inserted in the left pair sequence and (y.sub.i.sup.1,x) in the right pair sequence of (Line 5). Upon termination of the loop, all the values in {0, . . . , M.sub.D} appear in D and, thus, a w.c.d. is reached according to Theorem 2. The process concludes, after properly re-arranging the elements of , such that they comply with the unique uniform decomposition of (Line 7). This is done deterministically, by filling the missing depths from {0, . . . , B(r)} in the left sequence with the unique appropriate pair that exists (by Theorem 2) in the right sequence.

(88) In the running example, for the range [2,7], the T algorithm in URC converts the original token retrieved by the trapdoor algorithm of BRC, =(f.sub.k(001),1),(f.sub.k(01),2), as follows (a newly inserted element to the left sequence is underlined, and a newly inserted element to the right sequence is depicted as bold):

(89) $\begin{array}{c}\left(\left(f_k\left(001\right),1\right),\left(f_k\left(01\right),2\right)\right)\\ \\ \left(\underset{\_}{\left(f_k\left(0010\right),0\right)},\left(f_k\left(01\right),2\right),\left(f_k\left(0011\right),0\right)\right)\\ \\ \left(\underset{\_}{\left(f_k\left(010\right),1\right)},\left(f_k\left(0010\right),0\right),\left(f_k\left(011\right),1\right),\left(f_k\left(0011\right),0\right)\right)\end{array}$

(90) The C algorithm of URC is identical to BRC, because the trapdoor in URC has exactly the format expected by this algorithm, i.e., pairs of PRF values corresponding to GGM subtrees along with their depths. Moreover, during the evolution of the initial BRC trapdoor into one of uniform decomposition in the T algorithm of URC, a partial PRF value y is substituted by two new PRF values that can generate the same leaf PRF values as y. As such, the correctness of the BRC scheme is inherited in URC. Finally, due to Lemma 1, the size of a w.c.d. (and, hence, also a uniform decomposition) of r is O(log(r)), which means that the trapdoor size in URC is also O(log(r)).

(91) Security

(92) The security of the BRC and URC constructions are now addressed. The following discussion relies on the security of the pseudorandom generator of the underlying GGM construction. However, DPRFs entail a more involved security game than GGM and, hence, the constructions require a more complex discussion. The reason is that, contrary to the case of GGM where the adversary obtains only leaf PRFs, the adversary in a DPRF can obtain also partial PRF values in the GGM tree through the trapdoors.

(93) Note that the formation of a trapdoor (which is independent of k) for a range predicate P of size r is deterministic and public in both BRC and URC. Thus, when querying the oracle in the security game, the adversary can map the partial or full PRF values appearing in for a selected P to subtrees in the GGM tree. This implies that it can reduce its delegation queries to prefixes for strings in (0,1).sup.n, where n is the depth of the GGM tree. Hence, any queried prefix of the adversary is denoted as x.sub.n-1 . . . x.sub.t, where the maximum value of t depends on the maximum possible range size .sup.. Since the size of every exemplary trapdoor is O(log()), a PPT adversary makes polynomially many such queries. The formation of a trapdoor does not play any role in the security of a DPRF scheme, since the challenge will always be a single PRF value. Therefore, there will be no separation in discussing the security of the BRC and the URC constructions.

(94) The security property of the DPRF schemes are addressed by ensuring and leveraging the security of two special cases. First, consider the case that the adversary is non-adaptive, i.e., it poses all its queries in advance.

(95) Lemma 2 The BRC and URC DPRF schemes with depth n and maximum range size .sup., are secure against PPT adversaries that make all their queries, even the challenge query, non-adaptively.

(96) The above lemma is used to address the security of a special category of DPRF schemes, where the maximum range size is at least half of [0,2.sup.n1], which represents the biggest interval where range predicates are defined.

(97) Lemma 3 The BRC and URC DPRF schemes with depth n and maximum range size .sup. are secure if 2.sup.n-1.sup.<2.sup.n.

(98) Theorem 3 The BRC and URC DPRF schemes with depth n and maximum range size .sup. are secure.

(99) Policy Privacy

(100) This section analyzes the policy privacy of URC. As indicated above, URC cannot satisfy the general policy privacy property, because it is efficient. In a toy example, for challenge ranges [2,5] and [4,7], the trapdoors will contain PRF values corresponding to subtrees covering the ranges as [2,3], {4}, {5} and [4,5], {6}, {7}, respectively. Therefore, the adversary can issue query for leaf 4 and receive a PRF value y. Having (y.sub.1,1), (y.sub.2,0), (y.sub.3,0) as challenge trapdoor, it can check whether y.sub.2=y, which happens only when [2,5] was chosen by the challenger.

(101) Nevertheless, it can be shown that URC achieves union policy privacy. In the union policy privacy game, the adversary cannot obtain a PRF value for a leaf in the intersection of the challenge ranges, i.e., for 4 and 5. This prevents the adversary from launching the attack described above.

(102) Theorem 4 The URC scheme with depth n and maximum range size .sup. is a DPRF scheme with union policy privacy.

Extensions

(103) Multi-Instance DPRFs

(104) Consider a multi-instance version of delegatable PRFs. In the multi-instance version, there is a sequence of independent PRF instances from a PRF family {f.sub.k:A.fwdarw.B|k} that should simultaneously delegate following a certain policy. The corresponding correctness condition for a multi-instance PDRF is described.

(105) A triple (,T,C) is a multi-instance DPRF (MI-DPRF) with respect to policy if it satisfies a corresponding notion of correctness defined as follows. Let n be an integer polynomial in . T is a PPT algorithm such that given a description of P=(P.sub.1, . . . , P.sub.n) and a sequence of keys K=(k.sub.1, . . . , k.sub.n), outputs a trapdoor (dk.sub.1, . . . , dk.sub.n,). For every i, the reconstruction algorithm C and the correctness conditions follow the lines of the respective definition of DPRFs, instantiated for pair P.sub.i,k.sub.i. The only difference is that now the delegation of evaluations of an instance of the PRF family is facilitated by an additional individual delegation key dk.sub.i, which becomes part of the state.

(106) Formally, C can be considered as a function
C:St.sub.P.sub.i.sub.,k.sub.i.fwdarw.BSt.sub.P.sub.i.sub.,k.sub.i,
where St.sub.P.sub.i.sub.,k.sub.i is a set of states and the output C(s)=C.sub.L(s),C.sub.R(s) is a pair consisted of a PRF value and a state in St.sub.P.sub.i.sub.,k.sub.i. The set of reachable states (S) from subset SSt.sub.P.sub.i.sub.,k.sub.i is defined as previously.

(107) Definition 6 (Correctness, MI-DPRF) The DPRF scheme (,T,C) is correct for a policy if for every P,K and for every i[n]: 1. {(dk.sub.i,)|(dk.sub.1, . . . , dk.sub.n,)T(P,K)}{}St.sub.P.sub.i.sub.,k.sub.i. 2. C.sub.R()=. 3. There exists a polynomial p.sub.i s.t. |A.sub.P.sub.i|p.sub.i(). 4. There exists a polynomial q.sub.i s.t. for every (dk.sub.1, . . . , dk.sub.n,)(P,K): (a) ((dk.sub.i,)). (b) |((dk.sub.i,))|q.sub.i(|A.sub.P.sub.i|). (c) {f.sub.k.sub.i(x)|P.sub.i(x)}=f.sub.k.sub.i(A.sub.P.sub.i)={C.sub.L(s)|s((dk.sub.i,))}.

(108) The security definition of MI-DPRFs follows directly from the corresponding definition of DPRF security, by extending the latter in the obvious way. In the security game, the adversary has adaptive access to many instances of DPRFs while receiving a challenge from a particular instance of its choice. The restrictions on the challenge phase are straightforward.

(109) Generic Classes of DPRFs

(110) Consider two generic classes of DPRFs which by construction define corresponding general design frameworks for implementing DPRFs.

(111) Tree-like DPRFsIn a tree-like DPRF, the trapdoor generation algorithm T(P,k) is deterministic and public and the delegated computation is tree-wise, i.e., for each range the trapdoor is a specific array of keys that enable in a deterministic way the calculation of the final set of values through a tree-like derivation.

(112) Algebraic singleton-range multiple-instance (MI)-DPRFsIn an algebraic singleton-range MI-DPRF the policy predicates are singleton sets. Here, elliptic curve groups for which a bilinear map can be defined are employed. These MI-DPRFs have the following general form. Their domain is arbitrary, in which case assume the existence of a hash function H:{0,1}.fwdarw. and encode the input as an element of . Then the MI-DPRF's are based on a polynomial Q defined over a set of variables . Assuming that n=|| the secret-key of the MI-DPRF will be a random vector over n-size vector k in integers modulo p. The pseudorandom function determined by the DPRF are generally defined as follows:
F.sub.k(a)=e(H(a),g).sup.Q(k).

(113) Given the above, it is worth observing that in the multiple-instance DPRF setting it is even non-trivial to delegate for policies where P simply contains sequences of singletons over A, i.e., sequences of the form P.sub.1 . . . P.sub.n where each P.sub.i is true only for a fixed aA independently of i. In contrast, note that the same type of policies are entirely trivially delegatable in the single instance setting for any PRF.

Applications

(114) Authentication and Access Control in RFID

(115) Radio Frequency Identification (RFID) is a popular technology that is expected to become ubiquitous in the near future. An RFID tag is a small chip with an antenna. It typically stores a unique ID along with other data, which can be transmitted to a reading device lying within a certain range from the tag. Suppose that a trusted center (TC) possesses a set of RFID tags (attached to books, clothes, etc), and distributes RFID readers to specified locations (e.g., libraries, campuses, restaurants, etc.). Whenever a person or object carrying a tag lies in proximity with a reader, it transmits its data (e.g., the title of a book, the brand of a jacket, etc.). The TC can then retrieve these data from the RFID readers, and mine useful information (e.g., hotlist books, clothes, etc.).

(116) Despite its merits, RFID technology is challenged by security and privacy issues. For example, due to the availability and low cost of the RFID tags, one can easily create tags with arbitrary information. As such, an adversary may impersonate other tags, and provide falsified data to legitimate readers. On the other hand, a reader can receive data from any tag in its vicinity. Therefore, sensitive information may be leaked to a reader controlled by an adversary. For example, the adversary may learn the ID and the title of a book stored in a tag, match it with public library records, and discover the identity and reading habits of an individual.

(117) Motivated by the above, the literature has addressed authentication and access control in RFID. A notable paradigm was introduced in D. Molnar et al., A Scalable, Delegatable Pseudonym Protocol Enabling Ownership Transfer of RFID Tags, SAC, 276-290 (2006), which can be directly benefited by DPRFs. At a high level, every tag is associated with a key, and the trusted center (TC) delegates to a reader a set of these keys (i.e., the reader is authorized to authenticate and access data from only a subset of the tags). The goal is for the TC to reduce certain costs, e.g., the size of the delegation information required to derive the tag keys.

(118) Observe that a DPRF (,T,C) is directly applicable to the above setting. is defined on the domain of the tag IDs, and its range is the tag keys. Given a delegation predicate on the tag IDs, the TC generates a trapdoor via algorithm T, and sends it to the reader. The latter runs C on the trapdoor to retrieve the tag keys. In fact, for the special case where the access policy is a range of IDs, the delegation protocol suggested in D. Molnar et al. is identical to the non-private BRC scheme (D. Molnar et al. lacks rigorous definitions and proofs). Range policies are meaningful, since tag IDs may be sequenced according to some common theme (e.g., books on the same topic are assigned consecutive tag IDs). In this case, a range policy concisely describes a set of tags (e.g., books about a certain religion) and, hence, the system can enjoy the logarithmic delegation size of BRC. However, as explained above, BRC leaks the position of the IDs in the tree, which may further leak information about the tags. Although D. Molnar et al. addresses tag privacy, it provides no privacy formulation, and overlooks the above structural leakage. This can be mitigated by directly applying the disclosed policy-private URC construction for delegating tag keys to the readers. To sum up, DPRFs find excellent application in authentication and access control in RFID, enabling communication-efficient tag key delegation from the TC to the reader. Moreover, policy-private DPRFs provide a higher level of protection for the tag IDs against the readers.

(119) Batch Queries in Symmetric Searchable Encryption

(120) Symmetric searchable encryption (SSE) enables queries to be processed directly on ciphertexts generated with symmetric encryption. Although SSE is a general paradigm, consider the definitions and schemes of R. Curtmola et al., Searchable Symmetric Encryption: Improved Definitions and Efficient Constructions, CCS (2006). These works support the special case of keyword queries, and provide an acceptable level of provable security. The general framework underlying R. Curtmola et al. is as follows. In an offline stage, a client encrypts his data with his secret key k, and uploads the ciphertexts c to an untrusted server. He also creates and sends a secure index I on the data for efficient keyword search, which is essentially an encrypted lookup table or inverted index. Given a keyword w, the client generates a query token .sub.w using k, and forwards it to the server. It is important to stress that this trapdoor is merely comprised of one or more PRF values computed on w with k, which were used as keys to encrypt I. For simplicity and without loss of generality, assume that .sub.w is a single PRF value. The server uses .sub.w on I and retrieves the IDs of the ciphertexts associated with w. The results c.sub.1, . . . , c.sub.m are retrieved and transmitted back to the client, who eventually decrypts them with his key. The security goal is to protect both the data and the keyword from the server.

(121) Suppose that the client wishes to search for a batch of N keywords w.sub.1, . . . , w.sub.N. For instance, the client may ask for documents that contain multiple keywords of his choice (instead of just a single one). As another example, assume that the client's data are employee records, and each record contains a salary attribute that takes as values intervals of the form [i K, (i+1)K] (i.e., instead of exact salaries). These intervals can serve as keywords in SSE search. Suppose that the client wishes to retrieve records with salaries in a range of intervals, e.g., [1K, 10K]. Observe that this cannot be processed with a single keyword query (no record is associated with [1K, 10K]). To overcome this while utilizing the SSE functionality, the client can ask 9 distinct queries with keywords [1K, 2K], [2K, 3K], . . . , [9K, 10K], which cover the query range [1K, 10K]. Such scenarios are handled with traditional SSE as shown in FIG. 7A. FIG. 7A illustrates a conventional Symmetric searchable encryption scheme between a client 700 and a server 740. Given a predicate P that describes the keywords w.sub.1, . . . , w.sub.N in the batch query, the client 700 generates N trapdoors .sub.w.sub.1, . . . , .sub.w.sub.N using the standard SSE trapdoor algorithm, and sends them to the server 740. The server 740 then searches I with every .sub.w.sub.i following the SSE protocol. Apparently, for large N, the computational and communication cost at the client is greatly impacted.

(122) FIG. 7B illustrates a Symmetric searchable encryption scheme between a client 760 and a server 780 augmented with DPRFs in accordance with aspects of the present invention. The SSE framework of FIG. 7A can be augmented with DPRF functionality, in order to support batch queries with sublinear (in N) processing and communication cost at the client, while providing provable security along the lines of [22]. Recall that .sub.w.sub.i is practically a PRF on w.sub.i produced with key k. Therefore, instead of computing a PRF value for every w.sub.i himself, the client delegates the computation of these PRF values to the server by employing a DPRF (,T,C), where is defined over the domain of the keywords. Given predicate P and k, the client runs T and generates trapdoor , which is sent to the server. The latter executes C on to produce .sub.w.sub.1, . . . , .sub.w.sub.N. Execution then proceeds in the same manner as in traditional SSE. Observe that, for the special case of ranges, if URC is used as the DPRF, the computational and communication cost at the client decreases from O(N) to O(log(N)).

(123) The above framework can be proven secure against adaptive adversaries. The most important alteration in the security game and proof is the formulation of the information leakage of the C algorithm of the DPRF. Although a policy-private DPRF provides predicate indistinguishability, there may still be some information leaked from C about the computed PRFs, which may be critical in SSE. Specifically, C may disclose some relationships between two PRF values satisfying the predicate P. For instance, in the disclosed URC scheme, C may disclose that two PRF values correspond to adjacent domain values (e.g., when the two values are produced as left and right children in a subtree). Through this leakage, the adversary may infer that, e.g., two ciphertexts are employee records with adjacent salary intervals (but these values will remain encrypted obviously). If this leakage information is incorporated to the simulator in the security game, then slight modifications in the proof methodology of R. Curtmola et al. suffice in order to perfectly simulate the real execution DPRF-enhanced SSE framework; despite this moderate privacy loss the scheme offers an exponential improvements in terms of efficiency which from a practical point of view is a more deciding factor.

(124) Broadcast Encryption

(125) In a broadcast encryption scheme, a sender wishes to transmit data to a set of receivers so that at each transmission, the set of receivers excluded from the recipient set can be chosen on the fly by the sender. In particular, this means that the sender has to be able to make an initial key assignment to the recipients and then use the suitable key material so that only the specific set of users of its choosing can receive the message. In such schemes, it was early on observed that there is a natural tradeoff between receiver memory storage and ciphertext length. The intuition behind this is that if the receivers have more keys this gives to the sender more flexibility in the way it can encrypt a message to be transmitted.

(126) In the above sense, one can think of the key assignment step of a broadcast encryption scheme as a PRF defined over the set which contains all distinct subsets that the broadcast encryption scheme assigns a distinct key. Given this configuration, the user u will have to obtain all the keys corresponding to subsets S for which it holds that uS (denoted subsets by S.sub.u). In DPRF language, this would correspond to a delegation policy for a PRF: users will need to store the trapdoor that enables the evaluation of any value in the delegated key set S.sub.N.

(127) Seen in this way, any DPRF is a key assignment mechanism for a broadcast encryption scheme that saves space on receiver storage. For example, the disclosed construction for ranges gives rise to the following broadcast encryption scheme: receivers [n]={1, . . . , n} are placed in sequence; each receiver u[n] is initialized with the trapdoor for a range [ut,u+t] for some predetermined parameter t. In this broadcast encryption scheme, the sender can very efficiently enable any range of receivers that is positioned at distance at most t from a fixed location v[n]. This is done with a single ciphertext (encrypted with the key of location v). Any receiver of sufficient proximity t to location v can derive the corresponding decryption key from its trapdoor. Furthermore, given the efficiency of the disclosed construction, storage on receivers is only logarithmic on t. While the semantics of this scheme are more restricted than a full-fledged broadcast encryption scheme (which enables the sender to exclude any subset of users on demand), it succinctly illustrates the relation between broadcast encryption and DPRF.

(128) Regarding policy privacy, it is interesting to point out that this security property is yet unstudied in the domain of broadcast encryption. In the present context, policy privacy deals with the privacy of memory contents from the receiver point of view. Maintaining the indistinguishability of the storage contents is a useful security measure in broadcast encryption schemes and the DPRF primitive will motivate the study of this security property in the context of broadcast encryption (note that none of the tree-like key-delegation methods used in prior broadcast encryption schemes work satisfy policy privacy).

CONCLUSION

(129) The delegatable pseudorandom functions (DPRFs) disclosed herein are a new cryptographic primitive that allow for policy-based computation at an untrusted proxy 120 (FIG. 1) of PRF values without knowledge of a secret or even the input values. The core properties of DPRFs are defined for (1) correctness, the ability of the proxy 120 to compute PRF values only for inputs that satisfy a given predicate, (2) security, the standard pseudorandomness guarantee but against a stronger adversary that also issues delegation queries, and (3) policy privacy, preventing leakage of the secret preimages of the computed PRF values. In addition, two DPRF constructions are provided along with an analysis in terms of their security and privacy guarantees and some inherent trade-offs with efficiency. The proposed DPRFs are generic, yet practical, based on the well-understood and widely-adopted GGM design framework for PRFs and they find direct application in many key delegation or derivation settings providing interesting new results.

(130) FIG. 8 shows one possible implementation of a given one of the processing devices of FIG. 1. The device in this implementation includes a processor 800 coupled to a memory 802 and a network interface 804. These device elements may be implemented in whole or in part as a conventional microprocessor, digital signal processor, application-specific integrated circuit (ASIC) or other type of circuitry, as well as portions or combinations of such circuitry elements. As will be appreciated by those skilled in the art, a secure authentication protocol in accordance with the present invention can be implemented at least in part in the form of one or more software programs that are stored in device memory 802 and executed by the corresponding processor 800. The memory 802 is also used for storing information used to perform computations or other operations associated with the secure alerting protocols of the invention.

(131) As previously indicated, the above-described embodiments of the invention are presented by way of illustrative example only. Numerous variations and other alternative embodiments may be used, as noted above. Aspects of the present invention permit delegation of the evaluation of pseudorandom functions to a proxy.

(132) Additional details regarding certain conventional cryptographic techniques referred to herein may be found in, e.g., A. J. Menezes et al., Handbook of Applied Cryptography, CRC Press, 1997, which is incorporated by reference herein.

(133) The illustrative embodiments of the invention as described herein provide for secure delegation of the evaluation of pseudorandom functions to a proxy. Advantageously, the illustrative embodiments do not require changes to existing communication protocols. It is therefore transparent to both existing applications and communication protocols.

(134) It should again be emphasized that the particular authentication, encryption and/or communication techniques described above are provided by way of illustration, and should not be construed as limiting the present invention to any specific embodiment or group of embodiments. For example, as previously noted, the described embodiments may be adapted in a straightforward manner to operate with other types of credentials, encryption and/or authentication information. Also, the particular configuration of system elements, and their interactions, may be varied in other embodiments. Moreover, the various simplifying assumptions made above in the course of describing the illustrative embodiments should also be viewed as exemplary rather than as requirements or limitations of the invention. Numerous alternative embodiments within the scope of the appended claims will be readily apparent to those skilled in the art.