Information Security and Cryptography

Series Editors
David Basin
Kenny Paterson

Advisory Board
Michael Backes
Gilles Barthe
Ronald Cramer
Ivan Damgård
Andrew D. Gordon
Joshua D. Guttman
Christopher Kruegel
Ueli Maurer
Tatsuaki Okamoto
Adrian Perrig
Bart Preneel

More information about this series at http://www.springer.com/series/4752

Yehuda Lindell
Editor

Tutorials on the Foundations

of Cryptography
Dedicated to Oded Goldreich
Editor
Yehuda Lindell
Department of Computer Science
Bar-Ilan University
Ramat Gan, Israel

ISSN 1619-7100 ISSN 2197-845X (electronic)

Information Security and Cryptography
ISBN 978-3-319-57047-1 ISBN 978-3-319-57048-8 (eBook)
DOI 10.1007/978-3-319-57048-8

Library of Congress Control Number: 2017937580

© Springer International Publishing AG 2017

This work is subject to copyright. All rights are reserved by the Publisher, whether the whole or part of
the material is concerned, specifically the rights of translation, reprinting, reuse of illustrations,
recitation, broadcasting, reproduction on microfilms or in any other physical way, and transmission or
information storage and retrieval, electronic adaptation, computer software, or by similar or dissimilar
methodology now known or hereafter developed.
The use of general descriptive names, registered names, trademarks, service marks, etc. in this publication
does not imply, even in the absence of a specific statement, that such names are exempt from the
relevant protective laws and regulations and therefore free for general use.
The publisher, the authors and the editors are safe to assume that the advice and information in this
book are believed to be true and accurate at the date of publication. Neither the publisher nor the
authors or the editors give a warranty, express or implied, with respect to the material contained herein
or for any errors or omissions that may have been made. The publisher remains neutral with regard to
jurisdictional claims in published maps and institutional affiliations.

Printed on acid-free paper

This Springer imprint is published by Springer Nature

The registered company is Springer International Publishing AG
The registered company address is: Gewerbestrasse 11, 6330 Cham, Switzerland
To Oded, who is a continual inspiration to us

Benny Applebaum
Boaz Barak
Andrej Bogdanov
Iftach Haitner
Shai Halevi
Yehuda Lindell
Alon Rosen
Salil Vadhan
Preface

This tutorial book is dedicated to Oded Goldreich by his students and mentorees on
the occasion of his 60th birthday. This is an opportune time to celebrate Oded’s fun-
damental contributions to the foundations of cryptography. As one of the founders
of the field, Oded’s work has influenced the way we think about, define, and con-
struct cryptographic schemes. Oded’s research contributions are so numerous and
wide-ranging that attempting to enumerate even just the most important of them
would span many pages. Nevertheless, we would be amiss not to mention at least
Oded’s classic results on achieving pseudorandom functions, zero knowledge for
NP, secure two-party and multiparty computation, hard-core predicates for all one-
way functions, private information retrieval, lower bounds for black-box simulation,
limitations of the random-oracle methodology, oblivious RAM, and multiple defini-
tional works.
Having said the above, Oded’s contributions to cryptography have gone far be-
yond his numerous novel scientific results. In particular, I would like to elaborate on
his enormous influence on the role and character of the field of theoretical cryptog-
raphy and what he has termed the foundations of cryptography.
At CRYPTO’97, Oded gave an invited talk “On the Foundations of Modern Cryp-
tography” in which he articulated his vision for this subfield of cryptography. In the
talk and accompanying essay, he describes modern cryptography as comprising def-
initional activity (formulating what “secure” means) and constructive activity (con-
structing schemes that fulfill the definitions). Furthermore, he differentiates between
three types of results: feasibility results, introduction of paradigms and techniques
that may be applicable in practice, and presentation of schemes that are suitable for
practical applications. (Of course, as Oded mentions in the essay, the field also in-
cludes other activities such as establishing lower bounds and impossibility results.)
This essay and Oded’s lecture notes and seminal two-volume book Foundations of
Cryptography, have significantly influenced the way that we and others look at and
understand our field. Needless to say, there was active research being carried out on
the foundations of cryptography before Oded published his essay. However, Oded
was the first to articulate the importance of this work and create an identity for this
subfield of cryptography.

