This book constitutes the refereed proceedings of the 11th Theory of Cryptography Conference, TCC 2014, held in San Diego, CA, USA, in February 2014. The 30 revised full papers presented were carefully reviewed and selected from 90 submissions. The papers are organized in topical sections on obfuscation, applications of obfuscation, zero knowledge, black-box separations, secure computation, coding and cryptographic applications, leakage, encryption, hardware-aided secure protocols, and encryption and signatures.

In the setting of multi-party computation, sets of two or more parties with private inputs wish to jointly compute some (predetermined) function of their inputs. General results concerning secure two-party or multi-party computation were first announced in the 1980s. Put briefly, these results assert that under certain assumptions one can construct protocols for securely computing any desired multi-party functionality. However, this research relates only to a setting where a single protocol execution is carried out. In contrast, in modern networks, many different protocol executions are run at the same time.

This book is devoted to the general and systematic study of secure multi-party computation under composition. Despite its emphasis on a theoretically well-founded treatment of the subject, general techniques for designing secure protocols are developed that may even result in schemes or modules to be incorporated in practical systems. The book clarifies fundamental issues regarding security in a multi-execution environment and gives a comprehensive and unique treatment of the composition of secure multi-party protocols.

Now the most used texbook for introductory cryptography courses in both mathematics and computer science, the Third Edition builds upon previous editions by offering several new sections, topics, and exercises. The authors present the core principles of modern cryptography, with emphasis on formal definitions, rigorous proofs of security.

Table of Contents

I Introduction and Classical Cryptography

1. Introduction

Cryptography and Modern Cryptography

The Setting of Private-Key Encryption

Historical Ciphers and Their Cryptanalysis

Principles of Modern Cryptography

Principle 1 - Formal Definitions

Principle 2 - Precise Assumptions

Principle 3 - Proofs of Security

Provable Security and Real-World Security

References and Additional Reading

Exercises

2. Perfectly Secret Encryption

Definitions

The One-Time Pad

Limitations of Perfect Secrecy

*Shannon's Theorem

References and Additional Reading

Exercises

II Private-Key (Symmetric) Cryptography

3. Private-Key Encryption

Computational Security

The Concrete Approach

The Asymptotic Approach

Defining Computationally Secure Encryption

The Basic Definition of Security (EAV-Security)

*Semantic Security

Constructing an EAV-Secure Encryption Scheme

Pseudorandom Generators

Proofs by Reduction

EAV-Security from a Pseudorandom Generator

Stronger Security Notions

Security for Multiple Encryptions

Chosen-Plaintext Attacks and CPA-Security

CPA-Security for Multiple Encryptions

Constructing a CPA-Secure Encryption Scheme

Pseudorandom Functions and Permutations

CPA-Security from a Pseudorandom Function

Modes of Operation and Encryption in Practice

Stream Ciphers

Stream-Cipher Modes of Operation

Block Ciphers and Block-Cipher Modes of Operation

*Nonce-Based Encryption

References and Additional Reading

Exercises

4. Message Authentication Codes

Message Integrity

Secrecy vs Integrity

Encryption vs Message Authentication

Message Authentication Codes (MACs) - Definitions

Constructing Secure Message Authentication Codes

A Fixed-Length MAC

Domain Extension for MACs

CBC-MAC

The Basic Construction

*Proof of Security

GMAC and Poly

MACs from Difference-Universal Functions

Instantiations

*Information-Theoretic MACs

One-Time MACs from Strongly Universal Functions

One-Time MACs from Difference-Universal Functions

Limitations on Information-Theoretic MACs

References and Additional Reading

Exercises

5. CCA-Security and Authenticated Encryption

Chosen-Ciphertext Attacks and CCA-Security

Padding-Oracle Attacks

Defining CCA-Security

Authenticated Encryption

Defining Authenticated Encryption

CCA Security vs Authenticated Encryption

Authenticated Encryption Schemes

Generic Constructions

