Paper 2007/431

Notions of Efficiency in Simulation Paradigm

Tzer-jen Wei

Abstract

Abstract. There are some well-known conceptional and technical issues related to a common setting of simulation paradigm, i.e., EPT (expected polynomial time) simulator versus SPT (strict polynomial time) adversary. In fact, it has been shown that this setting is essential for achieving constant-round black-box zero-knowledge protocols. Many suggestions and results have been proposed to deal with these issues. In this paper, we propose an alternative solution. We study a new class of machines, MPT (Markov polynomial time), which is a cryptographic adaption of Levin's average polynomial-time. Since MPT has good compatibility to SPT and intuitive composition properties, we can use it as a drop-in replacement of SPT. Moreover, it is easy to construct simulators in MPT.

Metadata
Available format(s)
PDF PS
Category
Foundations
Publication info
Published elsewhere. Unknown where it was published
Keywords
zero-knowledgeexpected polynomial-timeAverage polynomial-timeMarkov polynomial-time
Contact author(s)
tjw @ mail ndhu edu tw
History
2007-11-24: received
Short URL
https://ia.cr/2007/431
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2007/431,
      author = {Tzer-jen Wei},
      title = {Notions of Efficiency in Simulation Paradigm},
      howpublished = {Cryptology ePrint Archive, Paper 2007/431},
      year = {2007},
      note = {\url{https://eprint.iacr.org/2007/431}},
      url = {https://eprint.iacr.org/2007/431}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.