Talks at CCD

We frequently host talks at CCD. At the moment, all our talks will be virtual, but we are eagerly awaiting the time when speakers can visit us and give talks in person. If you are interested in giving a talk, please reach out to us.

Speaker: Muthu V, Georgetown Univ
Date & Time: Friday, November 19, 2021, at 9:00AM IST.
Link: Please use “meet.google.com/uti-wqyb-bzi” to join the talk

Title: Average-case Complexity Through the Lens of Interactive Puzzles

Abstract:

Consider the following two fundamental open problems in complexity theory: (a) Does a hard-on-average language in NP imply the existence of one-way functions?, or (b) Does a hard-on-average language in NP imply a hard-on-average problem in TFNP (i.e., the class of total NP search problem)? Our main result is that the answer to (at least) one of these questions is yes.

Both one-way functions and problems in TFNP can be interpreted as promise-true distributional NP search problems — namely, distributional search problems where the sampler only samples true statements. As a direct corollary of the above result, we thus get that the existence of a hard-on-average distributional NP search problem implies a hard-on-average promise-true distributional NP search problem. In other words, ”It is no easier to find witnesses (a.k.a. proofs) for efficiently-sampled statements (theorems) that are guaranteed to be true.”

This result follows from a more general study of interactive puzzles — a generalization of average-case hardness in NP—and in particular, a novel round-collapse theorem for computationally-sound protocols, analogous to Babai-Moran's celebrated round-collapse theorem for information-theoretically sound protocols.

Joint work with Rafael Pass

Speaker: Pratik Soni, CMU
Date & Time: Tuesday, October 26, 2021, at 4:30PM IST.
Link: Please use “meet.google.com/wzy-byme-qbm” to join the talk

Title: Time- and Space-Efficient Zero-Knowledge Arguments from Groups of Unknown Order

Abstract:

Zero-knowledge protocols enable the truth of a mathematical statement to be certified by a verifier without revealing any other information. Such protocols are a cornerstone of modern cryptography and recently are becoming more and more practical. However, a major bottleneck in deployment is the efficiency of the prover and, in particular, the space-efficiency of the protocol.

For every NP relation that can be verified in time T and space S, we construct a public-coin zero-knowledge argument in which the prover runs in time Tpolylog(T) and space Spolylog(T) and the verifier runs in time n*polylog(T) where n is the input length. Our protocol relies on hidden order groups, which can be instantiated with a trusted setup from the hardness of factoring (products of safe primes), or without a trusted setup using class groups. The argument-system can heuristically be made non-interactive using the Fiat-Shamir transform.

This is a joint work with Alexander Block (Purdue University), Justin Holmgren (NTT Research), Alon Rosen (Bocconi University) and Ron Rothblum (Technion)

Speaker: Siyao Guo, NYU Shanghai
Date & Time: Thursday, September 2, 2021, at 11AM IST.
Link: Please use “meet.google.com/ryu-iimf-nmw” to join the talk

Title: Data Structures Meet Cryptography: 3SUM with Preprocessing

Abstract:

We show several connections between data structure problems and cryptography against preprocessing attacks. Our results span data structure upper bounds, cryptographic applications, and data structure lower bounds, as summarized next.

First, we apply Fiat-Naor inversion, a technique with cryptographic origins, to obtain a data structure upper bound. In particular, our technique yields a suite of algorithms with space S and (online) time T for a preprocessing version of the N-input 3SUM problem where S^3T = O(N^6). This disproves a strong conjecture (Goldstein et al., WADS 2017) that there is no data structure that solves this problem for S=N^{2−δ} and T = N^{1−δ} for any constant δ>0.

Secondly, we show equivalence between lower bounds for a broad class of (static) data structure problems and one-way functions in the random oracle model that resist a very strong form of preprocessing attack. Concretely, given a random function F: NN (accessed as an oracle) we show how to compile it into a function G^F: N^2N^2 which resists S-bit preprocessing attacks that run in query time T where ST=O(N^{2−ε}) (assuming a corresponding data structure lower bound on 3SUM). In contrast, a classical result of Hellman tells us that F itself can be more easily inverted, say with N^{23}-bit preprocessing in N^{23} time. We also show that much stronger lower bounds follow from the hardness of kSUM. Our results can be equivalently interpreted as security against adversaries that are very non-uniform, or have large auxiliary input, or as security in the face of a powerfully backdoored random oracle.

Thirdly, we give non-adaptive lower bounds for 3SUM which match the best known lower bounds for static data structure problems. Moreover, we show that our lower bound generalizes to a range of geometric problems, such as three points on a line, polygon containment, and others.

