Document Open Access Logo

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

Authors Gil Segev, Ido Shahaf

PDF
Thumbnail PDF

File

LIPIcs.ITC.2020.10.pdf
  • Filesize: 0.66 MB
  • 23 pages

Document Identifiers

Author Details

Gil Segev
  • School of Computer Science and Engineering, Hebrew University of Jerusalem, Jerusalem, Israel
Ido Shahaf
  • School of Computer Science and Engineering, Hebrew University of Jerusalem, Jerusalem, Israel

Funding

Supported by the European Union’s Horizon 2020 Framework Program (H2020) via an ERC Grant (Grant No. 714253).
  • Shahaf, Ido: Supported by the Clore Israel Foundation via the Clore Scholars Programme.

Cite As Get BibTex

Gil Segev and Ido Shahaf. Hardness vs. (Very Little) Structure in Cryptography: A Multi-Prover Interactive Proofs Perspective. In 1st Conference on Information-Theoretic Cryptography (ITC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 163, pp. 10:1-10:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020) https://doi.org/10.4230/LIPIcs.ITC.2020.10

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 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 NP ∩ coNP or 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 MIP ∩ coMIP from a black-box perspective. Conceptually, given that MIP = NEXP, our result rules out languages with very little structure. 
Already the cases of languages that have IP or 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 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 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 NP-verifiers both for the language itself and for its complement and for languages that have a statistical zero-knowledge proof system.

Subject Classification

ACM Subject Classification
  • Theory of computation → Computational complexity and cryptography
