A Mobile World of Security | EPFL Graph Search

Security in mobile communications is a topic of increasing relevance in everyday life. We all use mobile devices for everyday communications, maybe even for exchanging confidential information with the work place. This requires security systems that are reliable and stable even though mobility and number of users are increasing. An established solution in today's systems is to use symmetric cryptographic systems by relying on pre-established secrets. There are a few drawbacks. The first problem is that all security information is stored in one central storage place. This implies that users are required to trust this storage place. They need to trust that data is properly handled and well protected. The mechanism of storing pre-established long-term secrets at a central storage also makes it vulnerable to adversaries. As soon as someone gains access to it, he automatically has access to all secret information necessary to capture communications. A second problem is that security mechanisms implemented in today's mobile communication systems were designed for a moderate number of users. Since then, the number of users has grown significantly and continues to do so. It would thus be desirable to have a system that is flexible in terms of the number of users it can handle. The third and maybe the most crucial problem is the fact that today's security systems rely on computational cryptography. This means that the security mechanisms in cellular communication systems were designed with limited computational power of the adversary in mind. However, the computational power of computers is growing and systems might be breakable in the near future. A complementary notion of security is information-theoretic security. Systems built in this spirit are unbreakable even with unlimited computational power. These systems exploit the knowledge of statistical properties of the environment. This means mainly that security systems can be proved to be secure with respect to assumptions on the correlated sources and with respect to the nature of the knowledge the adversary can gain. The main idea of information-theoretic security is that two communication partners have access to correlated random sources. An adversary being potentially present in the system, has only degraded access to the source. The common knowledge can be used in order to generate sequences that are very similar among each other. Because the adversary has access to the random source, he is able to generate his own version of the sequence. It is fundamental that the sequences of the communicationpartners are stronger correlated among each other than with respect to the adversary. This advantage in knowledge can be interpreted as a secret among the communication partners to the adversary. In communicating over an authenticated but public channel, this secret can be extracted from the original sequence by both parties. In order for both keys to be equal, the original sequences need to coincide. This is not necessarily the case, but can be achieved by discussion over the public channel. In the first part of this thesis, we propose a security system that relies on information-theoretic security. We will demonstrate how this system can be implemented in cellular communication systems. The movement of the users is random and we want to use it as a random source. We assume that users are moving along a random itinerary while visiting a random sequence of cells. Users not only visit cells in a random order, they also stay for a random time in each cells. It turns out that it is the sequence of durations that contributes most to the randomness of the sequence. We call the sequence of durations timing. This sequence is known to users and to the infrastructure, but only parts of it are known to potential adversaries. By recording the sequence of cells along with the time of residence, both the user and the infrastructure will be able to acquire very similar sequences. After the collection process, a procedure for key agreement is applied. Due to the underlying process, the key will not be uniformly distributed. As this is a requirement for perfect secret keys, a final part of the protocol is privacy amplification, where the perfectly secret bits will be extracted. This system is lightweight as it is based on readily available information and only a small amount of post-processing is required. In the second part of this thesis, we analyze the performance of the system. For this, we demonstrate how the process of bit collection can be analytically modeled. Our analysis leads to two conclusions. It gives us intuition about how to choose parameters such that the scheme performs optimally. Our scheme can be applied to settings that fulfill certain conditions. Conclusions from analysis allow to specify such conditions. We will show the implication of this conclusion in sketching some alternative applications of our scheme.

Access control and privacy in location-aware applications

Maria Luisa Damiani