Standardized Schemes

Secure Communication Sessions

References and Additional Reading

Exercises

6. Hash Functions and Applications

Definitions

Collision Resistance

Weaker Notions of Security

Domain Extension: The Merkle-Damgard Transform

Message Authentication Using Hash Functions

Hash-and-MAC

HMAC

Generic Attacks on Hash Functions

Birthday Attacks for Finding Collisions

Small-Space Birthday Attacks

*Time/Space Tradeo s for Inverting Hash Functions

The Random-Oracle Model

The Random-Oracle Model in Detail

Is the Random-Oracle Methodology Sound?

Additional Applications of Hash Functions

Fingerprinting and Deduplication

Merkle Trees

Password Hashing

Key Derivation

Commitment Schemes

References and Additional Reading

Exercises

7. Practical Constructions of Symmetric-Key Primitives

Stream Ciphers

Linear-Feedback Shift Registers

Adding Nonlinearity

Trivium

RC4

ChaCha20

Block Ciphers

Substitution-Permutation Networks

Feistel Networks

DES - The Data Encryption Standard

3 DES: Increasing the Key Length of a Block Cipher

AES -The Advanced Encryption Standard

*Differential and Linear Cryptanalysis

Compression Functions and Hash Functions

Compression Functions from Block Ciphers

MD5, SHA-1, and SHA-2

The Sponge Construction and SHA-3 (Keccak)

References and Additional Reading

Exercises

8. *Theoretical Constructions of Symmetric-Key Primitives

One-Way Functions

Definitions

Candidate One-Way Functions

Hard-Core Predicates

From One-Way Functions to Pseudorandomness

Hard-Core Predicates from One-Way Functions

A Simple Case

A More Involved Case

The Full Proof

Constructing Pseudorandom Generators

Pseudorandom Generators with Minimal Expansion

Increasing the Expansion Factor

Constructing Pseudorandom Functions

Constructing (Strong) Pseudorandom Permutations

Assumptions for Private-Key Cryptography

Computational Indistinguishability

References and Additional Reading

Exercises

III Public-Key (Asymmetric) Cryptography

9. Number Theory and Cryptographic Hardness Assumptions

Preliminaries and Basic Group Theory

Primes and Divisibility

Modular Arithmetic

Groups

The Group ZN

*Isomorphisms and the Chinese Remainder Theorem

Primes, Factoring, and RSA

Generating Random Primes

*Primality Testing

The Factoring Assumption

The RSA Assumption

*Relating the Factoring and RSA Assumptions

Cryptographic Assumptions in Cyclic Groups

Cyclic Groups and Generators

The Discrete-Logarithm/Diffie-Hellman Assumptions

Working in (Subgroups of) Zp

Elliptic Curves

*Cryptographic Applications

One-Way Functions and Permutations

Collision-Resistant Hash Functions

References and Additional Reading

Exercises

10. *Algorithms for Factoring and Computing Discrete Logarithms

Algorithms for Factoring

Pollard's p - Algorithm

Pollard's Rho Algorithm

The Quadratic Sieve Algorithm

Generic Algorithms for Computing Discrete Logarithms

The Pohlig-Hellman Algorithm

The Baby-Step/Giant-Step Algorithm

Discrete Logarithms from Collisions

Index Calculus: Computing Discrete Logarithms in Zp

Recommended Key Lengths

References and Additional Reading

Exercises

11. Key Management and the Public-Key Revolution

Key Distribution and Key Management

A Partial Solution: Key-Distribution Centers

Key Exchange and the Diffie-Hellman Protocol

The Public-Key Revolution

References and Additional Reading

Exercises

12. Public-Key Encryption

Public-Key Encryption - An Overview

Definitions

Security against Chosen-Plaintext Attacks

Multiple Encryptions

Security against Chosen-Ciphertext Attacks

Hybrid Encryption and the KEM/DEM Paradigm

CPA-Security

CCA-Security

CDH/DDH-Based Encryption

