Title: Noisy Connections: A Survey of Interactive Coding and its Borders with Other Topics

We will discuss the task of interactive coding between two parties as introduced by Schulman, surveying some recent advances in protocols, as well as extensions to the multiparty setting and interactive proofs.

Title: On the Computational Security of the Static Distributed Storage System

We study the secrecy of a static distributed storage system for passwords. The encoder, Alice, observes a length-n password and describes it using δ s-bit hints, which she stores in different locations. The legitimate receiver, Bob, observes ν of those hints. In one scenario we require that the number of guesses it takes Bob to guess the password approach 1 as n tends to infinity and in the other that the size of the shortest list that Bob must form to guarantee that it contain the password approach 1. The eavesdropper, Eve, sees η < ν hints. Assuming that Alice cannot control which hints Bob and Eve observe, we characterize for each scenario the largest normalized (by n) exponent that we can guarantee for the number of guesses it takes Eve to guess the password.

Title: Applications of Secure Coding in Distributed Storage and Wireless Networking

Remote Data Checking (RDC) is a technique by which clients can establish that data outsourced at untrusted servers remains intact over time. We first describe an RDC scheme for network coding-based distributed storage systems that is able to preserve in an adversarial setting the minimal communication overhead achieved by network coding in a benign setting to repair damaged data.

We then consider a different setting in which network coding is used to improve communication performance in multihop wireless networks. We study entropy attacks against network coding, in which injecting non-innovative packets can result in a severe degradation of the system performance. We propose and evaluate several defenses that vary in detection capabilities and overhead.

Title: Non-malleable Codes in the Split-State Model

Non-malleable codes provide a useful and meaningful security guarantee in situations where traditional error-correction (and even error-detection) is impossible; for example, when the attacker can completely overwrite the encoded message. Informally, a code is non-malleable if the message contained in a modified codeword is either the original message, or a completely unrelated value. Although such codes do not exist if the family of tampering functions F is completely unrestricted, they are known to exist for many broad tampering families F. One such natural family is the family of tampering functions in the so called split-state model. Here the message m is encoded into two shares, and the attacker is allowed to arbitrarily tamper with each share individually. Prior to this work, non-malleable codes in the split-state model received considerable attention in the literature, but were either (1) constructed in the random oracle model, or (2) relied on advanced cryptographic assumptions (such as non-interactive zero-knowledge proofs and leakage-resilient encryption), or (3) could only encode 1-bit messages.

As our main result, we give several constructions of efficient, multi-bit, information-theoretically-secure non-malleable code in the split-state model, culminating in the first explicit construction achieving a constant encoding rate. The key to obtaining our results is a simple notion of *non-malleable reductions*, which is of independent interest.

Joint works with Divesh Aggarwal, Tomasz Kazana, Shachar Lovett and Maciej Obremski.

Title: How to Store a Secret

In this talk, I want to shed some light on the tension between security and reliability in distributed storage systems (DSS) leading to connections between secret sharing schemes and regenerating codes. This tension is the consequence of the dynamic nature of these systems in which nodes are frequently leaving or joining the system. This leads to a continuous exchange of data among the nodes to maintain the same redundancy level, and therefore the same system reliability. Unfortunately, this makes the DSS more vulnerable to eavesdropping and malicious attacks. I will focus on achieving information theoretic security of data in DSS, and describe on-going efforts for characterizing the fundamental limits of security in DSS and capacity achieving code constructions. I will conclude with an overview on the numerous open problems and challenges in this area.

Title: On the Connection Between Multiple-Unicast Network Coding and Single-Source Single-Sink Network Error Correction

We show that solving a multiple-unicast network coding problem can be reduced to solving a singlesource single-sink network error correction problem, in which an adversary may jam at most a single edge in the network. This reduction holds for the cases where the demands in these networks are satisfied with both zero and vanishing error probability. An important consequence of these results is that determining the capacity for the network error correction problem is at least as hard as solving the multiple-unicast network coding problem without adversarial errors. As a byproduct, we also show a constructive example that the single-source single-sink network error correction capacity may not be achievable.

Title: Polytope Codes in Networks, Storage, and Multiple Descriptions

Polytope codes constitute a new coding paradigm in which linear operations are employed over the integers rather than a finite field. This integer structure allows polytope codes to outperform finite field codes in the presence of active adversaries that can maliciously manipulate a subset of the system. The basic structure and properties of polytope codes will be discussed, and they will be applied to three problems. First, they are used in network coding, in which an active adversary may control an unknown subset of the network. Second, they are applied to a distributed storage in which an active adversary may control an unknown subset of storage nodes. Third, they are applied to a multiple descriptions problem, in which an active adversary may corrupt a subset of messages, and the decoder aims to determine the source as accurately as possible.