This is a joint work with Alexander Golovnev, Thibaut Horel, Sunoo Park and Vinod Vaikuntanathan.

Speaker: Diksha Gupta, NSU Singapore
Date & Time: Tuesday, August 24, 2021, at 2 PM IST.
Link: Please use “https:meet.google.com/bwh-otym-yyu” to join the talk

Title: Sybil Defense using Resource Burning

Abstract:

In this talk, I will begin by discussing a recent result for defending against Sybil attacks in dynamic permissionless systems, in the presence of a computationally bounded adversary -ERGO. This technique guarantees a majority of honest identities (IDs) at all times, at a computational cost to the protocol that is comparable to that of the attacker.

Next, I will talk about the concept of resource burning - the verifiable consumption of resources. This resource does not necessarily need to be computational power, but can also be communication capacity, computer memory, and human effort, subject to some constraints. Using this insight, I will conclude with a generalizing of our Sybil defense techniques to a variety of systems with churn, in the presence of a resource-bounded adversary.

Speaker: Kartik Nayak, Duke university
Date & Time: Monday, August 9, 2021, at 5 PM IST.
Link: Please use “meet.google.com/kjc-amem-qyv” to join the talk

Title: Bringing Synchronous Consensus Closer to Practice

Abstract:

Byzantine Fault Tolerant protocols in the synchronous setting have often been considered impractical due to the strong synchrony assumption. On the flip side, synchronous protocols can be used to tolerate up to one-half Byzantine faults. In this talk, I will explain my journey towards improving synchronous protocols, both in theory and practice.

Speaker: Ruta Jawale, UIUC
Date & Time: Thursday, July 29, 2021, at 9 AM IST.

Title: SNARGs and PPAD Hardness from Sub-exponential LWE

Abstract:

We construct a succinct non-interactive publicly-verifiable delegation scheme for any logspace uniform circuit under the sub-exponential Learning With Errors (LWE) assumption. For a circuit C : {0, 1}^N -> {0, 1} of size S and depth D, the prover runs in time poly(S), the communication complexity is D polylog(S), and the verifier runs in time (D + N) polylog(S). To obtain this result, we introduce a new cryptographic primitive: lossy correlation-intractable hash functions. We use this primitive to soundly instantiate the Fiat-Shamir transform for a large class of interactive proofs, including the interactive sum-check protocol and the GKR protocol, assuming the sub-exponential hardness of LWE. By relying on the result of Choudhuri et al. (STOC 2019), we also establish the sub-exponential average-case hardness of PPAD, assuming the sub-exponential hardness of LWE.

This is based on a joint work with Yael Tauman Kalai, Dakshita Khurana, and Rachel Zhang.

Speaker: Zhengzhong Jin, Johns Hopkins University
Date & Time: Friday, July 16, 2021, at 9 AM IST.

Title: Non-interactive Zero-knowledge from Sub-exponential DDH

Abstract:

A non-interactive zero-knowledge (NIZK) proof allows a prover to convince a verifier about the truth of a statement by sending a single message, without revealing any other information. NIZKs are fundamental cryptographic primitives that have many applications, such as CCA-secure cryptosystems, signature schemes, blockchains, and more. We provide the first constructions of non-interactive zero-knowledge and Zap arguments for NP based on the sub-exponential hardness of Decisional Diffie-Hellman against polynomial time adversaries (without use of groups with pairings).

Central to our results, and of independent interest, is a new notion of interactive trapdoor hashing protocols.

Joint work with Abhishek Jain.

Speaker: Suyash Gupta, UC Davis
Date & Time: Friday, April 30, 2021, at 11 AM.
Link: Sent via email to all CSE affiliates. Email John Augustine if you need the link.

Title: Resilient and Scalable Architecture for Permissioned Blockchain Fabrics

Abstract:

Since the introduction of Bitcoin—the first widespread application driven by blockchains—the interest in the design of blockchain-based applications has increased tremendously. At the core of these blockchain applications are consensus protocols that aim at securely replicating a client request among all replicas, even if some replicas are Byzantine faulty. Unfortunately, modern consensus protocols either yield low throughput or face design limitations.

In this work, we present the design of three consensus protocols that facilitate efficient consensus among the replicas. Our protocols help to scale cons ensus through the principles of phase-reduction, parallelization, and geo-scale clustering while ensuring no compromise in fault-tolerance. Further, we believe that the focus on consensus protocols is only one-side of the story. In specific, we present the design of a well-crafted permissioned blockchain fabric (ResilientDB) that can help even a slow consensus protocol outperform a faster protocol. Our results indicate that it is easy to scale BFT protocols to hundreds of replicas and achieve throughputs of the order 350K txns/s.