Paper 2024/1829
Compiled Nonlocal Games from any Trapdoor Claw-Free Function
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.
Metadata
- Available format(s)
-
PDF
- Category
- Foundations
- Publication info
- Preprint.
- Keywords
- Quantum Cryptography
- Contact author(s)
-
kano-b @ hotmail de
alexander kulpe @ rub de
giulio malavolta @ hotmail it
s schmidt @ rub de
michael walter @ gmail com - History
- 2024-11-08: approved
- 2024-11-07: received
- See all versions
- Short URL
- https://ia.cr/2024/1829
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2024/1829,
author = {Kaniuar Bacho and Alexander Kulpe and Giulio Malavolta and Simon Schmidt and Michael Walter},
title = {Compiled Nonlocal Games from any Trapdoor Claw-Free Function},
howpublished = {Cryptology {ePrint} Archive, Paper 2024/1829},
year = {2024},
url = {https://eprint.iacr.org/2024/1829}
}
