Partially Homomorphic Encryption

Description

This monograph describes and implements partially homomorphic encryption functions using a unified notation. After introducing the appropriate mathematical background, the authors offer a systematic examination of the following known algorithms: Rivest-Shamir-Adleman; Goldwasser-Micali; ElGamal; Benaloh; Naccache-Stern; Okamoto-Uchiyama; Paillier; Damgaard-Jurik; Boneh-Goh-Nissim; and Sander-Young-Yung. Over recent years partially and fully homomorphic encryption algorithms have been proposed and researchers have addressed issues related to their formulation, arithmetic, efficiency and security. Formidable efficiency barriers remain, but we now have a variety of algorithms that can be applied to various private computation problems in healthcare, finance and national security, and studying these functions may help us to understand the difficulties ahead. The book is valuable for researchers and graduate students in Computer Science, Engineering, and Mathematics who are engaged with Cryptology. Preface Contents Chapter 1 Introduction Chapter 2 Mathematical Background 2.1 Number Theory 2.1.1 Divisibility and Factorization 2.1.2 Greatest Common Divisor (GCD) 2.1.3 Modular Arithmetic 2.1.4 Modular Exponentiation 2.1.5 Modular Inverse 2.1.6 Euler's Theorem 2.1.7 Carmichael's Theorem 2.1.8 Generators 2.1.9 Chinese Remainder Theorem 2.1.10 Quadratic Residues 2.1.11 Higher-Order Residues 2.1.12 Residue Classes 2.1.13 Random Number Generators 2.2 Group Theory 2.2.1 Basic Axioms 2.2.2 Multiplicative Groups 2.2.3 Additive Groups 2.2.4 Order of a Group 2.2.5 Cyclic Groups and Subgroups 2.2.6 Discrete Logarithm Problem 2.2.7 Diffie-Hellman Problem 2.2.8 Cosets and Lagrange's Theorem 2.2.9 Sylow's Theorem 2.2.10 Direct Products 2.2.11 Homomorphisms 2.3 Field Theory 2.4 Elliptic Curves 2.4.1 Group Law 2.4.2 Elliptic Curve Point Multiplication 2.4.3 Elliptic Curves over Finite Fields Chapter 3 Rivest-Shamir-Adleman Algorithm 3.1 Key Generation 3.2 Encryption 3.3 Decryption 3.4 Homomorphic Properties 3.5 Security 3.6 Example Chapter 4 Goldwasser-Micali Algorithm 4.1 Key Generation 4.2 Encryption 4.3 Decryption 4.4 Homomorphic Properties 4.5 Security 4.6 Example Chapter 5 ElGamal Algorithm 5.1 Multiplicatively Homomorphic ElGamal Algorithm 5.1.1 Key Generation 5.1.2 Encryption 5.1.3 Decryption 5.1.14 Homomorphic Properties 5.1.5 Security 5.1.6 Example 5.2 Additively Homomorphic ElGamal 5.2.1 Encryption 5.2.2 Decryption 5.2.3 Homomorphic Properties 5.3 The Elliptic Curve ElGamal Algorithm 5.3.1 Key Generation 5.3.2 Encryption 5.3.3 Decryption 5.3.4 Homomorphic Properties Chapter 6 Benaloh Algorithm 6.1 Key Generation 6.2 Encryption 6.3 Decryption 6.4 Homomorphic Properties 6.5 Security 6.6 Example Chapter 7 Naccache-Stern Algorithm 7.1 The Deterministic Version 7.1.1 Key Generation 7.1.2 Encryption 7.1.3 Decryption 7.1.4 Security 7.2 The Probabilistic Version 7.2.1 Key Generation 7.2.2 Encryption 7.2.3 Decryption 7.2.4 Homomorphic Properties 7.2.5 Security 7.2.6 Example Chapter 8 Okamoto-Uchiyama Algorithm 8.1 Key Generation 8.2 Encryption 8.3 Decryption 8.4 Homomorphic Properties 8.5 Security 8.6 Example Chapter 9 Paillier Algorithm 9.1 Key Generation 9.2 Encryption 9.3 Decryption 9.4 Homomorphic Properties 9.5 Security 9.6 Example Chapter 10 Damgård-Jurik Algorithm 10.1 Forming the Plaintext Space 10.2 Key Generation 10.3 Encryption 10.4 Decryption 10.5 Homomorphic Properties 10.6 Security 10.7 Example Chapter 11 Boneh-Goh-Nissim Algorithm 11.1 Key Generation 11.2 Encryption 11.3 Decryption 11.4 Homomorphic Properties 11.5 Security 11.6 Example Chapter 12 Sander-Young-Yung Algorithm 12.1 Key Generation 12.2 Encryption 12.3 Decryption 12.4 Homomorphic Properties 12.5 Security 12.6 Example References Further Reading Index