We prove that Kilian's four-message succinct argument system is post-quantum secure in the standard model when instantiated with any probabilistically checkable proof and any collapsing hash function (which in turn exist based on the post-quantum hardness of Learning with Errors).

At the heart of our proof is a new ... more >>>

Locally correctable codes (LCCs) are error correcting codes C : \Sigma^k \to \Sigma^n which admit local algorithms that correct any individual symbol of a corrupted codeword via a minuscule number of queries. This notion is stronger than that of locally decodable codes (LDCs), where the goal is to only recover ... more >>>

Non-signaling strategies are a generalization of quantum strategies that have been studied in physics for decades, and have recently found applications in theoretical computer science. These applications motivate the study of local-to-global phenomena for non-signaling functions.

We present general results about the local testability of linear codes in the non-signaling ... more >>>

Non-signaling strategies are a generalization of quantum strategies that have been studied in physics over the past three decades. Recently, they have found applications in theoretical computer science, including to proving inapproximability results for linear programming and to constructing protocols for delegating computation. A central tool for these applications is ... more >>>

Non-signaling strategies are collections of distributions with certain non-local correlations. They have been studied in Physics as a strict generalization of quantum strategies to understand the power and limitations of Nature's apparent non-locality. Recently, they have received attention in Theoretical Computer Science due to connections to Complexity and Cryptography.

We ... more >>>

Zero knowledge plays a central role in cryptography and complexity. The seminal work of Ben-Or et al. (STOC 1988) shows that zero knowledge can be achieved unconditionally for any language in NEXP, as long as one is willing to make a suitable physical assumption: if the provers are spatially isolated, ... more >>>

Distribution testing is an area of property testing that studies algorithms that receive few samples from a probability distribution D and decide whether D has a certain property or is far (in total variation distance) from all distributions with that property. Most natural properties of distributions, however, require a large ... more >>>

Many low-degree tests examine the input function via its restrictions to random hyperplanes of a certain dimension. Examples include the line-vs-line (Arora, Sudan 2003), plane-vs-plane (Raz, Safra 1997), and cube-vs-cube (Bhangale, Dinur, Livni 2017) tests.

In this paper we study a test introduced by Ben-Sasson and Sudan in 2006 that ... more >>>

Many seminal results in Interactive Proofs (IPs) use algebraic techniques based on low-degree polynomials, the study of which is pervasive in theoretical computer science. Unfortunately, known methods for endowing such proofs with zero knowledge guarantees do not retain this rich algebraic structure.

In this work, we develop algebraic techniques for ... more >>>

We present the first constructions of *single*-prover proof systems that achieve *perfect* zero knowledge (PZK) for languages beyond NP, under no intractability assumptions:

1. The complexity class #P has PZK proofs in the model of Interactive PCPs (IPCPs) [KR08], where the verifier first receives from the prover a PCP and ... more >>>

We study *interactive oracle proofs* (IOPs) (Ben-Sasson, Chiesa, Spooner '16), which combine aspects of probabilistically checkable proofs (PCPs) and interactive proofs (IPs). We present IOP constructions and general techniques that enable us to obtain tradeoffs in proof length versus query complexity that are not known to be achievable via PCPs ... more >>>

The seminal result that every language having an interactive proof also has a zero-knowledge interactive proof assumes the existence of one-way functions. Ostrovsky and Wigderson (ISTCS 1993) proved that this assumption is necessary: if one-way functions do not exist, then only languages in BPP have zero-knowledge interactive proofs.

Ben-Or et ... more >>>

Probabilistically-Checkable Proofs (PCPs) form the algorithmic core that enables succinct verification of long proofs/computations in many cryptographic constructions, such as succinct arguments and proof-carrying data.

Despite the wonderful asymptotic savings they bring, PCPs are also the infamous computational bottleneck preventing these cryptographic constructions from being used in practice. This reflects ... more >>>

We present three contributions to the understanding of QMA with multiple provers:

1) We give a tight soundness analysis of the protocol of [Blier and Tapp, ICQNM '09], yielding a soundness gap $\Omega(N^{-2})$, which is the best-known soundness gap for two-prover QMA protocols with logarithmic proof size. Maybe ... more >>>