Welcome to the resource topic for 2024/1829
Title:
Compiled Nonlocal Games from any Trapdoor Claw-Free Function
Authors: Kaniuar Bacho, Alexander Kulpe, Giulio Malavolta, Simon Schmidt, Michael Walter
Abstract:A recent work of Kalai et al. (STOC 2023) shows how to compile any multi-player nonlocal game into a protocol with a single computationally-bounded prover. Subsequent works have built on this to develop new cryptographic protocols, where a completely classical client can verify the validity of quantum computation done by a quantum server. Their compiler relies on the existence of quantum fully-homomorphic encryption.
In this work, we propose a new compiler for transforming nonlocal games into single-prover protocols.
Our compiler is based on the framework of measurement-based quantum computation.
It can be instantiated assuming the existence of \emph{any} trapdoor function that satisfies the claw-freeness property.
Leveraging results by Natarajan and Zhang (FOCS 2023) on compiled nonlocal games, our work implies the existence of new protocols to classically verify quantum computation from potentially weaker computational assumptions than previously known.
ePrint: https://eprint.iacr.org/2024/1829
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .