Paper 2020/809

On (expected polynomial) runtime in cryptography

Michael Klooß

Abstract

A common definition of black-box zero-knowledge considers strict polynomial time (PPT) adversaries but expected polynomial time (EPT) simulation. This is necessary for constant round black-box zero-knowledge in the plain model, and the asymmetry between simulator and adversary an accepted consequence. Consideration of EPT adversaries naturally leads to designated adversaries, i.e. adversaries which are only required to be efficient in the protocol they are designed to attack. They were first examined in Feige’s thesis [Fei90], where obstructions to proving security are shown. Prior work on (designated) EPT adversaries by Katz and Lindell (TCC’05) requires superpolynomial hardness assumptions, whereas the work of Goldreich (TCC’07) postulates “nice” behaviour under rewinding. In this work, we start from scratch and revisit the definition of efficient algorithms. We argue that the standard runtime classes, PPT and EPT, behave “unnatural” from a cryptographic perspective. Namely, algorithms can have indistinguishable runtime distributions, yet one is considered efficient while the other is not. Hence, classical runtime classes are not “closed under indistinguishability”, which causes problems. Relaxations of PPT which are “closed” are (well-)known and used. We propose computationally expected polynomial time (CEPT), the class of runtimes which are (computationally) indistinguishable from EPT, which is “closed”. We analyze CEPT in the setting of uniform complexity (following Goldreich (JC’93)) with designated adversaries, and provide easy-to-check criteria for zero-knowledge protocols with black-box simulation in the plain model which show that many (all known?) such protocols handle designated CEPT adversaries in CEPT.

Note: Added hybrid lemma and SFE. Improved document structure.