Title: Low complexity constructions of secret keys using polar coding.

We discuss two protocols to generate secret keys in the information theoretic model where Alice and Bob have private common randomness and use public communication. The protocols are based on polar coding techniques and afford several desirable attributes: (i) the computational complexity is O(nlog(n)) (ii) the strong secrecy capacity is achieved for any common randomness distribution (iii) the key construction is deterministic and uses one communication round. Extensions of the results to more general models are discussed.

Title: The Link between Secret Key Agreement and Network Coding

It is found that the problem of having multiple users agree on a common secret key by public discussion after observing a private distributed random source can be mapped to the problem of multicasting information over a communication network. The practical implication is that a network coding solution can solve the secret key agreement problem while the secret key agreement framework can generalize the graphical network link model and improve the secure network coding solution. Optimality is shown by new concepts in matroid theory, which relate a natural notion of mutual information for multiple random variables to the partition connectivity of linking systems. The matroidal structure for communication networks turns out to help identify some polynomial-time solutions and generalize the Menger's theorem for graphs to cyclic non-layered linking systems, which may have wide applications.

Title: On Interactive wireless network security

The fundamental tenet of information-theoretic security for wireless networks is that the legitimate receiver and the eavesdropper have different "views" (i.e., channels) of the transmitted signal. This poses a difficult challenge: how can we guarantee such channel conditions? In this talk, we start by studying simpler channel models, that can perhaps be instantiated in a controlled channel environment. The model is the erasure broadcast channel, with all nodes in the network experiencing statistically identical (but independent) erasures. We develop several results for interactive security for this model, including group key generation, message security and private message broadcasting. We will then describe our experience in validating some of these results through preliminary experimental results on a test bed.

Parts of this talk are joint work with Katerina Argyraki, Laszlo Czap, Christina Fragouli, Iris Safaka and Vinod Prabhakaran.

Title: Overcoming Weak Expectations

Recently, there has been renewed interest in basing cryptographic primitives on weak secrets, where the only information about the secret is some non-trivial amount of (min-)entropy. From a formal point of view, such results require to upper bound the expectation of some function f(X), where X is a weak source in question. We show an elementary inequality which essentially upper bounds such .FŽˇweak expectationŽ˘ by two terms, the first of which is independent of f, while the second only depends on the ŽˇvarianceŽ˘ of f under uniform distribution. Quite remarkably, as relatively simple corollaries of this elementary inequality, we obtain some "unexpected" results, in several cases noticeably simplifying/improving prior techniques for the same problem. Examples include non-malleable extractors, leakage-resilient symmetric encryption, seed-dependent condensers, improved entropy loss for the leftover hash lemma, and alternative to the dense model theorem.

Title: The Trade-off between Expected Key Consumption and Transmission Cost in EPS Systems

Shannon's fundamental bound for perfect secrecy stated that the entropy of the secret message U cannot be larger than the entropy of the secret key R shared by the sender and the legitimated receiver. Massey gave an information-theoretic proof of this result and the proof did not require U and R to be independent. By adding an extra assumption that I(U;R) = 0, we show a tighter bound on H(R) in this talk. Our bound states that the logarithm of the message sample size cannot be larger than the entropy of the secret key. We also consider the case that a perfect secrecy system is used multiple times. A new parameter, namely expected key consumption, is defined and justified. We show the existence of a fundamental trade-off between the expected key consumption and the number of channel uses for transmitting a cipher-text. A coding scheme, which is optimal under certain conditions, is introduced.

Title: Security of quantum key distribution with encoding on optical phase shift

Differential-phase-shift quantum key distribution (DPSQKD) protocol, which encodes a bit value onto the 0/180 phase shifts between adjacent pulses in the laser pulse train, attracts much attention due to its simplicity in the implementation. In contrast to conventional 'photon-based' protocols such as the BB84 protocol, the DPSQKD is expected to be inherently robust against photon-number splitting attacks even if a conventional light source (laser) is used. Despite the simplicity of the protocol itself, its security is quite hard to analyze because many pulses are chained together and cannot be separated in the theoretical treatment. Here we present a proof of its security against any attack by an eavesdropper by considering a virtual protocol that is complementary to the original protocol. In the virtual protocol, the sender tries to guess the position of the photon received by the receiver, which is complementary to the information on the phase shift used in the original protocol. Then the feasibility of the virtual protocol and the security of the original protocol are shown to be connected via the law of quantum mechanics.

Title: Almost-Everywhere Secure Computation with Edge Corruptions

