CryptoDB
Notions of Efficiency in Simulation Paradigm
| Authors: | |
|---|---|
| Download: | |
| 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. |
BibTeX
@misc{eprint-2007-13711,
title={Notions of Efficiency in Simulation Paradigm},
booktitle={IACR Eprint archive},
keywords={foundations / zero-knowledge, expected polynomial-time, Average polynomial-time, Markov polynomial-time},
url={http://eprint.iacr.org/2007/431},
note={ tjw@mail.ndhu.edu.tw 13836 received 19 Nov 2007},
author={Tzer-jen Wei},
year=2007
}