Novel Ω-protocols for NP |
| |
| Authors: | Deng Yi Lin DongDai |
| |
| Affiliation: | 1. State Key Laboratory of Information Security, Institute of software, Chinese Academy of sciences, Beijing 100080, China;Graduate University of Chinese Academy of Sciences, Beijing 100049, China
2. State Key Laboratory of Information Security, Institute of software, Chinese Academy of sciences, Beijing 100080, China |
| |
| Abstract: | Ω-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 al. and we believe that the method for our
construction may be of independent interest.
Supported by the National Natural Science Foundation of China (Grant No. 60673069) and the National Basic Research Program
(Grant No. 2004CB318004) |
| |
| Keywords: | concurrent zero knowledge Ω -protocols Σ -protocols Hamiltonian cycle |
| 本文献已被 维普 万方数据 SpringerLink 等数据库收录！ |
|
