收稿日期: 2010-02-23
修回日期: 2010-05-07
网络出版日期: 2010-11-15
基金资助
Supported by National Nature Science Foundation of China (60773134, 61003276, 60803128), the National 863 Program (2006AA01Z416), the National 973 Program (2007CB311201), and the 47th Postdoctoral Fund of China(20100470598)
An efficient compiler from Σ-protocol to deniable zero knowledge in CRS model
Received date: 2010-02-23
Revised date: 2010-05-07
Online published: 2010-11-15
给出公共参考串(CRS)模型下可否认零知识的一个正面结果:从Σ-协议到CRS模型下的可否认零知识的高效转化.由Pass在CRYPTO 2003中给出的下界可知,我们的编译器取得了最优的轮效率.此外,转化所增加的通信复杂度较小.
关键词： CRS模型下的可否认零知识; Σ -协议; Σ -编译器
黄桂芳 , 胡磊 , 林东岱 . 从Σ-协议到公共参考串模型下可否认零知识的高效编译器[J]. 中国科学院大学学报, 2010 , 27(6) : 831 -837 . DOI: 10.7523/j.issn.2095-6134.2010.6.015
In this paper, we present a positive result on deniable zero knowledge in the common reference string (CRS) model: an efficient transformation from Σ-protocol to deniable zero knowledge in CRS model. According to the lower bound given by Pass, for deniable zero knowledge in CRS model, our compiler achieves optimal round efficiency. In addition, the transformation induces only a small additive overhead in communication complexity.
Key words： deniable zero knowledge in the CRS model; Σ-protocol; Σ-compiler
[1] Goldwasser S, Micali S, Rackoff C. The knowledge complexity of interactive proof system
[J]. SIAM Journal on Computing, 1989, 18(1): 186-208.
[2] Goldreich O, Micali S, Widerson A. Proofs that yields nothing but their validity or all languages in NP have zero knowledge proof systems
[J]. Journal of ACM, 1991, 38(3): 691-729.
[3] Dwork C, Naor M, Sahai A. Concurrent zero knowledge //Proceedings of the 30th Annual ACM Symposium on Theory of Computing, ACM Press, 1998, 409- 428.
[4] Canetti R, Kilian R, Petrank J, et al. Black-box concurrent zero- knowledge requires (almost) logarithm many rounds
[J]. SIAM Jonrnal on Computing, 2002, 32(1): 1- 47.
[5] Canetti R, Goldreich O, Goldwasser S, et al. Resettable zero knowledge //Proceedings of 32nd Annual ACM Symposium on Theory of Computing. ACM Press, 2000:235-244.
[6] Barak B, Goldreich O, Golawasser S, et al. Resettably-sound zero knowledge and its applications //Proceedings of 42nd Annual Symposium on Foundations of Computer Science. IEEE Computer Society, 2001:116-125.
[7] Blum M, Feldman P, Micali S. Non-interactive zero-knowledge and its applications //Proceedings of the 20th Annual ACM Symposium on Theory of Computing. ACM Press, 1988:103-112.
[8] Damgrd I. Efficient concurrent zero knowledge in the auxiliary string model //Advances in Cryptology-EUROCRYPT 2000. Springer-Verlag, 2000:419- 430.
[9] Canetti R. Universally composable security: A new paradigm for cryptographic protocols //Proceedings of 42nd IEEE Symposium on Foundations of Computer Science, IEEE Computer Society, 2002:136-145.
[10] Canetti R, Fischlin M. Universally composable commitments //Advances in Cryptology-Crypto 2001. Springer-Verlag, 2001:19- 40.
[11] Canetti R, Lindell Y, Ostrovsky R, et al. Universally composable two-party and multi-party computation //Proceedings of 34thAnnual ACM Symposium on Theory of Computing, ACM Press,2002:494-503.
[12] Chaum D, Antwerpen H. Undeniable signatures //Advances in Cryptology-CRYPTO 1989. Springer-Verlag, 1989:212-216.
[13] Pass R. On deniability in the common reference string and random oracle model //Advances in Cryptology-CRYPTO 2003. Springer-Verlag, 2003, 316-337.
[14] Cramer R, Damgard I, Schoenmakers B. Proofs of partial knowledge and simplified design of witness hiding protocols //Advances in Cryptology-CRYPTO 1994. Springer-Verlag, 1994:174-187.
[15] Damgard I. On sigma protocols . 2010 http://www.daimi.au.dk/~ivan/Sigma.pdf.
[16] Goldreich O. Foundation of cryptography-basic tools
[M]. Cambridge University Press, 2001.
/
| 〈 |
|
〉 |
