Seminar

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

Oct
26
Wed
[Theory Seminar] Adam Smith
Oct 26 @ 12:00 pm – 1:00 pm

Speaker: Adam Smith

Affiliation: Penn State University.

Title: Privacy, Information and Generalization

Abstract:

Consider an agency holding a large database of sensitive personal
information — medical records, census survey answers, web search
records, or genetic data, for example. The agency would like to
discover and publicly release global characteristics of the data (say,
to inform policy or business decisions) while protecting the privacy
of individuals’ records. I will begin by discussing what makes this
problem difficult, and exhibit some of the nontrivial issues that
plague simple attempts at anonymization and aggregation. Motivated by
this, I will present differential privacy, a rigorous definition of
privacy in statistical databases that has received significant
attention.

In the second part of the talk, I will explain how differential
privacy is connected to a seemingly different problem: “adaptive data
analysis”, the practice by which insights gathered from data are used
to inform further analysis of the same data sets. This is increasingly
common both in scientific research, in which data sets are shared and
re-used across multiple studies. Classical statistical theory assumes
that the analysis to be run is selected independently of the data.
This assumption breaks down when data re re-used; the resulting
dependencies can significantly bias the analyses’ outcome. I’ll show
how the limiting the information revealed about a data set during
analysis allows one to control such bias, and why differentially
private analyses provide a particularly attractive tool for limiting
information.

Based on several papers, including recent joint works with R. Bassily,
K. Nissim, U. Stemmer, T. Steinke and J. Ullman (STOC 2016) and R.
Rogers, A. Roth and O. Thakkar (FOCS 2016).

 

Bio:
Adam Smith is a professor of Computer Science and Engineering at Penn
State. His research interests lie in data privacy and cryptography,
and their connections to machine learning, statistics, information
theory, and quantum computing. He received his Ph.D. from MIT in 2004
and has held visiting positions at the Weizmann Institute of Science,
UCLA, Boston University and Harvard. In 2009, he received a
Presidential Early Career Award for Scientists and Engineers (PECASE).
In 2016, he received the Theory of Cryptography Test of Time award,
jointly with C. Dwork, F. McSherry and K. Nissim.

Nov
16
Wed
[Theory Seminar] Justin Thaler
Nov 16 @ 12:00 pm – 1:00 pm

Speaker: Justin Thaler

Affiliation: Georgetown University

Title: Approximate Degree, Sign-Rank, and the Method of Dual Polynomials

Abstract:

The eps-approximate degree of a Boolean function is the minimum degree of a real polynomial that point-wise approximates f to error eps. Approximate degree has wide-ranging applications in theoretical computer science, yet our understanding of approximate degree remains limited, with few general results known.

The focus of this talk will be on a relatively new method for proving lower bounds on approximate degree: specifying dual polynomials, which are dual solutions to a certain linear program capturing the approximate degree of any function. I will describe how the method of dual polynomials has recently enabled progress on a variety of open problems, especially in communication complexity and oracle separations. 

Joint work with Mark Bun, Adam Bouland, Lijie Chen, Dhiraj Holden, and Prashant Nalini Vasudevan

Nov
30
Wed
[Theory seminar] Jalaj Upadhyay
Nov 30 @ 12:00 pm – 1:00 pm

Speaker: Jalaj Upadhyay

Affiliation: Penn State University

Title: Fast and Space-Optimal Differentially-Private Low-Rank Factorization in the General Turnstile Update Model

Abstract:

The problem of {\em low-rank factorization} of an mxn matrix A requires outputting a singular value decomposition: an m x k matrix U, an n x k matrix V, and a k x k diagonal
matrix D) such that  U D V^T approximates the matrix A in the Frobenius norm.  In this paper, we study  releasing differentially-private low-rank factorization of a matrix in
the general turnstile update model.  We give two differentially-private algorithms instantiated with respect to two levels of privacy.  Both of our privacy levels are stronger
than  privacy levels for this and related problems studied in previous works, namely that of Blocki {\it et al.} (FOCS 2012), Dwork {\it et al.} (STOC 2014), Hardt and Roth
(STOC 2012, STOC 2013), and Hardt and Price (NIPS 2014). Our main contributions are as follows.

1. In our first level of privacy, we consider two matrices A and A’ as neighboring if  A – A’ can be represented as an outer product of two unit vectors. Our private algorithm
with respect to this privacy level incurs optimal  additive error.  We also prove a lower bound that shows that the space required by this algorithm is optimal up to a
logarithmic factor.
2. In our second level of privacy, we consider two matrices  as neighboring if their difference has the Frobenius norm at most 1. Our private algorithm with respect to this
privacy level is computationally more efficient than our first algorithm and incurs optimal additive error.

