Ω-protocols, introduced by Garay, Mackenzie and Yang, is a variant of S-protocols with online extractor which is a useful tool to overcome the nest effect in concurrent scenario. In this work, we construct an Ω-prot...Ω-protocols, introduced by Garay, Mackenzie and Yang, is a variant of S-protocols with online extractor which is a useful tool to overcome the nest effect in concurrent scenario. In this work, we construct an Ω-protocol for Hamiltonian cycle problem, and therefore, it allows us to present Ω-protocol for any NP relation. For most general NP relations, our construction of Ω-protocols is much more efficient than the informal one described by Garay et ah and we believe that the method for our construction may be of independent interest.展开更多
∑-protocol has been proved to be a very powerful cryptographic tool and widely used in nnmerous important cryptographic applications. In this paper, the authors make use of ∑-protocol as a main tool to resolve the f...∑-protocol has been proved to be a very powerful cryptographic tool and widely used in nnmerous important cryptographic applications. In this paper, the authors make use of ∑-protocol as a main tool to resolve the following difficult problems 1-3 and to construct three ettlcient cryptographic protocols 4 6：1） How to construct a protocol for proving a secret integer to be a Blum integer with form PQ, where P, Q are two different primes and both -- 3（mod 4）;2） How to construct a protocol for proving a secret polynomial with exact degree t - 1 iil a （t, n）- threshold secret sharing scheme：3） How to construct witness indistinguishable and witness hiding protocol not from zero-knowledge proof;4） A publicly verifiable secret sharing scheme with information-theoretic security;5） A delegateable signature scheme under the existence of one-way permutations;6） Non-interactive universal designated verifier signature schemes.展开更多
A delegateable signature scheme （DSS） which was first introduced by Barak is mainly based on the non-interactive zero-knowledge proof （NIZK） for preventing the signing verifier from telling which witness （i.e., r...A delegateable signature scheme （DSS） which was first introduced by Barak is mainly based on the non-interactive zero-knowledge proof （NIZK） for preventing the signing verifier from telling which witness （i.e., restricted subset） is being used. However, the scheme is not significantly efficient due to the difficulty of constructing NIZK. We first show that a non-interactive witness indistinguishable （NlWl） proof system and a non-interactive witness hiding （NIWH） proof system are easier and more efficient proof models than NIZK in some cases. Furthermore, the witnesses em- ployed in these two protocols （NlWl and NIWT） cannot also be distinguished by the verifiers. Combined with the E-protocol, we then construct NlWl and NIWH proofs for any NP statement under the existence of one-way functions and show that each proof is different from those under the existence of trapdoor permutations, Finally, based on our NlWl and NIWH proofs, we construct delegateable signature schemes under the existence of one-way functions, which are more efficient than Barak＇s scheme under the existence of trapdoor permutations.展开更多
基金Supported by the National Natural Science Foundation of China (Grant No. 60673069)the National Basic Research Program (Grant No. 2004CB318004)
文摘Ω-protocols, introduced by Garay, Mackenzie and Yang, is a variant of S-protocols with online extractor which is a useful tool to overcome the nest effect in concurrent scenario. In this work, we construct an Ω-protocol for Hamiltonian cycle problem, and therefore, it allows us to present Ω-protocol for any NP relation. For most general NP relations, our construction of Ω-protocols is much more efficient than the informal one described by Garay et ah and we believe that the method for our construction may be of independent interest.
基金supported by the Foundation of tihe National Natural Science of China under Grant Nos 90604034 (Key Project), 10726012, 10871222, 10531040,and 10471156
文摘∑-protocol has been proved to be a very powerful cryptographic tool and widely used in nnmerous important cryptographic applications. In this paper, the authors make use of ∑-protocol as a main tool to resolve the following difficult problems 1-3 and to construct three ettlcient cryptographic protocols 4 6：1） How to construct a protocol for proving a secret integer to be a Blum integer with form PQ, where P, Q are two different primes and both -- 3（mod 4）;2） How to construct a protocol for proving a secret polynomial with exact degree t - 1 iil a （t, n）- threshold secret sharing scheme：3） How to construct witness indistinguishable and witness hiding protocol not from zero-knowledge proof;4） A publicly verifiable secret sharing scheme with information-theoretic security;5） A delegateable signature scheme under the existence of one-way permutations;6） Non-interactive universal designated verifier signature schemes.
基金Supported partially by the National Natural Science Foundation of China(Grant Nos.90604034,10371127 and 10671114)
文摘A delegateable signature scheme （DSS） which was first introduced by Barak is mainly based on the non-interactive zero-knowledge proof （NIZK） for preventing the signing verifier from telling which witness （i.e., restricted subset） is being used. However, the scheme is not significantly efficient due to the difficulty of constructing NIZK. We first show that a non-interactive witness indistinguishable （NlWl） proof system and a non-interactive witness hiding （NIWH） proof system are easier and more efficient proof models than NIZK in some cases. Furthermore, the witnesses em- ployed in these two protocols （NlWl and NIWT） cannot also be distinguished by the verifiers. Combined with the E-protocol, we then construct NlWl and NIWH proofs for any NP statement under the existence of one-way functions and show that each proof is different from those under the existence of trapdoor permutations, Finally, based on our NlWl and NIWH proofs, we construct delegateable signature schemes under the existence of one-way functions, which are more efficient than Barak＇s scheme under the existence of trapdoor permutations.