vii
viii Preface

The success of this approach as articulated by Oded has been outstanding. He was
immensely influential in establishing a flourishing research community devoted to
studying the foundations of cryptography and the fundamental questions outlined in
his 1997 essay. Oded was one of the founders of the Theory of Cryptography Con-
ference in 2004 (together with Mihir Bellare and Shafi Goldwasser), and chaired its
steering committee from 2006 to 2012. Although many cryptography theory papers
are published at other venues, the TCC conference grew under Oded’s leadership to
be a natural home for such work.
The importance of this approach and the research carried out on the foundations
of cryptography has intrinsic scientific value, related to the theory of computer sci-
ence in general. The questions asked are fundamental in nature and of importance,
irrespective of any specific application. However, in his essay, Oded also discussed
the eventual utility of theoretical cryptography to practical constructions, and this
has been unequivocally demonstrated. One example of this utility is the fact that
all new proposed standards for modes of encryption, signatures, key-exchange pro-
tocols, and so on are accompanied with a proof of security. However, a far more
striking illustration is the transition of purely theoretical notions to tools that are
frequently used by the applied cryptography and security communities. One partic-
ularly interesting example is the paper “Towards a theory of software protection and
simulation by oblivious RAMs” published by Oded at STOC 1987 (and later merged
into a single journal paper with Rafi Ostrovsky). This paper introduced a new theo-
retical notion and construction and is a clear example of what one would call “pure
theory” today. Three decades later, oblivious RAM is a widely studied primitive,
from both a theoretical and practical perspective. Papers on oblivious RAM are pub-
lished at the top security conferences and constructions are implemented. Further-
more, the theoretical model of a secure processor with external memory is exactly
the model that Intel has adopted in its new SGX architecture and is one that also fits
many cloud computing scenarios where storage is held externally. The introduction
of this notion three decades ago, and the proof of feasibility provided back then,
informed the applied cryptography and security communities and formed the basis
they needed when this concept became of practical interest.
Due to the great importance of the “foundations approach” to the field, Oded
did not stop at writing a short essay. Rather, he also distributed widely used lecture
notes, and expanded these into the two-volume treatise Foundations of Cryptog-
raphy (published by Cambridge University Press in 2001 and 2004, respectively).
This work presented a truly comprehensive “bottom-up” approach, starting from
minimal assumptions and working up to construct higher-level primitives and appli-
cations. It is important to note that many of the results appearing in the Foundations
of Cryptography were never fully proven prior to the work (most notably, those in
the chapter on secure computation), and thus this involved a monumental effort. In
fact, new results were uncovered in this process, including an exact formulation of
the sufficient assumptions for obtaining oblivious transfer and noninteractive zero
knowledge.
The two volumes of the Foundations of Cryptography are the most used books on
my bookshelf, and are an absolute necessity in my research. The books also provide
Preface ix

