No-signaling Linear PCPs

Susumu Kiyoshima

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 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.

Note: (24 Sep 2018) added references to concurrent independent works, and made some minor editorial updates; (19 Nov 2018) fixed typo; (18 Jan 2019) made major editorial updates and fixed typo.

Metadata

Available format(s): PDF
Category: Foundations
Publication info: A major revision of an IACR publication in TCC 2018
DOI: 10.1007/978-3-030-03807-6_3
Contact author(s): susumu @ kiyoshima info
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

BibTeX

@misc{cryptoeprint:2018/649,
      author = {Susumu Kiyoshima},
      title = {No-signaling Linear {PCPs}},
      howpublished = {Cryptology {ePrint} Archive, Paper 2018/649},
      year = {2018},
      doi = {10.1007/978-3-030-03807-6_3},
      url = {https://eprint.iacr.org/2018/649}
}