Technical Report MSC-2021-20

Title: PCPs and Cryptography: New Limitations and Opportunities
Authors: Liron Bronfman
Supervisors: Ron Rothblum
PDFCurrently accessibly only within the Technion network
Abstract: The combination of information-theoretic proof systems, such as interactive proofs and probabilistically checkable proofs (PCPs) together with cryptography has been extremely fruitful, with diverse applications both in theory and in practice. In this thesis, we continue this line of research by showing new limitations and opportunities that arise from the combination of information-theoretic proof systems with cryptographic tools. Our main contributions are the following:

1. Opportunities: We consider two information theoretic objects that are known not to exist under standard complexity assumptions. The first, is a succinct PCP, in which the length of the PCP proof string is a fixed polynomial in the length of the original NP witness, rather than the (potentially much longer) instance. The second object is instance compression, which is a method for reducing long instances down to their witness length while preserving their correctness.

We bypass known impossibility results for these objects, by considering meaningful computational relaxations and constructing these computational versions for a large class of NP relations, under the sub-exponential learning with errors assumption.

2. Limitations: The Fiat-Shamir transform is a method for transforming interactive (public-coin) protocols to ones that are non-interactive and serves as a popular heuristic for designing efficient non-interactive arguments. One of the most notable applications of Fiat-Shamir is to Kilian’s efficient interactive argument-system, based on PCPs and collision-resistant hashing, as well as its more modern incarnations. We show that this paradigm is not sound unless one uses the components that underlie Kilian’s protocol in a non-generic way.

CopyrightThe above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information

Remark: Any link to this technical report should be to this page (, rather than to the URL of the PDF files directly. The latter URLs may change without notice.

To the list of the MSC technical reports of 2021
To the main CS technical reports page

Computer science department, Technion