David Pointcheval obtained a PhD in Computer Science and has since worked on the Cryptography Team at the École Normale Supérieure in France. His research focuses on provable security of cryptographic primitives and protocols.

• Foreword xiDavid POINTCHEVALChapter 1 Public-Key Encryption and Security Notions 1Nuttapong ATTRAPADUNG and Takahiro MATSUDA1.1. Basic definitions for PKE 21.1.1. Basic notation 21.1.2. Public-key encryption 21.1.3. IND-CPA and IND-CCA security 21.1.4. Other basic security notions and relations 41.2. Basic PKE schemes 51.2.1. Game-based proofs 51.2.2. ElGamal encryption 61.2.3. Simplified CS encryption 81.2.4. Cramer–Shoup encryption 111.2.5. Other specific PKE schemes 141.3. Generic constructions for IND-CCA secure PKE 161.3.1. Hybrid encryption 171.3.2. Naor–Yung construction and extensions 191.3.3. Fujisaki–Okamoto and other transforms in the RO model 211.3.4. Other generic constructions for IND-CCA secure PKE 231.4. Advanced topics 251.4.1. Intermediate notions related to CCA 251.4.2. IND-CCA security in multi-user setting and tight security 261.4.3. Key-dependent message security 281.4.4. More topics on PKE 301.5. References 31Chapter 2 Signatures and Security Notions 47Marc FISCHLIN2.1. Signature schemes 472.1.1. Definition 472.1.2. Examples of practical schemes 492.2. Unforgeability 512.2.1. Discussion 512.2.2. Existential unforgeability under chosen-message attacks 532.2.3. Unforgeability of practical schemes 542.3. Strong unforgeability 562.3.1. Discussion 562.3.2. Strong existential unforgeability under chosen-message attacks 572.3.3. Strong unforgeability of practical schemes 582.3.4. Building strongly unforgeable schemes 592.4. Summary 602.5. References 60Chapter 3 Zero-Knowledge Proofs 63Ivan VISCONTI3.1. Introduction 633.2. Notation 643.3. Classical zero-knowledge proofs 643.3.1. Zero knowledge 653.4. How to build a zero-knowledge proof system 683.4.1 ZK proofs for all NP 703.4.2. Round complexity 713.5. Relaxed security in proof systems 723.5.1. Honest-verifier ZK 723.5.2. Witness hiding/indistinguishability 733.5.3. Σ-Protocols 743.6. Non-black-box zero knowledge 753.7. Advanced notions 753.7.1. Publicly verifiable zero knowledge 763.7.2. Concurrent ZK and more 773.7.3. ZK with stateless players 783.7.4. Delayed-input proof systems 793.8. Conclusion 803.9. References 80Chapter 4 Secure Multiparty Computation 85Yehuda LINDELL4.1. Introduction 854.1.1. A note on terminology 874.2. Security of MPC 874.2.1. The definitional paradigm 874.2.2. Additional definitional parameters 894.2.3. Adversarial power 894.2.4. Modular sequential and concurrent composition 914.2.5. Important definitional implications 924.2.6. The ideal model and using MPC in practice 924.2.7. Any inputs are allowed 924.2.8. MPC secures the process, but not the output 924.3. Feasibility of MPC 934.4. Techniques 944.4.1. Shamir secret sharing 944.4.2. Honest-majority MPC with secret sharing 954.4.3. Private set intersection 974.4.4. Threshold cryptography 994.4.5. Dishonest-majority MPC 1004.4.6. Efficient and practical MPC 1004.5. MPC use cases 1014.5.1. Boston wage gap (Lapets et al. 2018) 1014.5.2. Advertising conversion (Ion et al. 2017) 1014.5.3. MPC for cryptographic key protection (Unbound Security; Sepior; Curv) 1014.5.4. Government collaboration (Sharemind) 1024.5.5. Privacy-preserving analytics (Duality) 1024.6. Discussion 1024.7. References 103Chapter 5 Pairing-Based Cryptography 107Olivier BLAZY5.1. Introduction 1085.1.1. Notations 1085.1.2. Generalities 1085.2. One small step for man, one giant leap for cryptography 1095.2.1. Opening Pandora’s box, demystifying the magic 1105.2.2. A new world of assumptions 1125.3. A new world of cryptographic protocols at your fingertips 1165.3.1. Identity-based encryption made easy 1175.3.2. Efficient deterministic compact signature 1185.4. References 119Chapter 6 Broadcast Encryption and Traitor Tracing 121Duong HIEU PHAN6.1. Introduction 1216.2. Security notions for broadcast encryption and TT 1236.3. Overview of broadcast encryption and TT 1256.4. Tree-based methods 1296.5. Code-based TT 1326.6. Algebraic schemes 1356.7. Lattice-based approach with post-quantum security 1426.8. References 143Chapter 7 Attribute-Based Encryption 151Romain GAY7.1. Introduction 1517.2. Pairing groups 1527.2.1. Cyclic groups 1527.2.2. Pairing groups 1527.3. Predicate encodings 1537.3.1. Definition 1537.3.2. Constructions 1547.4. Attribute-based encryption 1567.4.1. Definition 1567.4.2. A modular construction 1587.5. References 165Chapter 8 Advanced Signatures 167Olivier SANDERS8.1. Introduction 1678.2. Some constructions 1698.2.1. The case of scalar messages 1698.2.2. The case of non-scalar messages 1718.3. Applications 1738.3.1. Anonymous credentials 1738.3.2. Group signatures 1768.3.3. Direct anonymous attestations 1808.4. References 184Chapter 9 Key Exchange 187Colin BOYD9.1. Key exchange fundamentals 1879.1.1. Key exchange parties 1889.1.2. Key exchange messages 1899.1.3. Key derivation functions 1899.2. Unauthenticated key exchange 1919.2.1. Formal definitions and security models 1919.2.2. Constructions and examples 1929.3. Authenticated key exchange 1949.3.1. Non-interactive key exchange 1959.3.2. AKE security models 1969.3.3. Constructions and examples 2009.4. Conclusion 2069.5. References 207Chapter 10 Password Authenticated Key Exchange: Protocols and Security Models 213Stanislaw JARECKI10.1. Introduction 21310.2. First PAKE: EKE 21510.3. Game-based model of PAKE security 21810.3.1. The BPR security model 21810.3.2. Implicit versus explicit authentication 22110.3.3. Limitations of the BPR model 22110.3.4. EKE instantiated with Diffie–Hellman KE 22310.3.5. Implementing ideal cipher on arbitrary groups 22410.4. Simulation-based model of PAKE security 22510.4.1. The BMP security model 22510.4.2. Advantages of BMP definition: arbitrary passwords, tight security 22910.4.3. EKE using RO-derived one-time pad encryption 23010.4.4. BMP model for PAKE with explicit authentication (pake-ea) 23110.5. Universally composable model of PAKE security 23210.6. PAKE protocols in the standard model 23610.7. PAKE efficiency optimizations 23910.8. Asymmetric PAKE: PAKE for the client-server setting 24210.9. Threshold PAKE 24410.10. References 246Chapter 11 Verifiable Computation and Succinct Arguments for NP 257Dario FIORE11.1. Introduction 25711.1.1. Background 25811.2. Preliminaries 25911.3. Verifiable computation 26011.4. Constructing VC 26111.4.1. VC for circuits in three steps 26111.4.2. Succinct non-interactive arguments for non-deterministic computation 26311.4.3. Verifiable computation from SNARG 26411.5. A modular construction of SNARGs 26411.5.1. Algebraic non-interactive linear proofs 26511.5.2. Bilinear groups 26711.5.3. SNARGs from algebraic NILPs with degree-2 verifiers using bilinear groups 26911.6. Constructing algebraic NILPs for arithmetic circuits 27111.6.1. Arithmetic circuits 27111.6.2. Quadratic arithmetic programs 27111.6.3. Algebraic NILP for QAPs 27411.7. Conclusion 27911.8. References 279List of Authors 283Index 285

