Concurrent Knowledge Extraction in PublicKey Mode

Authors: Andrew ChiChih Yao Moti Yung Yunlei Zhao

Publish Date: 2014/11/11

Volume: 29, Issue: 1, Pages: 156-219

PDF Link

Abstract

Knowledge extraction is a fundamental notion modeling machine possession of values witnesses in a computational complexity sense and enabling one to argue about the internal state of a party in a protocol without probing its internal secret state However when transactions are concurrent say over the Internet with players possessing public keys as is common in cryptography assuring that entities “know” what they claim to know where adversaries may be well coordinated across different transactions turns out to be much more subtle and in need of reexamination In such settings mixing the publickey structure as part of the language and statements is a natural adversarial strategy Here we investigate how to formally treat knowledge possession by parties interacting concurrently in the publickey model More technically we look into the relative power of the notion of “concurrent knowledge extraction” CKE for concurrent zero knowledge CZK in the bare publickey BPK model where the language and statements being proved can be dynamically and adaptively chosen by the prover and may be possibly based on verifiers’ public keys By concrete attacks against some existing natural protocols we first show that concurrent soundness and normal arguments of knowledge do not guarantee concurrent verifier security in the publickey setting Here roughly speaking concurrent verifier security says that the malicious concurrent prover should “know all the witnesses to all the possibly publickeyrelated statements adaptively chosen and successfully proved in the concurrent sessions These concrete attacks serve as a good motivation for understanding “possession of knowledge” for concurrent transactions with registered public keys ie the subtleties of concurrent knowledge extraction in the publickey model This motivates us to introduce and formalize the notion of CKE along with clarifications of various subtleties Two implementations are then presented for constantround concurrently knowledge extractable concurrent zeroknowledge CZK–CKE argument for mathcal NP in the BPK model One protocol is generic and based on standard polynomialtime assumptions whereas the other protocol is computationally efficient and employs complexity leveraging in a novel way Both protocols can be practically instantiated for some specific numbertheoretic languages without going through general mathcal NPreductions Of independent interest are the discussions about the subtleties surrounding the fundamental structure of Feige–Shamir zero knowledge in the BPK modelThis research was supported in part by the National Basic Research Program of China 973 Program Nos 2007CB807900 2007CB807901 2014CB340600 National Natural Science Foundation of China Grant Nos 61472084 61272012 61033001 61061130540 61361136003 Innovation Project No 12ZZ013 of Shanghai Municipal Education Commission and Joint Project of SKLOLSFirst of all we are grateful to the anonymous referees for their very helpful and insightful review comments and suggestions which in particular have significantly improved this work We are indebted to Oded Goldreich for many invaluable suggestions and discussions particularly on strong WI and POK We are grateful to Alessandra Scafuro and Ivan Visconti for many helpful discussions particularly on roundoptimal CZK in the BPK model and for sending us an electronic copy of the work 75 We thank Giovanni Di Crescenzo Yehuda Lindell Giuseppe Persiano and Alon Rosen for helpful discussionsTo show the necessity of the double commitments c w and c sk used in Stage 2 of the efficient CZK–CKE protocol depicted in Fig 6 we demonstrate concrete attacks against variants of the protocol without either c w or c sk where WIA/POK protocols are implemented by Sigma OR protocolsOn the implementations of Sigma OR For the Sigma ORbased protocol variant depicted in Fig 8 to get statistical WI of Stage 1 there are two ways In particular we can require the underlying OWF f used in the keygeneration stage admit perfect/statistical Sigma protocols and thus the Sigma OR of Stage 1 is perfect/statistical WI In general the variant of the nparallel repetition of Blum’s protocol for DHC where the statistically binding commitments used in the first round are replaced by the oneround statistically hiding commitments based on collisionresistant hash functions is a statistical Sigma protocol as well as statistical WI argument for mathcal NP and thus can be applied to any mathcal NP language under the assumption of collisionresistant hash functionsP initiates the first session with V After receiving the firstround message denoted aprime V of the Sigma OR protocol of Stage 1 of the first session on common input y 0 y 1 ie V’s public key P suspends the first session

Keywords: