**Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?**

Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur GraphSearch.

Publication# Secure Communication in Erasure Networks with State-feedback

Résumé

The security and efficiency of communication are two of the main concerns for networks of today and the future. Our understanding of how to efficiently send information over various channels and networks has significantly increased in the past decade (see e.g., [1–3]), whereas our understanding of how to securely send information has not yet reached the same level. In this thesis, we advance the theory of secure communication by deriving capacity results and by developing coding schemes that provide information-theoretic security for erasure networks. We characterize the highest achievable secret-message rate in the presence of an eavesdropping adversary in various settings, where communication takes place over erasure channels with state-feedback. Our results provide such a characterization for a point-to-point erasure channel, for a broadcast erasure channel with multiple receivers, for a network with multiple parallel channels, a V-network and for a triangle network. We introduce several two-phase secure coding schemes that consist of a key generation phase and an encrypted message sending phase. Our schemes leverage several resources for security: channel erasures, feedback, common randomness and the topology of the network. We present coding schemes for all the above mentioned settings as well as for erasure networks with arbitrary topology. In all the cases where we provide exact characterization, a two-phase scheme achieves the secret-message capacity. All our proposed coding schemes use only linear operations and thus can serve as a basis for practical code designs. For networks, we develop a linear programming framework for describing secure coding schemes and for deriving new outer bounds. We use linear programs to describe our schemes and to prove their optimality. We derive new information theoretic outer bounds. In our intuitive interpretation, our proofs find the connection between the rate of the message and the rate of a secret key that is required to secure the message. Our results reveal nontrivial characteristics of secure communication in erasure networks. We find that – in contrast to non-secure communication – the secret message capacity of a cut does not simplify to the sum of the capacities of the channels that form the cut, moreover, the secret message capacity of a network does not simplify to the minimum secret message capacity of its cuts.

Official source

Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.

Concepts associés

Chargement

Publications associées

Chargement

Concepts associés (30)

