and OT-based protocols are proposed for multiplication triples generation in offline phase. The online phase is based on arithmetic secret sharing and division GC. Therefore, only linear operations are allowed in model training, and various approximations are done to nonlinear functions.
The Chameleon framework is another hybrid MPC framework based on ABY for neural network model inference [Demmler et al., 2015]. Arithmetic secret sharing is used to conduct linear operations, and GC as well as GMW [Goldreich et al., 1987] are used for nonlinear operations. Conversion protocols are also implemented to convert data representations among different protocols.
Privacy-preserving ID3 learning based on OT is addressed in Lindell and Pinkas [2002]. Shamir’s threshold secret sharing is used for secure model aggregation for PPML with security against both honest-but-curious and malicious adversaries [Bonawitz et al., 2017], where a group of clients do MPC to evaluate the average of their private input models, and disclose the average to the parameter server for model update. Recently, MPC-based approaches pursuing security against malicious corrupted majority has been studied. For example, linear regression and logistic regression training and evaluation with SPDZ is studied in Chen et al. [2019]. The authors in Damgård et al. [2019] embraces SPDZ2k [Cramer et al., 2018] for actively secure private ML against a dishonest majority. It implements decision tree and SVM evaluation algorithms.
2.4.2 HOMOMORPHIC ENCRYPTION
HE is generally considered as an alternative approach to MPC in PPML. HE can also be used to achieve MPC as discussed in Section 2.4.1. The concept of HE was proposed in 1978 by Rivest et al. [1978] as a solution to perform computation over ciphertext without decrypting the ciphertext. Since then, numerous attempts have been made by researchers all over the world to design such homomorphic schemes.
The encryption system proposed by Goldwasser and Micali [1982] was a provably secure encryption scheme that reached a remarkable level of safety. It allows an additive operation over ciphertext, but is able to encrypt only a single bit. Paillier [1999] proposed a provable security encryption system that also allows an additive operation over ciphertext in 1999. It has been widely used in various applications. A few years later, in 2005, Boneh et al. [2005] invented a system of provable security encryption, which allows unlimited number of additive operations and one multiplicative operation. Gentry made a breakthrough in 2009 and proposed the first HE scheme that supports both additive and multiplicative operations for unlimited number of times [Gentry, 2009].
Definition
An HE scheme H is an encryption scheme that allows certain algebraic operations to be carried out on the encrypted content, by applying an efficient operation to the corresponding ciphertext (without knowing the decryption key). An HE scheme H consists of a set of four functions:
where
- KeyGen: Key generation. A cryptographic generator g is taken as the input. For asymmetric HE, a pair of keys {pk, sk} = KeyGen(g) are generated, where pk is the public key for encryption of the plaintext and sk is the secret (private) key for decryption of the ciphertext. For symmetric HE, only a secret key sk = KeyGen(g) is generated.
- Enc: Encryption. For asymmetric HE, an encryption scheme takes the public key pk and the plaintext m as the input, and generates the ciphertext c = Encpk (m) as the output. For symmetric HE, an HE scheme takes the secret key sk and the plaintext m, and generates ciphertext c = Encsk(m).
- Dec: Decryption. For both symmetric and asymmetric HE, the secret key sk and the ciphertext c are taken as the input to produce the corresponding plaintext m = Decsk(c).
- Eval: Evaluation. The function Eval takes the ciphertext c and the public key pk (for asymmetric HE) as the input, and outputs a ciphertext corresponding to a functioned plaintext.
Let Encenk(·) denote the encryption function with enk as the encryption key. Let M denote the plaintext space and C denote the ciphertext space. A secure cryptosystem is called homomorphic if it satisfies the following condition:
for some operators ⨀M in M and ⨀C in C, where ← indicates the left-hand side term is equal to or can be directly computed from the right-hand side term without any intermediate decryption. In this book we denote homomorphic encryption operator as ⟦·⟧, and we overload the addition and multiplication operators over ciphertexts as follows.
• Addition: Decsk(⟦u⟧ ⨀C ⟦v⟧) = Decsk(⟦u + v⟧), where “⨀C” may represent multiplication of the ciphertexts (see, e.g., Paillier [1999]).
• Scalar multiplication: Decsk(⟦u⟧ ⨀C n) = Decsk(⟦u · n⟧), where “⨀C” may represent taking the power of n of the ciphertext (see, e.g., Paillier [1999]).
Categorization of HE Schemes
HE schemes can be categorized into three classes: Partially Homomorphic Encryption (PHE), Somewhat Homomorphic Encryption (SHE), and Fully Homomorphic Encryption (FHE). In general, for HE schemes, the computational complexity increases as the functionality grows. Here, we provide a brief introduction to different types of HE schemes. Interested readers can refer to Armknecht et al. [2015] and Acar et al. [2018] for more details regarding different classes of HE schemes.
Partially Homomorphic Encryption (PHE). For PHE, both (M, ⨀M) and (C, ⨀C) are groups. The operator ⨀C can be applied on ciphertexts for a unlimited number of times. PHE is a group homomorphism technique. Specifically, if ⨀M is addition operator, the scheme is additively homomorphic, and if ⨀M is a multiplication operator, we say that the scheme is multiplicative homomorphic. The references Rivest et al. [1978] and ElGamal [1985] represent two typical multiplicative HE schemes. Examples of additive HE schemes can be found in Goldwasser and Micali [1982] and Paillier [1999].
Somewhat Homomorphic Encryption (SHE). An HE scheme is called SHE if some operations (e.g., addition and multiplication) can be applied for only a limited number of times. Some literature also refer to the schemes supporting arbitrary operations while only some limited circuits (e.g., the branching programs [Ishai and Paskin, 2007], garbled circuit [Yao, 1982]) as SHE. Examples are BV [Brakerski and Vaikuntanathan, 2011], BGN [Boneh et al., 2005], and IP [Ishai and Paskin, 2007]. SHE schemes introduce noise for security. Each operation on the ciphertext increases the noise of the output ciphertext, and multiplication is the main technique for increasing noise. When the noise exceeds an upper bound, decryption cannot be conducted correctly. This is the reason why most SHE schemes require a limited number of times of applying the operations.
Fully Homomorphic Encryption (FHE). FHE schemes allow both additive and multiplicative operations with unlimited number of times over ciphertexts. It is worth noticing that additive and multiplicative operations are the only two operations needed to compute arbitrary functions. Consider A, B ∈ F2. The NAND gate can be constructed by 1 + A * B. Thanks to its functional completeness, the NAND gate can be used to construct any gate. Therefore, any functionality can be evaluated by FHE. There are four main families of
