Abstract
We prove a computational soundness theorem for symmetric-key encryption protocols that can be used to analyze security against adaptively corrupting adversaries (that is, adversaries who corrupt protocol participants during protocol execution). Our soundness theorem shows that if the encryption scheme used in the protocol is semantically secure, and encryption cycles are absent, then security against adaptive corruptions is achievable via a reduction factor of O(n·(2n)l), with n and l being (respectively) the size and depth of the key graph generated during any protocol execution. Since, in most protocols of practical interest, the depth of key graphs (measured as the longest chain of ciphertexts of the form \({\mathcal{E}_{k_1}(k_2)}\), \({\mathcal{E}_{k_2}(k_3)}\), \({\mathcal{E}_{k_3}(k_4),\cdots}\)) is much smaller than their size (the total number of keys), this gives us a powerful tool to argue about the adaptive security of such protocols, without resorting to non-standard techniques (like non-committing encryption).
We apply our soundness theorem to the security analysis of multicast encryption protocols and show that a variant of the Logical Key Hierarchy (LKH) protocol is adaptively secure (its security being quasi-polynomially related to the security of the underlying encryption scheme).
This material is based upon work supported by the National Science Foundation under the Grant CNS-0430595. A full version of the paper is available from the author’s webpage.
Chapter PDF
Similar content being viewed by others
References
Abadi, M., Rogaway, P.: Reconciling two views of cryptography (the computational soundness of formal encryption). Journal of Cryptology 15(2), 103–127 (2002)
Abadi, M., Warinschi, B.: Security analysis of cryptographically controlled access to xml documents. In: Proceedings of the 24th ACM Symposium on Principles of Database Systems (PODS), Baltimore, Maryland, June 2005, pp. 108–117. ACM Press, New York (2005)
Beaver, D., Haber, S.: Cryptographic protocols provably secure against dynamic adversaries. In: Rueppel, R.A. (ed.) EUROCRYPT 1992. LNCS, vol. 658, pp. 307–323. Springer, Heidelberg (1993)
Bellare, M., Desai, A., Jokipii, E., Rogaway, P.: A concrete security treatment of symmetric encryption. In: focsed (ed.) 38th FOCSAnnual Symposium on Foundations of Computer Science, October, pp. 394–403. IEEE Computer Society Press, Los Alamitos (1997)
Canetti, R., Feige, U., Goldreich, O., Naor, M.: Adaptively secure multiparty computation. In: stoced (ed.) 28th ACM STOCAnnual ACM Symposium on Theory of Computing, May, pp. 639–648. ACM Press, New York (1996)
Canetti, R., Herzog, J.: Universally composable symbolic analysis of mutual authentication and key exchange protocols. In: Halevi, S., Rabin, T. (eds.) TCC 2006. LNCS, vol. 3876, pp. 380–403. Springer, Heidelberg (2006)
Datta, A., Derek, A., Mitchell, J., Warinschi, B.: Computationally sound compositional logic for key exchange protocols. In: 19th IEEE Computer Security Foundations Workshop (CSFW ’06), pp. 321–334. IEEE Computer Society Press, Los Alamitos (2006)
Dwork, C., Naor, M., Reingold, O., Stockmeyer, L.: Magic functions. Journal of the ACM 50(6), 852–921 (2003)
Fiat, A., Naor, M.: Broadcast encryption. In: Stinson, D.R. (ed.) CRYPTO 1993. LNCS, vol. 773, pp. 480–491. Springer, Heidelberg (1994)
Gupta, P., Shmatikov, V.: Key confirmation and adaptive corruptions in the protocol security logic. In: FCS-ARSPA 2006 (Joint Workshop on Foundations of Computer Security and Automated Reasoning for Security Protocol Analysis) (2006)
Micciancio, D., Panjwani, S.: Adaptive security of symbolic encryption. In: Kilian, J. (ed.) TCC 2005. LNCS, vol. 3378, pp. 169–187. Springer, Heidelberg (2005)
Micciancio, D., Panjwani, S.: Corrupting one vs. corrupting many: The case of broadcast and multicast encryption (Manuscript). In: Bugliesi, M., Preneel, B., Sassone, V., Wegener, I. (eds.) ICALP 2006. LNCS, vol. 4052, Springer, Heidelberg (2006)
Micciancio, D., Warinschi, B.: Soundness of formal encryption in the presence of active adversaries. In: Naor, M. (ed.) TCC 2004. LNCS, vol. 2951, pp. 133–151. Springer, Heidelberg (2004)
Mittra, S.: Iolus: A framework for Scalable Secure Multicasting. In: Proceedings of ACM SIGCOMM, Cannes, France, pp. 277–288. ACM Press, New York (1997)
Naor, D., Naor, M., Lotspiech, J.: Revocation and tracing schemes for stateless receivers. In: Kilian, J. (ed.) CRYPTO 2001. LNCS, vol. 2139, pp. 41–62. Springer, Heidelberg (2001)
Nielsen, J.B.: Separating random oracle proofs from complexity theoretic proofs: The non-committing encryption case. In: Yung, M. (ed.) CRYPTO 2002. LNCS, vol. 2442, pp. 111–126. Springer, Heidelberg (2002)
Wong, C.K., Gouda, M., Lam, S.S.: Secure group communications using key graphs. IEEE/ACM Transactions on Networking 8(1), 16–30 (2000)
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 2007 Springer Berlin Heidelberg
About this paper
Cite this paper
Panjwani, S. (2007). Tackling Adaptive Corruptions in Multicast Encryption Protocols. In: Vadhan, S.P. (eds) Theory of Cryptography. TCC 2007. Lecture Notes in Computer Science, vol 4392. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-70936-7_2
Download citation
DOI: https://doi.org/10.1007/978-3-540-70936-7_2
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-70935-0
Online ISBN: 978-3-540-70936-7
eBook Packages: Computer ScienceComputer Science (R0)