Instance-Hiding Interactive Proofs

Abstract In an Instance-Hiding Interactive Proof (IHIP) (Beaver et al., in: Menezes and Vanstone (eds) Advances in cryptology—CRYPTO 1990, proceedings, lecture notes in computer science (including subseries lecture notes in artificial intelligence and lecture notes in bioinformatics), Springer, pp 326–338, 1990), an efficient verifier with a private input x interacts with an unbounded prover to determine whether x is contained in a language $$\mathcal {L}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>L</mml:mi> </mml:math> . In addition to completeness and soundness, the instance-hiding property requires that the prover should not learn anything about x in the course of the interaction. Such proof systems capture natural privacy properties and may be seen as a generalization of the influential concept of randomized encodings (Ishai and Kushilevitz, in: Proceedings 41st annual symposium on foundations of computer science, pp 294–304, 2000; Applebaum et al., in: 45th annual IEEE symposium on foundations of computer science, pp 166–175, 2004; Agrawal et al., in: Halldórsson, Iwama, Kobayashi, Speckmann (eds) Automata, languages, and programming, Springer, Berlin, Heidelberg, pp 1–13, 2015) and as a counterpart to zero-knowledge proofs (Goldwasser et al., in: Symposium on the theory of computing, 1985). We investigate the properties and power of such instance-hiding proofs and show the following: Any language with an IHIP is contained in $${\mathsf {NP/poly}}\cap {\mathsf {coNP/poly}}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mrow> <mml:mi>NP</mml:mi> <mml:mo>/</mml:mo> <mml:mi>poly</mml:mi> </mml:mrow> <mml:mo>∩</mml:mo> <mml:mrow> <mml:mi>coNP</mml:mi> <mml:mo>/</mml:mo> <mml:mi>poly</mml:mi> </mml:mrow> </mml:mrow> </mml:math> . If an average-case hard language has a constant-round IHIP, then infinitely often non-uniform one-way functions exist. There is an oracle with respect to which there is a language that has an IHIP but not an SZK proof. IHIP’s are closed under composition with any efficiently computable function. We further study a stronger version of IHIP (that we call Simulatable IHIP) where the view of the honest prover can be efficiently simulated. For these, we obtain stronger versions of some of the above: Any language with a Simulatable IHIP is contained in $${\textsf{AM}}\cap {\textsf{coAM}}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>AM</mml:mi> <mml:mo>∩</mml:mo> <mml:mi>coAM</mml:mi> </mml:mrow> </mml:math> . If a worst-case hard language has a Simulatable IHIP, then explicit uniform one-way functions exist.