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

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.

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.

Speaker: Martin Farach-Colton

Affiliation: Rutgers University

Title: TBA

Abstract: TBA