Paper 2016/046

How To Simulate It - A Tutorial on the Simulation Proof Technique

Yehuda Lindell

Abstract

One of the most fundamental notions of cryptography is that of \emph{simulation}. It stands behind the concepts of semantic security, zero knowledge, and security for multiparty computation. However, writing a simulator and proving security via the use of simulation is a non-trivial task, and one that many newcomers to the field often find difficult. In this tutorial, we provide a guide to how to write simulators and prove security via the simulation paradigm. Although we have tried to make this tutorial as stand-alone as possible, we assume some familiarity with the notions of secure encryption, zero-knowledge, and secure computation.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Published elsewhere. Minor revision. This paper appeared in the book "Tutorials on the Foundations of Cryptography", published in honor of Oded Goldreich's 60th birthday.
Keywords
secure computationthe simulation techniquetutorial
Contact author(s)
lindell @ biu ac il
History
2021-04-25: last of 6 revisions
2016-01-19: received
See all versions
Short URL
https://ia.cr/2016/046
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2016/046,
      author = {Yehuda Lindell},
      title = {How To Simulate It - A Tutorial on the Simulation Proof Technique},
      howpublished = {Cryptology ePrint Archive, Paper 2016/046},
      year = {2016},
      note = {\url{https://eprint.iacr.org/2016/046}},
      url = {https://eprint.iacr.org/2016/046}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.