An efficient compiler from Σ-protocol to deniable zero knowledge in CRS model

doi:10.7523/j.issn.2095-6134.2010.6.015

Abstract

Abstract:

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

CLC Number:

TP309

HUANG Gui-Fang, HU Lei, LIN Dong-Dai. An efficient compiler from Σ-protocol to deniable zero knowledge in CRS model[J]. , 2010, 27(6): 831-837.

References

[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 30^th 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 32^nd 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 42^nd 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 20^th Annual ACM Symposium on Theory of Computing. ACM Press, 1988:103-112.

[8] Damgrd 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 42^nd 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 34^thAnnual 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.