Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

International Conference on Availability, Reliability and Security (ARES)

Security in Quantum Networks as an Optimization Problem

Stefan Raß, Peter Schartner

Published Jan 1, 2009• 7 citations
Publisher

Abstract

We present a general framework for casting the problem of designing secure quantum networks into a classical optimization problem. We introduce a measure of risk that serves as upper bound on the probability of loosing a message to the adversary. Based on this results, we can transform the problem of secure network design into an optimization procedure, which opens the field for the entire framework of optimization theory to tackle the problem most efficiently. The latter is particularly appealing, since we prove the problem to be NP-hard in general. Our methodology is formulated to yield results that have interpretations in probabilistic terms, but can be generalized to other settings in a straightforward manner. The modeling approach is simple, and naturally accounts for different notions of security, depending on the situation at hand. Furthermore, our results are not limited to security in quantum networks, as we rely on quantum cryptography only to the extent of securing links. Hence, the analysis is equally applicable for any (multipath) transmission setup, where information-theoretic security is demanded.

DOI
10.1109/ares.2009.84

Related papers

Game-Theoretic Security Analysis of Quantum Networks

Stefan Raß, Peter Schartner

Unconditional security is the key-feature of quantum cryptography, which makes it superior to any classical encryption scheme. Most research in this area focuses on analyzing the theoretical properties and performance of particular quantum key distribution protocols, but a rigorous analysis on the network level seems to be missing. We present a game-theoretic approach which gives simple and tight bounds to the risk of communication that any two peers in a quantum network have to take when communicating, even if quantum cryptography is used. This work is motivated by recent (IM)possibility results regarding unconditionally secure message transmission in arbitrary networks, which puts stringent constraints on the network topology. Hence, our model naturally accounts for a given graph topology (existing fibre-optic networks which are natural candidates for a roll-out of a quantum network), as well as measuring risk in terms of probability or the designers subjective understanding. As a by-product, our model gives optimal path selection strategies, and the optimal design of network topologies under given constraints (like geographic or monetary ones).

International Conference on Quantum, Nano and Micro Technologies (ICQNM)•Feb 1, 2009•11 citations

Information-Theoretic Security as an Optimization Problem

Stefan Raß

Quantum key distribution is renowned for information-theoretic security on point-to-point connections, while it is by itself not directly capable of end-to-end security. Multipath transmission is known for perfect end-to-end security, provided that perfect point-to-point security is achievable. The marriage of the two is as natural as it is difficult to achieve in real life networks: secure multipath transmission imposes stringent requirements on the network connectivity, perhaps rarely found in a real-life network infrastructure. We consider the problem of network augmentation to support perfect end-to-end security in a network in which adjacent nodes share a perfectly confidential channel. Quantum networks are one example for this. Starting with a decision-theoretic formalization of risk and confidentiality, we cast the network augmentation task into a nonlinear optimization problem, whose computational complexity is studied. With the problem turning out NP-hard in at least two of its variants, we sketch heuristics that can help to keep calculations feasible in practical applications.

Journal of Next Generation Information Technology•Aug 31, 2011•1 citation

Quantum Network Optimization: From Optimal Routing to Fair Resource Allocation

Zhaozhen Wang, Xingang Shi, Zhengfeng Ji +1 more

Quantum networks are essential infrastructure for enabling large-scale and long-distance quantum communications but face significant challenges in routing optimization and resource allocation due to their probabilistic nature and quantum resource limitations. Existing approaches typically tackle these problems in isolation, often by simply applying classical routing algorithms, maximizing the overall profit to allocate resources without considering fairness, or improving fairness in an ad-hoc way without a rigorous model. This paper proposes a general framework to systematically address these challenges. First, we conduct a thorough analysis of quantum network metrics using routing algebra as the mathematical foundation, and design provably optimal routing algorithms to tackle the unique challenges arising from their probabilistic characteristics. Second, we formulate an optimization model that simultaneously considers fairness among concurrent requests while respecting various quantum resource constraints, and design efficient near-optimal heuristics to solve it. The proposed framework provides both theoretical insights and practical solutions for the design and management of future quantum networks.

ACM SIGMETRICS Performance Evaluation Review•Jun 16, 2025•0 citations

Quantum Network Optimization: From Optimal Routing to Fair Resource Allocation

Zhaozhen Wang, Xingang Shi, Zhengfeng Ji +1 more