David Pointcheval obtained a PhD in Computer Science and has since worked on the Cryptography Team at the École Normale Supérieure in France. His research focuses on provable security of cryptographic primitives and protocols.

• Foreword xiDavid POINTCHEVALChapter 1 Public-Key Encryption and Security Notions 1Nuttapong ATTRAPADUNG and Takahiro MATSUDA1.1. Basic definitions for PKE 21.1.1. Basic notation 21.1.2. Public-key encryption 21.1.3. IND-CPA and IND-CCA security 21.1.4. Other basic security notions and relations 41.2. Basic PKE schemes 51.2.1. Game-based proofs 51.2.2. ElGamal encryption 61.2.3. Simplified CS encryption 81.2.4. Cramer–Shoup encryption 111.2.5. Other specific PKE schemes 141.3. Generic constructions for IND-CCA secure PKE 161.3.1. Hybrid encryption 171.3.2. Naor–Yung construction and extensions 191.3.3. Fujisaki–Okamoto and other transforms in the RO model 211.3.4. Other generic constructions for IND-CCA secure PKE 231.4. Advanced topics 251.4.1. Intermediate notions related to CCA 251.4.2. IND-CCA security in multi-user setting and tight security 261.4.3. Key-dependent message security 281.4.4. More topics on PKE 301.5. References 31Chapter 2 Signatures and Security Notions 47Marc FISCHLIN2.1. Signature schemes 472.1.1. Definition 472.1.2. Examples of practical schemes 492.2. Unforgeability 512.2.1. Discussion 512.2.2. Existential unforgeability under chosen-message attacks 532.2.3. Unforgeability of practical schemes 542.3. Strong unforgeability 562.3.1. Discussion 562.3.2. Strong existential unforgeability under chosen-message attacks 572.3.3. Strong unforgeability of practical schemes 582.3.4. Building strongly unforgeable schemes 592.4. Summary 602.5. References 60Chapter 3 Zero-Knowledge Proofs 63Ivan VISCONTI3.1. Introduction 633.2. Notation 643.3. Classical zero-knowledge proofs 643.3.1. Zero knowledge 653.4. How to build a zero-knowledge proof system 683.4.1 ZK proofs for all NP 703.4.2. Round complexity 713.5. Relaxed security in proof systems 723.5.1. Honest-verifier ZK 723.5.2. Witness hiding/indistinguishability 733.5.3. Σ-Protocols 743.6. Non-black-box zero knowledge 753.7. Advanced notions 753.7.1. Publicly verifiable zero knowledge 763.7.2. Concurrent ZK and more 773.7.3. ZK with stateless players 783.7.4. Delayed-input proof systems 793.8. Conclusion 803.9. References 80Chapter 4 Secure Multiparty Computation 85Yehuda LINDELL4.1. Introduction 854.1.1. A note on terminology 874.2. Security of MPC 874.2.1. The definitional paradigm 874.2.2. Additional definitional parameters 894.2.3. Adversarial power 894.2.4. Modular sequential and concurrent composition 914.2.5. Important definitional implications 924.2.6. The ideal model and using MPC in practice 924.2.7. Any inputs are allowed 924.2.8. MPC secures the process, but not the output 924.3. Feasibility of MPC 934.4. Techniques 944.4.1. Shamir secret sharing 944.4.2. Honest-majority MPC with secret sharing 954.4.3. Private set intersection 974.4.4. Threshold cryptography 994.4.5. Dishonest-majority MPC 1004.4.6. Efficient and practical MPC 1004.5. MPC use cases 1014.5.1. Boston wage gap (Lapets et al. 2018) 1014.5.2. Advertising conversion (Ion et al. 2017) 1014.5.3. MPC for cryptographic key protection (Unbound Security; Sepior; Curv) 1014.5.4. Government collaboration (Sharemind) 1024.5.5. Privacy-preserving analytics (Duality) 1024.6. Discussion 1024.7. References 103Chapter 5 Pairing-Based Cryptography 107Olivier BLAZY5.1. Introduction 1085.1.1. Notations 1085.1.2. Generalities 1085.2. One small step for man, one giant leap for cryptography 1095.2.1. Opening Pandora’s box, demystifying the magic 1105.2.2. A new world of assumptions 1125.3. A new world of cryptographic protocols at your fingertips 1165.3.1. Identity-based encryption made easy 1175.3.2. Efficient deterministic compact signature 1185.4. References 119Chapter 6 Broadcast Encryption and Traitor Tracing 121Duong HIEU PHAN6.1. Introduction 1216.2. Security notions for broadcast encryption and TT 1236.3. Overview of broadcast encryption and TT 1256.4. Tree-based methods 1296.5. Code-based TT 1326.6. Algebraic schemes 1356.7. Lattice-based approach with post-quantum security 1426.8. References 143Chapter 7 Attribute-Based Encryption 151Romain GAY7.1. Introduction 1517.2. Pairing groups 1527.2.1. Cyclic groups 1527.2.2. Pairing groups 1527.3. Predicate encodings 1537.3.1. Definition 1537.3.2. Constructions 1547.4. Attribute-based encryption 1567.4.1. Definition 1567.4.2. A modular construction 1587.5. References 165Chapter 8 Advanced Signatures 167Olivier SANDERS8.1. Introduction 1678.2. Some constructions 1698.2.1. The case of scalar messages 1698.2.2. The case of non-scalar messages 1718.3. Applications 1738.3.1. Anonymous credentials 1738.3.2. Group signatures 1768.3.3. Direct anonymous attestations 1808.4. References 184Chapter 9 Key Exchange 187Colin BOYD9.1. Key exchange fundamentals 1879.1.1. Key exchange parties 1889.1.2. Key exchange messages 1899.1.3. Key derivation functions 1899.2. Unauthenticated key exchange 1919.2.1. Formal definitions and security models 1919.2.2. Constructions and examples 1929.3. Authenticated key exchange 1949.3.1. Non-interactive key exchange 1959.3.2. AKE security models 1969.3.3. Constructions and examples 2009.4. Conclusion 2069.5. References 207Chapter 10 Password Authenticated Key Exchange: Protocols and Security Models 213Stanislaw JARECKI10.1. Introduction 21310.2. First PAKE: EKE 21510.3. Game-based model of PAKE security 21810.3.1. The BPR security model 21810.3.2. Implicit versus explicit authentication 22110.3.3. Limitations of the BPR model 22110.3.4. EKE instantiated with Diffie–Hellman KE 22310.3.5. Implementing ideal cipher on arbitrary groups 22410.4. Simulation-based model of PAKE security 22510.4.1. The BMP security model 22510.4.2. Advantages of BMP definition: arbitrary passwords, tight security 22910.4.3. EKE using RO-derived one-time pad encryption 23010.4.4. BMP model for PAKE with explicit authentication (pake-ea) 23110.5. Universally composable model of PAKE security 23210.6. PAKE protocols in the standard model 23610.7. PAKE efficiency optimizations 23910.8. Asymmetric PAKE: PAKE for the client-server setting 24210.9. Threshold PAKE 24410.10. References 246Chapter 11 Verifiable Computation and Succinct Arguments for NP 257Dario FIORE11.1. Introduction 25711.1.1. Background 25811.2. Preliminaries 25911.3. Verifiable computation 26011.4. Constructing VC 26111.4.1. VC for circuits in three steps 26111.4.2. Succinct non-interactive arguments for non-deterministic computation 26311.4.3. Verifiable computation from SNARG 26411.5. A modular construction of SNARGs 26411.5.1. Algebraic non-interactive linear proofs 26511.5.2. Bilinear groups 26711.5.3. SNARGs from algebraic NILPs with degree-2 verifiers using bilinear groups 26911.6. Constructing algebraic NILPs for arithmetic circuits 27111.6.1. Arithmetic circuits 27111.6.2. Quadratic arithmetic programs 27111.6.3. Algebraic NILP for QAPs 27411.7. Conclusion 27911.8. References 279List of Authors 283Index 285

