KIT | KIT-Bibliothek | Impressum | Datenschutz

On Expected Polynomial Runtime in Cryptography

Klooß, Michael

Abstract (englisch):

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 [9], 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. ... mehr

Postprint §
DOI: 10.5445/IR/1000140294
Veröffentlicht am 05.11.2022
Cover der Publikation
Zugehörige Institution(en) am KIT Institut für Informationssicherheit und Verlässlichkeit (KASTEL)
Publikationstyp Proceedingsbeitrag
Publikationsjahr 2021
Sprache Englisch
Identifikator ISBN: 978-3-030-90458-6
ISSN: 0302-9743, 1611-3349
KITopen-ID: 1000140294
HGF-Programm 46.23.01 (POF IV, LK 01) Methods for Engineering Secure Systems
Erschienen in Theory of Cryptography : 19th International Conference, TCC 2021, Raleigh, NC, USA, November 8–11, 2021, Proceedings, Part I. Ed.: K. Nissim
Veranstaltung 19th Theory of Chryptography - International Conference (TCC 2021), Raleigh, NC, USA, 08.11.2021 – 11.11.2021
Auflage 1. ed.
Verlag Springer International Publishing
Seiten 558–590
Serie Security and Cryptology ; 13042
Vorab online veröffentlicht am 04.11.2021
Schlagwörter foundations / expected polynomial time, designated adversary, zero-knowledge, black-box simulation, uniform complexity
Nachgewiesen in Dimensions
KIT – Die Forschungsuniversität in der Helmholtz-Gemeinschaft
KITopen Landing Page