Mar
7
Tue
[Theory Seminar] Mohammad Mahmoody
Mar 7 @ 3:00 pm – 4:00 pm

Speaker: Mohammad Mahmoody, Assistant Professor, University of Virginia

Title: Lower Bounds on Indistinguishability Obfuscation from Zero-One Encryption

Abstract: Indistinguishability Obfuscation (IO) has recently emerged as a central primitive in cryptography, enabling many heretofore out-of-reach applications. However, currently all known constructions of IO are based on multilinear maps which are poorly understood. With the hope of basing IO on more standard assumptions, in this work we ask whether IO could be based on any of powerful (and recently realized) encryption primitives such as attribute-based/predicate encryption, fully homomorphic encryption, and witness encryption. What connects these primitives is that they are zero-one: either the message is revealed fully by the “right key” or it remains completely hidden.

Our main result is a negative one: we prove there is no black-box construction of IO from any of the above list of “zero-one” encryptions. We note many IO constructions are in fact non-black-box and e.g., results of Anath-Jain’15 and Bitansky-Vaikuntanathan’15 of basing IO on functional encryption is non-black-box. In fact, we prove our separations in an extension of the black-box framework of Impagliazzo-Rudich’89 and Reingold-Trevisan-Vadhan’04 which allows such non-black-box techniques as part of the model by default. Thus, we believe our extended model is of independent interest as a candidate for the new “standard” for cryptographic separations.

Mar
8
Wed
[Theory seminar] Avishay Tal
Mar 8 @ 12:00 pm – 1:00 pm

Speaker: Avishay Tal

Affiliation: IAS

Title:Time-Space Hardness of Learning Sparse Parities

Abstract:

How can one learn a parity function, i.e., a function of the form $f(x) = a_1 x_1 + a_2 x_2 + … + a_n x_n (mod 2)$ where a_1, …, a_n are in {0,1}, from random labeled examples? One approach is to gather O(n) random labeled examples and perform Gaussian-elimination. This requires a memory of size O(n^2) and poly(n) time. Another approach is to go over all possible 2^n parity functions and to verify them by checking O(n) random examples per each possibility. This requires a memory of size O(n), but O(2^n * n) time. In a recent work, Raz [FOCS, 2016] showed that if an algorithm has memory of size much smaller than n^2, then it has to spend exponential time in order to learn a parity function. In other words, fast learning requires a good memory. In this work, we show that even if the parity function is known to be extremely sparse, where only log(n) of the a_i’s are nonzero, then the learning task is still time-space hard. That is, we show that any algorithm with linear size memory and polynomial time fails to learn log(n)-sparse parities. Consequently, the classical tasks of learning linear-size DNF formulae, linear-size decision trees, and logarithmic-size juntas are all time-space hard. Based on joint work with Gillat Kol and Ran Raz.

 

Mar
22
Wed
[Theory Seminar] Yevgeniy Dodis @ Malone G33/35 (ground floor)
Mar 22 @ 12:00 pm – 1:00 pm

SPEAKER: Yevgeniy Dodis, New York University

TITLE: Fixing Cracks in the Concrete: Random Oracles with Auxiliary Input, Revisited

ABSTRACT: We revisit security proofs for various cryptographic primitives in the random oracle model with auxiliary input (ROM-AI): a (computationally unbounded) attacker A can compute arbitrary S bits of leakage z=z(O) about the random oracle O before attacking the system, and then use additional T oracle queries to O during the attack. This model was explicitly studied by Unruh in 2007 (CRYPTO 2007), but dates back to the seminal paper of Hellman in 1980 about time-space tradeoffs for inverting random functions, and has natural applications in settings where traditional random oracle proofs are not useful: (a) security against non-uniform attackers; (b) space-time tradeoffs; (c) security against preprocessing; (d) resilience to backdoors in hash functions. We obtain a number of new results about ROM-AI, but our main message is that ROM-AI is the “new cool kid in town”: it nicely connects theory and practice, has a lot of exciting open questions, leads to beautiful math, short definitions, elegant proofs, surprising algorithms, and is still in its infancy. In short, you should work on it! Joint Work with Siyao Guo and Jonathan Katz.

 

 

 

Mar
29
Wed
[Theory Seminar] Ori Rottenstriech
Mar 29 @ 12:00 pm – 1:00 pm
Speaker: Ori Rottenstriech, Princeton

Title: Novel Approaches to Challenges in Emerging Network Paradigms

Abstract:

SDN (Software defined networking) and NFV (Network Function Virtualization) are two emerging network paradigms that enable simplification, flexibility and cost-reduction in network management. We believe that the new paradigms will lead to many interesting research questions. We study how to rely on them for dealing with two common network challenges.

