Results 1991 - 2000 of 23898

Probabilistic proof systems allow a powerful prover to convince a computationally weak verifier of the validity of a large and complex computation. These seemingly magical objects have been an extremely important tool both in theory, where they have driven breakthroughs like the PCP theorem, zero-knowledge proofs, and advancements in approximation hardness, and in practice, where they are integral to the scalability of cloud computing and blockchain technology and are widely deployed, securing billions of dollars worth of transactions.

In this short introduction talk, I will give an overview of research topics related to cryptographic proof systems that interest me.

Despite all the success in modern cryptography, there are still some tasks in cryptography where achieving the “ideal” efficiency from standard assumptions has evaded us. Consider the following two settings:
 
* Can we construct succinct non-interactive arguments (SNARGs) for all of NP?
* Can we construct indistinguishability obfuscation (IO) for Turing machines? In particular, can we achieve an obfuscation size which is independent of the input length? 
 
While the problems seem unrelated at first glance, the root difficulty seems to stem from a similar place: both primitives have non-falsifiable security notions. In fact, this type of barrier exists for many other cryptographic primitives, including witness encryption. This leads to a central question: how can we construct non-falsifiable primitives from falsifiable assumptions?
 
In this talk, I’ll show how we can leverage “propositional proofs” to overcome the non-falsifiability barrier. I will then discuss how to use this idea to achieve succinctness in both the iO and SNARG settings.

My work studies connections between efficient proof systems and quantum information. My interests include post-quantum security reductions for classical cryptographic proof systems (quantum rewinding); quantum proof systems; and incrementally-verifiable computation.

Modern cryptographic techniques -- such as secure multiparty computation and zero-knowledge proofs -- enable secure computation over private data while ensuring the integrity of the computation. In this talk, I will highlight some recent advances in designing efficient protocols for these primitives, with a particular focus on approaches that achieve sublinear communication. I will conclude with some interesting open problems in this area.

Many central questions in quantum computing involve algorithms that apply a Haar-random unitary. But analyzing such algorithms is often difficult: if the unitary is applied k times, the final state depends on k-th moments of the Haar measure, which typically require sophisticated mathematical tools to control. 

In this talk, I'll present a new way to analyze Haar-random unitaries using the path recording oracle, a data structure that efficiently "spoofs" a random unitary. I’ll explain the intuition behind its definition, how it can be used to prove theorems about random unitaries, and how it works in settings where the algorithm can access both the unitary and its inverse. 

The talk is based on joint work with Robert Huang (https://arxiv.org/abs/2410.10116), but will focus primarily on the path-recording oracle.

I will explain the compressed oracle technique, which is a useful for reasoning about algorithms making quantum queries to a random oracle. I will give some example applications and conclude with some directions for future work.