Quantum networks are essential infrastructure for enabling large-scale and long-distance quantum communications but face significant challenges in routing optimization and resource allocation due to their probabilistic nature and quantum resource limitations. Existing approaches typically tackle these problems in isolation, often by simply applying classical routing algorithms, maximizing the overall profit to allocate resources without considering fairness, or improving fairness in an ad-hoc way without a rigorous model. This paper proposes a general framework to systematically address these challenges. First, we conduct a thorough analysis of quantum network metrics using routing algebra as the mathematical foundation, and design provably optimal routing algorithms to tackle the unique challenges arising from their probabilistic characteristics. Second, we formulate an optimization model that simultaneously considers fairness among concurrent requests while respecting various quantum resource constraints, and design efficient near-optimal heuristics to solve it. The proposed framework provides both theoretical insights and practical solutions for the design and management of future quantum networks.

Proceedings of the ACM on Measurement and Analysis of Computing Systems•May 27, 2025•7 citations

Quantum Network Optimization: From Optimal Routing to Fair Resource Allocation

Zhaozhen Wang, Xingang Shi, Zhengfeng Ji +1 more

Quantum networks are essential infrastructure for enabling large-scale and long-distance quantum communications but face significant challenges in routing optimization and resource allocation due to their probabilistic nature and quantum resource limitations. Existing approaches typically tackle these problems in isolation, often by simply applying classical routing algorithms, maximizing the overall profit to allocate resources without considering fairness, or improving fairness in an ad-hoc way without a rigorous model. This paper proposes a general framework to systematically address these challenges. First, we conduct a thorough analysis of quantum network metrics using routing algebra as the mathematical foundation, and design provably optimal routing algorithms to tackle the unique challenges arising from their probabilistic characteristics. Second, we formulate an optimization model that simultaneously considers fairness among concurrent requests while respecting various quantum resource constraints, and design efficient near-optimal heuristics to solve it. The proposed framework provides both theoretical insights and practical solutions for the design and management of future quantum networks.

ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Systems (SIGMETRICS)•Jun 4, 2025•0 citations

Information-theoretic Security in Practice

Stefan Raß

Information-theoretic secrecy is the strongest known security notion. Despite perfect secrecy being theoretically well-understood, one faces substantial practical difficulties when attempting to build communication systems providing this highest level of security. We consider two major approaches to perfectly secure communication: multipath transmission and quantum key distribution. The latter has seen a promising evolution over the last decades, culminating in the recent presentations of the world’s first real-life quantum networks. This book advocates a combination of the two techniques in order to complement each other and to overcome existing limitations in both worlds. Getting started with a graph-theoretic groundwork for multipath transmission networks, we continue by deriving results about multipath channel coding and interactive error correction. Based on game-theory, we introduce a general quantitative security valuation enjoying broad applicability. For a given network, the security measure indicates the quality of protection as well as it permits security infrastructure optimization. Both topics receive attention in dedicated chapters.

