[PDF] Fast Secure Matrix Multiplications over Ring-Based Homomorphic

View - Download Fast Secure Matrix Multiplications over Ring-Based Homomorphic

Previous PDF

Next PDF

Fast Secure Matrix Multiplications

over Ring-Based Homomorphic Encryption

Pradeep Kumar Mishra

1, Deevashwer Rathee2, Dung Hoang Duong3, and

Masaya Yasuda

4 1 Graduate School of Mathematics, Kyushu University,

744 Motooka Nishi-ku, Fukuoka 819-0395, Japan

p-mishra@math.kyushu-u.ac.jp

2Department of Computer Science and Engineering,

Indian Institute of Technology (BHU) Varanasi 221005, India. deevashwer.student.cse15@iitbhu.ac.in

3School of Computing and Information Technology, University of Wollongong,

Northelds Avenue, Wollongong NSW 2522, Australia.

hduong@uow.edu.au

4Institute of Mathematics for Industry, Kyushu University,

744 Motooka Nishi-ku, Fukuoka 819-0395, Japan

yasuda@imi.kyushu-u.ac.jp Abstract.Secure matrix computation is one of the most fundamen- tal and useful operations for statistical analysis and machine learning with protecting the condentiality of input data. Secure computation can be achieved by homomorphic encryption, supporting meaningful op- erations over encrypted data. HElib is a software library that implements the Brakerski-Gentry-Vaikuntanathan (BGV) homomorphic scheme, in which secure matrix-vector multiplication is proposed for operating ma- trices. Recently, Duong et al. (Tatra Mt. Publ. 2016) proposed a new method for secure single matrix multiplication over a ring-LWE-based scheme. In this paper, we generalize Duong et al.'s method for secure multiplematrix multiplications over the BGV scheme. We also imple- ment our method using HElib and show that our method is much faster than the matrix-vector multiplication in HElib for secure matrix multi- plications. Key words:Secure matrix multiplications, Leveled fully homomorphic encryption, Packing methods.

1 Introduction

Recent development of cloud computing allows users to easily outsource their data in the cloud. On the other hand, security and privacy concerns for stored data in the cloud have risen. An excellent solution for the issue is to store all the data in encrypted format and perform operations on encrypted data. Homomor- phic encryption can achieve the solution, and hence it has been expected as a powerful tool in cloud computing. The concept of homomorphic encryption was rst introduced by Rivest et al. in 1978 [25]. About 30 years later, the rst scheme offully homomorphic encryption (FHE)that supports arbitrary operations on encrypted data was constructed by Gentry [11]. After Gentry's pioneering work, a number of FHE schemes have been proposed and improved in both theory and practice. However, currently known FHE schemes are yet impractical for real applications. For example, it is reported in a recent work [7] that it takes 52 milliseconds forsingle gatebootstrapping to refresh the error in a ciphertext for unlimited operations. On the other hand, the Paillier scheme [24] and the BGN scheme [2] are practical, but their functionality is very limited. In recent years, somewhat homomorphic encryption (SHE), initially used as a building block for FHE construction, and its leveled improvement (calledleveled FHE) have at- tracted a lot of attention from various communities. Both SHE and leveled FHE can support only a limited number of additions and multiplications, but it is applicable in various scenarios with reasonable performance (e.g., see [23,13,29,

1,31,6]). In particular, since leveled FHE has slower growth of the error in a

ciphertext, it is more useful to evaluate a circuit of large depth. Matrix computation is one of the most basic and useful operations for var- ious applications, including statistical analysis, image processing and machine learning. In this paper, we focus on secure matrix multiplications (see Figure 1 below for an image of our goal). At present, ring-based leveled FHE schemes, such as BGV [4], FV [10], YASHE [3], and NTRU [19], are ecient and useful. BGV and FV schemes are based on the ring-LWE (learning with errors) as- sumption [21], and YASHE is a variant of NTRU. Costache and Smart [8] com- pared features of such schemes (see also [18] for a comparison), and showed that the BGV scheme is more ecient for large plaintext space than other schemes. Hence we useHElib[16] as a software library in our implementation of the BGV scheme. (Recently,HElibhas been improved for eciency [17].) For secure ma- trix computation, matrix-vector multiplication is proposed inHElib(see [15] for its manual). Recently, Lu et al. [20] slightly modied the matrix-vector multipli- cation for secure statistical analysis overHElib. As an individual work, Duong et al. [9] proposed ecient methods for securesinglematrix multiplication over ring-based SHE schemes. Later, Wang et al. [28] modied Duong et al.'s meth- ods for exible matrix computation, but their modication is much less ecient for matrices of larger size. Our ContributionsWe generalize Duong et al.'s methods [9] for securemul- tiplematrix multiplications over the BGV scheme usingR=Z[x]=(xn+ 1) as the base ring for a 2-power integern. Our method can be used over the other ring-based SHE schemes. For secure multiplication between two matricesAand B, a main ingredient of [9] is to packAandBinto two types of polynomial overR, and then encrypt the polynomials. The homomorphic property of the nativeplaintext space of the BGV scheme enables us to compute all the entries ofABover packed ciphertexts by homomorphic multiplication. Our new strat- egy for multiple matrix multiplicationsA1 A`is to propose three types of polynomial inRforA1A2,A3A`1, andA`. Specically, we pack 2 A

1by the rst transformation of [9], and

ip the columns ofA2and pack them using a method similar toA1to obtain the entries ofA1A2in polynomial format. We propose new transformation to pack the productA3 A`1 into polynomial format. In contrast, we make use of the second transformation of [9] forA`. But our method requires for us to take an appropriate jump for ex- ponents of the variablexof the polynomial ringRgreater than the total degree of polynomials overRcorresponding to the matricesA1;:::;A`1, in order to avoid overlapping the coecients of the decryption polynomial. Dierent from ours, the matrix-vector multiplication implemented inHElib makes use of the plaintextslotsof the BGV scheme, useful for SIMD (Single Instruction Multiple Data) operations (see [13] for a typical use). While the matrix-vector multiplication can only pack a row or column vector into a single ciphertext, ours can pack a matrix. Our method can also perform secure matrix multiplications by a few homomorphic multiplications over our packed cipher- texts. For a comparison of performance, we implement our method and compare with the matrix-vector multiplication overHElib. With our implementation re- sults, we also discuss advantages and limitations of our method. This is a fully revised paper of the conference paper [22]. Main dierences are as follows:

1. We complete a proof of our secure matrix multiplications among three ma-

trices (Theorem 2 below).

2. We also give a generalization of Duong et al.'s method forA1 A`