The topic addressed in this thesis concerns the relationship between spatial knowledge and information protection in a mobile setting. The proliferation of mobile devices in an increasingly connected world raises growing concern for information security and privacy. For example, sensitive data recorded in corporate and networked information systems can be accessed from uncontrolled locations, downloaded on mobile terminals and disclosed to unauthorized third parties. The protection of information against improper use and modification in a mobile context poses research questions which solicit the investigation of unconventional protection strategies. In such a perspective, this thesis investigates how to provide strong control over information access based on knowledge of location and movement of individuals. Indeed, the use of spatial information for secure access support has been prospected in mid nineties, yet such a vision has not had a significant follow-up at research level. This work focuses on the definition of a comprehensive framework for the specification and enforcement of spatially-aware access control policies. Policies are spatially-aware in that the access authorization depends on the position of users. The core contribution of this work is the GEO-RBAC model, a role-based access control model that complies with current standards in access control and geo-spatial data representation. In addition, two further models have been specified, which are, to some extent, complementary to GEO-RBAC: the former is a decentralized administration model for the specification of GEO-RBAC access control policies in large organizations; the latter is a location privacy model which can be integrated into the GEO-RBAC framework to protect personal location information, for example in Location Based Services applications. The thesis addresses also issues related to the design of a system based on GEO-RBAC: an architecture has been defined based on which a prototype has been then developed. The use of geographical knowledge in security is a novel area of research and that motivates the existence of several open issues. Some of these have been discussed in the dissertation and a possible direction of research has been finally prospected for future activity.

EPFL2008

Rate allocation and optimized decoding in inter-session network coding

Eirina Bourtsoulatze

Recent advances in data processing and communication systems have led to a continuous increase in the amount of data communicated over today’s networks. These large volumes of data pose new challenges on the current networking infrastructure that only offers a best effort mechanism for data delivery. The emergence of new distributed network architectures, such as peer-to-peer networks and wireless mesh networks, and the need for efficient data delivery mechanisms have motivated researchers to reconsider the way that information is communicated and processed in the networks. This has given rise to a new research field called network coding. The network coding paradigm departs from the traditional routing principle where information is simply relayed by the network nodes towards the destination, and introduces some intelligence in the network through coding at the intermediate nodes. This in-network data processing has been proved to substantially improve the performance of data delivery systems in terms of throughput and error resilience in networks with high path diversity. Motivated by the promising results in the network coding research, we focus in this thesis on the design of network coding algorithms for simultaneous transmission of multiple data sources in overlay networks. We investigate several problems that arise in the context of inter-session network coding, namely (i) decoding delay minimization in inter-session network coding, (ii) distributed rate allocation for inter-session network coding and (iii) correlation-aware decoding of incomplete network coded data. We start by proposing a novel framework for data delivery from multiple sources to multiple clients in an overlay wireline network, where intermediate nodes employ randomized inter-session network coding. We consider networks with high resource diversity, which creates network coding opportunities with possibly large gains in terms of throughput, delay and error robustness. However, the coding operations in the intermediate nodes must be carefully designed in order to enable efficient data delivery. We look at the problem from the decoding delay perspective and design solutions that lead to a small decoding delay at clients through proper coding and rate allocation. We cast the optimization problem as a rate allocation problem, which seeks for the coding operations that minimize the average decoding delay in the client population. We demonstrate the validity of our algorithm through simulations in representative network topologies. The results show that an effective combination of intra- and inter-session network coding based on randomized linear coding permits to reach small decoding delays and to better exploit the available network resources even in challenging network settings. Next, we design a distributed rate allocation algorithm where the users decide locally how many intra- and inter-session network coded packets should be requested from the parent nodes in order to get minimal decoding delay. The capability to take coding decisions locally with only a partial knowledge of the network statistics is of crucial importance for applications where users are organized in dynamic overlay networks. We propose a receiver-driven communication protocol that operates in two rounds. First, the users request and obtain information regarding the network conditions and packet availability in their local neighborhood. Then, every user independently optimizes the rate allocation among different possible intra- and inter-session packet combinations to be requested from its parents. We also introduce the novel concept of equivalent flows, which permits to efficiently estimate the expected number of packets that are necessary for decoding and hence to simplify the rate allocation process. Experimental results indicate that our algorithm is capable of eliminating the bottlenecks and reducing the decoding delay of users with limited resources. We further investigate the application of the proposed distributed rate allocation algorithm to the transmission of video sequences and validate the performance of our system using the NS-3 simulator. The simulation results show that the proposed rate allocation algorithm is successful in improving the quality of the delivered video compared to intra-session network coding based solutions. Finally, we investigate the problem of decoding the source information from an incomplete set of network coded data with the help of source priors in a finite algebraic field. The inability to form a complete decoding system can be often caused by transmission losses or timing constraints imposed by the application. In this case, exact reconstruction of the source data by conventional algorithms such as Gaussian elimination is not feasible; however, partial recovery of the source data may still be possible, which can be useful in applications where approximate reconstruction is informative. We use the statistical characteristics of the source data in order to perform approximate decoding. We first analyze the performance of a hypothetical maximum a posteriori decoder, which recovers the source data from an incomplete set of network coded data given the joint statistics of the sources. We derive an upper bound on the probability of erroneous source sequence decoding as a function of the system parameters. We then propose a constructive solution to the approximate decoding problem and design an iterative decoding algorithm based on message passing, which jointly considers the network coding and the correlation constraints. We illustrate the performance of our decoding algorithm through extensive simulations on synthetic and real data sets. The results demonstrate that, even by using a simple correlation model expressed as a correlation noise between pairs of sources, the original source data can be partially decoded in practice from an incomplete set of network coded symbols. Overall, this thesis addresses several important issues related to the design of efficient data delivery methods with inter-session network coding. Our novel framework for decoding delay minimization can impact the development of practical inter-session network coding algorithms that are appropriate for applications with low delay requirements. Our rate allocation algorithms are able to exploit the high resource diversity of modern networking systems and represent an effective alternative in the development of distributed communication systems. Finally, our algorithm for data recovery from incomplete network coded data using correlation priors can contribute significantly to the improvement of the delivered data quality and provide new insights towards the design of joint source and network coding algorithms.

