| NP问题的最优轮复杂性知识的零知识证明 |
| 其他题名 | round-optimal zero-knowledge proofs of knowledge for np
|
| 李红达; 冯登国; 李宝; 徐海霞
|
| 2012
|
| 发表期刊 | 中国科学:信息科学
 |
| ISSN | 1674-7267
|
| 卷号 | 42期号:1页码:20-31 |
| 摘要 | NP问题已有的知识的(黑箱)零知识证明都是非常数轮的,因此,在标准的复杂性假设下,NP问题是否存在常数轮的(黑箱)知识的零知识证明是一个有意义的问题.本文对该问题进行了研究,在一定的假设下给出了HC问题的两个常数轮知识的零知识证明系统.根据Katz最近的研究结果,在多项式分层不坍塌的条件下,本文基于claw-free陷门置换给出的HC问题的5轮知识的零知识证明系统具有最优的轮复杂性. |
| 收录类别 | CNKI
; CSCD
|
| 其他摘要 | It is well known that all the known black-box zero-knowledge proofs of knowledge for NP are nonconstant-round.Whether there exit constant-round black-box zero-knowledge proofs of knowledge for all NP languages under certain standard assumptions is an open problem.This paper focuses on the problem and gives a positive answer by presenting two constructions of constant-round(black-box) zero-knowledge proofs of knowledge for the HC(Hamiltonian cycle) problem.By the recent result of Katz,our second construction which relies on the existence of claw-free functions has optimal round complexity(5-round) assuming the polynomial hierarchy does not collapse. |
| 关键词 | 零知识证明
知识的证明
黑箱模拟
常数轮
密码学
|
| 部门归属 | 信息安全国家重点实验室;中国科学院研究生院;中国科学院软件研究所;
|
| 学科领域 | Computer Science (Provided By Thomson Reuters)
|
| 资助者 | 国家重点基础研究发展计划(批准号:2007CB311202,2007CB311201)|国家自然科学基金(批准号:60970139)资助项目
|
| 语种 | 中文
|
| CSCD记录号 | CSCD:4537713
|
| 内容类型 | 期刊论文
|
| URI标识 | http://ir.iscas.ac.cn/handle/311060/14907
|
| 专题 | 中国科学院软件研究所
|
推荐引用方式
GB/T 7714 |
李红达,冯登国,李宝,等. NP问题的最优轮复杂性知识的零知识证明[J]. 中国科学:信息科学,2012,42(1):20-31.
|
| APA |
李红达,冯登国,李宝,&徐海霞.(2012).NP问题的最优轮复杂性知识的零知识证明.中国科学:信息科学,42(1),20-31.
|
| MLA |
李红达,et al."NP问题的最优轮复杂性知识的零知识证明".中国科学:信息科学 42.1(2012):20-31.
|
除非特别说明，本系统中所有内容都受版权保护，并保留所有权利。
修改评论