El Gamal Encryption

DDH-Based Key Encapsulation

*A CDH-Based KEM in the Random-Oracle Model

*Chosen-Ciphertext Security and DHIES/ECIES

RSA-Based Encryption

Plain RSA Encryption

Padded RSA and PKCS # v

*CPA-Secure Encryption without Random Oracles

OAEP and PKCS # v

*A CCA-Secure KEM in the Random-Oracle Model

RSA Implementation Issues and Pitfalls

References and Additional Reading

Exercises

13. Digital Signature Schemes

Digital Signatures - An Overview

Definitions

The Hash-and-Sign Paradigm

RSA-Based Signatures

Plain RSA Signatures

RSA-FDH and PKCS #1 Standards

Signatures from the Discrete-Logarithm Problem

Identification Schemes and Signatures

The Schnorr Identification/Signature Schemes

DSA and ECDSA

Certificates and Public-Key Infrastructures

Putting It All Together { TLS

*Signcryption

References and Additional Reading

Exercises

14. *Post-Quantum Cryptography

Post-Quantum Symmetric-Key Cryptography

Grover's Algorithm and Symmetric-Key Lengths

Collision-Finding Algorithms and Hash Functions

Shor's Algorithm and its Impact on Cryptography

Post-Quantum Public-Key Encryption

Post-Quantum Signatures

Lamport's Signature Scheme

Chain-Based Signatures

Tree-Based Signatures

References and Additional Reading

Exercises

15. *Advanced Topics in Public-Key Encryption

Public-Key Encryption from Trapdoor Permutations

Trapdoor Permutations

Public-Key Encryption from Trapdoor Permutations

The Paillier Encryption Scheme

The Structure of Z_N

The Paillier Encryption Scheme

Homomorphic Encryption

Secret Sharing and Threshold Encryption

Secret Sharing

Verifiable Secret Sharing

Threshold Encryption and Electronic Voting

The Goldwasser-Micali Encryption Scheme

Quadratic Residues Modulo a Prime

Quadratic Residues Modulo a Composite

The Quadratic Residuosity Assumption

The Goldwasser-Micali Encryption Scheme

The Rabin Encryption Scheme

Computing Modular Square Roots

A Trapdoor Permutation Based on Factoring

The Rabin Encryption Scheme

References and Additional Reading

Exercises

Index of Common Notation

Appendix A Mathematical Background

A Identities and Inequalities

A Asymptotic Notation

A Basic Probability

A The \Birthday" Problem

A *Finite Fields

Appendix B Basic Algorithmic Number Theory

B Integer Arithmetic

B Basic Operations

B The Euclidean and Extended Euclidean Algorithms

B Modular Arithmetic

B Basic Operations

B Computing Modular Inverses

B Modular Exponentiation

B *Montgomery Multiplication

B Choosing a Uniform Group Element

B *Finding a Generator of a Cyclic Group

B Group-Theoretic Background

B Efficient Algorithms

References and Additional Reading

Exercises



　

/

This is a graduate textbook of advanced tutorials on the theory of cryptography and computational complexity. In particular, the chapters explain aspects of garbled circuits, public-key cryptography, pseudorandom functions, one-way functions, homomorphic encryption, the simulation proof technique, and the complexity of differential privacy. Most chapters progress methodically through motivations, foundations, definitions, major results, issues surrounding feasibility, surveys of recent developments, and suggestions for further study. This book honors Professor Oded Goldreich, a pioneering scientist, educator, and mentor. Oded was instrumental in laying down the foundations of cryptography, and he inspired the contributing authors, Benny Applebaum, Boaz Barak, Andrej Bogdanov, Iftach Haitner, Shai Halevi, Yehuda Lindell, Alon Rosen, and Salil Vadhan, themselves leading researchers on the theory of cryptography and computational complexity. The book is appropriate for graduate tutorials and seminars, and for self-study by experienced researchers, assuming prior knowledge of the theory of cryptography.