A Graduate Course in Applied Cryptography (Version 0.5)

1 Introduction 1 1.1 Historic ciphers 1 1.2 Terminology used throughout the book 1 I Secret key cryptography 17 2 Encryption 18 2.1 Shannon ciphers and perfect security 18 2.1.1 Definition of a Shannon cipher 18 2.1.2 Perfect security 21 2.1.3 The bad news 26 2.2 Computational ciphers and semantic security 27 2.2.1 Definition of a computational cipher 27 2.2.2 Definition of semantic security 29 2.2.3 Connections to weaker notions of security 32 2.2.4 Consequences of semantic security 36 2.2.5 Bit guessing: an alternative characterization of semantic security 39 2.3 Mathematical details 41 2.3.1 Negligible, super-poly, and poly-bounded functions 42 2.3.2 Computational ciphers: the formalities 43 2.3.3 Efficient adversaries and attack games 46 2.3.4 Semantic security: the formalities 48 2.4 A fun application: anonymous routing 49 2.5 Notes 52 2.6 Exercises 52 3 Stream ciphers 59 3.1 Pseudo-random generators 59 3.1.1 Definition of a pseudo-random generator 60 3.1.2 Mathematical details 62 3.2 Stream ciphers: encryption with a PRG 62 3.3 Stream cipher limitations: attacks on the one time pad 66 3.3.1 The two-time pad is insecure 67 3.3.2 The one-time pad is malleable 67 3.4 Composing PRGs 68 3.4.1 A parallel construction 68 3.4.2 A sequential construction: the Blum-Micali method 73 3.4.3 Mathematical details 75 3.5 The next bit test 78 3.6 Case study: the Salsa and ChaCha PRGs 81 3.7 Case study: linear generators 84 3.7.1 An example cryptanalysis: linear congruential generators 84 3.7.2 The subset sum generator 87 3.8 Case study: cryptanalysis of the DVD encryption system 88 3.9 Case study: cryptanalysis of the RC4 stream cipher 90 3.9.1 Security of RC4 92 3.10 Generating random bits in practice 94 3.11 A broader perspective: computational indistinguishability 95 3.11.1 Mathematical details 100 3.12 A fun application: coin flipping and bit commitment 101 3.13 Notes 102 3.14 Exercises 102 4 Block ciphers 108 4.1 Block ciphers: basic definitions and properties 108 4.1.1 Some implications of security 110 4.1.2 Efficient implementation of random permutations 113 4.1.3 Strongly secure block ciphers 113 4.1.4 Using a block cipher directly for encryption 114 4.1.5 Mathematical details 118 4.2 Constructing block ciphers in practice 119 4.2.1 Case study: DES 121 4.2.2 Exhaustive search on DES: the DES challenges 125 4.2.3 Strengthening ciphers against exhaustive search: the 3E construction 127 4.2.4 Case study: AES 129 4.3 Sophisticated attacks on block ciphers 134 4.3.1 Algorithmic attacks 135 4.3.2 Side-channel attacks 138 4.3.3 Fault-injection attacks on AES 142 4.3.4 Quantum exhaustive search attacks 143 4.4 Pseudo-random functions: basic definitions and properties 144 4.4.1 Definitions 144 4.4.2 Efficient implementation of random functions 145 4.4.3 When is a secure block cipher a secure PRF? 146 4.4.4 Constructing PRGs from PRFs 150 4.4.5 Mathematical details 151 4.5 Constructing block ciphers from PRFs 153 4.6 The tree construction: from PRGs to PRFs 159 4.6.1 Variable length tree construction 163 4.7 The ideal cipher model 166 4.7.1 Formal definitions 166 4.7.2 Exhaustive search in the ideal cipher model 167 4.7.3 The Even-Mansour block cipher and the EX construction 170 4.7.4 Proof of the Even-Mansour and EX theorems 171 4.8 Fun application: comparing information without revealing it 177 4.9 Notes 179 4.10 Exercises 179 5 Chosen Plaintext Attack 188 5.1 Introduction 188 5.2 Security against multi-key attacks 190 5.3 Semantic security against chosen plaintext attack 192 5.4 Building CPA secure ciphers 194 5.4.1 A generic hybrid construction 194 5.4.2 Randomized counter mode 200 5.4.3 CBC mode 205 5.4.4 Case study: CBC padding in TLS 1.0 210 5.4.5 Concrete parameters and a comparison of counter and CBC modes 210 5.5 Nonce-based encryption 212 5.5.1 Nonce-based generic hybrid encryption 214 5.5.2 Nonce-based Counter mode 214 5.5.3 Nonce-based CBC mode 215 5.6 A fun application: revocable broadcast encryption 216 5.7 Notes 219 5.8 Exercises 219 6 Message integrity 226 6.1 Definition of a message authentication code 228 6.1.1 Mathematical details 231 6.2 MAC verification queries do not help the attacker 231 6.3 Constructing MACs from PRFs 234 6.4 Prefix-free PRFs for long messages 236 6.4.1 The CBC prefix-free secure PRF 237 6.4.2 The cascade prefix-free secure PRF 240 6.4.3 Extension attacks: CBC and cascade are insecure MACs 241 6.5 From prefix-free secure PRF to fully secure PRF (method 1): encrypted PRF 242 6.5.1 ECBC and NMAC: MACs for variable length inputs 243 6.6 From prefix-free secure PRF to fully secure PRF (method 2): prefix-free encodings 246 6.6.1 Prefix free encodings 246 6.7 From prefix-free secure PRF to fully secure PRF (method 3): CMAC 247 6.8 Converting a block-wise PRF to bit-wise PRF 250 6.9 Case study: ANSI CBC-MAC 251 6.10 Case study: CMAC 252 6.11 PMAC: a parallel MAC 254 6.12 A fun application: searching on encrypted data 256 6.13 Notes 256 6.14 Exercises 257 7 Message integrity from universal hashing 262 7.1 Universal hash functions (UHFs) 262 7.1.1 Multi-query UHFs 264 7.1.2 Mathematical details 265 7.2 Constructing UHFs 265 7.2.1 Construction 1: UHFs using polynomials 265 7.2.2 Construction 2: CBC and cascade are computational UHFs 268 7.2.3 Construction 3: a parallel UHF from a small PRF 270 7.3 PRF(UHF) composition: constructing MACs using UHFs 272 7.3.1 Using PRF(UHF) composition: ECBC and NMAC security 275 7.3.2 Using PRF(UHF) composition with polynomial UHFs 275 7.3.3 Using PRF(UHF) composition: PMAC0 security 276 7.4 The Carter-Wegman MAC 276 7.4.1 Using Carter-Wegman with polynomial UHFs 283 7.5 Nonce-based MACs 283 7.5.1 Secure nonce-based MACs 283 7.6 Unconditionally secure one-time MACs 284 7.6.1 Pairwise unpredictable functions 285 7.6.2 Building unpredictable functions 285 7.6.3 From PUFs to unconditionally secure one-time MACs 286 7.7 A fun application: timing attacks 286 7.8 Notes 286 7.9 Exercises 287 8 Message integrity from collision resistant hashing 297 8.1 Definition of collision resistant hashing 300 8.1.1 Mathematical details 300 8.2 Building a MAC for large messages 301 8.3 Birthday attacks on collision resistant hash functions 303 8.4 The Merkle-Damgård paradigm 305 8.4.1 Joux's attack 308 8.5 Building Compression Functions 308 8.5.1 A simple but inefficient compression function 309 8.5.2 Davies-Meyer compression functions 309 8.5.3 Collision resistance of Davies-Meyer 311 8.6 Case study: SHA256 312 8.6.1 Other Merkle-Damgård hash functions 314 8.7 Case study: HMAC 316 8.7.1 Security of two-key nest 317 8.7.2 The HMAC standard 319 8.7.3 Davies-Meyer is a secure PRF in the ideal cipher model 320 8.8 The Sponge Construction and SHA3 323 8.8.1 The sponge construction 323 8.8.2 Case study: SHA3, SHAKE256, and SHAKE512 328 8.9 Merkle trees: proving properties of a hashed list 329 8.9.1 Authenticated data structures 332 8.10 Key derivation and the random oracle model 333 8.10.1 The key derivation problem 334 8.10.2 Random oracles: a useful heuristic 336 8.10.3 Random oracles: safe modes of operation 341 8.10.4 The leftover hash lemma 343 8.10.5 Case study: HKDF 344 8.11 Security without collision resistance 345 8.11.1 Second preimage resistance 345 8.11.2 Randomized hash functions: target collision resistance 346 8.11.3 TCR from 2nd-preimage resistance 347 8.11.4 Using target collision resistance 350 8.12 A fun application: commitments and auctions 352 8.13 Notes 356 8.14 Exercises 356 9 Authenticated Encryption 366 9.1 Authenticated encryption: definitions 367 9.1.1 One-time authenticated encryption 368 9.2 Implications of authenticated encryption 369 9.2.1 Chosen ciphertext attacks: a motivating example 369 9.2.2 Chosen ciphertext attacks: definition 371 9.2.3 Authenticated encryption implies chosen ciphertext security 372 9.3 Encryption as an abstract interface 374 9.4 Authenticated encryption ciphers from generic composition 376 9.4.1 Encrypt-then-MAC 376 9.4.2 MAC-then-encrypt is not generally secure: padding oracle attacks on SSL 378 9.4.3 More padding oracle attacks. 381 9.4.4 Secure instances of MAC-then-encrypt 382 9.4.5 Encrypt-then-MAC or MAC-then-encrypt? 386 9.5 Nonce-based authenticated encryption with associated data 386 9.6 One more variation: CCA-secure ciphers with associated data 389 9.7 Case study: Galois counter mode (GCM) 390 9.8 Case study: the TLS 1.3 record protocol 392 9.9 Case study: an attack on non-atomic decryption in SSH 395 9.10 Case study: 802.11b WEP, a badly broken system 398 9.11 Case study: IPsec 400 9.12 A fun application: private information retrieval 405 9.13 Notes 405 9.14 Exercises 405 II Public key cryptography 412 10 Public key tools 413 10.1 A toy problem: anonymous key exchange 413 10.2 One-way trapdoor functions 414 10.2.1 Key exchange using a one-way trapdoor function scheme 415 10.2.2 Mathematical details 416 10.3 A trapdoor permutation scheme based on RSA 417 10.3.1 Key exchange based on the RSA assumption 419 10.3.2 Mathematical details 419 10.4 Diffie-Hellman key exchange 420 10.4.1 The key exchange protocol 421 10.4.2 Security of Diffie-Hellman key exchange 421 10.5 Discrete logarithm and related assumptions 422 10.5.1 Random self-reducibility 425 10.5.2 Mathematical details 426 10.6 Collision resistant hash functions from number-theoretic primitives 428 10.6.1 Collision resistance based on DL 428 10.6.2 Collision resistance based on RSA 429 10.7 Attacks on the anonymous Diffie-Hellman protocol 431 10.8 Merkle puzzles: a partial solution to key exchange using block ciphers 432 10.9 Fun application: RSA accumulators 434 10.10 Notes 434 10.11 Exercises 434 11 Public key encryption 444 11.1 Two further example applications 445 11.1.1 Sharing encrypted files 445 11.1.2 Key escrow 445 11.2 Basic definitions 446 11.2.1 Mathematical details 447 11.3 Implications of semantic security 448 11.3.1 The need for randomized encryption 448 11.3.2 Semantic security against chosen plaintext attack 449 11.4 Encryption based on a trapdoor function scheme 451 11.4.1 Instantiating ETDF with RSA 454 11.5 ElGamal encryption 455 11.5.1 Semantic security of ElGamal in the random oracle model 456 11.5.2 Semantic security of ElGamal without random oracles 458 11.6 Threshold decryption 461 11.6.1 Shamir's secret sharing scheme 463 11.6.2 ElGamal threshold decryption 465 11.7 Fun application: oblivious transfer based on Diffie-Hellman 468 11.7.1 A secure OT from ElGamal encryption 469 11.7.2 Adaptive oblivious transfer 471 11.7.3 Oblivious PRFs 471 11.7.4 A simple adaptive OT from an oblivious PRF 474 11.8 Notes 475 11.9 Exercises 475 12 Chosen ciphertext secure public key encryption 485 12.1 Basic definitions 485 12.2 Understanding CCA security 487 12.2.1 CCA security and ciphertext malleability 487 12.2.2 CCA security vs authentication 488 12.2.3 CCA security and key escrow 489 12.2.4 Encryption as an abstract interface 490 12.3 CCA-secure encryption from trapdoor function schemes 492 12.3.1 Instantiating ETDF' with RSA 497 12.4 CCA-secure ElGamal encryption 497 12.5 CCA security from DDH without random oracles 502 12.5.1 Universal projective hash functions 502 12.5.2 Universal2 projective hash functions 505 12.5.3 The ECS scheme 506 12.6 CCA security via a generic transformation 512 12.6.1 A generic instantiation 517 12.6.2 A concrete instantiation with ElGamal 517 12.7 CCA-secure public-key encryption with associated data 519 12.8 Case study: PKCS1, OAEP, OAEP+, and SAEP 520 12.8.1 Padding schemes 521 12.8.2 PKCS1 padding 522 12.8.3 Bleichenbacher's attack on the RSA-PKCS1 encryption scheme 523 12.8.4 Optimal Asymmetric Encryption Padding (OAEP) 525 12.8.5 OAEP+ and SAEP+ 528 12.9 Fun application: Pedersen commitments 528 12.10 Notes 528 12.11 Exercises 528 13 Digital signatures 541 13.1 Definition of a digital signature 543 13.1.1 Secure signatures 544 13.1.2 Mathematical details 547 13.2 Extending the message space with collision resistant hashing 547 13.2.1 Extending the message space using TCR functions 548 13.3 Signatures from trapdoor permutations: the full domain hash 549 13.3.1 Signatures based on the RSA trapdoor permutation 550 13.4 Security analysis of full domain hash 553 13.4.1 Repeated one-way functions: a useful lemma 553 13.4.2 Proofs of Theorems 13.3 and 13.4 557 13.5 An RSA-based signature scheme with a tight security proof 558 13.6 Case study: PKCS1 signatures 560 13.6.1 Bleichenbacher's attack on PKCS1 signatures 562 13.7 Signcryption: combining signatures and encryption 563 13.7.1 Secure signcryption 565 13.7.2 Signcryption as an abstract interface 568 13.7.3 Constructions: encrypt-then-sign and sign-then-encrypt 570 13.7.4 A construction based on Diffie-Hellman key exchange 574 13.7.5 Additional desirable properties: forward secrecy and non-repudiation 576 13.8 Certificates and the public-key infrastructure 580 13.8.1 Coping with malicious or negligent certificate authorities 582 13.8.2 Certificate revocation 586 13.9 Case study: legal aspects of digital signatures 588 13.10 A fun application: signatures of non-existence 589 13.11 Notes 589 13.12 Exercises 589 14 Fast hash-based signatures 597 14.1 Basic Lamport signatures 598 14.1.1 Shrinking the signature using an enhanced TCR 599 14.2 A general Lamport framework 600 14.2.1 An explicit containment free function 602 14.3 Winternitz one-time signatures 603 14.3.1 A domination free function for Winternitz signatures 606 14.4 HORS: short Lamport signatures 607 14.4.1 Shrinking the public-key using a Merkle tree 608 14.5 Applications of one-time signatures 609 14.5.1 Online/offline signatures from one-time signatures 609 14.5.2 Authenticating streamed data with one-time signatures 610 14.6 From one-time signatures to many-time signatures 610 14.6.1 Indexed signatures 611 14.6.2 A many-time signature scheme from an indexed signature 612 14.6.3 The complete Merkle stateless signature system 614 14.6.4 Nonce-based Merkle signatures 616 14.7 A fun application: fair exchange of signatures 617 14.8 Notes 617 14.9 Exercises 618 15 Elliptic curve cryptography and pairings 625 15.1 The group of points of an elliptic curve 625 15.2 Elliptic curves over finite fields 627 15.2.1 Montgomery and Edwards curves 628 15.3 Elliptic curve cryptography 629 15.3.1 The curve P256 630 15.3.2 Curve25519 631 15.4 Pairing based cryptography 632 15.5 Signature schemes from pairings 635 15.5.1 The BLS signature scheme 635 15.5.2 Signature aggregation 637 15.5.3 Secure BLS aggregation 640 15.5.4 Signature schemes secure without random oracles 645 15.6 Advanced encryption schemes from pairings 650 15.6.1 Identity based encryption 650 15.6.2 Related security notions 653 15.6.3 Identity based encryption from pairings 655 15.6.4 Applications 660 15.7 The functional encryption paradigm 664 15.7.1 Sample functional encryption schemes from pairings 668 15.7.2 Variations on functional encryption 672 15.8 Multilinear maps 673 15.9 A fun application: secret handshakes 675 15.10 Notes 675 15.11 Exercises 675 16 Post-quantum cryptography: lattices and isogenies 1 16.1 Integer lattices 1 16.2 Hard problems on lattices 1 16.2.1 The SIS problem 1 16.2.2 The learning with errors (LWE) problem 1 16.2.3 The ring LWE problem 1 16.3 Trapdoor sampling from a lattice 1 16.4 Signatures from lattice problems 1 16.5 Public-key encryption from lattices 1 16.6 Fully homomorphic encryption 1 16.7 Isogenies on elliptic curves 1 16.8 Key exchange from isogenies 1 16.9 A fun application: factoring integers using lattices 1 16.10 Notes 1 16.11 Exercises 1 17 Analysis of number theoretic assumptions 685 17.1 How reasonable are the factoring and RSA assumptions? 1 17.2 How reasonable are the DL and CDH assumptions? 1 17.2.1 Brute-force search 1 17.2.2 The baby-step/giant-step method 1 17.2.3 Groups of order qe 1 17.2.4 The Pohlig-Hellman algorithm 1 17.2.5 The Pohlig-Hellman algorithm 1 17.2.6 Information leakage 1 17.3 Discrete log in Zp* 1 17.3.1 The number field sieve 1 17.3.2 Discrete-log records in Zp* 1 17.4 How reasonable is decision Diffie-Hellman? 1 17.5 Quantum attacks on number theoretic problems 1 17.6 Side channel and fault attacks 1 17.7 Notes 1 17.8 Exercises 1 III Protocols 686 18 Protocols for identification and login 687 18.1 Interactive protocols: general notions 689 18.1.1 Mathematical details 690 18.2 ID protocols: definitions 690 18.3 Password protocols: security against direct attacks 691 18.3.1 Password cracking using a dictionary attack 692 18.4 Making dictionary attacks harder 696 18.4.1 Public salts 696 18.4.2 Secret salts 698 18.4.3 Slow hash functions 698 18.4.4 Slow memory-hard hash functions 700 18.4.5 More password management issues 704 18.5 One time passwords: security against eavesdropping 705 18.5.1 PRF-based one-time passwords: HOTP and TOTP 707 18.5.2 The S/key system 709 18.6 Challenge-response: security against active attacks 710 18.6.1 Challenge-response protocols 712 18.7 A fun application: rainbow tables 714 18.8 Another fun application: hardening password storage 718 18.9 Notes 718 18.10 Exercises 719 19 Identification and signatures from sigma protocols 727 19.1 Schnorr's identification protocol 727 19.1.1 Honest verifier zero knowledge and security against eavesdropping 732 19.2 From identification protocols to signatures 734 19.2.1 A useful abstraction: repeated impersonation attacks 735 19.2.2 Security analysis of Schnorr signatures 736 19.2.3 A concrete implementation and an optimization 741 19.3 Case study: ECDSA signatures 742 19.4 Sigma protocols: basic definitions 743 19.4.1 Knowledge soundness 745 19.4.2 Special honest verifier zero knowledge 746 19.5 Sigma protocols: examples 746 19.5.1 Okamoto's protocol for representations 747 19.5.2 The Chaum-Pedersen protocol for DH-triples 749 19.5.3 A Sigma protocol for arbitrary linear relations 750 19.5.4 A Sigma protocol for the pre-image of a homomorphism 751 19.5.5 A Sigma protocol for RSA 753 19.6 Identification and signatures from Sigma protocols 754 19.6.1 The Fiat-Shamir heuristic for signatures 756 19.7 Combining Sigma protocols: AND and OR proofs 759 19.7.1 The AND-proof construction 759 19.7.2 The OR-proof construction 760 19.8 Witness independence and applications 761 19.8.1 Definition of witness independence 761 19.8.2 Special HVZK implies witness independence 762 19.8.3 Actively secure identification protocols 764 19.8.4 Okamoto's identification protocol 766 19.9 A fun application: a two round witness independent protocol 767 19.10 Notes 767 19.11 Exercises 768 20 Proving properties in zero-knowledge 781 20.1 Languages and existential soundness 781 20.2 Proving properties on encrypted data 782 20.2.1 A generic protocol for non-linear relations 787 20.3 Non-interactive proof systems 789 20.3.1 Example: a voting protocol 789 20.3.2 Non-interactive proofs: basic syntax 791 20.3.3 The Fiat-Shamir transform 791 20.3.4 Non-interactive existential soundness 792 20.3.5 Non-interactive zero knowledge 792 20.4 Computational zero-knowledge and applications 794 20.4.1 Example: range proofs 795 20.4.2 Special computational HVZK 796 20.4.3 An unconstrained generic protocol for non-linear relations 797 20.5 Efficient multi-round protocols 798 20.6 Succinct non-interactive zero-knowledge proofs (SNARKs) 798 20.7 A fun application: everything that can be proved, can be proved in zero knowledge 798 20.8 Notes 798 20.9 Exercises 799 21 Authenticated Key Exchange 809 21.1 Identification and AKE 811 21.2 An encryption-based protocol 812 21.2.1 Insecure variations 815 21.2.2 Summary 820 21.3 Perfect forward secrecy and a protocol based on ephemeral encryption 821 21.3.1 Assuming only semantically secure encryption 823 21.4 HSM security 823 21.4.1 A technical requirement: strongly unpredictable ciphertexts 826 21.4.2 Insecure variations 826 21.5 Identity protection 830 21.6 One-sided authenticated key exchange 832 21.6.1 A one-sided authenticated variant of AKE4 833 21.7 Deniability 834 21.7.1 Deniability without identity protection 835 21.7.2 Deniability with identity protection 836 21.8 Channel bindings 838 21.9 Formal definitions 839 21.9.1 Understanding the definition 843 21.9.2 Security of protocol AKE1 844 21.9.3 Modeling perfect forward secrecy 845 21.9.4 Modeling HSM security 847 21.9.5 Modeling one-sided authentication 850 21.9.6 Modeling channel bindings 851 21.10 Case study: TLS session setup 851 21.10.1 Authenticated key exchange with preshared keys 854 21.11 Password authenticated key exchange 857 21.11.1 Phishing attacks 857 21.11.2 PAKE: an introduction 860 21.11.3 Protocol PAKE0 860 21.11.4 Protocol PAKE1 861 21.11.5 Protocol PAKE2 863 21.11.6 Protocol PAKE2+ 865 21.11.7 Explicit key confirmation 867 21.11.8 Phishing again 867 21.11.9 Case study: PAKE used in the WiFi WPA3 protocol 868 21.12 Key exchange using an online trusted third party 868 21.12.1 A key exchange protocol with an online TTP 868 21.12.2 Insecure variations of protocol OnlineTTP 870 21.12.3 Security for protocol OnlineTTP 874 21.13 A fun application: establishing Tor channels 875 21.14 Notes 875 21.15 Exercises 875 22 Secure multi-party computation 878 22.1 The basic idea of MPC 1 22.1.1 Informal notions of security 1 22.1.2 Assumptions 1 22.1.3 Formal notions of security 1 22.1.4 Other examples of MPC 1 22.2 Securely evaluating arithmetic circuits 1 22.2.1 Arithmetic circuit evaluation 1 22.2.2 Beaver's protocol: an honest-but-curious 2.5-party protocol 1 22.2.3 Abstracting Beaver's 2.5-party protocol 1 22.2.4 A maliciously secure version of Beaver's 2.5-party protocol 1 22.3 Garbled circuits: another approach to MPC 1 22.3.1 Boolean circuit evaluation 1 22.3.2 Garbling schemes: basic ideas 1 22.3.3 Garbling schemes: an application to outsourcing computation 1 22.3.4 A simple implementation of garbled gate encodings 1 22.3.5 A general garbling framework 1 22.3.6 A 2-party garbling-based protocol secure against honest-but-curious adversaries 1 22.3.7 A 3-party garbling-based protocol secure against malicious adversaries 1 22.4 Multi-party computation based on a secure distributed core 1 22.4.1 Processing inputs 1 22.4.2 Processing outputs 1 22.5 Formal models for multi-party computation 1 22.5.1 The real protocol and its execution 1 22.5.2 The ideal protocol and its execution 1 22.5.3 Example: the ideal functionality for secure circuit evaluation 1 22.5.4 Secure implementation: a strong security notion 1 22.5.5 Consequences of secure implementation 1 22.5.6 An example security proof: Beaver's 2.5-party protocol 1 22.5.7 An example security proof: multi-party computation based on a secure distributed core 1 22.5.8 An example security proof: the 3-party garbled circuit protocol 1 IV Appendices 879 A Basic number theory 880 A.1 Cyclic groups 880 A.2 Arithmetic modulo primes 880 A.2.1 Basic concepts 880 A.2.2 Structure of Zp* 881 A.2.3 Quadratic residues 881 A.2.4 Computing in Zp 882 A.2.5 Summary: arithmetic modulo primes 883 A.3 Arithmetic modulo composites 883 B Basic probability theory 885 B.1 The birthday Paradox 885 B.1.1 More collision bounds 887 B.1.2 A simple distinguisher 887 C Basic complexity theory 889 D Probabilistic algorithms 890 cryptography