with`4 (Subsection 3.2 below).

3. While the BV scheme [5] is implemented in [22], we here implement the BGV

scheme overHElibfor our secure matrix multiplications. Furthermore, we compare performance results of our method and the matrix-vector multipli- cation overHElib(Section 4 below).

2 Preliminaries

HElib[16] is an open-sourceC++library that implements a variant of the ring- LWE-based BGV scheme [4], improved by Gentry, Halevi and Smart [12]. It includes the Smart-Vercauteren ciphertext packing [26], high-level procedures for data-movement and simple linear algebra, modulus and key switching operations, and bootstrapping. In this section, we review the BGV scheme implemented in

HElib.

2.1 The BGV Scheme

The BGV scheme is a leveled homomorphic encryption scheme based on ring- LWE. For a positive integerN, the scheme is dened over the ring

R=Z[x]=(N(x));

whereN(x) is theN-th cyclotomic polynomial of degree(N) (hereis the Euler's totient function). Every polynomial inRcan be represented as a vector 3 with coecients inZ(coecient representation). A distributionoverRis implemented inHElibfor error polynomials, drawing a random polynomial in Rwith every coecient chosen at random from a discrete Gaussian distribution with zero mean and variance2for a parameter(= 3:2 is default inHElib). For an odd primeq, denote by []qthe reduction moduloq, mapping an element of Rto the element ofRwith every coecient equal to the unique representative of its equivalence class moduloqin the interval (q=2;q=2]. For a prime or prime-powerp, we denote the ringRp=R=pR. Thenativeplaintext space of the BGV scheme, implemented inHElib, isRt for a prime-powert=pr(cf., see Subsection 2.3 below for plaintext slots). The scheme is parametrized by a sequence of decreasing moduli q

L> qL1>> q0(1)

for homomorphic evaluation. For every modulusqi, ani-th level ciphertext in the scheme is a vector inR2q i. A secret key inHElibis chosen as an element s2Rwith coecients inf0;1gand low Hamming weightH(e.g.,H=

64). Setsk= (1;s) as a secret key. For correct decryption, everyi-th level

ciphertextvi= (c0;c1)2R2q iof a plaintext2Rtshould satisfy that the \noise" polynomial [hsk;vii]qi= [c0c1s]qi2Rhas the form+t"for some \small" error"2R(i.e., all the coecients oft"2Rare considerably smaller thanqi). Then the decryption procedureDec(vi;sk) = [hsk;vii]qimodtcan recover the correct plaintext.

A public key is a pairpk= (a;b)2R2q

L, whereais uniformly sampled from

R qLandb= [as+te]qLis generated by samplingefrom the distribution. A \fresh" ciphertext (i.e., anL-th level ciphertext)vL=Enc(;pk) = (c0;c1)2 R 2q

Lof a plaintext2Rtis given by

(c

0=+bv+te0;

c

1=av+te1;

wherev2Ris a randomly chosen polynomial with coecients inf0;1g, and e

0;e12Rare chosen from. Since

c

0c1s=+bv+te0s(av+te1)

+t(ve+e0se1) modqL;(2) the noise polynomial ofvLsatises the requirement of correct decryption if large q Lis taken (note that every coecient ofve+e0se1is small). Otheri-th level ciphertexts, computed after homomorphic operations, are described below.

2.2 Homomorphic Operations and Noise Control

The noise polynomial of a ciphertext should be small for correct decryption. InHElib, the size of such noise is measured by thecanonical embedding norm (see [13, Appendix A]). Specically, everyi-th level ciphertext (c0;c1)2R2q iis 4 represented as ((c0;c1);i;), whereis an estimate on the noise magnitude in the ciphertext. For example, according to equation (2), an estimate for a fresh ciphertext is initialized by four parameters (N;t;;H) inHElib(see [14, Sub- section 3.1.4]). Givenc= ((c0;c1);i;) andc0= ((c00;c01);i0;0), homomorphic operations are dened as follows:

1.Homomorphic Addition: Ifi=i0, we add these two ciphertext vectors and

two noise estimates as c+c0= (([c0+c00]qi;[c1+c01]qi);i;+0): Ifi6=i0, we reduce the larger one modulo the smaller of the two moduli to bring them to the same level.

2.Homomorphic Multiplication: If needed, we bring the two ciphertexts to

the same level. Wheni=i0, we rst perform the tensor product ofc andc0as ((d0;d1;d2);i;0), where (d0;d1;d2) is the extended ciphertext (c0c00;c0c01+c00c1;c1c01)2R3q i:We then perform the \relinearlization/key- switching" operation [14, Subsection 3.1.4] to obtain acanonicalciphertext (c000;c001)2R2q iof the same plaintext, and estimate its noise magnitude00. As a result, homomorphic multiplication outputs the information cc0= ((c000;c001);i;00): The homomorphic correctness of the BGV scheme follows the ring structure of the plaintext spaceRt; For twoi-th level ciphertextscandc0of plaintexts and0, we have(Dec(c+c0;sk) =+0;

Dec(cc0;sk) =0;(3)

if thei-th level modulusqiis suciently large. In contrast, every homomor- phic operation grows the noise of a ciphertext, and it might fail to decrypt the ciphertext after a number of operations. In particular, homomorphic multiplica- tion grows the noise much larger than addition, and the noise grows only linearly with the number of multiplications. The \modulus-switching" operation takes as input ani-th level ciphertext to output an (i1)-th level ciphertext of the same plaintext, but it can reduce the noise size (see [14, Subsection 3.1.5]). InHElib, if one of the input ciphertexts for homomorphic multiplication have larger noises than a preset constant, the modulus-switching is performed before the multi- plication in order to avoid decryption failure. Namely, noises of ciphertexts are automatically controlled inHElib. Then we can ignore the noise magnitude and the level of a ciphertext in usingHElib.

2.3 Plaintext Slots of the BGV Scheme

Here we take a primepas the plaintext modulus for slots. TheN-th cyclotomic polynomial factors modulopintokirreducible factors asN(x)F1(x) 5 F

2(x) Fk(x) (modp) for somek2Z. Every polynomialFi(x)2Fp[x]

has degreed=(N)=k. Due to the ring-isomorphism R p'Fp[x]=(F1(x)) Fp[x]=(Fk(x));(4) any plaintext polynomial2Rpcan be identied as the vector (modFi(x))ki=1. Conversely, since every spaceFp[x]=(Fi(x)) is isomorphic to the extension eld F pd, we can handle any vectora= (a1;:::;ak)2Fk p das a plaintext (each entry is called a \slot"), and encrypt the vector asEnc(a;pk). By the isomorphism (4), for two ciphertextsc;c0of vectors (a1;:::;ak);(b1;:::;bk), it satises (Dec(c+c0;sk) = (a1+b1;:::;ak+bk);

Dec(cc0;sk) = (a1b1;:::;akbk):(5)

Namely, homomorphic addition (resp., multiplication) allows us to operate element- wise addition (resp., multiplication) over plaintext slots (cf., the homomorphic property (3) over the native plaintext spaceRt). Simply speaking, it enables SIMD operation over slots (see [13] for a typical use). Furthermore, procedures for data-movement such as rotation and shift over slots are implemented in

HElib.

2.4 Other Optimizations

We describe the following two optimizations implemented inHElib, which shall be used in our implementation.

1. Modulus Chain and Double-CRT Representation [14, Subsection 1.2]: For

the moduli chain (1), small primesp0;p1;:::;pLare chosen so thatN(x) factors modulopito linear terms for all 0iL. The`-th modulus in the chain is dened asq`=Q` j=0pjinHElib. For ecient arithmetic over ciphertexts, a polynomiala(x)2Rq`(in coecient representation) is represented as an (`+ 1)(N) matrixDoubleCRT`(a) (inevaluation representation), whose (i;j)-th entry is the evaluation ofa(x) atj-th root ofN(x) modulopi. Addition and multiplication inRq`is done entry-wise modulo the appropriate primespi. In the rest of description, we ignore the double CRT representation of polynomials lying in the ciphertext space and describe the scheme as if we were operating on polynomials directly.

