Cryptology ePrint Archive: Report 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.

Category / Keywords: foundations / zero-knowledge, expected polynomial-time, Average polynomial-time, Markov polynomial-time

Date: received 19 Nov 2007

Contact author: tjw at mail ndhu edu tw

Available format(s): Postscript (PS) | Compressed Postscript (PS.GZ) | PDF | BibTeX Citation

Version: 20071124:104025 (All versions of this report)

Short URL:

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]