Paper 2018/649
No-signaling Linear PCPs
Susumu Kiyoshima
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 P such that (1) the 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 scheme for delegating computation by using a known transformation. Compared with existing 2-message delegation schemes 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.
Note: (24 Sep 2018) added references to concurrent indecent works, and made some minor editorial updates; (19 Nov 2018) fixed typo.
Metadata
- Available format(s)
- Category
- Foundations
- Publication info
- A major revision of an IACR publication in TCC 2018
- Contact author(s)
- kiyoshima susumu @ lab ntt co jp
- History
- 2019-01-18: last of 4 revisions
- 2018-07-06: received
- See all versions
- Short URL
- https://ia.cr/2018/649
- License
-
CC BY