Institutional Repository
| NP问题的最优轮复杂性知识的零知识证明 | |
| Alternative Title | round-optimal zero-knowledge proofs of knowledge for np |
| 李红达; 冯登国; 李宝; 徐海霞 | |
| 2012 | |
| Source | 中国科学:信息科学
 |
| ISSN | 1674-7267 |
| Volume | 42Issue:1Pages:20-31 |
| English Abstract | NP问题已有的知识的(黑箱)零知识证明都是非常数轮的,因此,在标准的复杂性假设下,NP问题是否存在常数轮的(黑箱)知识的零知识证明是一个有意义的问题.本文对该问题进行了研究,在一定的假设下给出了HC问题的两个常数轮知识的零知识证明系统.根据Katz最近的研究结果,在多项式分层不坍塌的条件下,本文基于claw-free陷门置换给出的HC问题的5轮知识的零知识证明系统具有最优的轮复杂性. |
| Indexed Type | CNKI ; CSCD |
| Abstract | 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. |
| Keyword | 零知识证明 知识的证明 黑箱模拟 常数轮 密码学 |
| Department | 信息安全国家重点实验室;中国科学院研究生院;中国科学院软件研究所; |
| Subject | Computer Science (Provided By Thomson Reuters) |
| Sponsorship | 国家重点基础研究发展计划(批准号:2007CB311202,2007CB311201)|国家自然科学基金(批准号:60970139)资助项目 |
| Language | 中文 |
| CSCD ID | CSCD:4537713 |
| Content Type | 期刊论文 |
| URI | http://ir.iscas.ac.cn/handle/311060/14907 |
| Collection | 中国科学院软件研究所 |
| Recommended Citation 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. |
| Files in This Item: | There are no files associated with this item. | |||||
Items in the repository are protected by copyright, with all rights reserved, unless otherwise indicated.
Edit Comment