Cryptology ePrint Archive: Report 2018/649

No-signaling Linear PCPs

Susumu Kiyoshima

Abstract: In this paper, we give a no-signaling linear probabilistically checkable proof (PCP) system for P, i.e., a PCP system such that (1) the PCP oracle is a linear function and (2) the soundness holds against any (computational) no-signaling cheating prover, who answers 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 (which can be reused multiple times) but has a simpler structure and makes use of cheaper cryptographic primitives such as additive/multiplicative homomorphic encryption schemes.

Category / Keywords: foundations /

Date: received 5 Jul 2018

Contact author: kiyoshima susumu at lab ntt co jp

Available format(s): PDF | BibTeX Citation

Version: 20180706:125928 (All versions of this report)

Short URL: ia.cr/2018/649


[ Cryptology ePrint archive ]