Abstract
We formalize the simulation paradigm of cryptography in terms of category theory and show that protocols secure against abstract attacks form a symmetric monoidal category, thus giving an abstract model of composable security definitions in cryptography. Our model is able to incorporate computational security, set-up assumptions and various attack models such as colluding or independently acting subsets of adversaries in a modular, flexible fashion. We conclude by using string diagrams to rederive the security of the one-time pad and no-go results concerning the limits of bipartite and tripartite cryptography, ruling out e.g., composable commitments and broadcasting.
This work was supported by the Air Force Office of Scientific Research under award number FA9550-20-1-0375, Canada’s NFRF and NSERC, an Ontario ERA, and the University of Ottawa’s Research Chairs program.
Chapter PDF
Similar content being viewed by others
References
Abramsky, S., Barbosa, R.S., Karvonen, M., Mansfield, S.: A comonadic view of simulation and quantum resources. In: 2019 34th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS). IEEE (2019). https://doi.org/10.1109/LICS.2019.8785677
Backes, M., Pfitzmann, B., Waidner, M.: A general composition theorem for secure reactive systems. In: 1st Theory of Cryptography Conference—TCC 2004. pp. 336–354 (2004). https://doi.org/10.1007/978-3-540-24638-1_19
Backes, M., Pfitzmann, B., Waidner, M.: The reactive simulatability (RSIM) framework for asynchronous systems. Information and Computation 205(12), 1685–1720 (2007). https://doi.org/10.1016/j.ic.2007.05.002
Ben-Or, M., Canetti, R., Goldreich, O.: Asynchronous secure computation. In: Proceedings of the twenty-fifth annual ACM symposium on Theory of computing. pp. 52–61 (1993). https://doi.org/10.1145/167088.167109
Ben-Or, M., Horodecki, M., Leung, D.W., Mayers, D., Oppenheim, J.: The universal composable security of quantum key distribution. In: 2nd Theory of Cryptography Conference—TCC 2005. pp. 386–406 (2005). https://doi.org/10.1007/978-3-540-30576-7_21
Ben-Or, M., Mayers, D.: General security definition and composability for quantum & classical protocols (2004), https://arxiv.org/abs/quant-ph/0409062
Bennett, C.H., Brassard, G.: Quantum cryptography: Public key distribution and coin tossing. In: International Conference on Computers, Systems and Signal Processing. pp. 175–179 (1984)
Biham, E., Boyer, M., Boykin, P.O., Mor, T., Roychowdhury, V.: A proof of the security of quantum key distribution (extended abstract). In: 32nd Annual ACM Symposium on Theory of Computing—STOC 2000. pp. 715 – 724 (2000). https://doi.org/10.1145/335305.335406
Breiner, S., Kalev, A., Miller, C.A.: Parallel self-testing of the GHZ state with a proof by diagrams. In: Proceedings of QPL 2018. Electronic Proceedings in Theoretical Computer Science, vol. 287, pp. 43–66 (2018). https://doi.org/10.4204/eptcs.287.3
Breiner, S., Miller, C.A., Ross, N.J.: Graphical methods in device-independent quantum cryptography. Quantum 3, 146 (2019). https://doi.org/10.22331/q-2019-05-27-146
Broadbent, A., Fitzsimons, J., Kashefi, E.: Universal blind quantum computation. In: 50th Annual Symposium on Foundations of Computer Science—FOCS 2009. pp. 517–526 (2009). https://doi.org/10.1109/FOCS.2009.36
Camenisch, J., Küsters, R., Lysyanskaya, A., Scafuro, A.: Practical Yet Composably Secure Cryptographic Protocols (Dagstuhl Seminar 19042). Dagstuhl Reports 9(1), 88–103 (2019). https://doi.org/10.4230/DagRep.9.1.88
Canetti, R.: Universally composable security: A new paradigm for cryptographic protocols. In: 42nd Annual Symposium on Foundations of Computer Science—FOCS 2001. pp. 136–145 (2001). https://doi.org/10.1109/SFCS.2001.959888
Canetti, R., Fischlin, M.: Universally composable commitments. In: Advances in cryptology—CRYPTO 2001. pp. 19–40. Springer (2001). https://doi.org/10.1007/3-540-44647-8_2
Chiribella, G., D’Ariano, G.M., Perinotti, P.: Probabilistic theories with purification. Physical Review A 81(6) (Jun 2010). https://doi.org/10.1103/physreva.81.062348
Chitambar, E., Gour, G.: Quantum resource theories. Reviews of Modern Physics 91(2), 025001 (2019). https://doi.org/10.1103/revmodphys.91.025001
Chitambar, E., Leung, D., Mančinska, L., Ozols, M., Winter, A.: Everything you always wanted to know about LOCC (but were afraid to ask). Communications in Mathematical Physics 328(1), 303–326 (2014). https://doi.org/10.1007/s00220-014-1953-9
Clairambault, P., De Visme, M., Winskel, G.: Game semantics for quantum programming. Proceedings of the ACM on Programming Languages 3(POPL), 1–29 (2019). https://doi.org/10.1145/3290345
Clairambault, P., de Visme, M., Winskel, G.: Concurrent quantum strategies. In: International Conference on Reversible Computation. pp. 3–19. Springer (2019). https://doi.org/10.1007/978-3-030-21500-2_1
Coecke, B., Fritz, T., Spekkens, R.W.: A mathematical theory of resources. Information and Computation 250, 59–86 (2016). https://doi.org/10.1016/j.ic.2016.02.008
Coecke, B., Perdrix, S.: Environment and classical channels in categorical quantum mechanics. Logical Methods in Computer Science Volume 8, Issue 4 (2012). https://doi.org/10.2168/LMCS-8(4:14)2012
Coecke, B., Wang, Q., Wang, B., Wang, Y., Zhang, Q.: Graphical calculus for quantum key distribution (extended abstract). Electronic Notes in Theoretical Computer Science 270(2), 231–249 (2011). https://doi.org/10.1016/j.entcs.2011.01.034
Cruttwell, G., Gavranović, B., Ghani, N., Wilson, P., Zanasi, F.: Categorical foundations of gradient-based learning (2021), https://arxiv.org/abs/2103.01931
Cunningham, O., Heunen, C.: Purity through factorisation. In: Proceedings of QPL 2017. Electronic Proceedings in Theoretical Computer Science, vol. 266, pp. 315–328 (2017). https://doi.org/10.4204/EPTCS.266.20
Datta, A., Derek, A., Mitchell, J.C., Pavlovic, D.: A derivation system for security protocols and its logical formalization. In: 16th IEEE Computer Security Foundations Workshop, 2003. Proceedings. pp. 109–125. IEEE (2003). https://doi.org/10.1109/csfw.2003.1212708
Datta, A., Derek, A., Mitchell, J.C., Pavlovic, D.: Secure protocol composition. Electronic Notes in Theoretical Computer Science 83, 201–226 (2003). https://doi.org/10.1016/s1571-0661(03)50011-1
Datta, A., Derek, A., Mitchell, J.C., Pavlovic, D.: A derivation system and compositional logic for security protocols. Journal of Computer Security 13(3), 423–482 (Aug 2005). https://doi.org/10.3233/JCS-2005-13304
Datta, A., Derek, A., Mitchell, J.C., Roy, A.: Protocol composition logic (PCL). Electronic Notes in Theoretical Computer Science 172, 311–358 (Apr 2007). https://doi.org/10.1016/j.entcs.2007.02.012
Durgin, N., Mitchell, J., Pavlovic, D.: A compositional logic for protocol correctness. In: Proceedings. 14th IEEE Computer Security Foundations Workshop, 2001. IEEE (2001). https://doi.org/10.1109/csfw.2001.930150
Durgin, N., Mitchell, J., Pavlovic, D.: A compositional logic for proving security properties of protocols. Journal of Computer Security 11(4), 677–721 (Oct 2003). https://doi.org/10.3233/JCS-2003-11407
Fong, B., Spivak, D., Tuyeras, R.: Backprop as functor: A compositional perspective on supervised learning. In: 2019 34th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS) (2019). https://doi.org/10.1109/lics.2019.8785665
Fritz, T.: Resource convertibility and ordered commutative monoids. Mathematical Structures in Computer Science 27(6), 850–938 (2015). https://doi.org/10.1017/s0960129515000444
Gavranović, B.: Compositional deep learning (2019), https://arxiv.org/abs/1907.08292
Goldwasser, S., Micali, S.: Probabilistic encryption. Journal of Computer and System Sciences 28(2), 270–299 (1984). https://doi.org/10.1016/0022-0000(84)90070-9
Heunen, C.: Compactly accessible categories and quantum key distribution. Logical Methods in Computer Science 4(4) (2008). https://doi.org/10.2168/lmcs-4(4:9)2008
Hillebrand, A.: Superdense coding with GHZ and quantum key distribution with W in the ZX-calculus. In: Proceedings of QPL 2011. Electronic Proceedings in Theoretical Computer Science, vol. 95, pp. 103–121 (2011). https://doi.org/10.4204/EPTCS.95.10
Hines, P.M.: A diagrammatic approach to information flow in encrypted communication (2020). https://doi.org/10.1007/978-3-030-62230-5_9
Hofheinz, D., Shoup, V.: GNUC: A new universal composability framework. Journal of Cryptology 28(3), 423–508 (2015). https://doi.org/10.1007/s00145-013-9160-y
Horodecki, M., Oppenheim, J.: (Quantumness in the context of) Resource Theories. International Journal of Modern Physics B 27(01n03), 1345019 (2013). https://doi.org/10.1142/s0217979213450197
Katz, J., Maurer, U., Tackmann, B., Zikas, V.: Universally composable synchronous computation. In: Theory of Cryptography, pp. 477–498. Springer (2013). https://doi.org/10.1007/978-3-642-36594-2_27
Kissinger, A., Tull, S., Westerbaan, B.: Picture-perfect quantum key distribution (2017), https://arxiv.org/abs/1704.08668
König, R., Renner, R., Bariska, A., Maurer, U.: Small accessible quantum information does not imply security. Physical Review Letters 98(14), 140502 (2007). https://doi.org/10.1103/PhysRevLett.98.140502
Küsters, R., Tuengerthal, M., Rausch, D.: The IITM model: a simple and expressive model for universal composability. Journal of Cryptology 33(4), 1461–1584 (2020). https://doi.org/10.1007/s00145-020-09352-1
Liao, K., Hammer, M.A., Miller, A.: ILC: a calculus for composable, computational cryptography. In: Proceedings of the 40th ACM SIGPLAN Conference on Programming Language Design and Implementation. pp. 640–654. ACM (Jun 2019). https://doi.org/10.1145/3314221.3314607
Lo, H.K., Chau, H.F.: Is quantum bit commitment really possible? Physical Review Letters 78(17), 3410–3413 (1997). https://doi.org/10.1103/PhysRevLett.78.3410
Matt, C., Maurer, U., Portmann, C., Renner, R., Tackmann, B.: Toward an algebraic theory of systems. Theoretical Computer Science 747, 1–25 (2018). https://doi.org/10.1016/j.tcs.2018.06.001
Maurer, U.: Constructive cryptography–a new paradigm for security definitions and proofs. In: Joint Workshop on Theory of Security and Applications—TOSCA 2011. pp. 33–56 (2011). https://doi.org/10.1007/978-3-642-27375-9_3
Maurer, U., Renner, R.: Abstract cryptography. In: Innovations in Computer Science—ICS 2011 (2011)
Mayers, D.: The trouble with quantum bit commitment (1996), http://arxiv.org/abs/quant-ph/9603015
Mayers, D.: Unconditional security in quantum cryptography. Journal of the ACM 48(3), 351–406 (2001). https://doi.org/10.1145/382780.382781
Micciancio, D., Tessaro, S.: An equational approach to secure multi-party computation. In: 4th Conference on Innovations in Theoretical Computer Science—ITCS 2013. pp. 355–372 (2013). https://doi.org/10.1145/2422436.2422478
Mifsud, A., Milner, R., Power, J.: Control structures. In: Proceedings of Tenth Annual IEEE Symposium on Logic in Computer Science. pp. 188–198. IEEE (1995). https://doi.org/10.1109/lics.1995.523256
Moeller, J., Vasilakopoulou, C.: Monoidal Grothendieck construction. Theory and Applications of Categories 35(31), 1159–1207 (2020)
Müller-Quade, J., Renner, R.: Composability in quantum cryptography. New Journal of Physics 11(8), 085006 (2009). https://doi.org/10.1088/1367-2630/11/8/085006
Pavlovic, D.: Categorical logic of names and abstraction in action calculi. Mathematical Structures in Computer Science 7(6), 619–637 (1997). https://doi.org/10.1017/S0960129597002296
Pavlovic, D.: Tracing the man in the middle in monoidal categories. In: Coalgebraic Methods in Computer Science. pp. 191–217. Springer (2012). https://doi.org/10.1007/978-3-642-32784-1_11
Pavlovic, D.: Chasing diagrams in cryptography. In: Casadio, C., Coecke, B., Moortgat, M., Scott, P. (eds.) Categories and Types in Logic, Language, and Physics: Essays Dedicated to Jim Lambek on the Occasion of His 90th Birthday, pp. 353–367. Springer Berlin Heidelberg, Berlin, Heidelberg (2014). https://doi.org/10.1007/978-3-642-54789-8_19
Pfitzmann, B., Waidner, M.: A model for asynchronous reactive systems and its application to secure message transmission. In: 2001 IEEE Symposium on Security and Privacy—S&P 2001. pp. 184–200 (2000). https://doi.org/10.1109/SECPRI.2001.924298
Portmann, C., Matt, C., Maurer, U., Renner, R., Tackmann, B.: Causal boxes: quantum information-processing systems closed under composition. IEEE Transactions on Information Theory 63(5), 3277–3305 (2017). https://doi.org/10.1109/TIT.2017.2676805
Portmann, C., Renner, R.: Cryptographic security of quantum key distribution (2014), https://arxiv.org/abs/1409.3525
Prabhakaran, M., Rosulek, M.: Cryptographic complexity of multi-party computation problems: Classifications and separations. In: Advances in Cryptology—CRYPTO 2008. pp. 262–279 (2008). https://doi.org/10.1007/978-3-540-85174-5_15
Renner, R.: Security of quantum key distribution. International Journal of Quantum Information 06(01), 1–127 (2005). https://doi.org/10.1142/S0219749908003256
Selinger, P.: A survey of graphical languages for monoidal categories. In: New structures for physics, pp. 289–355. Springer (2010). https://doi.org/10.1007/978-3-642-12821-9_4
Shor, P.W., Preskill, J.: Simple proof of security of the BB84 quantum key distribution protocol. Physical Review Letters 85(2), 441–444 (2000). https://doi.org/10.1103/physrevlett.85.441
Stay, M., Vicary, J.: Bicategorical semantics for nondeterministic computation. In: Proceedings of the Twenty-ninth Conference on the Mathematical Foundations of Programming Semantics, MFPS XXIX. Electronic Notes in Theoretical Computer Science, vol. 298, pp. 367 – 382 (2013). https://doi.org/10.1016/j.entcs.2013.09.022
Sun, X., He, F., Wang, Q.: Impossibility of quantum bit commitment, a categorical perspective. Axioms 9(1), 28 (2020). https://doi.org/10.3390/axioms9010028
Tomamichel, M., Lim, C.C.W., Gisin, N., Renner, R.: Tight finite-key analysis for quantum cryptography. Nature Communications 3, 634 (2012). https://doi.org/10.1038/ncomms1631
Unruh, D.: Universally composable quantum multi-party computation. In: Advances in Cryptology—EUROCRYPT 2010. pp. 486–505 (2010). https://doi.org/10.1007/978-3-642-13190-5_25
Winskel, G.: Distributed probabilistic and quantum strategies. Electronic Notes in Theoretical Computer Science 298, 403–425 (2013). https://doi.org/10.1016/j.entcs.2013.09.024
Wolf, S., Wullschleger, J.: New monotones and lower bounds in unconditional two-party computation. IEEE Transactions on Information Theory 54(6), 2792–2797 (2008). https://doi.org/10.1109/tit.2008.921674
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Open Access This chapter is licensed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license and indicate if changes were made.
The images or other third party material in this chapter are included in the chapter's Creative Commons license, unless indicated otherwise in a credit line to the material. If material is not included in the chapter's Creative Commons license and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder.
Copyright information
© 2022 The Author(s)
About this paper
Cite this paper
Broadbent, A., Karvonen, M. (2022). Categorical composable cryptography. In: Bouyer, P., Schröder, L. (eds) Foundations of Software Science and Computation Structures. FoSSaCS 2022. Lecture Notes in Computer Science, vol 13242. Springer, Cham. https://doi.org/10.1007/978-3-030-99253-8_9
Download citation
DOI: https://doi.org/10.1007/978-3-030-99253-8_9
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-99252-1
Online ISBN: 978-3-030-99253-8
eBook Packages: Computer ScienceComputer Science (R0)
