Martti Karvonen
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Previous Organizations / Institutes
The organizations / institutes from the scholar's other articles in the past ten years
Research Subjects
Martti Karvonen has a total of 18 co-authors. Here are the top co-authors by number of shared publications:
- Anne Broadbent
University of Ottawa
5 shared publications - Chris Heunen
University of Edinburgh, Edinburgh, United Kingdom
3 shared publications - Rui Soares Barbosa
INL – International Iberian Nanotechnology Laboratory, Braga, Portugal
3 shared publications - Diana Kessler
Tallinn University of Technology
2 shared publications - Fabian Wiesner
Technische Universität Berlin
2 shared publications Pieter Hofstra
Univ Ottawa, Dept Math & Stat, Ottawa, ON, Canada
2 shared publications
Latest Publications
- Open Access
- 4 April 2026
- Published by Springer Nature in Applied Categorical Structures
- Vol. 34 (3) , 23
Towards a Unified Theory of Time-Varying Data
What is a time-varying graph, a time-varying topological space, or, more generally, a mathematical structure that evolves over time? In this work, we lay the foundations for a general theory of temporal data by introducing categories of narratives . These are sheaves on posets of time intervals that encode snapshots of a temporal object along with the relationships between them. This theory satisfies five desiderata distilled from the burgeoning field of time-varying graphs: (D1) it defines both time-varying objects and their morphisms; (D2) it distinguishes between cumulative and persistent interpretations and provides principled methods for transitioning between them; (D3) it systematically lifts static notions to their temporal analogues; (D4) it is object agnostic; (D5) it integrates with theories of dynamical systems. To achieve this, we build upon existing categorical and sheaf-theoretic approaches to temporal graph theory, generalizing them to any category with limits and colimits. We also formalize tacit intuitions that, while present, often remain implicit in temporal graph theory. Beyond synthesizing and reformulating existing ideas in categorical language, we introduce sheaf-theoretic constructions and prove results that, to our knowledge, have not appeared in the temporal data literature—such as the adjunction between persistent and cumulative narratives. More importantly, we integrate these existing and novel elements into a consistent and coherent framework, setting the stage for a unified theory of time-varying data.
- 4 April 2026
- Published by Springer Nature in Applied Categorical Structures
- Vol. 34 (3) , 23
Open AccessTowards a Unified Theory of Time-Varying Data
What is a time-varying graph, a time-varying topological space, or, more generally, a mathematical structure that evolves over time? In this work, we lay the foundations for a general theory of temporal data by introducing categories of narratives . These are sheaves on posets of time intervals that encode snapshots of a temporal object along with the relationships between them. This theory satisfies five desiderata distilled from the burgeoning field of time-varying graphs: (D1) it defines both time-varying objects and their morphisms; (D2) it distinguishes between cumulative and persistent interpretations and provides principled methods for transitioning between them; (D3) it systematically lifts static notions to their temporal analogues; (D4) it is object agnostic; (D5) it integrates with theories of dynamical systems. To achieve this, we build upon existing categorical and sheaf-theoretic approaches to temporal graph theory, generalizing them to any category with limits and colimits. We also formalize tacit intuitions that, while present, often remain implicit in temporal graph theory. Beyond synthesizing and reformulating existing ideas in categorical language, we introduce sheaf-theoretic constructions and prove results that, to our knowledge, have not appeared in the temporal data literature—such as the adjunction between persistent and cumulative narratives. More importantly, we integrate these existing and novel elements into a consistent and coherent framework, setting the stage for a unified theory of time-varying data.
- Open Access
- 8 January 2026
- Published by International Association for Cryptologic Research in IACR Communications in Cryptology
- Vol. 2 (4)
Why cut-and-choose quantum state verification cannot be both efficient and secure
Quantum state verification plays a vital role in many quantum cryptographic protocols, as it allows using quantum states from an untrusted source. While some progress has been made in this direction, the question of whether the most prevalent type of quantum state verification, namely cut-and-choose verification, can be efficient and secure, is still not answered in full generality. In this work, we show a fundamental limit for quantum state verification for all cut-and-choose approaches used to verify arbitrary quantum states. We provide a no-go result showing that the cut-and-choose techniques cannot lead to quantum state verification protocols that are both efficient and secure. We show this trade-off for stand-alone and composable security, where the scaling of the lower bound for the security parameters renders cut-and-choose quantum state verification effectively unusable.
- 8 January 2026
- Published by International Association for Cryptologic Research in IACR Communications in Cryptology
- Vol. 2 (4)
Open AccessWhy cut-and-choose quantum state verification cannot be both efficient and secure
Quantum state verification plays a vital role in many quantum cryptographic protocols, as it allows using quantum states from an untrusted source. While some progress has been made in this direction, the question of whether the most prevalent type of quantum state verification, namely cut-and-choose verification, can be efficient and secure, is still not answered in full generality. In this work, we show a fundamental limit for quantum state verification for all cut-and-choose approaches used to verify arbitrary quantum states. We provide a no-go result showing that the cut-and-choose techniques cannot lead to quantum state verification protocols that are both efficient and secure. We show this trade-off for stand-alone and composable security, where the scaling of the lower bound for the security parameters renders cut-and-choose quantum state verification effectively unusable.
- Open Access
Why cut-and-choose quantum state verification cannot be both efficient and secure
Quantum state verification plays a vital role in many quantum cryptographic protocols, as it allows the use of quantum states from untrusted sources. While some progress has been made in this direction, the question of whether the most prevalent type of quantum state verification, namely cut-and-choose verification, can be efficient and secure, is still not answered in full generality. In this work, we show a fundamental limit for quantum state verification for all cut-and-choose approaches used to verify arbitrary quantum states. We provide a no-go result showing that the cut-and-choose techniques cannot lead to quantum state verification protocols that are both efficient in the number of rounds and secure. We show this trade-off for stand-alone and composable security, where the scaling of the lower bound for the security parameters renders cut-and-choose quantum state verification effectively unusable.
Open AccessWhy cut-and-choose quantum state verification cannot be both efficient and secure
Quantum state verification plays a vital role in many quantum cryptographic protocols, as it allows the use of quantum states from untrusted sources. While some progress has been made in this direction, the question of whether the most prevalent type of quantum state verification, namely cut-and-choose verification, can be efficient and secure, is still not answered in full generality. In this work, we show a fundamental limit for quantum state verification for all cut-and-choose approaches used to verify arbitrary quantum states. We provide a no-go result showing that the cut-and-choose techniques cannot lead to quantum state verification protocols that are both efficient in the number of rounds and secure. We show this trade-off for stand-alone and composable security, where the scaling of the lower bound for the security parameters renders cut-and-choose quantum state verification effectively unusable.
- Open Access
- 7 October 2024
- Published by International Association for Cryptologic Research in IACR Communications in Cryptology
- Vol. 1 (3)
Uncloneable Quantum Advice
The famous no-cloning principle has been shown recently to enable a number of uncloneable cryptographic primitives, including the copy-protection of certain functionalities. Here we address for the first time unkeyed quantum uncloneablity, via the study of a complexity-theoretic tool that enables a computation, but that is natively unkeyed: quantum advice. Remarkably, this is an application of the no-cloning principle in a context where the quantum states of interest are not chosen by a random process. We establish unconditional constructions for promise problems admitting uncloneable quantum advice and, assuming the feasibility of quantum copy-protecting certain functions, for languages with uncloneable advice. Along the way, we note that state complexity classes, introduced by Rosenthal and Yuen (ITCS 2022) — which concern the computational difficulty of synthesizing sequences of quantum states — can be naturally generalized to obtain state cloning complexity classes. We make initial observations on these classes, notably obtaining a result analogous to the existence of undecidable problems. Our proof technique defines and constructs ingenerable sequences of finite bit strings, essentially meaning that they cannot be generated by any uniform circuit family with non-negligible probability. We then prove a generic result showing that the difficulty of accomplishing a computational task on uniformly random inputs implies its difficulty on any fixed, ingenerable sequence. We use this result to derandomize quantum cryptographic games that relate to cloning, and then incorporate a result of Kundu and Tan (arXiv 2022) to obtain uncloneable advice. Applying this two-step process to a monogamy-of-entanglement game yields a promise problem with uncloneable advice, and applying it to the quantum copy-protection of pseudorandom functions with super-logarithmic output lengths yields a language with uncloneable advice.
- 7 October 2024
- Published by International Association for Cryptologic Research in IACR Communications in Cryptology
- Vol. 1 (3)
Open AccessUncloneable Quantum Advice
The famous no-cloning principle has been shown recently to enable a number of uncloneable cryptographic primitives, including the copy-protection of certain functionalities. Here we address for the first time unkeyed quantum uncloneablity, via the study of a complexity-theoretic tool that enables a computation, but that is natively unkeyed: quantum advice. Remarkably, this is an application of the no-cloning principle in a context where the quantum states of interest are not chosen by a random process. We establish unconditional constructions for promise problems admitting uncloneable quantum advice and, assuming the feasibility of quantum copy-protecting certain functions, for languages with uncloneable advice. Along the way, we note that state complexity classes, introduced by Rosenthal and Yuen (ITCS 2022) — which concern the computational difficulty of synthesizing sequences of quantum states — can be naturally generalized to obtain state cloning complexity classes. We make initial observations on these classes, notably obtaining a result analogous to the existence of undecidable problems. Our proof technique defines and constructs ingenerable sequences of finite bit strings, essentially meaning that they cannot be generated by any uniform circuit family with non-negligible probability. We then prove a generic result showing that the difficulty of accomplishing a computational task on uniformly random inputs implies its difficulty on any fixed, ingenerable sequence. We use this result to derandomize quantum cryptographic games that relate to cloning, and then incorporate a result of Kundu and Tan (arXiv 2022) to obtain uncloneable advice. Applying this two-step process to a monogamy-of-entanglement game yields a promise problem with uncloneable advice, and applying it to the quantum copy-protection of pseudorandom functions with super-logarithmic output lengths yields a language with uncloneable advice.
- Open Access
- 17 May 2024
- Published by Elsevier in Journal of Pure and Applied Algebra
- Vol. 228 (11)
Inner autoequivalences in general and those of monoidal categories in particular
- 17 May 2024
- Published by Elsevier in Journal of Pure and Applied Algebra
- Vol. 228 (11)
Open AccessInner autoequivalences in general and those of monoidal categories in particular
- Open Access
Closing Bell: Boxing black box simulations in the resource theory of contextuality
This chapter contains an exposition of the sheaf-theoretic framework for contextuality emphasising resource-theoretic aspects, as well as some original results on this topic. In particular, we consider functions that transform empirical models on a scenario S to empirical models on another scenario T, and characterise those that are induced by classical procedures between S and T corresponding to 'free' operations in the (non-adaptive) resource theory of contextuality. We construct a new 'hom' scenario built from S and T, whose empirical models induce such functions. Our characterisation then boils down to being induced by a non-contextual model. We also show that this construction on scenarios provides a closed structure on the category of measurement scenarios.
Open AccessClosing Bell: Boxing black box simulations in the resource theory of contextuality
This chapter contains an exposition of the sheaf-theoretic framework for contextuality emphasising resource-theoretic aspects, as well as some original results on this topic. In particular, we consider functions that transform empirical models on a scenario S to empirical models on another scenario T, and characterise those that are induced by classical procedures between S and T corresponding to 'free' operations in the (non-adaptive) resource theory of contextuality. We construct a new 'hom' scenario built from S and T, whose empirical models induce such functions. Our characterisation then boils down to being induced by a non-contextual model. We also show that this construction on scenarios provides a closed structure on the category of measurement scenarios.
- Open Access
- 1 January 2024
- Published by Mount Allison University in Theory and Applications of Categories
- Vol. 42 (2) , 19-40
Inner automorphisms as 2-cells
Inner automorphisms can be used to promote any category into a 2-category, and we study two-dimensional limits and colimits in the resulting 2categories. Existing connected colimits and limits in the starting category become two-dimensional colimits and limits under fairly general conditions. Under the same conditions, colimits in the underlying category can be used to build many notable two-dimensional colimits such as coequifiers and coinserters. In contrast, disconnected colimits or genuinely 2-categorical limits such as inserters and equifiers and cotensors cannot exist unless no nontrivial abstract inner automorphisms exist and the resulting 2-category is locally discrete. We also study briefly when an ordinary functor can be extended to a 2-functor between the resulting 2-categories.
- 1 January 2024
- Published by Mount Allison University in Theory and Applications of Categories
- Vol. 42 (2) , 19-40
Open AccessInner automorphisms as 2-cells
Inner automorphisms can be used to promote any category into a 2-category, and we study two-dimensional limits and colimits in the resulting 2categories. Existing connected colimits and limits in the starting category become two-dimensional colimits and limits under fairly general conditions. Under the same conditions, colimits in the underlying category can be used to build many notable two-dimensional colimits such as coequifiers and coinserters. In contrast, disconnected colimits or genuinely 2-categorical limits such as inserters and equifiers and cotensors cannot exist unless no nontrivial abstract inner automorphisms exist and the resulting 2-category is locally discrete. We also study briefly when an ordinary functor can be extended to a 2-functor between the resulting 2-categories.
- Open Access
- 18 December 2023
- Published by Centre pour la Communication Scientifique Directe (CCSD) in Logical Methods in Computer Science
- Vol. ume 19, Is (4)
Categorical composable cryptography: extended version
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, correctness of Diffie-Hellman key exchange 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 multiple parties and one capturing resource conversions that succeed asymptotically.
- 18 December 2023
- Published by Centre pour la Communication Scientifique Directe (CCSD) in Logical Methods in Computer Science
- Vol. ume 19, Is (4)
Open AccessCategorical composable cryptography: extended version
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, correctness of Diffie-Hellman key exchange 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 multiple parties and one capturing resource conversions that succeed asymptotically.
- Open Access
Uncloneable Quantum Advice
The famous no-cloning principle has been shown recently to enable a number of uncloneable functionalities. Here we address for the first time unkeyed quantum uncloneablity, via the study of a complexity-theoretic tool that enables a computation, but that is natively unkeyed: quantum advice. Remarkably, this is an application of the no-cloning principle in a context where the quantum states of interest are not chosen by a random process. We show the unconditional existence of promise problems admitting uncloneable quantum advice, and the existence of languages with uncloneable advice, assuming the feasibility of quantum copy-protecting certain functions. Along the way, we note that state complexity classes, introduced by Rosenthal and Yuen (ITCS 2022) - which concern the computational difficulty of synthesizing sequences of quantum states - can be naturally generalized to obtain state cloning complexity classes. We make initial observations on these classes, notably obtaining a result analogous to the existence of undecidable problems. Our proof technique establishes the existence of ingenerable sequences of finite bit strings - essentially meaning that they cannot be generated by any uniform circuit family. We then prove a generic result showing that the difficulty of accomplishing a computational task on uniformly random inputs implies its difficulty on any fixed, ingenerable sequence. We use this result to derandomize quantum cryptographic games that relate to cloning, and then incorporate a result of Kundu and Tan (arXiv 2022) to obtain uncloneable advice. Applying this two-step process to a monogamy-of-entanglement game yields a promise problem with uncloneable advice, and applying it to the quantum copy-protection of pseudorandom functions with super-logarithmic output lengths yields a language with uncloneable advice.
Open AccessUncloneable Quantum Advice
The famous no-cloning principle has been shown recently to enable a number of uncloneable functionalities. Here we address for the first time unkeyed quantum uncloneablity, via the study of a complexity-theoretic tool that enables a computation, but that is natively unkeyed: quantum advice. Remarkably, this is an application of the no-cloning principle in a context where the quantum states of interest are not chosen by a random process. We show the unconditional existence of promise problems admitting uncloneable quantum advice, and the existence of languages with uncloneable advice, assuming the feasibility of quantum copy-protecting certain functions. Along the way, we note that state complexity classes, introduced by Rosenthal and Yuen (ITCS 2022) - which concern the computational difficulty of synthesizing sequences of quantum states - can be naturally generalized to obtain state cloning complexity classes. We make initial observations on these classes, notably obtaining a result analogous to the existence of undecidable problems. Our proof technique establishes the existence of ingenerable sequences of finite bit strings - essentially meaning that they cannot be generated by any uniform circuit family. We then prove a generic result showing that the difficulty of accomplishing a computational task on uniformly random inputs implies its difficulty on any fixed, ingenerable sequence. We use this result to derandomize quantum cryptographic games that relate to cloning, and then incorporate a result of Kundu and Tan (arXiv 2022) to obtain uncloneable advice. Applying this two-step process to a monogamy-of-entanglement game yields a promise problem with uncloneable advice, and applying it to the quantum copy-protection of pseudorandom functions with super-logarithmic output lengths yields a language with uncloneable advice.
- 2 August 2023
- Published by Springer Nature
- p. 475-529
Closing Bell Boxing Black Box Simulations in the Resource Theory of Contextuality
- 2 August 2023
- Published by Springer Nature
- p. 475-529
Closing Bell Boxing Black Box Simulations in the Resource Theory of Contextuality