Südwestdeutscher Verlag für Hochschulschriften eBooks•Sep 12, 2010•0 citations
We present a general framework for casting the problem of designing secure quantum networks into a classical optimization problem. We introduce a measure of risk that serves as upper bound on the probability of loosing a message to the adversary. Based on this results, we can transform the problem of secure network design into an optimization procedure, which opens the field for the entire framework of optimization theory to tackle the problem most efficiently. The latter is particularly appealing, since we prove the problem to be NP-hard in general. Our methodology is formulated to yield results that have interpretations in probabilistic terms, but can be generalized to other settings in a straightforward manner. The modeling approach is simple, and naturally accounts for different notions of security, depending on the situation at hand. Furthermore, our results are not limited to security in quantum networks, as we rely on quantum cryptography only to the extent of securing links. Hence, the analysis is equally applicable for any (multipath) transmission setup, where information-theoretic security is demanded.
Unconditional security is the key-feature of quantum cryptography, which makes it superior to any classical encryption scheme. Most research in this area focuses on analyzing the theoretical properties and performance of particular quantum key distribution protocols, but a rigorous analysis on the network level seems to be missing. We present a game-theoretic approach which gives simple and tight bounds to the risk of communication that any two peers in a quantum network have to take when communicating, even if quantum cryptography is used. This work is motivated by recent (IM)possibility results regarding unconditionally secure message transmission in arbitrary networks, which puts stringent constraints on the network topology. Hence, our model naturally accounts for a given graph topology (existing fibre-optic networks which are natural candidates for a roll-out of a quantum network), as well as measuring risk in terms of probability or the designers subjective understanding. As a by-product, our model gives optimal path selection strategies, and the optimal design of network topologies under given constraints (like geographic or monetary ones).
Quantum key distribution is renowned for information-theoretic security on point-to-point connections, while it is by itself not directly capable of end-to-end security. Multipath transmission is known for perfect end-to-end security, provided that perfect point-to-point security is achievable. The marriage of the two is as natural as it is difficult to achieve in real life networks: secure multipath transmission imposes stringent requirements on the network connectivity, perhaps rarely found in a real-life network infrastructure. We consider the problem of network augmentation to support perfect end-to-end security in a network in which adjacent nodes share a perfectly confidential channel. Quantum networks are one example for this. Starting with a decision-theoretic formalization of risk and confidentiality, we cast the network augmentation task into a nonlinear optimization problem, whose computational complexity is studied. With the problem turning out NP-hard in at least two of its variants, we sketch heuristics that can help to keep calculations feasible in practical applications.
Quantum networks are essential infrastructure for enabling large-scale and long-distance quantum communications but face significant challenges in routing optimization and resource allocation due to their probabilistic nature and quantum resource limitations. Existing approaches typically tackle these problems in isolation, often by simply applying classical routing algorithms, maximizing the overall profit to allocate resources without considering fairness, or improving fairness in an ad-hoc way without a rigorous model. This paper proposes a general framework to systematically address these challenges. First, we conduct a thorough analysis of quantum network metrics using routing algebra as the mathematical foundation, and design provably optimal routing algorithms to tackle the unique challenges arising from their probabilistic characteristics. Second, we formulate an optimization model that simultaneously considers fairness among concurrent requests while respecting various quantum resource constraints, and design efficient near-optimal heuristics to solve it. The proposed framework provides both theoretical insights and practical solutions for the design and management of future quantum networks.
Quantum networks are essential infrastructure for enabling large-scale and long-distance quantum communications but face significant challenges in routing optimization and resource allocation due to their probabilistic nature and quantum resource limitations. Existing approaches typically tackle these problems in isolation, often by simply applying classical routing algorithms, maximizing the overall profit to allocate resources without considering fairness, or improving fairness in an ad-hoc way without a rigorous model. This paper proposes a general framework to systematically address these challenges. First, we conduct a thorough analysis of quantum network metrics using routing algebra as the mathematical foundation, and design provably optimal routing algorithms to tackle the unique challenges arising from their probabilistic characteristics. Second, we formulate an optimization model that simultaneously considers fairness among concurrent requests while respecting various quantum resource constraints, and design efficient near-optimal heuristics to solve it. The proposed framework provides both theoretical insights and practical solutions for the design and management of future quantum networks.
Quantum networks are essential infrastructure for enabling large-scale and long-distance quantum communications but face significant challenges in routing optimization and resource allocation due to their probabilistic nature and quantum resource limitations. Existing approaches typically tackle these problems in isolation, often by simply applying classical routing algorithms, maximizing the overall profit to allocate resources without considering fairness, or improving fairness in an ad-hoc way without a rigorous model. This paper proposes a general framework to systematically address these challenges. First, we conduct a thorough analysis of quantum network metrics using routing algebra as the mathematical foundation, and design provably optimal routing algorithms to tackle the unique challenges arising from their probabilistic characteristics. Second, we formulate an optimization model that simultaneously considers fairness among concurrent requests while respecting various quantum resource constraints, and design efficient near-optimal heuristics to solve it. The proposed framework provides both theoretical insights and practical solutions for the design and management of future quantum networks.
Information-theoretic secrecy is the strongest known security notion. Despite perfect secrecy being theoretically well-understood, one faces substantial practical difficulties when attempting to build communication systems providing this highest level of security. We consider two major approaches to perfectly secure communication: multipath transmission and quantum key distribution. The latter has seen a promising evolution over the last decades, culminating in the recent presentations of the world’s first real-life quantum networks. This book advocates a combination of the two techniques in order to complement each other and to overcome existing limitations in both worlds. Getting started with a graph-theoretic groundwork for multipath transmission networks, we continue by deriving results about multipath channel coding and interactive error correction. Based on game-theory, we introduce a general quantitative security valuation enjoying broad applicability. For a given network, the security measure indicates the quality of protection as well as it permits security infrastructure optimization. Both topics receive attention in dedicated chapters.