[Resource Topic] 2020/1312: Individual Simulations

Welcome to the resource topic for 2020/1312

Title:
Individual Simulations

Authors: 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.

ePrint: https://eprint.iacr.org/2020/1312

Talk: https://www.youtube.com/watch?v=MBqYHLEM4SQ

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .