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

IEEE International Symposium on Information Theory (ISIT)

LP formulations for secrecy over erasure networks with feedback

Athanasios Papadopoulos, László Czap, Christina Fragouli

Published Jun 1, 2015• 7 citations
Publisher

Abstract

We design polynomial time schemes for secure message transmission over arbitrary networks, in the presence of an eavesdropper, and where each edge corresponds to an erasure channel with public feedback. Our schemes are described through linear programming (LP) formulations, that explicitly select (possibly different) sets of paths for key-generation and message sending. Although our LPs are not always capacity-achieving, they outperform the best known alternatives in the literature, and extend to incorporate several interesting scenaria.

DOI
10.1109/isit.2015.7282596

Related papers

LP formulations for secrecy over erasure networks with feedback

Papadopoulos, Athanasios, László Czap, Christina Fragouli

We design polynomial time schemes for secure message transmission over arbitrary networks, in the presence of an eavesdropper, and where each edge corresponds to an erasure channel with public feedback. Our schemes are described through linear programming (LP) formulations, that explicitly select (possibly different) sets of paths for key-generation and message sending. Although our LPs are not always capacity-achieving, they outperform the best known alternatives in the literature, and extend to incorporate several interesting scenaria.

arXiv:1504.06593•Apr 24, 2015•0 citations

Achievable secrecy in arbitrary erasure networks with feedback

László Czap, Athanasios Papadopoulos, Christina Fragouli

We present achievability schemes for secure message transmission in the presence of a passive eavesdropper, over arbitrary networks, where each edge corresponds to an independent erasure channel and we have available public channel state feedback. Our schemes are efficiently described through linear programming formulations, that generalize the information flow linear programs to networks with security constraints; different sources of secrecy show up as parameters in our linear programs, and solving the optimization problem enables to select the optimal (in terms of rate) scheme that integrates them. As far as we know, these are the first linear programming formulations for secret message transmission over arbitrary networks with erasures and channel state feedback.

IEEE Global Conference on Signal and Information Processing•Dec 1, 2014•2 citations

An LP Characterization of the Secret-message Capacity of Three Erasure Networks With Feedback

László Czap, Vinod M. Prabhakaran, Christina Fragouli +1 more

This paper presents exact capacity characterizations for the case, when a principal, Alice, wants to securely send a message to another principal, Bob, over three network configurations: the parallel edges network, the V-network, and the triangle network. We assume that: 1) a passive eavesdropper, Eve, overhears any one edge in the network; 2) each edge corresponds to an independent broadcast packet erasure channel with arbitrary erasure probabilities; and 3) all legitimate nodes can publicly but causally acknowledge whether they received each packet or not. We develop optimal achievability schemes that are expressed as linear programs (LPs) and share a two-phase structure, where at the first phase, we create secret keys, and at the second phase, we use them to encrypt the transmitted message. Our outer bounds are also expressed through LP formulations. We prove that our schemes are optimal by showing that the optimal solution of the outer bound LP and the optimal solution of the achievability scheme LP coincide.

IEEE Transactions on Information Theory•Mar 23, 2016•0 citations

Secret Communication Over Broadcast Erasure Channels With State-Feedback

László Czap, Vinod M. Prabhakaran, Christina Fragouli +1 more

We consider a 1-to-K communication scenario, where a source transmits private messages to K receivers through a broadcast erasure channel, and the receivers feedback strictly, causally, and publicly their channel states after each transmission. We explore the achievable rate region when we require that the message to each receiver remains secret-in the information theoretical sense-from all the other receivers. We characterize the capacity of secure communication in all the cases where the capacity of the 1-to-K communication scenario without the requirement of security is known. As a special case, we characterize the secret-message capacity of a single receiver point-to-point erasure channel with public state-feedback in the presence of a passive eavesdropper. We find that in all the cases where we have an exact characterization, we can achieve the capacity using linear complexity two-phase schemes: in the first phase, we create appropriate secret keys, and in the second phase, we use them to encrypt each message. We find that the amount of key we need is smaller than the size of the message, and equal to the amount of encrypted message the potential eavesdroppers jointly collect. Moreover, we prove that a dishonest receiver that provides deceptive feedback cannot diminish the rate experienced by the honest receivers. We also develop a converse proof which reflects the two-phase structure of our achievability scheme. As a side result, our technique leads to a new outer bound proof for the nonsecure communication problem.

IEEE Transactions on Information Theory•Jul 22, 2015•16 citations

Secret message capacity of a line network

Papadopoulos, Athanasios, László Czap, Christina Fragouli

We investigate the problem of information theoretically secure communication in a line network with erasure channels and state feedback. We consider a spectrum of cases for the private randomness that intermediate nodes can generate, ranging from having intermediate nodes generate unlimited private randomness, to having intermediate nodes generate no private randomness, and all cases in between. We characterize the secret message capacity when either only one of the channels is eavesdropped or all of the channels are eavesdropped, and we develop polynomial time algorithms that achieve these capacities. We also give an outer bound for the case where an arbitrary number of channels is eavesdropped. Our work is the first to characterize the secrecy capacity of a network of arbitrary size, with imperfect channels and feedback. As a side result, we derive the secret key and secret message capacity of an one-hop network, when the source has limited randomness.

arXiv:1407.1922•Jul 8, 2014•1 citation

Secret message capacity of a line network

