Making any identity-based encryption accountable, efficiently. (English) Zbl 1504.94160

Kiayias, Aggelos; Tang, Qiang

Pernul, Günther (ed.) et al., Computer security – ESORICS 2015. 20th European symposium on research in computer security, Vienna, Austria, September 21–25, 2015. Proceedings. Part I. Cham: Springer. Lect. Notes Comput. Sci. 9326, 326-346 (2015).

Summary: Identity-Based Encryption (IBE) provides a compelling solution to the PKI management problem, however it comes with the serious privacy consideration that a trusted party (called the PKG) is required to generate (and hence also know) the secret keys of all users. This inherent key escrow problem is considered to be one of the major reasons hindering the wider utilization of IBE systems. In order to address this problem, V. Goyal [Lect. Notes Comput. Sci. 4622, 430–447 (2007; Zbl 1215.94047)] introduced the notion of accountable authority IBE (A-IBE), in which a judge can differentiate the PKG from the user as the source of a decryption software. Via this “tracing” mechanism, A-IBE deters the PKG from leaking the user’s secret key and hence offers a defense mechanism for IBE users against a malicious PKG.
All previous works on A-IBE focused on specialized constructions trying to achieve different properties and efficiency enhancements. In this paper for the first time we show how to add accountability to any IBE scheme using oblivious transfer (OT), with almost the same ciphertext efficiency as the underlying IBE. Furthermore, we extend our generic construction to support identity reuse without losing efficiency. This property is desirable in practice as users may accidentally lose their secret keys and they – naturally – prefer not to abandon their identities. How to achieve this property was open until our work. Along the way, we first modify the generic construction and develop a new technique to provide public traceability generically.
For the entire collection see [Zbl 1492.68028].

MSC:

94A60	Cryptography
94A62	Authentication, digital signatures and secret sharing

Keywords:

key escrow problem; IBE scheme; oblivious transfer

Citations:

Zbl 1215.94047

References:

