Class Description

OIP: Oblivious IP

IP where only the input size is known during the interaction with the prover, and after that interaction, the verifier gets the specific input.

L is in OIP if there exists a randomized, polynomial time interrogator I which takes an input size and interacts with a prover to produce a witness, and polynomial time verifier V that takes an input and a witness so that

  1. Given an input size n, there is prover so that I given n and interacting with the prover produces a witness w so that, for any input x of length n where x is in L, V accepts on x and w.
  2. For any x not in L of length n, for any prover interacting with I on input n gives a witness w' which V will reject with x and w' with probability at least 2/3.

OIP = IPP/poly [GM15].

Linked From

No class.