Paper 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
Metadata
- Available format(s)
-
PDF
- Publication info
- Published elsewhere. Major revision. Conference on Information-Theoretic Cryptography (ITC) 2020
- Contact author(s)
-
ido shahaf @ cs huji ac il
segev @ cs huji ac il - History
- 2020-10-11: revised
- 2020-03-17: received
- See all versions
- Short URL
- https://ia.cr/2020/330
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2020/330, author = {Gil Segev and Ido Shahaf}, title = {Hardness vs. (Very Little) Structure in Cryptography: A Multi-Prover Interactive Proofs Perspective}, howpublished = {Cryptology {ePrint} Archive, Paper 2020/330}, year = {2020}, url = {https://eprint.iacr.org/2020/330} }