Thumbnail
Access Restriction
Open

Author Goyal, Vipul
Source CiteSeerX
Content type Text
File Format PDF
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Subject Keyword Round Complexity ♦ Non-black-box Simulation Technique ♦ Concurrent Session ♦ Strict Polynomial Time ♦ Secure Computation Protocol ♦ Straight-line Simulator ♦ First Construction ♦ Public-coin Parallel Zero-knowledge ♦ Black-box Simulation ♦ Arguable Cleaner ♦ Public-coin Concurrent Zero-knowledge Protocol ♦ Corresponding Construc-tion ♦ New Zero-knowledge Argument Protocol ♦ Non-black-box Simulation ♦ Simultaneous Resettable Zero-knowledge Argument System ♦ Important Feature ♦ Different Tool ♦ Public-coin Concurrent Zero-knowledge ♦ Collision-resistant Hash Function ♦ Concurrent Resettably-sound Zero-knowledge Protocol ♦ Main Technique
Description We present a new zero-knowledge argument protocol by relying on the non-black-box simulation technique of Barak (FOCS’01). Similar to the protocol of Barak, ours is public-coin, is based on the existence of collision-resistant hash functions, and, is not based on “rewinding techniques ” but rather uses non-black-box simulation. However in contrast to the protocol of Barak, our protocol is secure even if there are any unbounded (polynomial) number of concurrent sessions. This gives us the first construction of public-coin concurrent zero-knowledge. Prior to our work, Pass, Tseng and Wikström (SIAM J. Comp. 2011) had shown that using black-box simulation, getting a construction for even public-coin parallel zero-knowledge is impossible. A public-coin concurrent zero-knowledge protocol directly implies the existence of a concurrent resettably-sound zero-knowledge protocol. This is an improvement over the corresponding construc-tion of Deng, Goyal and Sahai (FOCS’09) which was based on stronger assumptions. Furthermore, this also directly leads to an alternative (and arguable cleaner) construction of a simultaneous resettable zero-knowledge argument system. An important feature of our protocol is the existence of a “straight-line ” simulator. This gives a fundamentally different tool for constructing concurrently secure computation protocols (for func-tionalities even beyond zero-knowledge). The round complexity of our protocol is n (for any constant > 0), and, the simulator runs in strict polynomial time. The main technique behind our construction is purely combinatorial in nature. 1
In STOC
Educational Role Student ♦ Teacher
Age Range above 22 year
Educational Use Research
Education Level UG and PG ♦ Career/Technical Study
Learning Resource Type Article
Publisher Date 2013-01-01