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

Category / Keywords: foundations / secure computation, the simulation technique, tutorial

Original Publication (with minor differences): This paper appeared in the book "Tutorials on the Foundations of Cryptography", published in honor of Oded Goldreich's 60th birthday.

Date: received 18 Jan 2016, last revised 27 Jun 2017

Contact author: lindell at biu ac il

Available format(s): PDF | BibTeX Citation

Version: 20170627:062740 (All versions of this report)

Short URL: ia.cr/2016/046

Discussion forum: Show discussion | Start new discussion


[ Cryptology ePrint archive ]