Joint state composition theorems for public-key encryption and digital signature functionalities with local computation. (English) Zbl 1453.94094
Summary: In frameworks for universal composability, complex protocols can be built from sub-protocols in a modular way using composition theorems. However, as first pointed out and studied by R. Canetti and T. Rabin [Crypto 2003, Lect. Notes Comput. Sci. 2729, 265–281 (2003; Zbl 1122.94360)], this modular approach often leads to impractical implementations. For example, when using a functionality for digital signatures within a more complex protocol, parties have to generate new verification and signing keys for every session of the protocol. This motivates to generalize composition theorems to so-called joint state (composition) theorems, where different copies of a functionality may share some state, e.g., the same verification and signing keys. In this paper, we present a joint state theorem which is more general than the original theorem of Canetti and Rabin, for which several problems and limitations are pointed out. We apply our theorem to obtain joint state realizations for three functionalities: public-key encryption, replayable public-key encryption, and digital signatures. Unlike most other formulations, our functionalities model that ciphertexts and signatures are computed locally, rather than being provided by the adversary. To obtain the joint state realizations, the functionalities have to be designed carefully. Other formulations proposed in the literature are shown to be unsuitable. Our work is based on the IITM model. Our definitions and results demonstrate the expressivity and simplicity of this model. For example, unlike Canetti’s UC model, in the IITM model no explicit joint state operator needs to be defined and the joint state theorem follows immediately from the composition theorem in the IITM model.
Keywords:
universal composability; IITM model; joint state composition; ideal functionalities; public-key encryption; digital signaturesCitations:
Zbl 1122.94360Software:
GNUCReferences:
| [1] | M. Backes and D. Hofheinz. How to Break and Repair a Universally Composable Signature Functionality. In Information Security, 7th International Conference, ISC 2004, Proceedings, volume 3225 of Lecture Notes in Computer Science, pages 61-72. Springer, 2004. · Zbl 1109.68441 |
| [2] | M. Backes, B. Pfitzmann, and M. Waidner. A composable cryptographic library with nested operations. In S. Jajodia, V. Atluri, and T. Jaeger, editors, Proceedings of the 10th ACM Conference on Computer and Communications Security (CCS 2003), pages 220-230. ACM, 2003. |
| [3] | M. Bellare, A. Desai, D. Pointcheval, and P. Rogaway. Relations Among Notions of Security for Public-Key Encryption Schemes. In H. Krawczyk, editor, Advances in Cryptology, 18th Annual International Cryptology Conference (CRYPTO 1998), volume 1462 of Lecture Notes in Computer Science, pages 549-570. Springer, 1998. · Zbl 0931.94014 |
| [4] | M. Bellare, D. Hofheinz, and E. Kiltz. Subtleties in the Definition of IND-CCA: When and How Should Challenge-Decryption be Disallowed? Technical Report 2009/418, Cryptology ePrint Archive, 2009. Available at http://eprint.iacr.org/2009/418. · Zbl 1308.94059 |
| [5] | J. Camenisch, R. R. Enderlein, S. Krenn, R. Küsters, and D. Rausch. Universal Composition with Responsive Environments. In J. H. Cheon and T. Takagi, editors, Advances in Cryptology - ASIACRYPT 2016 - 22nd International Conference on the Theory and Application of Cryptology and Information Security, volume 10032 of Lecture Notes in Computer Science, pages 807-840. Springer, 2016. A full version is available at https://eprint.iacr.org/2016/034. · Zbl 1407.94092 |
| [6] | R. Canetti. Universally Composable Security: A New Paradigm for Cryptographic Protocols. Technical Report 2000/067, Cryptology ePrint Archive, 2000. Available at http://eprint.iacr.org/2000/067 with new versions from December 2005, July 2013, and December 2018. |
| [7] | R. Canetti. Universally Composable Security: A New Paradigm for Cryptographic Protocols. In Proceedings of the 42nd Annual Symposium on Foundations of Computer Science (FOCS 2001), pages 136-145. IEEE Computer Society, 2001. |
| [8] | R. Canetti. Universally Composable Signature, Certification, and Authentication. In Proceedings of the 17th IEEE Computer Security Foundations Workshop (CSFW-17 2004), pages 219-233. IEEE Computer Society, 2004. |
| [9] | R. Canetti, L. Cheung, D. Kaynar, M. Liskov, N. Lynch, O. Pereira, and R. Segala. Time-Bounded Task-PIOAs: A Framework for Analyzing Security Protocols. In S. Dolev, editor, 20th International Symposium on Distributed Computing (DISC 2006), pages 238-253. Springer, 2006. · Zbl 1155.68326 |
| [10] | R. Canetti, Y. Dodis, R. Pass, and S. Walfish. Universally Composable Security with Global Setup. In S. P. Vadhan, editor, Theory of Cryptography, Proceedings of TCC 2007, volume 4392 of Lecture Notes in Computer Science, pages 61-85. Springer, 2007. · Zbl 1129.94014 |
| [11] | R. Canetti and J. Herzog. Universally Composable Symbolic Analysis of Mutual Authentication and Key-Exchange Protocols. In S. Halevi and T. Rabin, editors, Theory of Cryptography, Third Theory of Cryptography Conference, TCC 2006, volume 3876 of Lecture Notes in Computer Science, pages 380-403. Springer, 2006. · Zbl 1112.94025 |
| [12] | R. Canetti, H. Krawczyk, and J. Nielsen. Relaxing Chosen-Ciphertext Security. In Advances in Cryptology, 23rd Annual International Cryptology Conference (CRYPTO 2003), volume 2729 of Lecture Notes in Computer Science, pages 565-582. Springer, 2003. · Zbl 1122.94359 |
| [13] | R. Canetti and T. Rabin. Universal Composition with Joint State. Technical Report 2002/047, Cryptology ePrint Archive, 2002. Version of Nov. 2003. Available at http://eprint.iacr.org/2002/047. · Zbl 1122.94360 |
| [14] | R. Canetti and T. Rabin. Universal Composition with Joint State. In Advances in Cryptology, 23rd Annual International Cryptology Conference (CRYPTO 2003), Proceedings, volume 2729 of Lecture Notes in Computer Science, pages 265-281. Springer, 2003. · Zbl 1122.94360 |
| [15] | A. Datta, R. Küsters, J. Mitchell, and A. Ramanathan. On the Relationships Between Notions of Simulation-Based Security. In J. Kilian, editor, Proceedings of the 2nd Theory of Cryptography Conference (TCC 2005), volume 3378 of Lecture Notes in Computer Science, pages 476-494. Springer, 2005. · Zbl 1079.94543 |
| [16] | Goldwasser, S.; Micali, S.; Rivest, R., A digital signature scheme secure against adaptive chosen-message attacks, SIAM Journal on Computing, 17, 2, 281-308 (1988) · Zbl 0644.94012 · doi:10.1137/0217017 |
| [17] | D. Hofheinz, J. Mueller-Quade, and R. Steinwandt. On Modeling IND-CCA Security in Cryptographic Protocols. Cryptology ePrint Archive, Report 2003/024, 2003. Available at http://eprint.iacr.org/2003/024. · Zbl 1174.94359 |
| [18] | D. Hofheinz, J. Müller-Quade, and D. Unruh. Polynomial Runtime in Simulatability Definitions. In 18th IEEE Computer Security Foundations Workshop (CSFW-18 2005), pages 156-169. IEEE Computer Society, 2005. |
| [19] | D. Hofheinz, J. Müller-Quade, and D. Unruh. A simple model of polynomial time uc. One-page abstract of a talk given at the Workshop on Models for Cryptographic Protocols (MCP 2006), 2006. |
| [20] | D. Hofheinz and V. Shoup. GNUC: A New Universal Composability Framework. Technical Report 2011/303, Cryptology ePrint Archive, 2011. Available at http://eprint.iacr.org/2011/303. · Zbl 1356.94062 |
| [21] | R. Küsters. Simulation-Based Security with Inexhaustible Interactive Turing Machines. In Proceedings of the 19th IEEE Computer Security Foundations Workshop (CSFW-19 2006), pages 309-320. IEEE Computer Society, 2006. See [24] for a full and revised version. |
| [22] | R. Küsters and M. Tuengerthal. Joint State Theorems for Public-Key Encryption and Digital Signature Functionalities with Local Computation. In Proceedings of the 21st IEEE Computer Security Foundations Symposium (CSF 2008), pages 270-284. IEEE Computer Society, 2008. The full version is available at https://eprint.iacr.org/2008/006. |
| [23] | R. Küsters and M. Tuengerthal. Composition Theorems Without Pre-Established Session Identifiers. In Y. Chen, G. Danezis, and V. Shmatikov, editors, Proceedings of the 18th ACM Conference on Computer and Communications Security (CCS 2011), pages 41-50. ACM, 2011. |
| [24] | R. Küsters, M. Tuengerthal, and D. Rausch. The IITM Model: a Simple and Expressive Model for Universal Composability. Journal of Cryptology. To appear. Available at http://eprint.iacr.org/2013/025. |
| [25] | J. B. Nielsen. Separating Random Oracle Proofs from Complexity Theoretic Proofs: The Non-committing Encryption Case. In M. Yung, editor, Advances in Cryptology, 22nd Annual International Cryptology Conference (CRYPTO 2002), volume 2442 of Lecture Notes in Computer Science, pages 191-214. Springer, 2002. · Zbl 1027.68601 |
| [26] | B. Pfitzmann and M. Waidner. A Model for Asynchronous Reactive Systems and its Application to Secure Message Transmission. In IEEE Symposium on Security and Privacy, pages 184-201. IEEE Computer Society, 2001. |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
