Cryptology ePrint Archive: Report 2020/1312

Individual Simulations

Yi Deng

Abstract: We develop an individual simulation technique that explicitly makes use of particular properties/structures of a given adversary's functionality. Using this simulation technique, we obtain the following results.

1. We construct the first protocols that \emph{break previous black-box barriers} of [Xiao, TCC'11 and Alwen et al., Crypto'05] under the standard hardness of factoring, both of which are polynomial time simulatable against all a-priori bounded polynomial size distinguishers:

-- Two-round selective opening secure commitment scheme.

-- Three-round concurrent zero knowledge and concurrent witness hiding argument for NP in the bare public-key model.

2. We present a simpler two-round weak zero knowledge and witness hiding argument for NP in the plain model under the sub-exponential hardness of factoring. Our technique also yields a significantly simpler proof that existing distinguisher-dependent simulatable zero knowledge protocols are also polynomial time simulatable against all distinguishers of a-priori bounded polynomial size.

The core conceptual idea underlying our individual simulation technique is an observation of the existence of nearly optimal extractors for all hard distributions: For any NP-instance(s) sampling algorithm, there exists a polynomial-size witness extractor (depending on the sampler's functionality) that almost outperforms any circuit of a-priori bounded polynomial size in terms of the success probability.

Category / Keywords:

Original Publication (with minor differences): IACR-ASIACRYPT-2020

Date: received 20 Oct 2020, last revised 23 Oct 2020

Contact author: deng at iie ac cn

Available format(s): PDF | BibTeX Citation

Version: 20201023:101913 (All versions of this report)

Short URL: ia.cr/2020/1312


[ Cryptology ePrint archive ]