Information-theoretic cryptography / Himanshu Tyagi, Shun Watanabe.

Format:

Book

Author/Creator:

Tyagi, Himanshu, author.

Watanabe, Shun, author.

Language:

English

Subjects (All):

Cryptography.

Physical Description:

1 online resource (xiv, 504 pages) : illustrations (black and white), digital, PDF file(s)

Edition:

First edition.

Place of Publication:

Cambridge : Cambridge University Press, 2023.

Summary:

This introductory graduate coursebook offers a mathematical foundation for modern cryptography. Coverage includes secret key agreement, authentication, secret sharing, and secure computation. The book will also serve experts in the field as a reference for information-theoretic tools such as smooth min/max entropies and information spectrum.

Contents:

Cover

Halftitle page

Title page

Copyright page

Dedication

Contents

Preface

1 Introduction

1.1 Information Theory and Cryptography

1.2 Overview of Covered Topics

1.3 Overview of the Technical Framework

1.3.1 A Resource Theory for Cryptography

1.3.2 Formal Security Definitions

1.4 Possible Course Plans

1.5 References and Additional Reading

Part I External Adversary: Encryption, Authentication, Secret Key

2 Basic Information Theory

2.1 Very Basic Probability

2.2 The Law of Large Numbers

2.3 Convex and Concave Functions

2.4 Total Variation Distance

2.5 Kullback-Leibler Divergence

2.6 Shannon Entropy

2.7 Mutual Information

2.8 Fano's Inequality

2.9 Maximal Coupling Lemma

2.10 A Variational Formula for KL Divergence

2.11 Continuity of Entropy

2.12 Hoeffding's Inequality

2.13 Pinsker's Inequality

2.14 Rényi Entropy

2.15 References and Additional Reading

Problems

3 Secret Keys and Encryption

3.1 Secure Communication

3.2 Approximate Security

3.2.1 Indistinguishable and Semantic Security

3.2.2 Mutual Information and Total Variation Security

3.2.3 Impossibility Theorem for Approximate Security

3.3 Approximately Secure Keys

3.3.1 One-time Pad Using an Approximately Secure Key

3.3.2 Composable Security

3.4 Security and Reliability

3.5 References and Additional Reading

4 Universal Hash Families

4.1 A Short Primer on Finite Fields

4.2 Universal Hash Family: Basic Definition

4.3 Strong Universal Hash Families

4.4 Example Applications

4.4.1 Compression

4.4.2 Random Number Generation

4.4.3 Authentication

4.5 Almost Universal Hash Families

4.6 Practical Constructions

4.6.1 The Poly1305 Hash

4.6.2 The Nonlinear Hash (NH)

4.6.3 Reducing Randomness Cost.

4.7 References and Additional Reading

5 Hypothesis Testing

5.1 Binary Hypothesis Testing: The Neyman-Pearson Formulation

5.2 The Neyman-Pearson Lemma

5.3 Divergence and Hypothesis Testing

5.4 Stein's Lemma

5.5 A Primer on Method of Types

5.6 Composite Hypothesis Testing

5.7 References and Additional Reading

6 Information Reconciliation

6.1 Source Coding and Smooth Max-entropy

6.2 Source Coding with Side-information and Conditional Smooth Max-entropy

6.3 Evaluation of Smooth Max-entropies

6.4 References and Additional Reading

7 Random Number Generation

7.1 Random Number Generation

7.2 Leftover Hashing

7.3 Leftover Hashing with Side-information

7.4 Smoothing

7.5 A General Leftover Hash Lemma

7.6 Evaluation of Smooth Min-entropies

7.7 References and Additional Reading

8 Authentication

8.1 Message Authentication Using Secret Keys

8.2 MAC with Optimal Attack Detection Probabilities

8.3 MAC with Optimal Length Secret Keys

8.4 Authentication of Multiple Messages

8.5 Nonmalleability

8.6 References and Additional Reading

9 Computationally Secure Encryption and Authentication

9.1 One-time Encryption Revisited

9.2 Pseudorandom Generators and Computational Security

9.3 CPA Secure Encryption and Pseudorandom Functions

9.4 CCA Secure Encryption and Authentication

9.5 References and Additional Reading

10 Secret Key Agreement

10.1 Information-theoretic Secret Key Agreement

10.2 Information Reconciliation and Privacy Amplification

10.3 Impossibility Bounds

10.3.1 A Basic Impossibility Bound

10.3.2 Conditional Independence Testing Bound

10.3.3 Bounds Using Monotones

10.4 Secret Key Capacity

10.5 Protocols with Interactive Communication.

10.6 References and Additional Reading

Part II Internal Adversary: Secure Computation

11 Secret Sharing

11.1 Threshold Schemes

11.2 Ramp Schemes

11.3 Secret Sharing Schemes with a General Access Structure

11.4 Dishonest Share Holders

11.5 Error Correction and Secret Sharing

11.6 References and Additional Reading

12 Two-party Secure Computation for a Passive Adversary

12.1 Secure Computation with Interactive Communication

12.2 Secure Computation of Asymmetric Functions and Randomized Functions

12.3 Perfect Secure Computation from Scratch

12.4 Oblivious Transfer

12.5 Oracle Access and Memoryless Channels

12.6 Completeness of Oblivious Transfer

12.7 Classification of Deterministic Symmetric Functions

12.8 References and Additional Reading

13 Oblivious Transfer from Correlated Randomness

13.1 Information-theoretic Construction of Oblivious Transfer

13.2 String Oblivious Transfer from Correlation

13.3 Construction of Oblivious Transfer from Correlation

13.3.1 Erasure Correlation

13.3.2 Generalized Erasure Correlation

13.3.3 Correlation with Degenerate Reverse Channel

13.3.4 The Alphabet Extension Technique

13.4 Impossibility Results

13.4.1 Bound Based on Correlation

13.4.2 Bound Based on Uncertainty

13.5 Oblivious Transfer Capacity

13.6 Proof of Characterization of Complete Functions

13.6.1 The Construction of a Secure Computing Protocol

13.6.2 Impossibility Results on OT Generation

13.7 References and Additional Reading

14 Bit Commitment from Correlated Randomness

14.1 Bit Commitment

14.2 Example Applications

14.2.1 Coin Flipping

14.2.2 Zero-knowledge Proof

14.3 Standalone Security of Implemented Bit Commitment

14.4 Schemes for Implementing Bit Commitment Protocols.

14.4.1 Bit Commitment from Oblivious Transfer

14.4.2 Adversarial Correlation Test

14.4.3 Bit Commitment from General Correlation

14.5 Impossibility Result

14.6 Bit Commitment Capacity

14.7 References and Additional Reading

15 Active Adversary and Composable Security

15.1 Functions and Protocols

15.2 Admissible and Nonadmissible Attacks

15.3 Perfect Standalone Security

15.4 Approximate Standalone Security and Protocols with Abort

15.5 Composable Security and the Sequential Composition Theorem

15.6 Security for Multiphase Functions

15.7 Complete Fairness and Relaxation

15.8 Concurrent Composition

15.9 Oblivious Transfer from Correlated Randomness: Active Adversary

15.10 References and Additional Reading

16 Zero-knowledge Proof

16.1 Interactive Proofs and Zero-knowledge Proofs

16.2 Zero-knowledge Proof for an NP Language

16.3 Multi-prover Interactive Proofs

16.4 Parallel Repetition

16.5 References and Additional Reading

17 Two-party Secure Computation for an Active Adversary

17.1 The AND Function

17.2 The Committed Copy Function

17.3 Proving Linear Relations

17.4 The Committed Oblivious Transfer Function

17.5 Security Analysis of the Protocol for AND

17.6 References and Additional Reading

18 Broadcast, Byzantine Agreement, and Digital Signature

18.1 Multiparty Communication Model

18.2 Broadcast and Byzantine Agreement

18.3 Broadcast from Scratch

18.4 Impossibility of Broadcast from Scratch without a Supermajority

18.5 Broadcast without a Supermajority

18.5.1 Digital Signature

18.5.2 Broadcast and Digital Signature

18.6 Computationally Secure Digital Signature

18.7 References and Additional Reading

19 Multiparty Secure Computation

19.1 Multiparty Computation Formulation.

19.2 Secure Computation from Scratch for a Passive Adversary

19.3 Verifiable Secret Sharing

19.3.1 Dishonest Dealer

19.3.2 Scheme for an Honest Supermajority

19.4 Secure Computation for an Active Adversary

19.4.1 Commitment Using Verifiable Secret Sharing

19.4.2 Committed Addition

19.4.3 Committed Multiplication

19.5 Beyond an Honest Majority

19.5.1 Securely Computable Functions from Scratch

19.5.2 Secure Computation Using OT

19.6 References and Additional Reading

Appendix Solutions to Selected Problems

Solutions to Problems in Chapter 8

Problem 8.6

Solutions to Problems in Chapter 12

Problem 12.4

Solutions to Problems in Chapter 13

Problem 13.4

Problem 13.5

Problem 13.9

Problem 13.13

Solutions to Problems in Chapter 15

Problem 15.3

Problem 15.5

Problem 15.6

Problem 15.7

Problem 15.9

Solutions to Problems in Chapter 18

Problem 18.3

Problem 18.4

Problem 18.5

Problem 18.8

Problem 18.11

Problem 18.12

Problem 18.14

Problem 18.15

Problem 18.17

References

Symbol Index

Index.

Notes:

Also issued in print: 2023.

Includes bibliographical references and index.

Description based on online resource; title from PDF title page (viewed on April 12, 2023).

ISBN:

9781108598682

1108598684

9781108670203

1108670202

OCLC:

1376020366