The aim of this text is to treat selected topics of the subject of contemporary cryptology, structured in five quite independent but related themes: Efficient distributed computation modulo a shared secret, multiparty computation, modern cryptography, provable security for public key schemes, and efficient and secure public-key cryptosystems. The aim of this text is to treat selected topics of the subject of contemporary cryptology, structured in five quite independent but related themes: Efficient distributed computation modulo a shared secret, multiparty computation, modern cryptography, provable security for public key schemes, and efficient and secure public-key cryptosystems. Foreword ix A Efficient Distributed Computation Modulo a Shared Secret 1(40) Dario Catalano 1 Introduction 1(3) 1.1 Previous Work 2(1) 1.2 Organization of this Lecture 3(1) 2 Preliminaries 4(1) 2.1 The Network Model 4(1) 2.2 Definitions and Notations 4(1) 3 Building Blocks 5(4) 3.1 Additive Sharing over Zq 6(1) 3.2 Polynomial Sharing over Zq 6(1) 3.3 Additive Sharing over Z 7(1) 3.4 Polynomial Sharing over Z 8(1) 4 Basic Protocols 9(2) 4.1 Distributed Computation Modulo q 9(1) 4.2 Joint Random Sharing over Zq 10(1) 4.3 Joint Random Sharing of 0 in Zq 10(1) 4.4 Computing Shares of the Inverse of a Shared Secret 11(1) 4.5 Joint Random Invertible Element Sharing 11(1) 5 A Different Approach 11(1) 6 Converting among Different Secret Sharing Methods 12(5) 6.1 Converting between Additive and Polynomial Shares 12(1) 6.2 Converting between Integer Shares and Zq Shares 13(3) 6.3 Computing Shares of the Binary Representation of a Secret 16(1) 6.4 Approximate Truncation 16(1) 7 Distributed Modular Reduction 17(6) 7.1 Newton Iteration Method 17(1) 7.2 First Step: Computing Shares of an Approximation of 1/? 18(2) 7.3 Second Step: the Modular Reduction Protocol 20(3) 8 Exponentiation with a Shared Exponent 23(3) 8.1 Set Membership 24(2) 9 Generating Shared Random Primes 26(4) 9.1 The Basic Miller-Rabin Algorithm 26(1) 9.2 Generation of a Shared Candidate Prime 27(1) 9.3 Distributed Miller-Rabin Primality Test 27(1) 9.4 Generation of Shared Random Safe Primes 28(2) 10 Efficient Generation of Shared RSA Keys 30(1) 11 Computing Inverses over a Shared Modulus 30(6) 11.1 The Basic Idea 30(1) 11.2 The Full Protocol 31(3) 11.3 A Fundamental Lemma 34(2) References 36(5) B Multiparty Computation, an Introduction Ronald Cramer and Ivan Damgård 41(48) 1 Introduction 41(1) 2 What is Multiparty Computation? 41(8) 2.1 The MPC and VSS Problems 41(1) 2.2 Adversaries and their Powers 42(1) 2.3 Models of Communication 43(1) 2.4 Definition of Security 44(5) 3 Results on MPC 49(2) 3.1 Results for Threshold Adversaries 49(1) 3.2 Results for General Adversaries 50(1) 4 MPC Protocols 51(25) 4.1 The Passive Case 53(7) 4.2 The Active Case 60(5) 4.3 Realization of Fcom: Information Theoretic Scenario 65(10) 4.4 Formal Proof for the Fcom: Realization 75(1) 5 The Cryptographic Scenario 76(2) 5.1 Using Encryption to Implement the Channels 76(1) 5.2 Cryptographic Implementations of Higher-Level Functionalities 77(1) 6 Protocols Secure for General Adversary Structures 78(1) A Formal Details of the General Security Model for Protocols 78(7) A.1 The Real-Life Execution 79(1) A.2 The Ideal Process 80(2) A.3 The Hybrid Models 82(1) A.4 Composing Protocols 83(1) A.5 Composing Interfaces 84(1) References 85(4) C Foundations of Modern Cryptography Giovanni Di Crescenzo 89(44) 1 Introduction 89(1) 2 One-Way Functions 89(9) 2.1 Definitions 90(2) 2.2 Candidates from Number Theory 92(2) 2.3 Weak vs. Strong One-Way Functions 94(4) 3 Pseudo-Random Generators 98(5) 3.1 Definitions 99(1) 3.2 Constructions 100(3) 3.3 A Cryptographic Application 103(1) 4 Pseudo-Random Functions 103(6) 4.1 Definitions 104(1) 4.2 Constructions 105(3) 4.3 Examples and Applications 108(1) 5 Zero-Knowledge Protocols 109(20) 5.1 Basic Definitions 110(1) 5.2 Zero-Knowledge Proof Systems of Membership 111(5) 5.3 Witness-Indistinguishable Proof Systems of Knowledge 116(3) 5.4 Zero-Knowledge Proof Systems of Decision Power 119(5) 5.5 Zero-Knowledge Transfers of Decision 124(5) References 129(4) D Provable Security for Public Key Schemes David Pointcheval 133(58) 1 Introduction 133(2) 1.1 Provable Security 134(1) 1.2 Exact Security and Practical Security 134(1) 1.3 Outline of the Notes 135(1) 1.4 Related Work 135(1) 2 Security Proofs and Security Arguments 135(3) 2.1 Computational Assumptions 135(1) 2.2 "Reductionist" Security Proofs 136(1) 2.3 Practical Security 136(1) 2.4 The Random-Oracle Model 137(1) 2.5 The General Framework 138(1) 3 A First Formalism 138(5) 3.1 Digital Signature Schemes 139(1) 3.2 Public-Key Encryption 140(3) 4 The Computational Assumptions 143(3) 4.1 Integer Factoring and the R SA Problem 143(2) 4.2 The Discrete Logarithm and the Diffie-Hellman Problems 145(1) 5 Digital Signature Schemes 146(17) 5.1 Provable Security 147(1) 5.2 DL-Based Signatures 148(6) 5.3 RSA-Based Signatures 154(9) 6 Public-Key Encryption 163(21) 6.1 History 163(1) 6.2 A First Generic Construction 164(3) 6.3 OAEP: the Optimal Asymmetric Encryption Padding 167(12) 6.4 REACT: a Rapid Enhanced-security Asymmetric Cryptosystem Transform 179(5) 7 Conclusion 184(1) References 185(6) E Efficient and Secure Public Key Cryptosystems Tsugoshi Takagi 191 1 Efficient Integer Arithmetic 191(5) 1.1 Modular Exponentiation 191(1) 1.2 Window Methods 192(2) 1.3 Montgomery Multiplication 194(2) 2 Fast Variants of RSA Cryptosystem 196(5) 2.1 PKCS #1 Version 2.1 196(1) 2.2 Multi-Exponent RSA 197(2) 2.3 Size of Secret Primes 199(1) 2.4 Comparison 200(1) 3 Implementation Attack on RSA-CRT 201(3) 4 EPOC Cryptosystem 204(10) 4.1 EPOC-2 Cryptosystem 204(3) 4.2 Reject Timing Attack on EPOC-2 207(5) 4.3 Relation to Other Cryptosystems 212(1) 4.4 Other Encryption Primitives 213(1) 5 Elliptic Curve Cryptosystem 214(4) 5.1 Scalar Multiplication 215(2) 5.2 Efficient Coordinate System 217(1) 6 Side Channel Attacks on ECC 218(2) 6.1 SPA on ECC 218(1) 6.2 DPA and Countermeasures 219(1) 6.3 Goubin's Power-Analysis Attack 220(1) 7 Zero-Value Point Attack on ECC 220(11) 7.1 Non-Zero Digit Methods 226(1) 7.2 Montgomery Ladder Method 226(5) 7.3 Non-Zero Window Method 231(1) References 231