[1]	Al-Riyami, SS; Paterson, KG; Laih, C-S, Certificateless public key cryptography, Advances in Cryptology - ASIACRYPT 2003, 452-473, 2003, Heidelberg: Springer, Heidelberg · Zbl 1205.94072 · doi:10.1007/978-3-540-40061-5_29
[2]	Au, MH; Huang, Q.; Liu, JK; Susilo, W.; Wong, DS; Yang, G.; Bellovin, SM; Gennaro, R.; Keromytis, AD; Yung, M., Traceable and retrievable identity-based encryption, Applied Cryptography and Network Security, 94-110, 2008, Heidelberg: Springer, Heidelberg · Zbl 1319.94051 · doi:10.1007/978-3-540-68914-0_6
[3]	Bellare, M.; Micali, S.; Brassard, G., Non-interactive oblivious transfer and applications, Advances in Cryptology - CRYPTO 1989, 547-557, 1989, Heidelberg: Springer, Heidelberg · Zbl 0722.68041
[4]	Bellare, M., Rogaway, P.: Random oracles are practical: Aa paradigm for designing efficient protocols. In: ACM Conference on Computer and Communications Security, pp. 62-73 (1993)
[5]	Boneh, D.; Boyen, X.; Cachin, C.; Camenisch, JL, Efficient selective-ID secure identity-based encryption without random oracles-, Advances in Cryptology - EUROCRYPT 2004, 223-238, 2004, Heidelberg: Springer, Heidelberg · Zbl 1122.94355 · doi:10.1007/978-3-540-24676-3_14
[6]	Boneh, D.; Boyen, X.; Franklin, M., Secure identity based encryption without random oracles, Advances in Cryptology - CRYPTO 2004, 443-459, 2004, Heidelberg: Springer, Heidelberg · Zbl 1104.94019 · doi:10.1007/978-3-540-28628-8_27
[7]	Boneh, D.; Boyen, X.; Shacham, H.; Franklin, M., Short group signatures, Advances in Cryptology - CRYPTO 2004, 41-55, 2004, Heidelberg: Springer, Heidelberg · Zbl 1104.94044 · doi:10.1007/978-3-540-28628-8_3
[8]	Boneh, D.; Franklin, M.; Kilian, J., Identity-based encryption from the weil pairing, Advances in Cryptology - CRYPTO 2001, 213, 2001, Heidelberg: Springer, Heidelberg · Zbl 1002.94023 · doi:10.1007/3-540-44647-8_13
[9]	Boneh, D.; Halevi, S.; Hamburg, M.; Ostrovsky, R.; Wagner, D., Circular-secure encryption from decision Diffie-Hellman, Advances in Cryptology - CRYPTO 2008, 108-125, 2008, Heidelberg: Springer, Heidelberg · Zbl 1183.94025 · doi:10.1007/978-3-540-85174-5_7
[10]	Boneh, D., Naor, M.: Traitor tracing with constant size ciphertext. In: ACM Conference on Computer and Communications Security, pp. 501-510 (2008)
[11]	Boneh, D.; Sahai, A.; Waters, B.; Ishai, Y., Functional encryption: definitions and challenges, Theory of Cryptography, 253-273, 2011, Heidelberg: Springer, Heidelberg · Zbl 1295.94027 · doi:10.1007/978-3-642-19571-6_16
[12]	Boyen, X., Martin, L.: Identity-Based Cryptography Standard (IBCS) #1: Supersingular Curve Implementations of the BF and BB1 Cryptosystems. RFC 5091 (Informational), December (2007)
[13]	Canetti, R., Security and composition of multiparty cryptographic protocols, J. Cryptol., 13, 1, 143-202, 2000 · Zbl 0957.68040 · doi:10.1007/s001459910006
[14]	Chow, SSM; Jarecki, S.; Tsudik, G., Removing escrow from identity-based encryption, Public Key Cryptography - PKC 2009, 256-276, 2009, Heidelberg: Springer, Heidelberg · Zbl 1227.94039 · doi:10.1007/978-3-642-00468-1_15
[15]	Cramer, R.; Damgåard, I.; Schoenmakers, B.; Desmedt, YG, Proofs of partial knowledge and simplified design of witness hiding protocols, Advances in Cryptology - CRYPTO 1994, 174-187, 1994, Heidelberg: Springer, Heidelberg · Zbl 0939.94546
[16]	Fiat, A.; Shamir, A.; Odlyzko, AM, How to prove yourself: practical solutions to identification and signature problems, Advances in Cryptology - CRYPTO 1986, 186-194, 1987, Heidelberg: Springer, Heidelberg · Zbl 0636.94012
[17]	Gamal, TE, A public key cryptosystem and a signature scheme based on discrete logarithms, IEEE Trans. Inf. Theory, 31, 4, 469-472, 1985 · Zbl 0571.94014 · doi:10.1109/TIT.1985.1057074
[18]	Gentry, C.; Biham, E., Certificate-based encryption and the certificate revocation problem, Advances in Cryptology - EUROCRYPT 2003, 272-293, 2003, Heidelberg: Springer, Heidelberg · Zbl 1037.68533 · doi:10.1007/3-540-39200-9_17
[19]	Gentry, C.; Vaudenay, S., Practical identity-based encryption without random oracles, Advances in Cryptology - EUROCRYPT 2006, 445-464, 2006, Heidelberg: Springer, Heidelberg · Zbl 1140.94340 · doi:10.1007/11761679_27
[20]	Goyal, V.; Menezes, A., Reducing trust in the PKG in identity based cryptosystems, Advances in Cryptology - CRYPTO 2007, 430-447, 2007, Heidelberg: Springer, Heidelberg · Zbl 1215.94047 · doi:10.1007/978-3-540-74143-5_24
[21]	Goyal, V., Lu, S., Sahai, A., Waters, B.: Black-box accountable authority identity-based encryption. In: ACM Conference on Computer and Communications Security, pp. 427-436 (2008)
[22]	Goyal, V., Pandey, O., Sahai, A., Waters, B.: Attribute-based encryption for fine-grained access control of encrypted data. In: ACM Conference on Computer and Communications Security, pp. 89-98 (2006)
[23]	Guruswami, V.; Indyk, P., Expander-based constructions of efficiently decodable codes, FOCS, 2001, 658-667, 2001
[24]	Kiayias, A., Tang, Q.: How to keep a secret: leakage deterring public-key cryptosystems. In: ACM Conference on Computer and Communications Security, pp. 943-954 (2013)
[25]	Lai, J.; Deng, RH; Zhao, Y.; Weng, J.; Dawson, E., Accountable authority identity-based encryption with public traceability, Topics in Cryptology - CT-RSA 2013, 326-342, 2013, Heidelberg: Springer, Heidelberg · Zbl 1312.94067 · doi:10.1007/978-3-642-36095-4_21
[26]	Libert, B.; Vergnaud, D.; Jarecki, S.; Tsudik, G., Towards black-box accountable authority ibe with short ciphertexts and private keys, Public Key Cryptography - PKC 2009, 235-255, 2009, Springer: Springer, Springer · Zbl 1227.94053 · doi:10.1007/978-3-642-00468-1_14
[27]	Naor, M., Pinkas, B.: Efficient oblivious transfer protocols. In: SODA, pp. 448-457 (2001) · Zbl 0991.94045
[28]	Sahai, A.; Seyalioglu, H.; Catalano, D.; Fazio, N.; Gennaro, R.; Nicolosi, A., Fully secure accountable-authority identity-based encryption, Public Key Cryptography - PKC 2011, 296-316, 2011, Heidelberg: Springer, Heidelberg · Zbl 1291.94147 · doi:10.1007/978-3-642-19379-8_19
[29]	Sahai, A.; Waters, B.; Cramer, R., Fuzzy Identity-based encryption, Advances in Cryptology - EUROCRYPT 2005, 457-473, 2005, Heidelberg: Springer, Heidelberg · Zbl 1137.94355 · doi:10.1007/11426639_27
[30]	Schnorr, C-P; Brassard, G., Efficient identification and signatures for smart cards, Advances in Cryptology - CRYPTO 1989, 239-252, 1990, Heidelberg: Springer, Heidelberg · Zbl 0722.68050
[31]	Shamir, A.; Blakely, GR; Chaum, D., Identity-based cryptosystems and signature schemes, Advances in Cryptology of CRYPTO 1984, 47-53, 1985, Heidelberg: Springer, Heidelberg · Zbl 1359.94626
[32]	Waters, B.; Cramer, R., Efficient identity-based encryption without random oracles, Advances in Cryptology - EUROCRYPT 2005, 114-127, 2005, Heidelberg: Springer, Heidelberg · Zbl 1137.94360 · doi:10.1007/11426639_7
[33]	Waters, B.; Halevi, S., Dual system encryption: realizing fully secure IBE and HIBE under simple assumptions, Advances in Cryptology - CRYPTO 2009, 619-636, 2009, Heidelberg: Springer, Heidelberg · Zbl 1252.94101 · doi:10.1007/978-3-642-03356-8_36
[34]	Yuen, TH; Chow, SSM; Zhang, C.; Yiu, S-M, Exponent-inversion signatures and ibe under static assumptions, IACR Cryptol. ePrint Arch., 2014, 311, 2014