Keywords
  • Hardness vs. Structure
  • Black-box Constructions
  • Interactive Proofs

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. William Aiello and Johan Håstad. Statistical zero-knowledge languages can be recognized in two rounds. Journal of Computer and System Sciences, 42(3):327-345, 1991. Google Scholar
  2. Gilad Asharov and Gil Segev. Limits on the power of indistinguishability obfuscation and functional encryption. In Proceedings of the 56th Annual IEEE Symposium on Foundations of Computer Science, pages 191-209, 2015. Google Scholar
  3. Gilad Asharov and Gil Segev. On constructing one-way permutations from indistinguishability obfuscation. In Proceedings of the 13th Theory of Cryptography Conference, pages 512-541, 2016. Google Scholar
  4. László Babai, Lance Fortnow, and Carsten Lund. Non-deterministic exponential time has two-prover interactive protocols. Computational Complexity, 1:3-40, 1991. Google Scholar
  5. Boaz Barak. Structure vs. combinatorics in computational complexity. Windows on Theory (available at https://windowsontheory.org/2013/10/07/structure-vs-combinatorics-in-computational-complexity/), 2013. URL: https://windowsontheory.org/2013/10/07/structure-vs-combinatorics-in-computational-complexity/.
  6. Boaz Barak, Oded Goldreich, Russell Impagliazzo, Steven Rudich, Amit Sahai, Salil P. Vadhan, and Ke Yang. On the (im)possibility of obfuscating programs. Journal of the ACM, 59(2):6, 2012. Google Scholar
  7. Paul Beame, Stephen A. Cook, Jeff Edmonds, Russell Impagliazzo, and Toniann Pitassi. The relative complexity of NP search problems. In Proceedings of the 27th Annual ACM Symposium on Theory of Computing, pages 303-314, 1995. Google Scholar
  8. Michael Ben-Or, Shafi Goldwasser, Joe Kilian, and Avi Wigderson. Multi-prover interactive proofs: How to remove intractability assumptions. In Proceedings of the 20th Annual ACM Symposium on Theory of Computing, pages 113-131, 1988. Google Scholar
  9. Nir Bitansky and Akshay Degwekar. On the complexity of collision resistant hash functions: New and old black-box separations. In Proceedings of the 17th Theory of Cryptography Conference, pages 422-450, 2019. Google Scholar
  10. Nir Bitansky, Akshay Degwekar, and Vinod Vaikuntanathan. Structure vs. hardness through the obfuscation lens. In Advances in Cryptology - CRYPTO '17, pages 696-723, 2017. Google Scholar
  11. Nir Bitansky, Omer Paneth, and Alon Rosen. On the cryptographic hardness of finding a Nash equilibrium. In Proceedings of the 56th Annual IEEE Symposium on Foundations of Computer Science, pages 1480-1498, 2015. Google Scholar
  12. Nir Bitansky, Omer Paneth, and Daniel Wichs. Perfect structure on the edge of chaos - trapdoor permutations from indistinguishability obfuscation. In Proceedings of the 13th Theory of Cryptography Conference, pages 474-502, 2016. Google Scholar
  13. Manuel Blum and Russell Impagliazzo. Generic oracles and oracle classes. In Proceedings of the 28th Annual IEEE Symposium on Foundations of Computer Science, pages 118-126, 1987. Google Scholar
  14. Andrej Bogdanov and Chin Ho Lee. Limits of provable security for homomorphic encryption. In Advances in Cryptology - CRYPTO '13, pages 111-128, 2013. Google Scholar
  15. Gilles Brassard. Relativized cryptography. In Proceedings of the 20th Annual IEEE Symposium on Foundations of Computer Science, pages 383-391, 1979. Google Scholar
  16. Richard Chang, Benny Chor, Oded Goldreich, Juris Hartmanis, Johan Håstad, Desh Ranjan, and Pankaj Rohatgi. The random oracle hypothesis is false. Journal of Computer and System Sciences, 49(1):24-39, 1994. Google Scholar
  17. Stephen A. Cook, Russell Impagliazzo, and Tomoyuki Yamakami. A tight relationship between generic oracles and type-2 complexity theory. Information and Computation, 137(2):159-170, 1997. Google Scholar
  18. Whitfield Diffie and Martin E. Hellman. New directions in cryptography. IEEE Transactions on Information Theorey, 22(6):644-654, 1976. Google Scholar
  19. Lance Jeremy Fortnow. Complexity-theoretic aspects of interactive proof systems. Ph.D. Thesis, MIT, 1989. Google Scholar
  20. Sanjam Garg, Craig Gentry, Shai Halevi, Mariana Raykova, Amit Sahai, and Brent Waters. Candidate indistinguishability obfuscation and functional encryption for all circuits. In Proceedings of the 54th Annual IEEE Symposium on Foundations of Computer Science, pages 40-49, 2013. Google Scholar
  21. Sanjam Garg, Omkant Pandey, and Akshayaram Srinivasan. Revisiting the cryptographic hardness of finding a Nash equilibrium. In Advances in Cryptology - CRYPTO '16, pages 579-604, 2016. Google Scholar
  22. Oded Goldreich. On security preserving reductions - revised terminology. Cryptology ePrint Archive, Report 2000/001, 2000. Google Scholar
  23. Shafi Goldwasser and Silvio Micali. Probabilistic encryption. Journal of Computer and System Sciences, 28(2):270-299, 1984. Google Scholar
  24. Shafi Goldwasser, Silvio Micali, and Charles Rackoff. The knowledge complexity of interactive proof systems. SIAM Journal on Computing, 18(1):186-208, 1989. Google Scholar
  25. Juris Hartmanis and Lane A. Hemachandra. One-way functions, robustness, and the non-isomorphism of NP-complete sets. In Proceedings of the 2nd Annual Conference on Structure in Complexity Theory, 1987. Google Scholar
  26. Russell Impagliazzo and Steven Rudich. Limits on the provable consequences of one-way permutations. In Proceedings of the 21st Annual ACM Symposium on Theory of Computing, pages 44-61, 1989. Google Scholar
  27. Ilan Komargodski, Tal Moran, Moni Naor, Rafael Pass, Alon Rosen, and Eylon Yogev. One-way functions and (im)perfect obfuscation. In Proceedings of the 55th Annual IEEE Symposium on Foundations of Computer Science, pages 374-383, 2014. Google Scholar
  28. Tianren Liu and Vinod Vaikuntanathan. On basing private information retrieval on NP-hardness. In Proceedings on the 13th Theory of Cryptography Conference, pages 372-386, 2016. Google Scholar
  29. Michael Luby. Pseudorandomness and Cryptographic Applications. Princeton University Press, 1996. Google Scholar
  30. Carsten Lund, Lance Fortnow, Howard J. Karloff, and Noam Nisan. Algebraic methods for interactive proof systems. Journal of the ACM, 39(4):859-868, 1992. Google Scholar
  31. Omer Reingold, Luca Trevisan, and Salil P. Vadhan. Notions of reducibility between cryptographic primitives. In Proceedings of the 1st Theory of Cryptography Conference, TCC 2004, pages 1-20, 2004. Google Scholar
  32. Ronald L. Rivest, Adi Shamir, and Leonard M. Adleman. A method for obtaining digital signatures and public-key cryptosystems. Communication of the ACM, 21(2):120-126, 1978. Google Scholar
  33. Steven Rudich. Limits on the Provable Consequences of One-way Functions. PhD thesis, EECS Department, University of California, Berkeley, 1988. Google Scholar
  34. Amit Sahai and Brent Waters. How to use indistinguishability obfuscation: Deniable encryption, and more. In Proceedings of the 46th Annual ACM Symposium on Theory of Computing, pages 475-484, 2014. Google Scholar
  35. Gil Segev and Ido Shahaf. Hardness vs. (very little) structure in cryptography: A multi-prover interactive proofs perspective. Cryptology ePrint Archive, Report 2020/330, 2020. URL: https://eprint.iacr.org/2020/330.
  36. Adi Shamir. IP=PSPACE. In Proceedings of the 31st Annual IEEE Symposium on Foundations of Computer Science, pages 11-15, 1990. Google Scholar
  37. Brent Waters. A punctured programming approach to adaptively secure functional encryption. In Advances in Cryptology - CRYPTO '15, pages 678-697, 2015. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact