Paper 2020/809

On (expected polynomial) runtime in cryptography

Michael Klooß


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.

Available format(s)
Publication info
Preprint. MINOR revision.
expected polynomial timedesignated adversaryzero-knowledgeblack-box simulationuniform complexity
Contact author(s)
michael klooss @ kit edu
2021-05-31: revised
2020-06-30: received
See all versions
Short URL
Creative Commons Attribution


      author = {Michael Klooß},
      title = {On (expected polynomial) runtime in cryptography},
      howpublished = {Cryptology ePrint Archive, Paper 2020/809},
      year = {2020},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.