We typically have seminars on Wednesday at noon in Malone 228. All seminar announcements will be sent to the theory mailing list.

Speaker: Sepehr Assadi, UPenn

Title:

Abstract:

Speaker: Dana Dachman Soled, UMD

**Title: Tight Upper and Lower Bounds for Leakage-Resilient, Locally Decodable and Updatable Non-Malleable Codes**

**Abstract: **In a recent result, Dachman-Soled et al.~(TCC ’15) proposed a new notion called locally decodable and updatable non-malleable codes, which informally, provides the security guarantees of a non-malleable code while also allowing for efficient random access. They also considered locally decodable and updatable non-malleable codes that are leakage-resilient, allowing for adversaries who continually leak information in addition to tampering. Unfortunately, the locality of their construction in the continual setting was Omega(log n), meaning that if the original message size was n, then Omega(log n) positions of the codeword had to be accessed upon each decode and update instruction.

In this work, we ask whether super-constant locality is inherent in this setting. We answer the question affirmatively by showing tight upper and lower bounds. Specifically, in any threat model which allows for a rewind attack-wherein the attacker leaks a small amount of data, waits for the data to be overwritten and then writes the original data back-we show that a locally decodable and updatable non-malleable code with block size Chi in poly(lambda) number of bits requires locality delta(n) in omega(1), where n = poly(lambda) is message length and lambda is security parameter. On the other hand, we re-visit the threat model of Dachman-Soled et al.~(TCC ’15)-which indeed allows the adversary to launch a rewind attack-and present a construction of a locally decodable and updatable non-malleable code with block size Chi in Omega(lambda^{1/mu}) number of bits (for constant 0 < mu < 1) with locality delta(n), for any delta(n) in omega(1), and n = poly(lambda).

Speaker: Mohammad Hajiesmaili

Affiliation: Johns Hopkins University

Title: Online storage management in electricity market

Abstract:

With unprecedented benefits in terms of efficiency, economy, reliability, and environmental awareness, in the recent years, there has been a rapid proliferation of renewable energy sources such as solar and wind in electric power systems. Despite these benefits, the inherent uncertainty in renewables places severe challenges on the management of the entire energy systems, including electricity market. Leveraging energy storage systems is a promising approach to mitigate the uncertainty of renewables, by charging and discharging during the mismatched periods. Energy storage systems, however, offers a new design space for additional optimization. That is, a storage system can capture energy during periods when the market prices are low and surrender stored energy when energy prices are high.

In this talk, we consider different scenarios of storage management in both supply and demand sides of the electricity market. The uncertainties in both renewable output and electricity market price, emphasizes the need for online solution design. The underlying theoretical problems could be described as extensions of conversion problems in financial markets, i.e., the search for best prices to buy and/or sell assets. The difference with the conversion problems, is that in addition to the uncertainty in the price, our problems suffer from another uncertainty originated from renewable output. We follow online algorithm design and use competitive ratio as the performance measure of our algorithms. We present our recent results in designing competitive online algorithms that achieve constant competitive ratios. In addition, we briefly talk about the case of utilizing aggregate potentials distributed small-scale storage systems, such as EVs or residential storages, to participate in electricity market through an aggregator. This setting is more challenging than the previous one, since the distributed sources also arrive in online manner with heterogeneous profiles.

Overall, we believe that changing the landscape of electric power system from a centralized predictable system to a distributed uncertain system opens a new research direction for leveraging online framework designs in this relatively under-explored area.

Speaker: Kuan Cheng

Affiliation: Johns Hopkins University

Title: Near-Optimal Secret Sharing and Error Correcting Codes in $\AC^0$

Abstract:

We study the question of minimizing the computational complexity of (robust) secret sharing schemes and error correcting codes. In standard instances of these objects, both encoding and decoding involve linear algebra, and thus cannot be implemented in the class $\AC^0$. The feasibility of non-trivial secret sharing schemes in $\AC^0$ was recently shown by Bogdanov et al.\ (Crypto 2016) and that of (locally) decoding errors in $\AC^0$ by Goldwasser et al.\ (STOC 2007).

In this paper, we show that by allowing some slight relaxation such as a small error probability, we can construct much better secret sharing schemes and error correcting codes in the class $\AC^0$. In some cases, our parameters are close to optimal and would be impossible to achieve without the relaxation. Our results significantly improve previous constructions in various parameters.

Our constructions combine several ingredients in pseudorandomness and combinatorics in an innovative way. Specifically, we develop a general technique to simultaneously amplify security threshold and reduce alphabet size, using a two-level concatenation of protocols together with a random permutation. We demonstrate the broader usefulness of this technique by applying it in the context of a variant of secure broadcast.

Based on a joint work with Yuval Ishai and Xin Li.

Speaker: Ilan Komargodski

Affiliation: Cornell Tech

Title: White-Box vs. Black-Box Complexity of Search Problems: Ramsey and Graph Property Testing

Abstract: Ramsey theory assures us that in any graph there is a clique or independent set of a certain size, roughly logarithmic in the graph size. But how difficult is it to find the clique or independent set? This problem is in TFNP, the class of search problems with guaranteed solutions. If the graph is given explicitly, then it is possible to do so while examining a linear number of edges. If the graph is given by a black-box, where to figure out whether a certain edge exists the box should be queried, then a large number of queries must be issued.

1) What if one is given a program or circuit (“white-box”) for computing the existence of an edge. Does the search problem remain hard?

