International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Paper: No-signaling Linear PCPs

Authors:
Susumu Kiyoshima
Download:
DOI: 10.1007/978-3-030-03807-6_3
Search ePrint
Search Google
Conference: TCC 2018
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 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.
BibTeX
@inproceedings{tcc-2018-29004,
  title={No-signaling Linear PCPs},
  booktitle={Theory of Cryptography},
  series={Theory of Cryptography},
  publisher={Springer},
  volume={11239},
  pages={67-97},
  doi={10.1007/978-3-030-03807-6_3},
  author={Susumu Kiyoshima},
  year=2018
}