Title: Robust Secret Sharing Schemes Against Local Adversaries

We study robust secret sharing schemes in which between one third and one half of the players are corrupted. In this scenario, robust secret sharing is possible only with a share size larger than the secrets, and allowing a positive probability of reconstructing the wrong secret. In the standard model, it is known that at least $m+k$ bits per share are needed to robustly share a secret of bit-length $m$ with an error probability of $2^{-k}$; however, to the best of our knowledge, the efficient scheme that gets closest to this lower bound has share size $m+\widetilde O (n+k)$, where $n$ is the number of players in the scheme.

We show that it is possible to obtain schemes with close to minimal share size in a model of local adversaries, i.e. in which corrupt players cannot communicate between receiving their respective honest shares and submitting corrupted shares to the reconstruction procedure, but may coordinate before the execution of the protocol and can also gather information afterwards. In this limited adversarial model, we prove a lower bound of roughly $m+k$ bits on the minimal share size, which is (somewhat surprisingly) similar to the lower bound in the standard model, where much stronger adversaries are allowed. We then present an efficient secret sharing scheme that essentially meets our lower bound, therefore improving upon the best known constructions in the standard model by removing a linear dependence on the number of players. For our construction, we introduce a novel procedure that compiles an error correcting code into a new randomized one, with the following two properties: a single local portion of a codeword leaks no information on the encoded message itself, and any set of portions of a codeword reconstructs the message with error probability exponentially low in the set size.

Joint work with Allison Bishop Lewko.

Title: New Techniques for Rebuilding Data Efficiently and Securely

Rebuilding erasure-coded or secret-shared data in can be an order of magnitude more expensive than rebuilding replicated data. We have developed a fundamentally new algorithm for rebuilding erasure-coded and secret-shared data that can drastically reduce network traffic and bottlenecks related to rebuilding. Further, it can be made secure such that no participant learns anything about other fragments used in the reconstruction. This technique is applicable to many existing encodings, including Shamir and Blakley secret sharing, (AONT) Reed-Solomon, and Rabin's Information Dispersal.

Title: Towards Universal Weakly-Secure Codes for Data Exchange and Storage

Weakly secure codes aim to hide information about individual packets as well as small groups of packets from an eavesdropper that can intercept wireless transmissions or has access to a small number of storage nodes. Such codes are a practical alternative to more traditional schemes that hide information about the entire set of files from the eavesdropper. The weakly secure codes do not use random keys, and, as a result, have better performance and lower overhead than the traditional schemes. In this talk, we discuss constructions of universal codes for weak security, focusing on two settings. The first setting involves construction of weakly secure codes that enable clients to exchange data over a shared broadcast channel in the presence of an eavesdropper. Second, we present an explicit construction of a coset coding based outer code to enhance the weak security properties of a regeneration code, i.e., a code which optimizes the repair bandwidth in a distributed storage system.

Title: Tamper Detection and Non-malleable Codes

We consider a public and keyless code which is used to encode a message and derive a codeword. The codeword can be adversarially tampered via a function from some "tampering-function family". We study the different types of security guarantees that can be achieved in this scenario for different families of tampering functions.

Firstly, we will study tamper-detection codes, which must detect that a tampered codeword is invalid. We show that such codes exist for any tampering-function family over n-bit codewords, as long as (1) the family is sufficiently small, of size < 2^{2^n}, (2) the functions can only have a few fixed points x such that f(x)=x, (3) the functions must have high entropy of f(x) over a random x. Such codes can also be made efficient when the family is of size 2^{poly(n)}. For example, this holds for the family of all low-degree polynomials excluding constant and identity polynomials. Such tamper-detection codes generalize the algebraic manipulation detection (AMD) codes of Cramer et al. (EUROCRYPT '08).

Next, we will study non-malleable codes, which require that a tampered codeword either decodes to the original message m, or to some unrelated value that doesn't provide any information about m. We achieve such codes for any sufficiently small function family. We give a modular construction of non-malleable codes by combining tamper-detection codes and leakage-resilient codes.

Finally, we study continuous non-malleable codes, which provide the non-malleability guarantee against an attacker that can tamper a codeword multiple times.

Title: Codes with local decoding procedures

Error correcting codes allow senders to add redundancy to messages, encoding bit strings representing messages into longer bit strings called codewords, in a way that the message can still be recovered even if a fraction of the codeword bits are corrupted. In certain settings however the receiver might not be interested in recovering all the message, but rather seek to quickly recover just a few coordinates of it. Codes that allow one to recover individual message coordinates extremely fast (locally), from accessing just a small number of carefully chosen coordinates of a corrupted codeword are said to admit a local decoding procedure. Such codes have recently played an important role in cryptography in the design of private information retrieval schemes and have also been used in practice to provide reliability in large distributed storage systems. We survey what is known about these codes.