On expected probabilistic polynomial-time adversaries: a suggestion for restricted definitions and their benefits (Q2267359)

This paper proposes new definitions of expected probabilistic polynomial-time strategies, more restrictive that the definitions from [\textit{U. Feige}, Alternative models for zero-knowledge interactive proofs, Ph.D. Thesis, Weizmann Institute of Science (1990)] and [\textit{J. Katz} and \textit{Y. Lindell}, J. Cryptology 21, No. 3, 303--349 (2008; Zbl 1161.94410)]. The aim is the possibility of developing a coherent theory of security when feasibility is associated with expected probabilistic polynomial-time, and the class so called normal black-box simulators. It has been shown that the normal black-box simulators that handle strict probabilistic polynomial-time adversaries also handle adversaries that satisfy the new definitions, and that these definitions support various natural composition theorems. The thesis that the same results hold for arbitrary black-box simulators and even for each universal simulator is left as an open problem.