We consider switches that imply network policies in SDN through rule matching tables of limited size. We study the applicability of rule caching and lossy compression to create packet classifiers requiring much less memory than the theoretical size limits of semantically-equivalent representations. We would like to find limited-size classifiers that can correctly classify a high portion of the traffic. We address different goals with unique settings and explain how to deal with the traffic that cannot be classified correctly.

Network functions such as load balancing and deep packet inspection are often implemented in dedicated hardware called middleboxes. Those can suffer from temporary unavailability due to misconfiguration or software and hardware malfunction. We suggest to rely on virtualization for planning and deploying backup schemes for network functions. The schemes guarantee high levels of survivability with significant reduction in resource consumption. We discuss different goals that network designers should take into account. We describe a graph theoretical model for finding properties of efficient solutions and developing algorithms that can build them.

Bio: Ori Rottenstriech is a postdoctoral research associate at the Department of Computer Science, Princeton University. He received his Ph.D. from the Electrical Engineering department of the Technion. His research interests include the intersection of computer networking and algorithms.

 

Apr
19
Wed
[Theory Seminar] Sepehr Assadi
Apr 19 @ 12:00 pm – 1:00 pm

Speaker: Sepehr Assadi, UPenn

Title:

Matching Size and Matrix Rank Estimation in Data Streams

 

Abstract:

How well a sub-linear space algorithm can estimate the size of a largest matching in a graph or the rank of a given matrix, if the input is revealed in a streaming fashion? In this talk, we consider this question from both upper bound and lower bound ends and establish new results on the tradeoff between the space requirement and desired accuracy of streaming algorithms for these tasks.

 

We show that while the problem of matching size estimation is provably easier than the problem of finding an approximate matching (i.e., finding the actual edges of the matching), the space complexity of the two problems starts to converge together as the accuracy desired in the computation approaches near-optimality. A well-known connection between matching size estimation and computing rank of Tutte matrices allows us to further carry our lower bound results to the matrix rank estimation problem, and we show that an almost quadratic space is necessary to obtain a near-optimal approximation of matrix rank in data streams.

 

Based on a joint work with Sanjeev Khanna and Yang Li (in SODA’17, invited to HALG’17).
Apr
26
Wed
[Theory Seminar] Dana Dachman Soled
Apr 26 @ 12:00 pm – 1:00 pm

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).

Sep
6
Wed
[Theory Seminar] Mohammad Hajiesmaili @ Malone 228
Sep 6 @ 12:00 pm – 1:00 pm

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.

Oct
11
Wed
[Theory Seminar] Kuan Cheng @ Malone 228
Oct 11 @ 12:00 pm – 1:00 pm

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.

Oct
25
Wed
[Theory Seminar] Ilan Komargodski @ Malone 228
Oct 25 @ 12:00 pm – 1:00 pm

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.

Nov
13
Mon
[Theory Seminar] Ran Ben Basat
Nov 13 @ 12:00 pm – 1:00 pm

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.

Nov
29
Wed
[Theory Seminar] Samson Zhou
Nov 29 @ 12:00 pm – 1:00 pm

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.

Dec
6
Wed
[Theory] Venkata Gandikota @ Malone 228
Dec 6 @ 12:00 pm – 1:00 pm

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).

Dec
13
Wed
[Theory Seminar] Amirbehshad Shahrasbi @ Malone 228
Dec 13 @ 12:00 pm – 1:00 pm

Speaker: Amirbehshad Shahrasbi
Affiliation:Carnegie Mellon University

Title: Synchronization Strings
In this talk, I will introduce “synchronization strings”, mathematical objects which provide a novel way of efficiently dealing with synchronization errors, i.e., insertions and deletions in communication problems. Synchronization errors are strictly more general and much harder to deal with than more commonly studied symbol corruption and symbol erasure errors. For every eps > 0, synchronization strings allow to index a sequence such that one can efficiently transform k synchronization errors into (1+eps)k erasure and corruption errors. This powerful new technique has many applications.
A straight forward application of our synchronization string based indexing method gives a simple black-box construction which transforms any error correcting code (ECC) into an equally efficient insertion-deletion code with only a small increase in the alphabet size. This instantly transfers much of the highly developed understanding for regular ECCs into the realm of insertion-deletion codes. Most notably, for the complete noise spectrum, we obtain efficient near-MDS insertion-deletion codes which get arbitrarily close to the optimal rate-distance trade-off given by the Singleton bound.
Further applications of synchronization strings will be discussed including a general method of simulating symbol corruption channels over any given insertion-deletion channel, an efficient and near-optimal coding scheme for interactive communication over insertion-deletion channels, and list-decodable insertion-deletion codes.
This talk is based on joint works with Bernhard Haeupler and Ellen Vitercik from CMU.
Mar
14
Wed
[Theory Seminar] Samson Zhou
Mar 14 @ 12:00 pm – 1:00 pm

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.

