全同態(tài)加密算法概述

全同態(tài)加密算法概述全同態(tài)加密概述01全同態(tài)加密方案02格密碼03算法性能比較04Content目錄

01

全同態(tài)加密概述全同態(tài)加密全同態(tài)加密屬于密碼學(xué)領(lǐng)域。由于全同態(tài)加密支持無需解密，就能夠?qū)γ芪倪M(jìn)行任意計(jì)算，因此可以立竿見影的解決數(shù)據(jù)隱私安全問題，有很大的應(yīng)用需求。例如，在云環(huán)境下，用戶加密數(shù)據(jù)后存儲(chǔ)在云端，由于數(shù)據(jù)加密使得云端無法獲得數(shù)據(jù)的內(nèi)容，從而保證了數(shù)據(jù)的隱私。此外，由于是全同態(tài)加密，云端可以對(duì)密文數(shù)據(jù)進(jìn)行任意計(jì)算。總而言之，全同態(tài)加密不但通過加密保護(hù)了數(shù)據(jù)，而且沒有喪失計(jì)算性。02

全同態(tài)加密方案全同態(tài)加密方案全同態(tài)加密的概念早在1978年就提出，然后一找就是30多年過去了。當(dāng)然這30多年也沒閑著，30年間人們提出的方案隨后就被證明是不安全的。當(dāng)然在這30年間，人們也退而求其次，能做一次加法和一次乘法的也可以，例如c1c2+c3c4，即一個(gè)二次多項(xiàng)式。這樣的方案稱為BGN方案。當(dāng)然再退而求其次，就是只能做加法，或者只能做乘法，這種方案稱為單同態(tài)。例如，RSA就是乘法同態(tài)，Paillier就是加法同態(tài)。這些方案在有些地方大放異彩，盡管只能做一種同態(tài)計(jì)算。直到2009年，Gentry，一個(gè)斯坦福大學(xué)的博士生，基于理想格提出一個(gè)全同態(tài)加密方案。Gentry的全同態(tài)加密方案是基于理想格構(gòu)造的。03

格密碼格密碼說到這里，不得不說兩句格密碼。很多人只知道RSA,ECC，但是提起格密碼一臉的茫然與恐懼，覺得格密碼一定是一個(gè)很難理解的問題。事實(shí)上，恰好相反，所謂的格（Lattice）就是整系數(shù)基的線性組合構(gòu)成的點(diǎn)，通俗地說就是一個(gè)空間中的一些離散有規(guī)律的點(diǎn)。既然是離散的點(diǎn)，那么點(diǎn)之間一定有距離，距離產(chǎn)生美，從而產(chǎn)生了一些困難問題，例如：最短向量問題(SVP)。格密碼如果是一個(gè)二維平面，那么尋找在格上尋找最短向量問題是簡(jiǎn)單的，但是當(dāng)維數(shù)變大的時(shí)候，例如200多維，尋找格上的最短向量問題就變的異常困難，稱之為格上標(biāo)準(zhǔn)困難問題，是一個(gè)指數(shù)級(jí)的困難問題。你可以想象一下，當(dāng)你在迷宮里時(shí)（現(xiàn)實(shí)世界是3維的），找出口還不算很困難，但是當(dāng)在一個(gè)200多維的迷宮里時(shí)，困難程度立刻指數(shù)級(jí)上升。04

算法性能比較算法性能比較全同態(tài)加密算法的主要優(yōu)勢(shì)是可以針對(duì)密文進(jìn)行操作，仍然可以回復(fù)明文，因此，滿足用戶對(duì)云服務(wù)的基本要求。本文算法與2種全同態(tài)加密算法進(jìn)行比較（表1）：算法性能比較(1)理想格全同態(tài)加密算法：需要進(jìn)行矩陣運(yùn)算和向量模運(yùn)算（向量的加法和乘法），每加密一個(gè)比特都需要進(jìn)行矩陣和向量運(yùn)算（表示為連續(xù)性不好），公鑰擴(kuò)展O(n7)，每個(gè)Evaluate中計(jì)算門的計(jì)算量為O(n6)。(2)整數(shù)全同態(tài)加密算法：需要進(jìn)行整數(shù)模運(yùn)算，連續(xù)性好，Evaluate算法中輸入超過本身算法要求，就不會(huì)實(shí)現(xiàn)全同態(tài)的性質(zhì)，存在攻擊危險(xiǎn)。每個(gè)