International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Susumu Kiyoshima

Affiliation: NTT

Publications

Year
Venue
Title
2018
EUROCRYPT
2018
TCC
No-signaling Linear PCPs
Susumu Kiyoshima
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.
2017
EUROCRYPT
2017
TCC
2016
EUROCRYPT
2015
EPRINT
2015
EPRINT
2015
TCC
2015
CRYPTO
2015
ASIACRYPT
2014
CRYPTO
2014
TCC
2014
EPRINT

Program Committees

Eurocrypt 2020
TCC 2019