Delegating Computation

煤气表校准仪 正确性 数学证明 随机预言 甲骨文公司 离散数学 证明复杂性 时间复杂性 鸽子洞原理 计算 数学 计算机科学 复杂度等级 可计算函数 通信复杂性 理论计算机科学 算法 程序设计语言 公钥密码术 几何学 操作系统 加密
作者
Shafi Goldwasser,Yael Tauman Kalai,Guy N. Rothblum
出处
期刊:Journal of the ACM [Association for Computing Machinery]
卷期号:62 (4): 1-64 被引量:198
标识
DOI:10.1145/2699436
摘要

In this work we study interactive proofs for tractable languages. The (honest) prover should be efficient and run in polynomial time or, in other words, a “muggle”.1 The verifier should be super-efficient and run in nearly linear time. These proof systems can be used for delegating computation: a server can run a computation for a client and interactively prove the correctness of the result. The client can verify the result’s correctness in nearly linear time (instead of running the entire computation itself). Previously, related questions were considered in the holographic proof setting by Babai et al. [1991b] in the argument setting under computational assumptions by Kilian, and in the random oracle model by Micali [1994]. Our focus, however, is on the original interactive proof model where no assumptions are made on the computational power or adaptiveness of dishonest provers. Our main technical theorem gives a public coin interactive proof for any language computable by a log-space uniform boolean circuit with depth d and input length n . The verifier runs in time n · poly( d , log( n )) and space O (log( n )), the communication complexity is poly( d , log( n )), and the prover runs in time poly( n ). In particular, for languages computable by log-space uniform NC (circuits of polylog( n ) depth), the prover is efficient, the verifier runs in time n · polylog( n ) and space O (log( n )), and the communication complexity is polylog( n ). Using this theorem we make progress on several questions. --- We show how to construct 1-round computationally sound arguments with polylog communication for any log-space uniform NC computation. The verifier runs in quasi-linear time. This result uses a recent transformation of Kalai and Raz from public coin interactive proofs to 1-round arguments . The soundness of the argument system is based on the existence of a PIR scheme with polylog communication. --- We construct interactive proofs with public coin, log-space, poly-time verifiers for all of P are given. This settles an open question regarding the expressive power of proof systems with such verifiers. --- We construct zero-knowledge interactive proofs are given with communication complexity quasi-linear in the witness length for any NP language verifiable in NC , based on the existence of 1-way functions. --- We construct probabilistically checkable arguments (a model due to Kalai and Raz) of size polynomial in the witness length (rather than instance length) for any NP language verifiable in NC , under computational assumptions, are provided.
最长约 10秒,即可获得该文献文件

科研通智能强力驱动
Strongly Powered by AbleSci AI
科研通是完全免费的文献互助平台,具备全网最快的应助速度,最高的求助完成率。 对每一个文献求助,科研通都将尽心尽力,给求助人一个满意的交代。
实时播报
GraveDiggaz完成签到,获得积分10
刚刚
1秒前
零零五完成签到,获得积分10
1秒前
2秒前
2秒前
3秒前
123完成签到,获得积分10
3秒前
3秒前
4秒前
恐怖稽器人完成签到,获得积分10
4秒前
zeroayanami0完成签到,获得积分10
4秒前
5秒前
11完成签到,获得积分10
6秒前
现代雪晴完成签到,获得积分10
6秒前
sssyz发布了新的文献求助10
6秒前
dogking发布了新的文献求助10
6秒前
腼腆的戾发布了新的文献求助10
7秒前
5tcl完成签到,获得积分10
7秒前
cxyyy完成签到,获得积分10
7秒前
7秒前
lele发布了新的文献求助10
7秒前
香蕉觅云的应助被123采纳,获得10
8秒前
8秒前
8秒前
yy发布了新的文献求助30
8秒前
8秒前
9秒前
LZ发布了新的文献求助10
10秒前
不再挨训完成签到 ,获得积分10
10秒前
10秒前
10秒前
星空发布了新的文献求助10
10秒前
11秒前
王培德完成签到 ,获得积分10
11秒前
zz完成签到,获得积分10
12秒前
腼腆的戾完成签到,获得积分10
12秒前
77完成签到 ,获得积分10
13秒前
zhangzz发布了新的文献求助10
13秒前
今后的应助被sh131采纳,获得10
13秒前
13秒前
高分求助中
(应助此贴封号)【重要!!请各用户(尤其是新用户)详细阅读】【科研通的精品贴汇总】 10000
拉伸高分子熔体中缠结行为的模拟和小角中子散射研究 1700
The World Atlas of Wine 9th edition 1000
奈特基础组织学:配套组织病理学(第4版)(Netter's Essential Histology With Correlated Histopathology) 800
八旗制度の研究 600
高分子基功能界面水蒸发材料与应用研究 500
外场增强的水汽发电研究 500
热门求助领域 (近24小时)
化学 材料科学 医学 生物 纳米技术 计算机科学 工程类 有机化学 化学工程 生物化学 物理 复合材料 内科学 催化作用 光电子学 人工智能 细胞生物学 无机化学 物理化学 数学
热门帖子
关注 科研通微信公众号,转发送积分 8185894
求助须知:如何正确求助?哪些是违规求助? 9574569
关于积分的说明 21836585
捐赠科研通 7783675
什么是DOI,文献DOI怎么找? 3434685
关于科研通互助平台的介绍 2559031
邀请新用户注册赠送积分活动 2481484