students and beginning researchers with the ability to enter the world of theoretical
cryptography. I cannot imagine how one would learn the topic of zero knowledge in
depth without Chapter 3 of the Foundations of Cryptography, and likewise all the
other topics covered.
It is therefore most appropriate that, in celebration of Oded’s 60th birthday (and
20 years since the publication of that essay), we present a book in his honor that
focuses on the foundations of cryptography. The chapters in this book consist of
tutorials that are inspired by the “foundations of cryptography” approach:
Chapter 1 – Garbled Circuits as Randomized Encodings of Functions: a Primer
(Benny Applebaum): Yao’s garbled circuit construction is a central crypto-
graphic tool with numerous applications. This chapter reviews garbled circuits
from a foundational point of view under the framework of randomized encod-
ing of functions, including positive and negative results and a sample of basic
applications.
Chapter 2 – The Complexity of Public-Key Cryptography (Boaz Barak): This chap-
ter surveys what is known (and the many things that are not known) about the
computational assumptions that can enable public-key cryptography, and the
qualitative differences between these assumptions and those that are known to
enable private-key cryptography.
Chapter 3 – Pseudorandom Functions: Three Decades Later (Andrej Bogdanov
and Alon Rosen): Pseudorandom functions are an extremely influential abstrac-
tion, with applications ranging from message authentication to barriers in prov-
ing computational complexity lower bounds. This chapter surveys various incar-
nations of pseudorandom functions, giving self-contained proofs of key results
from the literature.
Chapter 4 – The Many Entropies in One-Way Functions (Iftach Haitner and Salil
Vadhan): This chapter introduces two recent computational notions of entropy,
shows that they can be easily found in any one-way function, and uses them to
present simpler and more efficient constructions of pseudorandom generators
and statistically hiding commitments from one-way functions.
Chapter 5 – Homomorphic Encryption (Shai Halevi): Fully homomorphic encryp-
tion is a relatively new discovery and has gained much attention. This chapter
provides a tutorial on the topic, from definitions and properties, to constructions
and applications.
Chapter 6 – How to Simulate It — A Tutorial on the Simulation Proof Technique
(Yehuda Lindell): The simulation paradigm is central to cryptographic def-
initions and proofs. This chapter consists of a systematic tutorial on how
simulation-based proofs work, from semantic security through zero knowledge
and finally secure computation.
Chapter 7 – The Complexity of Differential Privacy (Salil Vadhan): Differential pri-
vacy is a theoretical framework for ensuring the privacy of individual-level data
when performing statistical analysis of privacy-sensitive datasets. The goal of
this chapter is to convey the deep connections between differential privacy and
a variety of other topics in computational complexity, cryptography, and theo-
retical computer science at large.
x Preface

Oded has quoted his mother as saying “there are no privileges without duties”,
and this is a message that Oded has also infused into his students by his personal
example. I feel greatly privileged to have had Oded as my Ph.D. advisor, and I am
sure that the same is true of all the authors of this book (and many others who Oded
has advised and mentored over the years). This privilege indeed comes with duties.
We hope that the tutorials in this book are helpful to those who are interested in
pursuing the foundations of cryptography approach, and as such will constitute a
very small part of the fulfillment of our obligations.
In the name of all the authors of this book, I would like to wish Oded a very
happy 60th birthday. There is great happiness in being able to look back at a life
full of accomplishments, to see the positive influence that you have had on so many
people, and to appreciate the continuing influence your work will have in the future.
Happy birthday!

Israel, Yehuda Lindell

April 2017
Contents

1 Garbled Circuits as Randomized Encodings of Functions: a Primer . . 1

Benny Applebaum
1.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 Definitions and Basic Properties . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.3 Feasibility Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
1.4 Advanced Constructions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
1.5 Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
1.6 Summary and Suggestions for Further Reading . . . . . . . . . . . . . . . . 35
1.7 Appendix: Randomized Encodings Versus Garbling Schemes [26] 37
References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38

2 The Complexity of Public-Key Cryptography . . . . . . . . . . . . . . . . . . . . . 45

Boaz Barak
2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
2.2 Private-Key Cryptography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
2.3 Public-Key Cryptography: an Overview . . . . . . . . . . . . . . . . . . . . . . 55
2.4 The Two “Mainstream” Public-Key Constructions . . . . . . . . . . . . . . 56
2.5 Alternative Public-Key Constructions . . . . . . . . . . . . . . . . . . . . . . . . 61
2.6 Is Computational Hardness the Rule or the Exception? . . . . . . . . . . 67
References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69
3 Pseudorandom Functions: Three Decades Later . . . . . . . . . . . . . . . . . . . 79
Andrej Bogdanov and Alon Rosen
3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80
3.2 Definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87
3.3 Generic Constructions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92
3.4 Instantiations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99
3.5 Transformations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110
3.6 Complexity of Pseudorandom Functions . . . . . . . . . . . . . . . . . . . . . . 120
3.7 Distinguishers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 126
3.8 Contemporary Constructions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 139

