幾類同態(tài)加密方案的研究.pdf

1、雖然在有效的全同態(tài)加密方案的構(gòu)造上取得重大進(jìn)展,但是全同態(tài)加密的計(jì)算代價還是十分昂貴的。造成這種局面的主要原因是對加密數(shù)據(jù)的同態(tài)操作比對明文數(shù)據(jù)的操作需要更多的計(jì)算。本文致力于同態(tài)加密方案的構(gòu)造、方案效率的優(yōu)化和方案功能拓展等方面的研究,引入諸如密文進(jìn)化技術(shù),逐步定比特填充法,具有同態(tài)性質(zhì)的概率編碼等新技術(shù)在一定程度上解決這個問題。
　　本研究主要內(nèi)容包括：⑴設(shè)計(jì)了基于RLWE(Ring Learning With Errors)

2、問題的雙重批處理限層全同態(tài)加密方案。該方案允許雙重打包許多明文進(jìn)入到每一個密文中以實(shí)現(xiàn)單指令多數(shù)據(jù)型操作,從而有效地降低了密文的擴(kuò)展比。同時,也給出了一種有效的密文進(jìn)化技術(shù)。該技術(shù)使用給定的私鑰轉(zhuǎn)換陣就可以同態(tài)地對密文中的明文向量實(shí)現(xiàn)任意置換。⑵給出格上無證書加密方案。利用原像抽樣算法抽取部分私鑰并采用帶誤差的學(xué)習(xí)問題生成秘密值及公鑰來構(gòu)造格上無證書加密方案。在隨機(jī)預(yù)言模型下,借助可抵抗擁有詢問秘密值能力的兩類攻擊者,形式化地證明了該方

3、案在選擇明文和自適應(yīng)選擇身份攻擊下(甚至是量子的)是密文不可區(qū)分的。使用兩種不同的擴(kuò)大明文空間的方法來進(jìn)一步提高方案的效率。特別地,給出了逐步定比特填充法。它是一種由固定長度比特串去確定多個更長比特串的有效方法。該方法在構(gòu)建多比特?zé)o證書加密起到重要作用。⑶為降低密鑰尺寸,利用陷門抽樣算法在優(yōu)選的NTRU(Number Theory Research Unit)格上抽取部分私鑰并使用多項(xiàng)式環(huán)上帶誤差的學(xué)習(xí)問題計(jì)算公鑰等方法來構(gòu)造格上無證書

4、加密方案。它的安全性基于多項(xiàng)式環(huán)上帶誤差學(xué)習(xí)的判定問題和小多項(xiàng)式比判定問題這兩個困難問題假設(shè)。為獲取更高的效率,還提出一個無證書并行加密方案。該方案用中國剩余定理將擴(kuò)大后的明文空間分解為多個不同素理想之積來實(shí)現(xiàn)并行加密。它還用中國剩余定理分解加密運(yùn)算所在的多項(xiàng)式環(huán)獲取中國剩余基來優(yōu)化算法,使算法只涉及整數(shù)間運(yùn)算。⑷引入概率同態(tài)編碼新技術(shù)并基于帶誤差的學(xué)習(xí)問題構(gòu)造出一個無證書的限層全同態(tài)加密方案。該技術(shù)可方便地把一個待加密的消息轉(zhuǎn)化為環(huán)中

5、兩個元素。在無證書體制下,這兩個元素可以使用用戶的兩個公鑰分別加密。一旦同時知道這兩個元素就能恢復(fù)原來的消息。否則,由編碼的不確定性知,該消息可被完美隱藏。該方案借助Gentry等人提出的近似特征向量法以消除同態(tài)計(jì)算公鑰,從而構(gòu)造出真正意義上的無證書全同態(tài)加密方案。⑸給出關(guān)于Smart-Vercauteren所構(gòu)造的同態(tài)加密方案的幾個性質(zhì)。這些性質(zhì)不僅表明了私鑰可以由一個向量簡化為它的任一個分量,而且對每個i可以產(chǎn)生一個三元組(第i級簡

6、化明文空間,第i級簡化密文空間,第i級簡化私鑰)。在這個三元組所組成的序列中第i級簡化私鑰可以解密第i級簡化密文并且第i級簡化私鑰可由第i級代理密鑰有效地計(jì)算出來。同時,第i+1級代理私鑰可以利用第i級代理私鑰有效算出。反之,由第i+1級代理私鑰推導(dǎo)出第i級代理私鑰是不可行的(這種方向上的推導(dǎo)除了前幾步外)。利用上面的性質(zhì),給出一個簡單且密鑰和密文尺寸相對較短的分級加密方案。⑹提出一個加法同態(tài)的加密方案,它基于Smart-Vercaut