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 <InlineEquation ID="IEq1"> <EquationSource Format="TEX">$\mathcal {L}$</EquationSource> <EquationSource Format="MATHML"><math> <mi mathvariant="script">L</mi> </math></EquationSource> </InlineEquation>. 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: <OrderedList> <ListItem> <ItemNumber>1.</ItemNumber> <ItemContent> Any language with an IHIP is contained in <InlineEquation ID="IEq2"> <EquationSource Format="TEX">${\mathsf {NP/poly}}\cap {\mathsf {coNP/poly}}$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mrow> <mi mathvariant="sans-serif">NP</mi> <mo stretchy="false">/</mo> <mi mathvariant="sans-serif">poly</mi> </mrow> <mo>∩</mo> <mrow> <mi mathvariant="sans-serif">coNP</mi> <mo stretchy="false">/</mo> <mi mathvariant="sans-serif">poly</mi> </mrow> </mrow> </math></EquationSource> </InlineEquation>. </ItemContent> </ListItem> <ListItem> <ItemNumber>2.</ItemNumber> <ItemContent> If an average-case hard language has a constant-round IHIP, then infinitely often non-uniform one-way functions exist. </ItemContent> </ListItem> <ListItem> <ItemNumber>3.</ItemNumber> <ItemContent> There is an oracle with respect to which there is a language that has an IHIP but not an SZK proof. </ItemContent> </ListItem> <ListItem> <ItemNumber>4.</ItemNumber> <ItemContent> IHIP’s are closed under composition with any efficiently computable function. </ItemContent> </ListItem> </OrderedList> 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: <OrderedList> <ListItem> <ItemNumber>5.</ItemNumber> <ItemContent> Any language with a Simulatable IHIP is contained in <InlineEquation ID="IEq3"> <EquationSource Format="TEX">${\textsf{AM}}\cap {\textsf{coAM}}$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi mathvariant="sans-serif">AM</mi> <mo>∩</mo> <mi mathvariant="sans-serif">coAM</mi> </mrow> </math></EquationSource> </InlineEquation>. </ItemContent> </ListItem> <ListItem> <ItemNumber>6.</ItemNumber> <ItemContent> If a worst-case hard language has a Simulatable IHIP, then explicit uniform one-way functions exist. </ItemContent> </ListItem> </OrderedList>

Instance-Hiding Interactive Proofs

期刊论文
出版模式：

开放获取
发表日期：

2026年3月26日

查看全文

Changrui Mu,
Prashant Nalini Vasudevan

摘要

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}$ $L$ . 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: 1.

Any language with an IHIP is contained in ${\mathsf {NP/poly}}\cap {\mathsf {coNP/poly}}$ $NP / poly \cap coNP / poly$ .

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: 5.

Any language with a Simulatable IHIP is contained in ${\textsf{AM}}\cap {\textsf{coAM}}$ $AM \cap coAM$ .

If a worst-case hard language has a Simulatable IHIP, then explicit uniform one-way functions exist.