2) Can we generically translate all TFNP black-box hardness into white-box hardness?

3) Does the problem remain hard if the black-box instance is small?

We will answer all of these questions and discuss related questions in the setting of property testing.

Joint work with Moni Naor and Eylon Yogev.

Speaker: Ran Ben Basat

Affiliation: Technion

Title: Classic Network Measurement meets Virtual Switching

Abstract: In modern cloud infrastructures, each physical server often runs multiple virtual machines and employs a software Virtual Switch (VS) to handle their traffic. In addition to switching, the VS performs network measurements, such as identifying the most frequent flows, which are essential for networking applications such as load balancing and intrusion detection.

Unlike traditional streaming algorithms, which minimize the space requirements, the bottleneck in virtual switching measurement is the CPU utilization. In this talk, I will present new hardware-oriented algorithms and acceleration methods that optimize the update time for software, at the cost of a slight memory overhead.

Bio: Ran is a Ph.D. candidate at the Technion, Israel. He does research in streaming algorithms for networking applications, focusing on efficient processing and query speeds.

Speaker: Samson Zhou

Affiliation: Purdue University

Title: Pattern Matching over Noisy Data Streams

Abstract: The identification of low-complexity structure in strings is a fundamental building block for many algorithms in computational biology or natural language processing. The general paradigm in these algorithms is to find either highly repetitive structure, in the form of periodicity or palindromes in a pre-processing stage, to filter out locations where a certain pattern cannot occur, thus improving efficiency.

Unfortunately, we must expect massive data to contain a number of small imperfections, such as through human error or mutations. This motivates the need to study structure in models of sublinear space, resilient to sources of noise. In this talk, we introduce several types of structure and noise, and discuss efficient algorithms to identify these structures over data streams.

As a warm-up, we provide an algorithm for identifying a longest common aligned substring of two inputs, resilient up to d errors of insertions, substitutions, or deletions. We then present a streaming algorithm for identifying the longest palindrome, resilient up to a threshold of d substitution errors. Finally, we discuss the problem of finding all periods of a string including up to d persistent changes or erasures. For each of these scenarios, we also provide complementary lower bounds.

Joint work with Funda Ergun, Elena Grigorescu, and Erfan Sadeqi Azer.

BIO:

Samson is a PhD candidate in the Department of Computer Science at Purdue University, under the supervision of Greg Frederickson and Elena Grigorescu. He received his undergraduate education at MIT, where he obtained a Bachelor’s in math and computer science, as well as a Master’s in computer science. He is a member of the Theory Group at Purdue, and his current research interests are sublinear and approximation algorithms, with an emphasis on streaming algorithms.

Speaker: Venkata Gandikota

Affiliation: Johns Hopkins University

Title: NP-Hardness of Reed-Solomon Decoding and the Prouhet-Tarry-Escott Problem

Abstract: Establishing the complexity of Bounded Distance Decoding for Reed-Solomon codes is a fundamental open problem in coding theory, explicitly asked by Guruswami and Vardy (IEEE Trans. Inf. Theory, 2005). The problem is motivated by the large current gap between the regime when it is NP-hard, and the regime when it is efficiently solvable (i.e., the Johnson radius).

We show the first NP-hardness results for asymptotically smaller decoding radii than the maximum likelihood decoding radius of Guruswami and Vardy. Specifically, for Reed-Solomon codes of length N and dimension K = O(N), we show that it is NP-hard to decode more than N-K-O(log N / log log N) errors.

These results follow from the NP-hardness of a generalization of the classical Subset Sum problem to higher moments, called Moments Subset Sum, which has been a known open problem, and which may be of independent interest. We further reveal a strong connection with the well-studied Prouhet-Tarry-Escott problem in Number Theory, which turns out to capture a main barrier in extending our techniques. We believe the Prouhet-Tarry-Escott problem deserves further study in the theoretical computer science community.

This is a joint work with Badih Ghazi (MIT) and Elena Grigorescu (Purdue).

Speaker: Amirbehshad Shahrasbi

Affiliation:Carnegie Mellon University

Speaker: Samson Zhou

Affiliation: Purdue University

Title: Password Hashing and Graph Pebbling

Abstract: Although the passwords of users are no longer being stored, we show an offline attacker is compelled to crack all stolen passwords under current security recommendations. Memory hard functions have been proposed as moderately expensive cryptographic tools for password hashing. The cryptanalysis of these functions has focused on the cumulative memory complexity and the energy complexity of the function. The first metric measures how much memory users must commit to evaluating a function, while the second metric measures how much energy users must commit. We prove these evaluations reduce to pebbling games on graphs but show that a tool for exact cryptanalysis of functions is unlikely to exist. Nevertheless, we provide asymptotic upper and lower bounds on several families of functions, including Argon2i, the winner of the password hashing competition that is currently being considered for standardization by the Cryptography Form Research Group of the Internet Research Task Force.

Joint work with Jeremiah Blocki, Ben Harsha, Ling Ren

BIO:

Samson is a PhD candidate in the Department of Computer Science at Purdue University, under the supervision of Greg Frederickson and Elena Grigorescu. He received his undergraduate education at MIT, where he obtained a Bachelor’s in math and computer science, as well as a Master’s in computer science. He is a member of the Theory Group at Purdue and a winner of the Sigma Xi Research Awards Competition for graduate students in engineering. His current research interests are sublinear and approximation algorithms, with an emphasis on streaming algorithms.