纯公钥模型下对NP语言的高效并发零知识证明系统
作者:
基金项目:

Supported by the National Natural Science Foundation of China under Grant No.60673069 (国家自然科学基金); the National High-Tech Research and Development Plan of China under Grant No.2003AA144030 (国家高技术研究发展计划(863))


Efficient Concurrent Zero Knowledge Arguments for NP in the Bare Public-Key Model
  • 摘要
  • | |
  • 访问统计
  • |
  • 参考文献 [18]
  • |
  • 相似文献 [20]
  • | | |
  • 文章评论
    摘要:

    提出了一种从3轮公开掷币的对任何NP语言的诚实验证者零知识证明系统到纯公钥模型下4轮(轮最优)对同一语言的具有并发合理性的并发零知识证明系统.该转化方法有如下优点:1) 它只引起O(1)(常数个)额外的模指数运算,相比Di Crescenzo等人在ICALP 05上提出的需要((n)个额外的模指数运算的转化方法,该系统在效率上有着本质上的提高,而所需的困难性假设不变;2) 在离散对数假设下,该转化方法产生一个完美零知识证明系统.注意到Di Crescenzo等人提出的系统只具有计算零知识性质.该转化方法依赖于一个特殊的对承诺中的离散对数的3轮诚实验证者零知识的证明系统.构造了两个基于不同承诺方案的只需要常数个模指数运算的系统,这种系统可能有着独立价值.

    Abstract:

    This paper shows how to efficiently transform any 3-round public-coin honest verifier zero knowledge argument system for any language in NP into a 4 round (round-optimal) concurrent zero knowledge argument for the same language in the bare public-key model. The transformation has the following properties: 1) incurs only O(1) (small constant, about 20) additional modular exponentiations. Compared to the concurrent zero knowledge protocol proposed by Di Crescenzo and Visconti in ICALP 2005, in which their transformation requires an overhead of ((n), the protocol is significantly more efficient under the same intractability assumptions; 2) yields a perfect zero knowledge argument under DL assumption. Note that the Di Crescenzo, et al.'s argument system enjoys only computational zero knowledge property. The transformation relies on a specific 3-round honest verifier zero knowledge proof of knowledge for committed discrete log. Such protocols that require only O(1) modular exponentiations based on different kinds of commitment scheme are developed and they may be of independent interest.

    参考文献
    [1]Goldwasser S,Micali S,Rackoff C.The knowledge complexity of interactive proof systems.SIAM.Journal Computing,1989,18(1):186-208.
    [2]Micali S,Wigderson A.Proofs that yield nothing but their validity or all languages in NP have zero-knowledge proof systems.Journal of ACM,1991,38(3):691-729.
    [3]Dwork C,Naor M,Sahai A.Concurrent zero-knowledge.In:Vitter J,ed.Proc.of the ACM Symp.on Theory of Computing.New York:ACM Press,1998.409-418.
    [4]Canetti R,Kilian J,Petrank E,Rosen A.Concurrent zero-knowledge requires rounds.In:Vitter J,et al.,eds.Proc.of the ACM Symp.on Theory of Computing.New York:ACM Press,2001.570-579.
    [5]Damgard I.Efficient concurrent zero-knowledge in the auxiliary string model.In:Preneel B,ed.Advances in Cryptology-EUROCYPT.LNCS 1807,Berlin:Springer-Verlag,2000.174-187.
    [6]Barak B.How to go beyond the black-box simulation barrier.In:Proc.of the IEEE Conf.on Foundation of Computer Science.IEEE Computer Society Press,2001.106-115.
    [7]Canetti R,Goldreich O,Goldwasser S,Micali S.Resettable zero knowledge.In:Yao F,et al.,eds.Proc.of the ACM Symp.on Theory of Computing.New York:ACM Press,2000,235-244.
    [8]Di Crescenzo G,Ostrovsky R.On concurrent zero knowledge with preprocessing.In:Wiener M,ed.Advances in Cryptology-Crypto.LNCS1666,Berlin:Springer-Verlag,1999.485-502.
    [9]Micali S,Reyzin L.Soundness in the public-key model.In:Kilian J,ed.Advances in Cryptology-Crypto.LNCS 2139,Berlin:Springer-Verlag,2001.542-565.
    [10]Di Crescenzo G,Persiano G,Visconti I.Constant round resettable zero knowledge with concurrent soundness in the bare public-key model.In:Franklin M,ed.Advances of Cryptology-Crypto.LNCS 3152,Berlin:Springer-Verlag,2004.237-253.
    [11]Di Crescenzo G,Visconti I.Concurrent zero knowledge in the public-key model.In:Italiano GF,ed.Proc.of the Int'l Colloquium on Automata,Languages and Programming.LNCS 3580,Berlin:Springer-Verlag,2005.816-827.1
    [12]Zhao Y.Concurrent/Resettable zero knowledge with concurrent soundness in the bare public-key model and its applications.Report 2003/265,Cryptology ePrint Archive.http://eprint.iacr.org/2003/265
    [13]Visconti I.Efficient zero knowledge on the Internet.In:Bugliesi M,et al.,eds.Proc.of the Int'l Colloquium on Automata,Languages and Programming.LNCS 4052,Berlin:Springer-Verlag,2006.22-33.
    [14]Guillou LC,Quisquater JJ.A practical zero-knowledge protocol fitted to security microprocessors minimizing both transmission and memery.In:Günther CG,ed.Advance in Cryptology-EUROCRYPT.LNCS 330,Berlin:Springer-Verlag,1988.123-128.
    [15]Schnorr CP.Efficient signature generation for smart cards.Journal of Cryptology,1991,4(3):239-252.
    [16]De Santis A,Di Crescenzo G,Persiano G,Yung M.On monotone formaula close of SZK.In:Proc.of the IEEE Conf.on Foundation of Computer Science.IEEE Computer Society Press,1994.454-465.
    [17]Pedersen TP.Non-Interactive and information-theoreticl secure verifiable secret sharing.In:Feigenbaum J,ed.Advances in Cryptology-Crypto.LNCS 576,Berlin:Springer-Verlag,1991.129-140.
    [18]Feige U,Shamir A.Witness indistinguishability and witness hiding protocols.In:Ortiz H,ed.Proc.of the ACM Symp.on Theory of Computing.New York:ACM Press,1990.416-426.
    引证文献
    网友评论
    网友评论
    分享到微博
    发 布
引用本文

邓 燚,林东岱.纯公钥模型下对NP语言的高效并发零知识证明系统.软件学报,2008,19(2):468-478

复制
分享
文章指标
  • 点击次数:5375
  • 下载次数: 5528
  • HTML阅读次数: 0
  • 引用次数: 0
历史
  • 收稿日期:2006-05-18
  • 最后修改日期:2006-10-10
文章二维码
您是第19939888位访问者
版权所有:中国科学院软件研究所 京ICP备05046678号-3
地址:北京市海淀区中关村南四街4号,邮政编码:100190
电话:010-62562563 传真:010-62562533 Email:jos@iscas.ac.cn
技术支持:北京勤云科技发展有限公司

京公网安备 11040202500063号