Cryptology ePrint Archive: Report 2020/330

Hardness vs. (Very Little) Structure in Cryptography: A Multi-Prover Interactive Proofs Perspective

Gil Segev and Ido Shahaf

Abstract: The hardness of highly-structured computational problems gives rise to a variety of public-key primitives. On one hand, the structure exhibited by such problems underlies the basic functionality of public-key primitives, but on the other hand it may endanger public-key cryptography in its entirety via potential algorithmic advances. This subtle interplay initiated a fundamental line of research on whether structure is inherently necessary for cryptography, starting with Rudich's early work (PhD Thesis '88) and recently leading to that of Bitansky, Degwekar and Vaikuntanathan (CRYPTO '17).

Identifying the structure of computational problems with their corresponding complexity classes, Bitansky et al. proved that a variety of public-key primitives (e.g., public-key encryption, oblivious transfer and even functional encryption) cannot be used in a black-box manner to construct either any hard language that has $\mathsf{NP}$-verifiers both for the language itself and for its complement, or any hard language (and even promise problem) that has a statistical zero-knowledge proof system -- corresponding to hardness in the structured classes $\mathsf{NP} \cap \mathsf{coNP}$ or $\mathsf{SZK}$, respectively, from a black-box perspective.

In this work we prove that the same variety of public-key primitives do not inherently require even very little structure in a black-box manner: We prove that they do not imply any hard language that has multi-prover interactive proof systems both for the language and for its complement -- corresponding to hardness in the class $\mathsf{MIP} \cap \mathsf{coMIP}$ from a black-box perspective. Conceptually, given that $\mathsf{MIP} = \mathsf{NEXP}$, our result rules out languages with very little structure.

Already the cases of languages that have $\mathsf{IP}$ or $\mathsf{AM}$ proof systems both for the language itself and for its complement, which we rule out as immediate corollaries, lead to intriguing insights. For the case of $\mathsf{IP}$, where our result can be circumvented using non-black-box techniques, we reveal a gap between black-box and non-black-box techniques. For the case of $\mathsf{AM}$, where circumventing our result via non-black-box techniques would be a major development, we both strengthen and unify the proofs of Bitansky et al. for languages that have $\mathsf{NP}$-verifiers both for the language itself and for its complement and for languages that have a statistical zero-knowledge proof system.

Category / Keywords:

Original Publication (in the same form): Conference on Information-Theoretic Cryptography (ITC) 2020

Date: received 17 Mar 2020

Contact author: ido shahaf at cs huji ac il,segev@cs huji ac il

Available format(s): PDF | BibTeX Citation

Version: 20200317:183614 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]