NP问题的最优轮复杂性知识的零知识证明
文献类型：期刊论文
| 作者 | 李红达 ; 冯登国 ; 李宝 ; 徐海霞 |
| 刊名 | 中国科学:信息科学
 |
| 出版日期 | 2012 |
| 卷号 | 42期号:1页码:20-31 |
| ISSN号 | 1674-7267 |
| 关键词 | 零知识证明 知识的证明 黑箱模拟 常数轮 密码学 |
| 其他题名 | round-optimal zero-knowledge proofs of knowledge for np |
| 中文摘要 | NP问题已有的知识的(黑箱)零知识证明都是非常数轮的,因此,在标准的复杂性假设下,NP问题是否存在常数轮的(黑箱)知识的零知识证明是一个有意义的问题.本文对该问题进行了研究,在一定的假设下给出了HC问题的两个常数轮知识的零知识证明系统.根据Katz最近的研究结果,在多项式分层不坍塌的条件下,本文基于claw-free陷门置换给出的HC问题的5轮知识的零知识证明系统具有最优的轮复杂性. |
| 英文摘要 | 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)资助项目 |
| 收录类别 | CNKI ; CSCD |
| 语种 | 中文 |
| CSCD记录号 | CSCD:4537713 |
| 公开日期 | 2013-09-17 |
| 源URL | [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. |
入库方式： OAI收割
来源：软件研究所
浏览0
下载0
收藏0
其他版本
除非特别说明，本系统中所有内容都受版权保护，并保留所有权利。