Efficient Arguments without Short PCPs

Yuval Ishai
Technion - Israel Institute of Technology

Current constructions of communication-efficient argument systems combine a short (polynomial-size) PCP with a cryptographic hashing technique. We suggest an alternative approach for this problem that simplifies the underlying PCP machinery using a stronger cryptographic technique.

Joint work with Eyal Kushilevitz and Rafail Ostrovsky.


Back to Workshop II: Locally decodable codes, private information retrieval, privacy-preserving data-mining, and public key encryption with special properties