CryptoDB
No-Signaling Linear PCPs
| Authors: | |
|---|---|
| Download: | |
| Abstract: | In this paper, we give a no-signaling linear probabilistically checkable proof (PCP) system for polynomial-time deterministic computation, i.e., a PCP system for $$\mathcal {P}$$ P such that (1) the honest PCP oracle is a linear function and (2) the soundness holds against any (computational) no-signaling cheating prover, who is allowed to answer each query according to a distribution that depends on the entire query set in a certain way. To the best of our knowledge, our construction is the first PCP system that satisfies these two properties simultaneously. As an application of our PCP system, we obtain a 2-message delegating computation scheme by using a known transformation. Compared with the existing 2-message delegating computation schemes that are based on standard cryptographic assumptions, our scheme requires preprocessing but has a simpler structure and makes use of different (possibly cheaper) standard cryptographic primitives, namely additive/multiplicative homomorphic encryption schemes. |
BibTeX
@article{jofc-2023-33066,
title={No-Signaling Linear PCPs},
journal={Journal of Cryptology},
publisher={Springer},
volume={36},
doi={10.1007/s00145-023-09448-4},
author={Susumu Kiyoshima},
year=2023
}