Delegate predicate encryption and its application to anonymous authentication

ABSTRACT

Predicate encryption provides fine-grained control over encryption and decryption. In a predicate encryption scheme, message is encrypted with a set of attributes, and decryption key is incorporated with a predicate. Only when the predicate evaluates to true over these attributes, the message can be correctly decrypted. We propose an extension to predicate encryption named delegate predicate encryption. In our extension, a user generates a encryption capability of a set of attributes, then sends the capability to a encryption proxy. Using this capability, the proxy can encrypt arbitrary message with these attributes without knowing anything about these attributes. We give a concrete construction from a predicate encryption scheme which supports the widest range of predicate known to date. Then, using our extension, we are able to construct an anonymous authentication scheme. In our anonymous authentication scheme, authentication rules can be described in an very expressive way, while the anonymity of user is protected and the authentication rules are also hidden.

REFERENCES

• 1: Abdalla, M., Bellare, M., Catalano, D., Kiltz, E., Kohno, T., Lange, T., Malone- Lee, J., Neven, G., Paillier, P., Shi, H.: Searchable Encryption Revisited: Consistency Properties, Relation to Anonymous IBE, and Extensions. In: Shoup, V. (ed.) CRYPTO 2005. LNCS, vol. 3621, pp. 205--222. Springer, Heidelberg (2005)
• 2: Adi Shamir, Identity-based cryptosystems and signature schemes, Proceedings of CRYPTO 84 on Advances in cryptology, p.47-53, August 1985, Santa Barbara, California, United States
• 3: Boyen, X., Waters, B.: Anonymous hierarchical identity-based encryption (without random oracles). In: Dwork, C. (ed.) CRYPTO 2006. LNCS, vol. 4117, Springer, Heidelberg (2006)
• 4: Vipul Goyal , Omkant Pandey , Amit Sahai , Brent Waters, Attribute-based encryption for fine-grained access control of encrypted data, Proceedings of the 13th ACM conference on Computer and communications security, October 30-November 03, 2006, Alexandria, Virginia, USA [doi>10.1145/1180405.1180418]
• 5: Katz, J., Sahai, A., Waters, B.: Predicate encryption supporting disjunctions, polynomial equations, and inner products. Cryptology ePrint Archive, Report 2007/404
• 6: M. Naor , M. Yung, Public-key cryptosystems provably secure against chosen ciphertext attacks, Proceedings of the twenty-second annual ACM symposium on Theory of computing, p.427-437, May 13-17, 1990, Baltimore, Maryland, United States [doi>10.1145/100216.100273]
• 7: Rafail Ostrovsky , Amit Sahai , Brent Waters, Attribute-based encryption with non-monotonic access structures, Proceedings of the 14th ACM conference on Computer and communications security, October 28-31, 2007, Alexandria, Virginia, USA [doi>10.1145/1315245.1315270]
• 8: Sahai, A., Waters, B.: Fuzzy identity-based encryption. In: Cramer, R. J. F. (ed.) EUROCRYPT 2005. LNCS, vol. 3494, Springer, Heidelberg (2005)
• 9: Elaine Shi , John Bethencourt , T-H. Hubert Chan , Dawn Song , Adrian Perrig, Multi-Dimensional Range Query over Encrypted Data, Proceedings of the 2007 IEEE Symposium on Security and Privacy, p.350-364, May 20-23, 2007 [doi>10.1109/SP.2007.29]
• 10: John Bethencourt , Amit Sahai , Brent Waters, Ciphertext-Policy Attribute-Based Encryption, Proceedings of the 2007 IEEE Symposium on Security and Privacy, p.321-334, May 20-23, 2007 [doi>10.1109/SP.2007.11]
• 11: David Chaum, Security without identification: transaction systems to make big brother obsolete, Communications of the ACM, v.28 n.10, p.1030-1044, Oct. 1985 [doi>10.1145/4372.4373]
• 12: Anna Lysyanskaya , Ronald L. Rivest , Amit Sahai , Stefan Wolf, Pseudonym Systems, Proceedings of the 6th Annual International Workshop on Selected Areas in Cryptography, p.184-199, August 09-10, 1999
• 13: J. Camenisch and A. Lysyanskaya. Signature schemes and anonymous credentials from bilinear maps. In CRYPTO 2004, volume 3152 of LNCS, p. 56--72, 2004.
• 14: Boneh, D., Boyen, X.: Secure identity based encryption without random oracles. In: Franklin, M. (ed.) CRYPTO 2004. LNCS, vol. 3152, Springer, Heidelberg (2004)
• 15: Boneh, D., Di Crescenzo, G., Ostrovsky, R., Persiano, G.: Public-key encryption with keyword search. In: Cachin, C., Camenisch, J. L. (eds.) EUROCRYPT 2004. LNCS, vol. 3027, Springer, Heidelberg (2004)
• 16: Dan Boneh , Matthew Franklin, Identity-Based Encryption from the Weil Pairing, SIAM Journal on Computing, v.32 n.3, p.586-615, 2003 [doi>10.1137/S0097539701398521]
• 17: Boneh, D., Waters, B.: Conjunctive, subset, and range queries on encrypted data. In: Theory of Cryptography Conference (2007)
• 18: Elaine Shi , Brent Waters, Delegating Capabilities in Predicate Encryption Systems, Proceedings of the 35th international colloquium on Automata, Languages and Programming, Part II, July 07-11, 2008, Reykjavik, Iceland [doi>10.1007/978-3-540-70583-3_46]

INDEX TERMS

Primary Classification:
  E. Data
  E.3 DATA ENCRYPTION

General Terms:
Security

Keywords:
anonymous authentication, predicate encryption