David Pointcheval obtained a PhD in Computer Science and has since worked on the Cryptography Team at the École Normale Supérieure in France. His research focuses on provable security of cryptographic primitives and protocols.

• Foreword xiDavid POINTCHEVALChapter 1 Public-Key Encryption and Security Notions 1Nuttapong ATTRAPADUNG and Takahiro MATSUDA1.1. Basic definitions for PKE 21.1.1. Basic notation 21.1.2. Public-key encryption 21.1.3. IND-CPA and IND-CCA security 21.1.4. Other basic security notions and relations 41.2. Basic PKE schemes 51.2.1. Game-based proofs 51.2.2. ElGamal encryption 61.2.3. Simplified CS encryption 81.2.4. Cramer–Shoup encryption 111.2.5. Other specific PKE schemes 141.3. Generic constructions for IND-CCA secure PKE 161.3.1. Hybrid encryption 171.3.2. Naor–Yung construction and extensions 191.3.3. Fujisaki–Okamoto and other transforms in the RO model 211.3.4. Other generic constructions for IND-CCA secure PKE 231.4. Advanced topics 251.4.1. Intermediate notions related to CCA 251.4.2. IND-CCA security in multi-user setting and tight security 261.4.3. Key-dependent message security 281.4.4. More topics on PKE 301.5. References 31Chapter 2 Signatures and Security Notions 47Marc FISCHLIN2.1. Signature schemes 472.1.1. Definition 472.1.2. Examples of practical schemes 492.2. Unforgeability 512.2.1. Discussion 512.2.2. Existential unforgeability under chosen-message attacks 532.2.3. Unforgeability of practical schemes 542.3. Strong unforgeability 562.3.1. Discussion 562.3.2. Strong existential unforgeability under chosen-message attacks 572.3.3. Strong unforgeability of practical schemes 582.3.4. Building strongly unforgeable schemes 592.4. Summary 602.5. References 60Chapter 3 Zero-Knowledge Proofs 63Ivan VISCONTI3.1. Introduction 633.2. Notation 643.3. Classical zero-knowledge proofs 643.3.1. Zero knowledge 653.4. How to build a zero-knowledge proof system 683.4.1 ZK proofs for all NP 703.4.2. Round complexity 713.5. Relaxed security in proof systems 723.5.1. Honest-verifier ZK 723.5.2. Witness hiding/indistinguishability 733.5.3. Σ-Protocols 743.6. Non-black-box zero knowledge 753.7. Advanced notions 753.7.1. Publicly verifiable zero knowledge 763.7.2. Concurrent ZK and more 773.7.3. ZK with stateless players 783.7.4. Delayed-input proof systems 793.8. Conclusion 803.9. References 80Chapter 4 Secure Multiparty Computation 85Yehuda LINDELL4.1. Introduction 854.1.1. A note on terminology 874.2. Security of MPC 874.2.1. The definitional paradigm 874.2.2. Additional definitional parameters 894.2.3. Adversarial power 894.2.4. Modular sequential and concurrent composition 914.2.5. Important definitional implications 924.2.6. The ideal model and using MPC in practice 924.2.7. Any inputs are allowed 924.2.8. MPC secures the process, but not the output 924.3. Feasibility of MPC 934.4. Techniques 944.4.1. Shamir secret sharing 944.4.2. Honest-majority MPC with secret sharing 954.4.3. Private set intersection 974.4.4. Threshold cryptography 994.4.5. Dishonest-majority MPC 1004.4.6. Efficient and practical MPC 1004.5. MPC use cases 1014.5.1. Boston wage gap (Lapets et al. 2018) 1014.5.2. Advertising conversion (Ion et al. 2017) 1014.5.3. MPC for cryptographic key protection (Unbound Security; Sepior; Curv) 1014.5.4. Government collaboration (Sharemind) 1024.5.5. Privacy-preserving analytics (Duality) 1024.6. Discussion 1024.7. References 103Chapter 5 Pairing-Based Cryptography 107Olivier BLAZY5.1. Introduction 1085.1.1. Notations 1085.1.2. Generalities 1085.2. One small step for man, one giant leap for cryptography 1095.2.1. Opening Pandora’s box, demystifying the magic 1105.2.2. A new world of assumptions 1125.3. A new world of cryptographic protocols at your fingertips 1165.3.1. Identity-based encryption made easy 1175.3.2. Efficient deterministic compact signature 1185.4. References 119Chapter 6 Broadcast Encryption and Traitor Tracing 121Duong HIEU PHAN6.1. Introduction 1216.2. Security notions for broadcast encryption and TT 1236.3. Overview of broadcast encryption and TT 1256.4. Tree-based methods 1296.5. Code-based TT 1326.6. Algebraic schemes 1356.7. Lattice-based approach with post-quantum security 1426.8. References 143Chapter 7 Attribute-Based Encryption 151Romain GAY7.1. Introduction 1517.2. Pairing groups 1527.2.1. Cyclic groups 1527.2.2. Pairing groups 1527.3. Predicate encodings 1537.3.1. Definition 1537.3.2. Constructions 1547.4. Attribute-based encryption 1567.4.1. Definition 1567.4.2. A modular construction 1587.5. References 165Chapter 8 Advanced Signatures 167Olivier SANDERS8.1. Introduction 1678.2. Some constructions 1698.2.1. The case of scalar messages 1698.2.2. The case of non-scalar messages 1718.3. Applications 1738.3.1. Anonymous credentials 1738.3.2. Group signatures 1768.3.3. Direct anonymous attestations 1808.4. References 184Chapter 9 Key Exchange 187Colin BOYD9.1. Key exchange fundamentals 1879.1.1. Key exchange parties 1889.1.2. Key exchange messages 1899.1.3. Key derivation functions 1899.2. Unauthenticated key exchange 1919.2.1. Formal definitions and security models 1919.2.2. Constructions and examples 1929.3. Authenticated key exchange 1949.3.1. Non-interactive key exchange 1959.3.2. AKE security models 1969.3.3. Constructions and examples 2009.4. Conclusion 2069.5. References 207Chapter 10 Password Authenticated Key Exchange: Protocols and Security Models 213Stanislaw JARECKI10.1. Introduction 21310.2. First PAKE: EKE 21510.3. Game-based model of PAKE security 21810.3.1. The BPR security model 21810.3.2. Implicit versus explicit authentication 22110.3.3. Limitations of the BPR model 22110.3.4. EKE instantiated with Diffie–Hellman KE 22310.3.5. Implementing ideal cipher on arbitrary groups 22410.4. Simulation-based model of PAKE security 22510.4.1. The BMP security model 22510.4.2. Advantages of BMP definition: arbitrary passwords, tight security 22910.4.3. EKE using RO-derived one-time pad encryption 23010.4.4. BMP model for PAKE with explicit authentication (pake-ea) 23110.5. Universally composable model of PAKE security 23210.6. PAKE protocols in the standard model 23610.7. PAKE efficiency optimizations 23910.8. Asymmetric PAKE: PAKE for the client-server setting 24210.9. Threshold PAKE 24410.10. References 246Chapter 11 Verifiable Computation and Succinct Arguments for NP 257Dario FIORE11.1. Introduction 25711.1.1. Background 25811.2. Preliminaries 25911.3. Verifiable computation 26011.4. Constructing VC 26111.4.1. VC for circuits in three steps 26111.4.2. Succinct non-interactive arguments for non-deterministic computation 26311.4.3. Verifiable computation from SNARG 26411.5. A modular construction of SNARGs 26411.5.1. Algebraic non-interactive linear proofs 26511.5.2. Bilinear groups 26711.5.3. SNARGs from algebraic NILPs with degree-2 verifiers using bilinear groups 26911.6. Constructing algebraic NILPs for arithmetic circuits 27111.6.1. Arithmetic circuits 27111.6.2. Quadratic arithmetic programs 27111.6.3. Algebraic NILP for QAPs 27411.7. Conclusion 27911.8. References 279List of Authors 283Index 285