Scalable Bias-Resistant Distributed Randomness

Bias-resistant public randomness is a critical component in many (distributed) protocols. Existing solutions do not scale to hundreds or thousands of participants, as is needed in many decentralized systems. We propose two large-scale distributed protocols, RandHound and RandHerd, which provide publicly-verifiable, unpredictable, and unbiasable randomness against Byzantine adversaries. RandHound relies on an untrusted client to divide a set of randomness servers into groups for scalability, and it depends on the pigeonhole principle to ensure output integrity, even for non-random, adversarial group choices. RandHerd implements an efficient, decentralized randomness beacon. RandHerd is structurally similar to a BFT protocol, but uses RandHound in a one-time setup to arrange participants into verifiably unbiased random secret-sharing groups, which then repeatedly produce random output at predefined intervals. Our prototype demonstrates that RandHound and RandHerd achieve good performance across hundreds of participants while retaining a low failure probability by properly selecting protocol parameters, such as a group size and secret-sharing threshold. For example, when sharding 512 nodes into groups of 32, our experiments show that RandHound can produce fresh random output after 240 seconds. RandHerd, after a setup phase of 260 seconds, is able to generate fresh random output in intervals of approximately 6 seconds. For this configuration, both protocols operate at a failure probability of at most 0.08% against a Byzantine adversary.

A Mobile World of Security

Christine Neuberg

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.

EPFL2011

Contracts for Real-Time, Safety Critical Systems

Chandrakana Nandi

Verifying real-time systems goes beyond the verification of functional properties: it also requires the checking of real-time properties. This makes traditional contract-frameworks partially inept for checking real-time programs. This is a major problem because the failure of real-time and safety critical systems can have serious consequences. This thesis presents a solution to this problem by incorporating Design by Contract (annotating programs with function pre and post conditions) to such systems. The main contribution of this thesis is the development of a contract framework for cyclic real-time control applications written in C++. The contract framework allows the users to specify both functional and temporal properties for the applications. A novel approach of empirical cumulative distribution function (cdf ) based statistical inference is used for dynamically estimating temporal constraints and incorporating them in future contracts. The thesis also illustrates the use of Real-time Logic (RTL) for formal specification of the temporal properties. For evaluating our methodology, we have integrated it to a component-based framework called FASA (Future Automation System Architecture) developed at ABB Corporate Research for writing hard real time control applications. Experiments show that this contract framework can be smoothly integrated to existing control applications thereby increasing their reliability while having a acceptable overhead (less than 10%) on the performance.

2014

Multilingual Training and Adaptation in Speech Recognition

Sibo Tong

State-of-the-art acoustic models for Automatic Speech Recognition (ASR) are based on Hidden Markov Models (HMM) and Deep Neural Networks (DNN) and often require thousands of hours of transcribed speech data during training. Therefore, building multilingual ASR systems or systems on a language with few resources is a challenging task. Multilingual training and cross-lingual adaptation are potential solutions. However, context-dependent states modeling creates difficulties for multilingual and cross-lingual ASR because of the large increase in context dependent labels arising from the phone set mismatch. The goal of this thesis is to improve current state-of-the-art acoustic modeling techniques in general for ASR, with a particular focus on multilingual ASR and cross-lingual adaptation. We systematically exploited new training frameworks, from Maximum Likelihood Estimation, Connectionist Temporal Classification to Maximum Mutual Information, in the context of phoneme-based multilingual training. In order to minimize the negative effects of data impurity arising from language mismatch, we investigated language adaptive training approaches which help further improve the multilingual ASR performance. Through comprehensive experimental comparison we demonstrated that phoneme-based multilingual models are easily extensible to unseen phonemes of new languages, from which the cross-lingual adaptation yields significant improvement over traditional approaches on limited data. Finally, we proposed a semi-supervised training approach based on dropout to boost the performance in low-resourced languages using untranscribed data. In the other part of the thesis, we conducted more theoretical analysis of techniques found to be useful in sequential multilingual training. More specifically, we revisited the recurrent architecture based on Bayesâs theorem. This leads to a Bayesian recurrent unit dictated by the probabilistic formulation and naturally support a backward recursion. Experiments show that the proposed architecture exceeds the performance of conventional recurrent network. Together, this thesis constitutes a thorough analysis of the current field. Through theoretical and experimental comparisons, the proposed approaches are shown to yield significant improvement over the conventional hybrid systems on multilingual speech recognition.