Delegatable pseudorandom functions and applications

• US 9,712,320 B1
• Filed: 06/30/2013
• Issued: 07/18/2017
• Est. Priority Date: 06/11/2013
• Status: Active Grant

• Current Assignee: Emc IP Holding Company LLC (Dell Technologies Inc.)
• Original Assignee: Emc IP Holding Company LLC (Dell Technologies Inc.)
• Inventors: Kiayias, Aggelos, Papadopoulos, Stavros, Triandopoulos, Nikolaos, Zacharias, Thomas Megas
• Primary Examiner(s): Desrosiers, Evans
• Application Number:
  US13/931,939
• Time in Patent Office: 1,479 Days
• Field of Search: 380 46, 370204, 723150-194, 713150-194
• CPC Class Codes: H04L 2209/50 Oblivious transfer
• CPC Class Codes: H04L 2209/76 Proxy, i.e. using intermediary entity to perform cryptographic operations network architectures or network communication protocols using hop-by-hop encryption H04L63/0464
• CPC Class Codes: H04L 9/008 involving homomorphic encryption
• CPC Class Codes: H04L 9/0662 with particular pseudorandom sequence generator
• CPC Class Codes: H04L 9/3218 using proof of knowledge, e.g. Fiat-Shamir, GQ, Schnorr, ornon-interactive zero-knowledge proofs

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.