EPFL2013

High-Dimensional Inference on Dense Graphs with Applications to Coding Theory and Machine Learning

Mohamad Baker Dia

We are living in the era of "Big Data", an era characterized by a voluminous amount of available data. Such amount is mainly due to the continuing advances in the computational capabilities for capturing, storing, transmitting and processing data. However, it is not always the volume of data that matters, but rather the "relevant" information that resides in it. Exactly 70 years ago, Claude Shannon, the father of information theory, was able to quantify the amount of information in a communication scenario based on a probabilistic model of the data. It turns out that Shannon's theory can be adapted to various probability-based information processing fields, ranging from coding theory to machine learning. The computation of some information theoretic quantities, such as the mutual information, can help in setting fundamental limits and devising more efficient algorithms for many inference problems. This thesis deals with two different, yet intimately related, inference problems in the fields of coding theory and machine learning. We use Bayesian probabilistic formulations for both problems, and we analyse them in the asymptotic high-dimensional regime. The goal of our analysis is to assess the algorithmic performance on the first hand and to predict the Bayes-optimal performance on the second hand, using an information theoretic approach. To this end, we employ powerful analytical tools from statistical physics. The first problem is a recent forward-error-correction code called sparse superposition code. We consider the extension of such code to a large class of noisy channels by exploiting the similarity with the compressed sensing paradigm. Moreover, we show the amenability of sparse superposition codes to perform joint distribution matching and channel coding. In the second problem, we study symmetric rank-one matrix factorization, a prominent model in machine learning and statistics with many applications ranging from community detection to sparse principal component analysis. We provide an explicit expression for the normalized mutual information and the minimum mean-square error of this model in the asymptotic limit. This allows us to prove the optimality of a certain iterative algorithm on a large set of parameters. A common feature of the two problems stems from the fact that both of them are represented on dense graphical models. Hence, similar message-passing algorithms and analysis tools can be adopted. Furthermore, spatial coupling, a new technique introduced in the context of low-density parity-check (LDPC) codes, can be applied to both problems. Spatial coupling is used in this thesis as a "construction technique" to boost the algorithmic performance and as a "proof technique" to compute some information theoretic quantities. Moreover, both of our problems retain close connections with spin glass models studied in statistical mechanics of disordered systems. This allows us to use sophisticated techniques developed in statistical physics. In this thesis, we use the potential function predicted by the replica method in order to prove the threshold saturation phenomenon associated with spatially coupled models. Moreover, one of the main contributions of this thesis is proving that the predictions given by the "heuristic" replica method are exact. Hence, our results could be of great interest for the statistical physics community as well, as they help to set a rigorous mathematical foundation of the replica predictions.

EPFL2018