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.
Author(s): Çetin Kaya Koç; Funda Özdemir; Zeynep Ödemiş Özger
Edition: 1
Publisher: Springer
Year: 2021
Language: English
Pages: 146
Tags: Partially Homomorphic Encryption; Rivest-Shamir-Adleman; Goldwasser-Micali; ElGamal; Benaloh; Naccache-Stern; Okamoto-Uchiyama; Paillier; Damgaard-Jurik; Boneh-Goh-Nissim; Sander-Young-Yung; Cryptography;
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
