Paper 2023/1378
Advisor-Verifier-Prover Games and the Hardness of Information Theoretic Cryptography
Abstract
A major open problem in information-theoretic cryptography is to obtain a super-polynomial lower bound for the communication complexity of basic cryptographic tasks. This question is wide open even for very powerful non-interactive primitives such as private information retrieval (or locally-decodable codes), general secret sharing schemes, conditional disclosure of secrets, and fully-decomposable randomized encoding (or garbling schemes). In fact, for all these primitives we do not even have super-linear lower bounds. Furthermore, it is unknown how to relate these questions to each other or to other complexity-theoretic questions.
In this note, we relate all these questions to the classical topic of query/space trade-offs, lifted to the setting of interactive proof systems. Specifically, we consider the following Advisor-Verifier-Prover (AVP) game: First, a function
Metadata
- Available format(s)
-
PDF
- Category
- Cryptographic protocols
- Publication info
- Preprint.
- Keywords
- Information Theoretic CryptographySecret SharingPrivate Information RetrievalInteractive Proof Systems
- Contact author(s)
-
benny applebaum @ gmail com
odednir123 @ gmail com - History
- 2023-09-15: approved
- 2023-09-14: received
- See all versions
- Short URL
- https://ia.cr/2023/1378
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2023/1378, author = {Benny Applebaum and Oded Nir}, title = {Advisor-Verifier-Prover Games and the Hardness of Information Theoretic Cryptography}, howpublished = {Cryptology {ePrint} Archive, Paper 2023/1378}, year = {2023}, url = {https://eprint.iacr.org/2023/1378} }