2. Key Switching [14, Subsection 3.1.6]: The public key has key switching ma-

trices that transform a ciphertext decryptable by a secret keysk0into a ciphertext decryptable by another secret keysk. This transformation is used in multiplication and data-movement over slots (in particular, this is an op- timization in getting a canonical ciphertext).

3 Secure Matrix Multiplications

In this section, we review typical known methods for secure matrix multiplica- tions over ring-LWE based homomorphic encryption (see also Figure 1 for its 6 image). We also extend the method of Duong et al. [9] for securemultiplematrix multiplications. For simplicity, in this paper, we only handle square matrices of sizemwith positive integer entries.

3.1 Typical Known Methods

Matrix-Vector Multiplication inHElibTo perform secure matrix multi- plications, several methods for the matrix-vector multiplication over the BGV scheme are implemented inHElib. According to [15, Subsection 4.3], the method to put a matrix indiagonal orderis the best solution if the matrix is given to us in plaintext (cf., if a matrix is encrypted, expensive data movement techniques in HElibare required to change the representation of the matrix). LetA= (aij) be an integer square matrix of sizem, andv= (vi) a column vector of lengthm. We representAbymcolumn vectors in diagonal order asd1= (a1;1;a2;2;:::;am;m) and d i= (a1;i;a2;i+1;:::;ami+1;m;ami+2;1;;am;i1) for 2im. Then the productAvcan be computed asPm i=1di(vn i)2Zm, where (vni) is theitimes left-rotated vector ofvandabis the element-wise multiplication between two vectorsaandb. To evaluate this procedure over the BGV scheme, we encrypt vectorsdiandvencoded in slots asci=Enc(di;pk) andc=Enc(v;pk) (it requires at leastmslots). From the homomorphic property (5) over slots, a combination of homomorphic operations m X i=1c iRotatei1(c) outputs a ciphertext of the productAv, whereRotatej(c) is thejtimes left- rotated ciphertext ofc. This requires (m1) rotations and additions, andm multiplications. The hoisting technique mentioned in [17] can be used to make rotations more ecient when multiple rotations are to be performed on the same ciphertext. This matrix-vector multiplication can be applied to matrix multipli- cations. (Recently, Lu et al. [20] slightly modied the matrix-vector multipli- cation of [15, Section 4.3] for homomorphic evaluation of principal component analysis and linear regression.) Duong et al.'s Method for Single Matrix MultiplicationWhile the above method makes use of the homomorphic property (5) over slots, Duong et al. [9] use the property (3) over the native plaintext spaceRtof the BGV scheme (they in [9] implemented their method over the BV scheme [5], the origin of the BGV scheme without optimizations). For a 2-power integern, we here takeN= 2nas the parameter dening the base ringRof the BGV scheme. Then we haveN(x) =xn+ 1 and hence

R=Z[x]=(xn+ 1):

7 Fig.1.An image of secure matrix multiplicationABin the cloud LetAandBbe two square matrices of sizemwith positive integer entries. We pack each rowAi= (ai;0;:::;ai;m1) and columnBTj= (b0;j;:::;bm1;j) of matricesAandB, respectively, into polynomials ofRas follows:

8>>>><

>>>:pm (1)

2(Ai) :=m1X

u=0a i;uxu; pm (2)

2(BTj) :=mX

v=0b v;jxnv: Furthermore, dene the following two types of polynomial inRassociated to two matricesAandB:

8>>>><

>>>:Pol (1)quotesdbs_dbs47.pdfusesText_47

[PDF] multiplications des nombres relatifs

[PDF] multiplicité des critères pour rendre compte de la structure sociale

[PDF] Multiplié deux identités remarquables

[PDF] multiplier

[PDF] Multiplier des equations par (-1) et Diviser des equations par (-2)

[PDF] Multiplier des fractions

[PDF] multiplier des heures

[PDF] multiplier des nombres en écriture fractionnaire

[PDF] multiplier des nombres en écritures fractionnaires

[PDF] Multiplier des nombres positifs en écriture fractionnaire

[PDF] Multiplier des nombres positifs en écriture fractionnaire - 4eme

[PDF] Multiplier des nombres positifs en écriture fractionnaire - Maths

[PDF] multiplier deux fractions

[PDF] multiplier deux racines carrées identiques

[PDF] Multiplier et diviser des nombres relatifs en écriture fractionnaire