Paper 2020/809

On (expected polynomial) runtime in cryptography

Michael Klooß

Abstract

We revisit the definition of efficient algorithms and argue, that the standard runtime classes, strict probabilistic polynomial time (PPT) and expected probabilistic polynomial time (EPT) are “unnatural” from a cryptographic perspective. They are not closed under indistinguishability. Applied to EPT, this suggests computationally expected polynomial time (CEPT), the class of runtimes which are (computationally) indistinguishable from EPT. We analyse the behaviour of CEPT for zero-knowledge proofs and designated adversaries in the setting of uniform complexity (following Goldreich (JC’93)). A designated adversary is (only) efficient in the protocol it is designed to attack. This security notion, first proposed in Feige’s thesis [Fei90], is very natural, but there are obstructions to achieving it. Prior work on handling (designated) EPT adversaries by Katz and Lindell (TCC’05) requires superpolynomial hardness assumptions, whereas the work of Goldreich (TCC’07) requires “nice” adversarial behaviour under rewinding. We 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.