We consider secure multi-party computation (MPC) in a setting where the adversary can separately corrupt not only the parties (nodes) but also the communication channels (edges), and can furthermore choose selectively and adaptively which edges or nodes to corrupt. Note that if an adversary corrupts an edge, even if the two nodes that share that edge are honest, the adversary can control the link and thus deliver wrong messages to both players. We consider this question in the information-theoretic setting, and require security against a computationally unbounded adversary.

In a fully connected network the above question is simple (and we also provide an answer that is optimal up to a constant factor). What makes the problem more challenging is to consider the case of sparse networks. Partially connected networks are far more realistic than fully connected networks, which led Garay and Ostrovsky [Eurocrypt'08] to formulate the notion of (unconditional) almost-everywhere (a.e.) secure computation in the node-corruption model, i.e., a model in which not all pairs of nodes are connected by secure channels and the adversary can corrupt some of the nodes (but not the edges). In such a setting, MPC amongst all honest nodes cannot be guaranteed due to the possible poor connectivity of some honest nodes with other honest nodes, and hence some of them must be "abandoned"' and left out of the computation. The number of such nodes is a function of the underlying communication graph and the adversarial set of nodes.

In this work we introduce the notion of almost-everywhere secure computation with edge corruptions, which is exactly the same problem as described above, except that we additionally allow the adversary to completely control some of the communication channels between two correct nodes---i.e., to "corrupt" edges in the network. While it is easy to see that an a.e. secure computation protocol for the original node-corruption model is also an a.e. secure computation protocol tolerating edge corruptions (albeit for a reduced fraction of edge corruptions with respect to the bound for node corruptions), no polynomial-time protocol is known in the case where a constant fraction of the edges can be corrupted (i.e., the maximum that can be tolerated) and the degree of the network is sub-linear. We make progress on this front, by constructing graphs of degree $O(n^\epsilon)$ (for arbitrary constant $0<\epsilon<1$) on which we can run a.e. secure computation protocols tolerating a constant fraction of adversarial edges. The number of given-up nodes in our construction is $\mu n$ (for some constant $0<\mu<1$ that depends on the fraction of corrupted edges), which is also asymptotically optimal.

This is joint work with Nishanth Chandran (MSR) and Rafail Ostrovsky (UCLA).

Title: Brief Encounters with Random Key Graphs

The notion of the random key graph (a.k.a. "uniform random intersection graph") was defined for probabilistic pre-distribution of cryptographic keys in wireless sensor networks. Connectivity properties of these graphs have been extensively analyzed and used for various applications that are unrelated to cryptographic key pre-distribution, during the past few years; e.g., cryptanalysis of hash functions, trust networks, recommender systems using collaborative filtering, and "small world" problems. Zero-one laws for k-connectivity of random key graphs have already been established. These applications, however, require that the network nodes have global visibility. That is, all nodes must be within direct communication range of each other.

In this presentation, I will review current results on the connectivity of random key graphs and define new desirable properties for cryptographic key pre-distribution when network nodes operate under physical link constraints; i.e., communication between nodes assures only local visibility among nodes. That is, a secure link exists between two nodes if and only if their key rings have at least one key in common and the physical link constraint between them is satisfied. In this setting, I will discuss new results for the standard on/off channel model, whereby the communication channel between two nodes has a probability pn of being on, and the disk model, whereby each node's transmission area is a disk of a uniform transmission range rn (where pn and rn are functions of the number of nodes n). I will also present new applications for random key graphs and open problems, where local visibility among nodes is of the essence.

This work is in collaboration with Jun Zhao and Osman Ya'an

Title: Interactive Secret-Key Generation From Channel Reciprocity

Channel reciprocity has been traditionally used to acquire channel state information at the transmitter (CSIT) in wireless systems. However, in recent years there has been a growing interest in using channel reciprocity for secret-key generation at the physical layer. Despite this, the associated information-theoretic limits have received limited attention in the literature. We study a two-way, non-coherent, block-fading channel model, where the channel gains in uplink and downlink are correlated and establish a new upper bound on the secret-key generation capacity. We also study a two-phase protocol that involves separate training and source-emulation stages, and establish its optimality in a certain asymptotic regimes. Numerical results show that unless the cross-correlation in uplink and downlink is close to 1, the source-emulation stage provides the dominant contribution to the overall secret-key rate and should be exploited in practical systems.

Title: Information Theoretic Security Based on Bounded Observability

A secure key distribution scheme based on correlated randomness is considered. Under the condition that all users can observe a common object, each using an observation function independently chosen from the same limited set of observation functions, Bounded Observability, which is necessary and sufficient conditions for users to be able to generate secret keys by public discussion, is introduced. Furthermore, a secure key distribution scheme based on correlated physical randomness in remote optical scramblers driven by common random light is introduced.

Title: Security in Malicious Environments: NSF's programs in Information-Theoretic Network Security.

This presentation will give an overview of NSF funding opportunities and some recent funding trends in information-theoretic network security.

Title: Reliable and Secure Message Transmission in Networks

We consider the problem of reliable and secure message transmission in a network setting where there are multiple node disjoint paths between the sender and the receiver with a subset of the paths being controlled by a Byzantine adversary. We give a formalization of reliability and security in this setting and discuss and propose constructions of 1-round protocols with optimal performance.

Title: Perfect Secrecy in Bidirectional Relaying

The XOR of two bits is independent of each one of them. This fact was used in the classical one-time pad to get perfect secrecy. The central question we ask is whether perfect secrecy arises in a similar fashion in other scenarios. Specifically, we consider compute-and-forward in bidirectional relaying, where a relay node wants to compute the XOR of two bits from two other nodes. In this scenario, the two nodes modulate their individual bits to integers and transmit them simultaneously. These integers get summed at the relay node. Is it possible to design the modulation such that the sum of the integers is independent of each of the bits? Can the sum still convey the XOR of the bits to the relay node? Can such a modulation be power-limited? We answer these questions in the affirmative and establish an achievable rate using lattice codes.

Joint work with Navin Kashyap and Shashank V at the Indian Institute of Science, Bangalore.

Title: Physical Layer Security: The Good, the Bad, and the Ugly

There has recently been a significant increase in the interest to apply the principles of information-theoretical security and signal processing to the design of secure physical layer systems. Although the community has made progress in understanding how the wireless fading channel can be exploited to establish secret and even authenticated communications, it is important to realize that there are many important issues that must be addressed if physical layer security is ever to be adopted by real and practical security systems. In this talk, we shall briefly review several different flavors of physical layer security (at least for wireless systems), highlight some interesting practical results, and then proceed to identify why the foundation for physical layer security is in fact not a firm foundation at all. The hope is to highlight new directions for the community to investigate, with the objective of keeping physical layer security research targeted on having a practical impact on real systems.

Title: Secure Degrees of Freedom of Wireless Networks

The secure d.o.f. of the canonical Gaussian wiretap channel is zero, indicating a severe penalty due to secrecy. It has been known for some time that a strictly positive secure d.o.f. can be obtained in the Gaussian wiretap channel by using a helper which sends structured cooperative signals. We show that the exact secure d.o.f. of the Gaussian wiretap channel with a helper is 1/2. We extend this result to the case of M helpers and show that the exact secure d.o.f. in this case is M/(M+1). We present generalizations to networks with multiple secure messages, such as, the Gaussian broadcast channel with confidential messages and helpers, the interference channel with confidential messages and helpers, and the multiple access wiretap channel, as well as, to multi-hop networks, such as, the two-unicast layered network. Our achievable schemes are based on interference alignment and cooperative jamming, which together render the message signal(s) and the cooperative jamming signal(s) separable at the legitimate receiver, but align them perfectly at the eavesdropper preventing any reliable decoding of the message signal(s). Our converse is based on two key lemmas. The first lemma quantifies the secrecy penalty by showing that the net effect of an eavesdropper on the system is that it eliminates one of the independent channel inputs. The second lemma quantifies the role of a helper by developing a direct relationship between the cooperative jamming signal of a helper and the message rate.

This work is jointly with Jianwei Xie.

Title: Information theoretic secret key generation in WiFi systems

This talk addresses secret key generation for communication in real world wireless channels. Considering the secrecy inherent in the reciprocal nature of such channels, we present a technique to generate an information theoretic secret key shared by two terminals observing signals over a common channel. Starting with techniques developed for jointly Gaussian secrets, we propose an approach that enables reliable secret key establishment for the typical WiFi channel. We focus on how the theoretical techniques are used and adopted to the real-world challenges. We further propose a way to enhance the current 802.11i using the generated secret key.

Title: Biometrics: Identification and Authentication

In this lecture we discuss the fundamental limits for biometric identification and authentication procedures. We consider unprotected but also protected storage of the templates. In the protected case we focus on privacy leakage. Fundamental limits corresponding to searching databases for identification are given. The relation between secret-key length and FAR is investigated for authentication with protected templates.