Canal de communication (théorie de l'information)

vignette
En théorie de l'information, un canal de communication ou canal de transmission est un support (physique ou non) permettant la transmission d'une certaine quantité d'information, depuis une s

Optimisation linéaire

thumb|upright=0.5|Optimisation linéaire dans un espace à deux dimensions (x1, x2). La fonction-coût fc est représentée par les lignes de niveau bleues à gauche et par le plan bleu à droite. L'ensemble

Rétroaction

vignette|Représentation d'une boucle de rétroaction.
La rétroaction (en anglais feedback) est un processus dans lequel un effet intervient aussi comme agent causal sur sa propre origine, la séquence

Publications associées (87)

Chargement

Chargement

Chargement

An active distribution network (ADN) is an electrical-power distribution network that implements a real-time monitoring and control of the electrical resources and the grid. Effective monitoring and control is realised by deploying a large number of sensing and actuating devices and a communication network to facilitates the two-way transfer of data. The reliance of ADN operations on a large number of electronic devices and on communication networks poses a challenge in protecting the system against cyber-attacks. Identifying these challenges and commissioning appropriate solutions is of utmost importance to realize the full potential of a smart grid that seamlessly integrates distributed generation, such as renewable energy sources. As a first step, we perform a thorough threat analysis of a typical ADN. We identify potential threats against field devices, the communication infrastructure and servers at control centers. We also propose a check-list of security solutions and best practices that guarantee a distribution network's resilient operation in the presence of malicious attackers, natural disasters, and other unintended failures that could potentially lead to islanded communication zone. For the next step, we investigate the security of MPLS-TP, a technology that is mainly used for long-distance inter-domain communication in smart grid. We find that an MPLS-TP implementation in Cisco IOS has serious security vulnerabilities in two of its protocols, BFD and PSC. These two protocols control protection-switching features in MPLS-TP. In our test-bed, we demonstrate that an attacker who has physical access to the network can exploit the vulnerabilities in order to inject forged BFD or PSC messages that affect the network's availability. Third, we consider multicast source authentication for synchrophasor data communication in grid monitoring systems (GMS). Ensuring source authentication without violating the stringent real-time requirement of GMS is challenging. Through an extensive review of existing schemes, we identified a set of schemes that satisfy some desirable requirements for GMS. The identified schemes are ECDSA, TV-HORS and Incomplete- key-set. We experimentally compared these schemes using computation, communication and key management overheads as performance metrics. A tweak in ECDSA's implementation to make it use pre-generated tokens to generate signatures significantly improves the computation overhead of ECDSA, making it the preferred scheme for GMS. This finding is contrary to the generally accepted view that asymmetric cryptography is inapplicable for real-time systems. Finally, we studied a planning problem that arises when a utility wants to roll out a software patch that requires rebooting to all PMUs while maintaining system observability. The problem we address is how to find a partitioning of the set of the deployed PMUs into as few subsets as possible such that all the PMUs in one subset can be patched in one round while all the PMUs in the other subsets provide full observability. We show that the problem is NP-complete in the general case and and formulated it as binary integer linear programming (BILP) problem. We have also provided an heuristic algorithm to find an approximate solution. Furthermore, we have identified a special case of the problem where the grid is a tree and provided a polynomial-time algorithm that finds an optimal patching plan that requires only two rounds to patch the PMUs.

Wireless adhoc networks consist of users that want to communicate with each other over a shared wireless medium. The users have transmitting and receiving capabilities but there is no additional infrastructure for assisting communication. This is in contrast to existing wireless systems, cellular networks for example, where communication between wireless users heavily relies on an additional infrastructure of base stations connected with a high-capacity wired backbone. The fact that they are infrastructureless makes wireless adhoc networks inexpensive, easy to build and robust but at the same time technically more challenging. The fundamental challenge is how to deal with interference: many simultaneous transmissions have to be accommodated on the same wireless channel when each of these transmissions constitutes interference for the others, degrading the quality of the communication. The traditional approach to wireless adhoc networks is to organize users so that they relay information for each other in a multi-hop fashion. Such multi-hopping strategies face scalability problems at large system size. As shown by Gupta and Kumar in their seminal work in 2000, the maximal communication rate per user under such strategies scales inversely proportional to the square root of the number of users in the network, hence decreases to zero with increasing system size. This limitation is due to interference that precludes having many simultaneous point-to-point transmissions inside the network. In this thesis, we propose a multiscale hierarchical cooperation architecture for distributed MIMO communication in wireless adhoc networks. This novel architecture removes the interference limitation at least as far as scaling is concerned: we show that the per-user communication rate under this strategy does not degrade significantly even if there are more and more users entering into the network. This is in sharp contrast to the performance achieved by the classical multi-hopping schemes. However, the overall picture is much richer than what can be depicted by a single scheme or a single scaling law formula. Nowadays, wireless adhoc networks are considered for a wide range of practical applications and this translates to having a number of system parameters (e.g., area, power, bandwidth) with large operational range. Different applications lie in different parameter ranges and can therefore exhibit different characteristics. A thorough understanding of wireless adhoc networks can only be obtained by exploring the whole parameter space. Existing scaling law formulations are insufficient for this purpose as they concentrate on very small subsets of the system parameters. We propose a new scaling law formulation for wireless adhoc networks that serves as a mathematical tool to characterize their fundamental operating regimes. For the standard wireless channel model where signals are subject to power path-loss attenuation and random phase changes, we identify four qualitatively different operating regimes in wireless adhoc networks with large number of users. In each of these regimes, we characterize the dependence of the capacity on major system parameters. In particular, we clarify the impact of the power and bandwidth limitations on performance. This is done by deriving upper bounds on the information theoretic capacity of wireless adhoc networks in Chapter 3, and constructing communication schemes that achieve these upper bounds in Chapter 4. Our analysis identifies three engineering quantities that together determine the operating regime of a given wireless network: the short-distance signal-to-noise power ratio (SNRs), the long-distance signal-to-noise power ratio (SNRl) and the power path-loss exponent of the environment. The right communication strategy for a given application is dictated by its operating regime. We show that conventional multi-hopping schemes are optimal when the power path-loss exponent of the environment is larger than 3 and SNRs ≪ 0 dB. Such networks are extremely power-limited. On the other hand, the novel architecture proposed in this thesis, based on hierarchical cooperation and distributed MIMO, is the fundamentally right strategy for wireless networks with SNRl ≫ 0 dB. Such networks experience no power limitation. In the intermediate cases, captured by the remaining two operating regimes, neither multi-hopping nor hierarchical-MIMO achieves optimal performance. We construct new schemes for these regimes that achieve capacity. The proposed characterization of wireless adhoc networks in terms of their fundamental operating regimes, is analogous to the familiar understanding of the two operating regimes of the point-to-point additive white Gaussian noise (AWGN) channel. From an engineering point of view, one of the most important contributions of Shannon's celebrated capacity formula is to identify two qualitatively different operating regimes on this channel. Determined by its signal-to-noise power ratio (SNR), an AWGN channel can be either in a bandwidth-limited (SNR ≫ 0 dB) or a power-limited (SNR ≪ 0 dB) regime. Communication system design for this channel has been primarily driven by the operating regime one is in.

Shannon, in his landmark 1948 paper, developed a framework for characterizing the fundamental limits of information transmission. Among other results, he showed that reliable communication over a channel is possible at any rate below its capacity. In 2008, Arikan discovered polar codes; the only class of explicitly constructed low-complexity codes that achieve the capacity of any binary-input memoryless symmetric-output channel. Arikan's polar transform turns independent copies of a noisy channel into a collection of synthetic almost-noiseless and almost-useless channels. Polar codes are realized by sending data bits over the almost-noiseless channels and recovering them by using a low-complexity successive-cancellation (SC) decoder, at the receiver. In the first part of this thesis, we study polar codes for communications. When the underlying channel is an erasure channel, we show that almost all correlation coefficients between the erasure events of the synthetic channels decay rapidly. Hence, the sum of the erasure probabilities of the information-carrying channels is a tight estimate of the block-error probability of polar codes when used for communication over the erasure channel. We study SC list (SCL) decoding, a method for boosting the performance of short polar codes. We prove that the method has a numerically stable formulation in log-likelihood ratios. In hardware, this formulation increases the decoding throughput by 53% and reduces the decoder's size about 33%. We present empirical results on the trade-off between the length of the CRC and the performance gains in a CRC-aided version of the list decoder. We also make numerical comparisons of the performance of long polar codes under SC decoding with that of short polar codes under SCL decoding. Shannon's framework also quantifies the secrecy of communications. Wyner, in 1975, proposed a model for communications in the presence of an eavesdropper. It was shown that, at rates below the secrecy capacity, there exist reliable communication schemes in which the amount of information leaked to the eavesdropper decays exponentially in the block-length of the code. In the second part of this thesis, we study the rate of this decay. We derive the exact exponential decay rate of the ensemble-average of the information leaked to the eavesdropper in Wyner's model when a randomly constructed code is used for secure communications. For codes sampled from the ensemble of i.i.d. random codes, we show that the previously known lower bound to the exponent is exact. Our ensemble-optimal exponent for random constant-composition codes improves the lower bound extant in the literature. Finally, we show that random linear codes have the same secrecy power as i.i.d. random codes. The key to securing messages against an eavesdropper is to exploit the randomness of her communication channel so that the statistics of her observation resembles that of a pure noise process for any sent message. We study the effect of feedback on this approximation and show that it does not reduce the minimum entropy rate required to approximate a given process. However, we give examples where variable-length schemes achieve much larger exponents in this approximation in the presence of feedback than the exponents in systems without feedback. Upper-bounding the best exponent that block codes attain, we conclude that variable-length coding is necessary for achieving the improved exponents.