Athanasios Papadopoulos, László Czap, Christina Fragouli

We investigate the problem of information theoretically secure communication in a line network with erasure channels and state feedback. We consider a spectrum of cases for the private randomness that intermediate nodes can generate, ranging from having intermediate nodes generate unlimited private randomness, to having intermediate nodes generate no private randomness, and all cases in between. We characterize the secret message capacity when either only one of the channels is eavesdropped or all of the channels are eavesdropped, and we develop polynomial time algorithms that achieve these capacities. We also give an outer bound for the case where an arbitrary number of channels is eavesdropped. Our work is the first to characterize the secrecy capacity of a network of arbitrary size, with imperfect channels and feedback.

Allerton Conference on Communication, Control, and Computing•Sep 1, 2014•6 citations
We design polynomial time schemes for secure message transmission over arbitrary networks, in the presence of an eavesdropper, and where each edge corresponds to an erasure channel with public feedback. Our schemes are described through linear programming (LP) formulations, that explicitly select (possibly different) sets of paths for key-generation and message sending. Although our LPs are not always capacity-achieving, they outperform the best known alternatives in the literature, and extend to incorporate several interesting scenaria.
We design polynomial time schemes for secure message transmission over arbitrary networks, in the presence of an eavesdropper, and where each edge corresponds to an erasure channel with public feedback. Our schemes are described through linear programming (LP) formulations, that explicitly select (possibly different) sets of paths for key-generation and message sending. Although our LPs are not always capacity-achieving, they outperform the best known alternatives in the literature, and extend to incorporate several interesting scenaria.
We present achievability schemes for secure message transmission in the presence of a passive eavesdropper, over arbitrary networks, where each edge corresponds to an independent erasure channel and we have available public channel state feedback. Our schemes are efficiently described through linear programming formulations, that generalize the information flow linear programs to networks with security constraints; different sources of secrecy show up as parameters in our linear programs, and solving the optimization problem enables to select the optimal (in terms of rate) scheme that integrates them. As far as we know, these are the first linear programming formulations for secret message transmission over arbitrary networks with erasures and channel state feedback.
This paper presents exact capacity characterizations for the case, when a principal, Alice, wants to securely send a message to another principal, Bob, over three network configurations: the parallel edges network, the V-network, and the triangle network. We assume that: 1) a passive eavesdropper, Eve, overhears any one edge in the network; 2) each edge corresponds to an independent broadcast packet erasure channel with arbitrary erasure probabilities; and 3) all legitimate nodes can publicly but causally acknowledge whether they received each packet or not. We develop optimal achievability schemes that are expressed as linear programs (LPs) and share a two-phase structure, where at the first phase, we create secret keys, and at the second phase, we use them to encrypt the transmitted message. Our outer bounds are also expressed through LP formulations. We prove that our schemes are optimal by showing that the optimal solution of the outer bound LP and the optimal solution of the achievability scheme LP coincide.
We consider a 1-to-K communication scenario, where a source transmits private messages to K receivers through a broadcast erasure channel, and the receivers feedback strictly, causally, and publicly their channel states after each transmission. We explore the achievable rate region when we require that the message to each receiver remains secret-in the information theoretical sense-from all the other receivers. We characterize the capacity of secure communication in all the cases where the capacity of the 1-to-K communication scenario without the requirement of security is known. As a special case, we characterize the secret-message capacity of a single receiver point-to-point erasure channel with public state-feedback in the presence of a passive eavesdropper. We find that in all the cases where we have an exact characterization, we can achieve the capacity using linear complexity two-phase schemes: in the first phase, we create appropriate secret keys, and in the second phase, we use them to encrypt each message. We find that the amount of key we need is smaller than the size of the message, and equal to the amount of encrypted message the potential eavesdroppers jointly collect. Moreover, we prove that a dishonest receiver that provides deceptive feedback cannot diminish the rate experienced by the honest receivers. We also develop a converse proof which reflects the two-phase structure of our achievability scheme. As a side result, our technique leads to a new outer bound proof for the nonsecure communication problem.
We investigate the problem of information theoretically secure communication in a line network with erasure channels and state feedback. We consider a spectrum of cases for the private randomness that intermediate nodes can generate, ranging from having intermediate nodes generate unlimited private randomness, to having intermediate nodes generate no private randomness, and all cases in between. We characterize the secret message capacity when either only one of the channels is eavesdropped or all of the channels are eavesdropped, and we develop polynomial time algorithms that achieve these capacities. We also give an outer bound for the case where an arbitrary number of channels is eavesdropped. Our work is the first to characterize the secrecy capacity of a network of arbitrary size, with imperfect channels and feedback. As a side result, we derive the secret key and secret message capacity of an one-hop network, when the source has limited randomness.
We investigate the problem of information theoretically secure communication in a line network with erasure channels and state feedback. We consider a spectrum of cases for the private randomness that intermediate nodes can generate, ranging from having intermediate nodes generate unlimited private randomness, to having intermediate nodes generate no private randomness, and all cases in between. We characterize the secret message capacity when either only one of the channels is eavesdropped or all of the channels are eavesdropped, and we develop polynomial time algorithms that achieve these capacities. We also give an outer bound for the case where an arbitrary number of channels is eavesdropped. Our work is the first to characterize the secrecy capacity of a network of arbitrary size, with imperfect channels and feedback.