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
-
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},
url = {https://eprint.iacr.org/2007/431}
}