xi
xii Contents

References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 149
4 The Many Entropies in One-Way Functions . . . . . . . . . . . . . . . . . . . . . . . 159
Iftach Haitner and Salil Vadhan
4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 160
4.2 Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 167
4.3 Next-Block Entropy and Pseudorandom Generators . . . . . . . . . . . . . 173
4.4 Inaccessible Entropy and Statistically Hiding Commitment . . . . . . 188
References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 215

5 Homomorphic Encryption . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 219

Shai Halevi
5.1 Computing on Encrypted Data . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 219
5.2 Defining Homomorphic Encryption . . . . . . . . . . . . . . . . . . . . . . . . . . 226
5.3 Realizing Leveled Homomorphic Encryption . . . . . . . . . . . . . . . . . . 239
5.4 Realizing Fully Homomorphic Encryption . . . . . . . . . . . . . . . . . . . . 248
5.5 Advanced Topics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 259
5.6 Suggested Reading . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 267
References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 268
6 How to Simulate It – A Tutorial on the Simulation Proof Technique . . 277
Yehuda Lindell
6.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 277
6.2 Preliminaries and Notation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 279
6.3 The Basic Paradigm – Semantic Security . . . . . . . . . . . . . . . . . . . . . 280
6.4 Secure Computation – Simulation for Semi-honest Adversaries . . . 282
6.5 Simulating the View of Malicious Adversaries – Zero Knowledge . 291
6.6 Defining Security for Malicious Adversaries . . . . . . . . . . . . . . . . . . . 310
6.7 Determining Output – Coin Tossing . . . . . . . . . . . . . . . . . . . . . . . . . . 316
6.8 Extracting Inputs – Oblivious Transfer . . . . . . . . . . . . . . . . . . . . . . . . 329
6.9 The Common Reference String Model – Oblivious Transfer . . . . . . 338
6.10 Advanced Topics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 340
References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 343

7 The Complexity of Differential Privacy . . . . . . . . . . . . . . . . . . . . . . . . . . . 347

Salil Vadhan
7.1 Introduction and Definition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 348
7.2 Composition Theorems for Differential Privacy . . . . . . . . . . . . . . . . 360
7.3 Alternatives to Global Sensitivity . . . . . . . . . . . . . . . . . . . . . . . . . . . . 367
7.4 Releasing Many Counting Queries with Correlated Noise . . . . . . . . 373
7.5 Information-Theoretic Lower Bounds . . . . . . . . . . . . . . . . . . . . . . . . 381
7.6 Computational Lower Bounds . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 400
7.7 Efficient Algorithms for Specific Query Families . . . . . . . . . . . . . . . 409
7.8 Private PAC Learning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 417
7.9 Multiparty Differential Privacy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 425
7.10 Computational Differential Privacy . . . . . . . . . . . . . . . . . . . . . . . . . . . 431
Contents xiii

7.11 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 435

References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 438
Nomenclature . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 449
List of Contributors

Benny Applebaum
School of Electrical Engineering, Tel Aviv University, Israel
e-mail: bennyap@post.tau.ac.il
Boaz Barak
School of Engineering and Applied Sciences, Harvard University, USA
e-mail: b@boazbarak.org
Andrej Bogdanov
Department of Computer Science, Chinese University of Hong Kong, China
e-mail: andrejb@cse.cuhk.edu.hk
Iftach Haitner
Department of Computer Science, Tel Aviv University, Israel
e-mail: iftach.haitner@cs.tau.ac.il
Shai Halevi
IBM T.J. Watson Research Center, USA
e-mail: shaih@alum.mit.edu
Yehuda Lindell
Department of Computer Science, Bar-Ilan University, Israel
e-mail: lindell@biu.ac.il
Alon Rosen
School of Computer Science, Herzliya Interdisciplinary Center, Israel
e-mail: alon.rosen@idc.ac.il
Salil Vadhan
School of Engineering and Applied Sciences, Harvard University, USA
e-mail: salil@seas.harvard.edu

xv