Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with Interactive Proof:
TR10-020 | 19th February 2010
Vipul Goyal, Yuval Ishai, Mohammad Mahmoody, Amit Sahai

Interactive Locking, Zero-Knowledge PCPs, and Unconditional Cryptography

Motivated by the question of basing cryptographic protocols on stateless tamper-proof hardware tokens, we revisit the question of unconditional two-prover zero-knowledge proofs for $NP$. We show that such protocols exist in the {\em interactive PCP} model of Kalai and Raz (ICALP '08), where one of the provers is replaced by ... more >>>

TR17-108 | 19th June 2017
Shafi Goldwasser, Guy Rothblum, Yael Tauman Kalai

Delegating Computation: Interactive Proofs for Muggles

Revisions: 1

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'' (Muggle: ``In the fiction of J.K. Rowling: a person who possesses no magical powers''; from the Oxford English Dictionary). The verifier should be ... more >>>

TR18-022 | 1st February 2018
Omer Reingold, Guy Rothblum, Ron Rothblum

Efficient Batch Verification for UP

Consider a setting in which a prover wants to convince a verifier of the correctness of k NP statements. For example, the prover wants to convince the verifier that k given integers N_1,...,N_k are all RSA moduli (i.e., products of equal length primes). Clearly this problem can be solved by ... more >>>

TR18-213 | 28th December 2018
Moni Naor, Merav Parter, Eylon Yogev

The Power of Distributed Verifiers in Interactive Proofs

Revisions: 1

We explore the power of interactive proofs with a distributed verifier. In this setting, the verifier consists of $n$ nodes and a graph $G$ that defines their communication pattern. The prover is a single entity that communicates with all nodes by short messages. The goal is to verify that the ... more >>>

TR20-157 | 21st October 2020
Guy Rothblum, Ron Rothblum

Batch Verification and Proofs of Proximity with Polylog Overhead

Suppose Alice wants to convince Bob of the correctness of k NP statements. Alice could send k witnesses to Bob, but as k grows the communication becomes prohibitive. Is it possible to convince Bob using smaller communication (without making cryptographic assumptions or bounding the computational power of a malicious Alice)? ... more >>>

TR23-015 | 20th February 2023
Scott Aaronson, Harry Buhrman, William Kretschmer

A Qubit, a Coin, and an Advice String Walk Into a Relational Problem

Revisions: 1

Relational problems (those with many possible valid outputs) are different from decision problems, but it is easy to forget just how different. This paper initiates the study of FBQP/qpoly, the class of relational problems solvable in quantum polynomial-time with the help of polynomial-sized quantum advice, along with its analogues for ... more >>>

TR23-020 | 3rd March 2023
Scott Aaronson, Shih-Han Hung

Certified Randomness from Quantum Supremacy

We propose an application for near-term quantum devices: namely, generating cryptographically certified random bits, to use (for example) in proof-of-stake cryptocurrencies. Our protocol repurposes the existing "quantum supremacy" experiments, based on random circuit sampling, that Google and USTC have successfully carried out starting in 2019. We show that, whenever the ... more >>>

TR23-070 | 9th May 2023
Shuichi Hirahara, Zhenjian Lu, Hanlin Ren

Bounded Relativization

Relativization is one of the most fundamental concepts in complexity theory, which explains the difficulty of resolving major open problems. In this paper, we propose a weaker notion of relativization called *bounded relativization*. For a complexity class $C$, we say that a statement is *$C$-relativizing* if the statement holds relative ... more >>>

TR24-100 | 21st May 2024
Changrui Mu, Prashant Nalini Vasudevan

Instance-Hiding Interactive Proofs

In an Instance-Hiding Interactive Proof (IHIP) [Beaver et al. CRYPTO 90], an efficient verifier with a _private_ input x interacts with an unbounded prover to determine whether x is contained in a language L. In addition to completeness and soundness, the instance-hiding property requires that the prover should not learn ... more >>>

ISSN 1433-8092 | Imprint