Categorical composable cryptography: extended version
We formalize the key ideas of constructive cryptography in categorical terms. This results in viewing cryptography as a resource theory in the sense of Fritz, Coecke & Spekkens: the resources are cryptographic functionalities and resources conversions are protocols that transform securely such resources to others. 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 also use 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. On the way, we exhibit two categorical constructions of resource theories that might be of independent interest: one capturing resources shared among n parties and one capturing resource conversions that succeed asymptotically.
Broadbent, A., & Karvonen, M. (2022). Categorical composable cryptography: extended version.
PDF
ArXiv
Inner autoequivalences in general and those of monoidal categories in particular
Our main result states that inner autoequivalences of monoidal categories are essentially the same as conjugations by a weakly invertible element. For this to be a theorem, there needs to be a general theory of inner autoequivalences, and indeed there is: developing that is the other main contribution.
Hofstra, P., & Karvonen, M. (2022). Inner autoequivalences in general and those of monoidal categories in particular.
PDF
ArXiv
Categorical composable cryptography
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.
Broadbent, A., & Karvonen, M. (2022). Categorical composable cryptography. In Foundations of Software Science and Computation Structures (FoSSaCS) 2022.
PDF
BibTeX
ArXiv
Proceedings
Closing Bell: Boxing black box simulations in the resource theory of contextuality
After an exposition of the sheaf-theoretic approach to contextuality, we discuss and answer the following question: given a function that maps empirical models over a scenario S to those over a scenario T, when is this function induced by a mapping between the scenarios? To answer this, we build a new scenario out of S and T, and associate to any such function an empirical model over this. Modulo some technicalities, a function between models is then induced by a map of scenarios iff the corresponding model is noncontextual.
Barbosa, R. S., Karvonen, M., & Mansfield, S. (2023). Closing Bell: Boxing black box simulations in the resource theory of contextuality. To appear in Samson Abramsky on Logic and Structure in Computer Science and Beyond in Springer's Outstanding Contributions to Logic series.
PDF
BibTeX
ArXiv
Neither Contextuality nor Nonlocality Admits Catalysts
It turns out that there are no catalysts for contextuality nor for non-locality. This is in contrast with entanglement, for which catalysts famously exist.
Karvonen, M. (2021). Neither Contextuality nor Nonlocality Admits Catalysts. Phys. Rev. Lett. 127, 160402
PDF
BibTeX
ArXiv
Journal
Biproducts without pointedness
Turns out one can define a well-behaved notion of a biproduct in any category without assuming pointedness.
Karvonen, M. (2020). Biproducts without pointedness. Cahiers de topologie et géométrie différentielle catégoriques, Vol LXI, Issue 3, 229-238.
PDF
BibTeX
ArXiv
Journal
A comonadic view of simulation and quantum resources
We simplify and generalize the ideas in the QPL paper below.
Abramsky, S., Barbosa, R. S., Karvonen, M., & Mansfield, S. (2019). A comonadic view of simulation and quantum resources. In 2019 34th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS). IEEE.
PDF
BibTeX
ArXiv
Proceedings
Limits in dagger categories
We define a notion of limit suitable for dagger categories and explore it.
Heunen, C., & Karvonen, M. (2019). Limits in dagger categories. Theory and Applications of Categories, Vol. 34, No. 18, 468-513.
PDF
BibTeX
ArXiv
Journal
Reversible effects as inverse arrows
We study (reversible) side-effects in a reversible programming language. As reversible computing can be modelled by inverse categories, we model side-effects using a notion of arrow suitable for inverse categories. Since inverse categories can be defined as certain dagger categories, we also develop a notion of a dagger arrow.
Heunen, C., Kaarsgaard, R., & Karvonen, M. (2018). Reversible effects as inverse arrows. Proceedings of MFPS 2018. ENTCS, 341, 179-199.
PDF
BibTeX
ArXiv
Proceedings
Categories of Empirical Models
A notion of morphism that is suitable for the sheaf-theoretic approach to contextuality is developed, resulting in a resource theory for contextuality.
Karvonen, M. (2018). Categories of empirical models. Proceedings of QPL 2018, EPTCS 287, pp. 239-252.
PDF
BibTeX
ArXiv
Monads on dagger categories
This is the extended version of the previous conference paper.
Heunen, C., & Karvonen, M. (2016). Monads on dagger categories. Theory and Applications of Categories, Vol. 31, No. 35, 1016-1043.
PDF
BibTeX
ArXiv
Journal
Reversible monadic computing
Heunen, C., & Karvonen, M. (2015). Reversible monadic computing. Electronic Notes in Theoretical Computer Science, 319, 217-237.
PDF
BibTeX
ArXiv
Proceedings