Quantum cryptography is the art and science of exploiting quantum mechanical effects in
order to perform cryptographic tasks. While the most well-known example of this discipline is …

We initiate the study of a proof system model that naturally combines interactive proofs (IPs)
and probabilistically-checkable proofs (PCPs), and generalizes interactive PCPs (which …

Quantum cryptography promises levels of security that are impossible to attain in a classical
world. Can this security be guaranteed to classical users of a quantum protocol, who may …

We provide the first construction of a succinct non-interactive argument (SNARG) for all
polynomial time deterministic computations based on standard assumptions. For T steps of …

In this work we study interactive proofs for tractable languages. The (honest) prover should
be efficient and run in polynomial time or, in other words, a “muggle”. 1 The verifier should …

In a homomorphic signature scheme, a user Alice signs some large dataset x using her
secret signing key and uploads the signed data to an untrusted remote server. The server …

We construct new private-information-retrieval protocols in the single-server setting. Our
schemes allow a client to privately fetch a sequence of database records from a server …

Non-interactive batch arguments for NP provide a way to amortize the cost of NP verification
across multiple instances. They enable a prover to convince a verifier of multiple NP …

We show how to generically improve the succinctness of non-interactive publicly verifiable
batch argument (BARG) systems. In particular, we show (under a mild additional …

The celebrated IP= PSPACE Theorem of Lund et-al.(J. ACM 1992) and Shamir (J. ACM
1992), allows an all-powerful but untrusted prover to convince a polynomial-time verifier of …