Jul
2
Mon
[Theory Seminar] Sai Lakshmi Bhavana Obbattu
Jul 2 @ 12:00 pm – 1:00 pm

Speaker: Sai Lakshmi Bhavana Obbattu
Affiliation: IISC Bangalore, India

Title: Privacy Amplification from Non-malleable Codes

The goal of a Privacy Amplification (PA) protocol is to allow two parties, who start out sharing a non-uniform secret ‘w’, to agree on a uniform secret ‘k’, in the presence of a computationally unbounded man-in-the-middle adversary. An interactive PA protocol is rated based on three parameters: 1) Number of rounds, 2) Entropy loss (entropy of w – |k|), and 3) Min-entropy requirement for w, while the asymptotically optimal parameters are 2, O(s) and O(s+log n) respectively (where s is the security parameter and n =|w|). There have been two popular approaches to solve this problem: one using use bit authentication protocols and the other using non-malleable extractors, but none of the prior protocols using these approaches had all asymptotically optimal parameters.

We give an alternate approach to solve the problem using Non-malleable Codes (NMCs). This approach results in a 8-round protocol with min-entropy requirement O(s+log n) and an entropy loss of O(s log s). Augmented NMCs with better parameters would result in optimal entropy loss of O(s). Our result is one of the first information theoretic applications of NMCs. In this talk, I will introduce NMCs and show connection of NMCs to PA.

In a concurrent and independent work, Xin Li gives a protocol with asymptotically optimal parameters based on non-malleable extractors. Because all known approaches have large hidden constants, exploring alternatives is necessary if we hope to get practical concrete parameters

The talk is based on:

Eshan Chattopadhyay, Bhavana Kanukurthi, Sai Lakshmi Bhavana Obbattu and Sruthi Sekar. Privacy Amplification from Non-malleable Codes. (eprint.iacr.org/2018/293)

Bhavana Kanukurthi, Sai Lakshmi Bhavana Obbattu and Sruthi Sekar. Non-malleable Randomness Encoders and their Applications (Eurocrypt 2018)

Bio: Sai Lakshmi Bhavana Obbattu is a doctoral student at Indian Institute of Science(IISc), Bangalore, advised by Dr. Bhavana Kanukurthi. Her publication venues include the Theory of Cryptography Conference (TCC) and Eurocrypt. Her TCC publication on Four-state Non-malleable Codes was invited to the Journal of Cryptology. She received her Integrated Dual Degree (B.Tech and M.Tech) from IIT(BHU), Varanasi. Her research interests include Non-malleable codes, Privacy Amplification and Applied Multi-party computation.

Aug
23
Thu
[Theory Seminar] Akash Kumar @ Malone 338
Aug 23 @ 12:00 pm – 1:00 pm

Speaker: Akash Kumar
Affiliation: Purdue University
Location: Malone 338 (note change of location)

Title:
Finding Minors in Sublinear time in Bounded degree graphs with (almost) optimal one-sided query complexity.

Abstract:
Let G be an undirected, bounded degree graph with n vertices. Fix a finite graph H, and suppose one must remove \varepsilon n edges from G to make it H-minor free (for some small constant \varepsilon > 0). We give an n^{1/2+o(1)}-time randomized procedure that, with high probability, finds an H-minor in such a graph. For an example application, suppose one must remove \varepsilon n edges from a bounded degree graph G to make it planar. This result implies an algorithm, with the same running time, that produces a K_{3,3} or K_5 minor in G. No sublinear time bound was known for this problem, prior to this result.

By the graph minor theorem, we get an analogous result for any minor-closed property. Up to n^{o(1)} factors, this resolves a conjecture of Benjamini-Schramm-Shapira (STOC 2008) on the existence of one-sided property testers for minor-closed properties. Furthermore, our algorithm is nearly optimal, by an \Omega(\sqrt{n}) lower bound of Czumaj et al (RSA 2014).

Prior to this work, the only graphs H for which non-trivial property testers were known for H-minor freeness are the following: H being a forest or a cycle (Czumaj et al, RSA 2014), K_{2,k}, (k\times 2)-grid, and the k-circus (Fichtenberger et al, Arxiv 2017).

(Joint work with C. Seshadhri and Andrew Stolman).

Sep
5
Wed
[Theory Seminar] Welcome and Introductions
Sep 5 @ 12:00 pm – 1:00 pm

Welcome and Introductions