隨著對(duì)crypten與密碼學(xué)的了解，我們將逐漸深入學(xué)習(xí)相關(guān)知識(shí)。今天，我們將跟隨同態(tài)加密的發(fā)展歷程對(duì)相關(guān)算法進(jìn)行簡(jiǎn)單的收集整理?。

目錄

同態(tài)加密概念

RSA算法

ElGamal算法

ELGamal簽名算法

Paillier算法

BGN方案

Gentry 方案

BGV 方案

BFV 方案

GSW 方案

CKKS方案

---

同態(tài)加密概念

同態(tài)加密是基于數(shù)學(xué)難題與計(jì)算復(fù)雜性理論的密碼學(xué)技術(shù)。

它是指密文狀態(tài)下對(duì)加密信息進(jìn)行計(jì)算得到一個(gè)輸出，將這一輸出進(jìn)行解密，其結(jié)果與用同一方法處理未加密的明文信息計(jì)算得到的輸出結(jié)果是一致的。

同態(tài)加密分為半同態(tài)加密和全同態(tài)加密。其中：

半同態(tài)加密：允許在加密數(shù)據(jù)上執(zhí)行特定的算術(shù)運(yùn)算，加法或乘法。

全同態(tài)加密：支持對(duì)密文進(jìn)行任意形式的加法和乘法運(yùn)算。

半同態(tài)加密				全同態(tài)加密
乘法同態(tài)		加法同態(tài)	有限次數(shù)全同態(tài)	第一代	第二代	第二代	第三代	可實(shí)現(xiàn)浮點(diǎn)數(shù)近似計(jì)算，適合機(jī)器學(xué)習(xí)建模場(chǎng)景
RSA算法	ElGamal算法	Paillier算法	Boneh-Goh-Nissim方案	Gentry方案	BGV方案	BFV方案	GSW方案	CKKS方案

RSA算法

RSA算法是一種公鑰算法體制，即每一位用戶都有一對(duì)密鑰，一個(gè)是可以公開的，另一個(gè)則是秘密的，（分為加密密鑰Ka和解密密鑰Kd）。加密密鑰控制加密，解密密鑰控制解密，由計(jì)算復(fù)雜性原理保證加密鑰Ka不能通過計(jì)算推出解密鑰。這樣，就實(shí)現(xiàn)了即使將Ka公開也不會(huì)暴露Kd。

RSA算法描述：

1. 任意選取兩個(gè)不同的大素?cái)?shù)p和q（經(jīng)典值為1024位）計(jì)算乘積n=pq，z=（p-1）（q-1）；
2. 任意選取一個(gè)大整數(shù)e，滿足gcd（e，z）=1，即e和z互質(zhì)。整數(shù)e用作加密鑰。（注意：e的選取是很容易，例如，所有大于p和q的素?cái)?shù)都可用）
3. 確定解密鑰d。滿足（de）modz=1，即de=kz+1，（因此，若知道e和z，則很容易計(jì)算出d）
4. 公開整數(shù)n和e，秘密保存d。

加密算法(明文m，m為小于n的整數(shù)，加密為密文c)

c=m^emodn

解密算法(將密文c解密為明文m)

m=c^dmodn

代碼示例：

import randomdef fastExpMod(b, n, m):'''return : b^n mod m'''result = 1while n != 0:if (n & 1) == 1: ?# 按位與操作result = (result * b) % mb = (b * b) % mn = n >> 1 ?# 位數(shù)右移操作return resultdef Euclid(a, b):'''歐幾里得算法 ax + by = gcd(a,b)Return : [x , y , gcd(a,b)]'''X = [1, 0, a]Y = [0, 1, b]while Y[2] != 0:Q = X[2] // Y[2]NEW_Y = [i * Q for i in Y]T = list(map(lambda x: x[0] - x[1], zip(X, NEW_Y)))X = Y.copy()Y = T.copy()return Xdef fermatPrimeTest(m, k):'''費(fèi)馬素性檢驗(yàn)算法m : 給定整數(shù)k : 安全參數(shù)，重復(fù)K次'''if m % 2 == 0:return Falsefor i in range(k):a = random.randint(2, m - 2)g = Euclid(a, m)if g[2] == 1:r = fastExpMod(a, m - 1, m)if r == 1:continueelse:return Falseelse:return Falsereturn Truedef findPrime(lower, upper):'''return : 一個(gè)位于upper和lower之間的素?cái)?shù)'''while True:n = random.randint(lower, upper)if fermatPrimeTest(n, 6) == True:return ndef selectE(fn):'''fn : euler functionReturn : e'''while True:e = random.randint(1, fn)temp = Euclid(e, fn)if temp[2] == 1:return edef keyGenerate(lower, upper):'''給定兩個(gè)素?cái)?shù)p和q生成的區(qū)間return : e,n,d'''p = findPrime(lower, upper)q = findPrime(lower, upper)print("p:" + str(p) + " ??q:" + str(q))# print("q:"+str(q))n = p * qfn = (p - 1) * (q - 1)e = selectE(fn)temp = Euclid(e, fn) ?# 歐幾里得算法求逆元d = temp[0]if d < 0: ?# 由于e和fn互素故一定存在逆元d = d + fn ?# 保證d為正數(shù)return e, n, ddef Encryption_Decryption():e, n, d = keyGenerate(1000, 10000) ?# 密鑰生成# 更改keyGenerate函數(shù)的兩個(gè)參數(shù)，可以改變生成素?cái)?shù)的位數(shù)大小。print("public key (e,n):", end="")print("(" + str(e) + " ?, ?" + str(n) + ")\n")print("private key d: " + str(d) + "\n")m = random.randint(1, n) ?# m < n m為明文print("Plaintext: " + str(m))c = fastExpMod(m, e, n) ?# 加密 ?c為密文 m^e mod nprint("\nEncryption of PlainText: " + str(c))x = fastExpMod(c, d, n) ?# 解密 c^d mod nprint("\nDecryption of CipherText: " + str(x))if x == m:print("\nThe plaintext and ciphertext are the same.")if __name__ == "__main__":Encryption_Decryption()

運(yùn)行結(jié)果：

這段代碼通過生成RSA密鑰對(duì)，加密一個(gè)隨機(jī)生成的明文，然后解密密文，驗(yàn)證了加密和解密的正確性。具體步驟包括生成素?cái)?shù)、計(jì)算 n 和 ?(n)、選擇公鑰 e、計(jì)算私鑰 d、加密明文、解密密文，并最終驗(yàn)證解密后的明文與原始明文是否相同。

ElGamal算法

EIGamal密碼是除了RSA密碼之外最有代表性的公開密鑰密碼。

與RSA算法不同，RSA是基于因數(shù)分解的公鑰體制密碼，而EIGamal是建立在離散對(duì)數(shù)的困難問題上的一種公鑰體制密碼。

EIGamal算法描述

1. 選取一個(gè)素?cái)?shù)p，以及小于p的兩個(gè)隨機(jī)數(shù)g和x；
2. 計(jì)算y=g^xmodp；
3. 公鑰為（y，g，p），私鑰為x；

加密算法 M為明文

1. 選取一個(gè)與p-1互質(zhì)的整數(shù)k；
2. C1=g^kmodp
3. C2=y^kMmodp
4. (C1,C2)即為密文

解密算法

C2/C1^x modp=Mmodp

舉例：

取p=11, g=5, x=2

則 y = g^xmodp = 3

取 k 為 7， m為10

則C1 = g^kmodp = 3

C2 = y^k*m mod?p = 2

則C1^xmodp= 9

9在模11下的逆元為5

所以 C 2 /C 1^?x=2?5mod10 =10mod10，所以解密成功

示例代碼：

import random# 判斷一個(gè)數(shù)是否為素?cái)?shù)def is_prime(n):if n <= 1:return Falseif n <= 3:return Trueif n % 2 == 0 or n % 3 == 0:return Falsei = 5while i * i <= n:if n % i == 0 or n % (i + 2) == 0:return Falsei += 6return True# 生成一個(gè)隨機(jī)的素?cái)?shù)def generate_prime():while True:p = random.randint(100, 1000)if is_prime(p):return p# 生成一個(gè)原根def generate_generator(p):phi = p - 1factors = []for i in range(2, int(phi ** 0.5) + 1):if phi % i == 0:factors.append(i)while phi % i == 0:phi //= iif phi > 1:factors.append(phi)for g in range(2, p):is_generator = Truefor factor in factors:if pow(g, phi // factor, p) == 1:is_generator = Falsebreakif is_generator:return g# 生成ElGamal公私鑰對(duì)def generate_keys():p = generate_prime()g = generate_generator(p)a = random.randint(2, p - 1)h = pow(g, a, p)return (p, g, h, a)keys = generate_keys()print("公鑰：(p, g, h) =", keys[0], ",", keys[1], ",", keys[2])print("私鑰：a =", keys[3])

運(yùn)行結(jié)果：

這段代碼實(shí)現(xiàn)了 ElGamal 密碼體制的公私鑰對(duì)生成，包括生成隨機(jī)素?cái)?shù)、原根和計(jì)算公私鑰。生成的公鑰 (p, g, h) 和私鑰 a 可以用于后續(xù)的加密和解密操作。

ELGamal簽名算法

密鑰產(chǎn)生

確定一個(gè)大素?cái)?shù)p

取p的一個(gè)本原根g

在Zp域上選擇一個(gè)隨機(jī)數(shù)x

y = gxmodp

(y, g, p)為公鑰，x為私鑰

簽名算法

設(shè)待簽名的消息為m

取一個(gè)與p-1互質(zhì)的k

C1=gkmodp

C2=(H(m)-x*C1) * k-1mod(p-1)

輸出簽名(C1,C2)和消息m

代碼示例：

import randomfrom sympy import isprime, mod_inverse# 選擇一個(gè)素?cái)?shù)p和生成元gdef generate_prime_and_generator():while True:p = random.randint(2 ** 10, 2 ** 11) ?# p的范圍if isprime(p):breakwhile True:g = random.randint(2, p - 2)if pow(g, (p - 1), p) == 1:breakreturn p, g# 生成密鑰對(duì)def generate_key_pair(p, g):x = random.randint(2, p - 2)y = pow(g, x, p)return x, y# 簽署消息def sign_message(p, g, x, m):k = random.randint(1, p - 2)r = pow(g, k, p)s = (m - x * r) * mod_inverse(k, p - 1) % (p - 1)return (r, s)# 驗(yàn)證簽名def verify_signature(p, g, y, m, r, s):if not (0 < r < p and 0 < s < p - 1):return Falseleft = pow(y, r, p) * pow(r, s, p) % pright = pow(g, m, p)return left == right# 輸出簽名詳細(xì)過程def print_signature_process(p, g, x, m, r, s):print("--------------------簽名過程--------------------")print(f"簽名消息為: {m}")print(f"私鑰x為: {x}")print(f"隨機(jī)數(shù)k為: {k}")print(f"簽名結(jié)果r為: {r}")print(f"簽名結(jié)果s為: {s}")# 主程序if __name__ == "__main__":# 生成素?cái)?shù)和生成元p, g = generate_prime_and_generator()# Alice生成密鑰對(duì)x_alice, y_alice = generate_key_pair(p, g)# 輸出參數(shù)print("--------------------參數(shù)生成過程--------------------")print(f"素?cái)?shù)p為: {p}")print(f"生成元g為: {g}")print(f"Alice的公鑰y為: {y_alice}")# Alice簽署消息message = 20240301k = random.randint(1, p - 2)r, s = sign_message(p, g, x_alice, message)# 輸出簽名詳細(xì)過程print_signature_process(p, g, x_alice, message, r, s)# 用戶輸入簽名print("--------------------驗(yàn)證簽名過程--------------------")user_r = int(input("請(qǐng)輸入r的值: "))user_s = int(input("請(qǐng)輸入s的值: "))# 驗(yàn)證簽名if verify_signature(p, g, y_alice, message, user_r, user_s):print("簽名有效")else:print("簽名無效")

運(yùn)行結(jié)果：

這段代碼實(shí)現(xiàn)了 ElGamal 簽名方案的生成、簽署和驗(yàn)證過程。通過生成素?cái)?shù) p 和生成元 g，生成密鑰對(duì)，簽署消息，并驗(yàn)證簽名，確保了數(shù)字簽名的安全性和有效性。

Paillier算法

Paillier 同態(tài)加密算法是一種非對(duì)稱加密算法，該算法利用了數(shù)論中的復(fù)合剩余類的數(shù)學(xué)性質(zhì)。

Paillier算法描述

1.隨機(jī)選擇兩個(gè)大質(zhì)數(shù)p和q滿足gcd（pq,(p-1)(q-1)）=1。 這個(gè)屬性是保證兩個(gè)質(zhì)數(shù)長(zhǎng)度相等。

2.計(jì)算 n = pq和λ= lcm (p - 1,q-1)。

3.選擇隨機(jī)整數(shù)g（g屬于Z*n^2），使得滿足n整除g的階。

4.公鑰為（n，g）

5.私鑰為λ。

加密算法

m屬于Zn，r為[1,n-1]的隨機(jī)數(shù)，轉(zhuǎn)換成密文：

C=g^m·r^n modn^2;

解密算法

代碼示例：

from phe import paillierimport gmpy2 as gy# 生成 Paillier 密鑰對(duì)public_key, private_key = paillier.generate_paillier_keypair(n_length=128)print("n: ", public_key.n)print("g: ", public_key.g)print("p: ",private_key.p)print("q: ",private_key.q)a = 15b = 20print("a: ",a)print("b: ",b)# 加密 a 和 ba_enc = public_key.encrypt(a)print("a_enc: ",a_enc.ciphertext())b_enc = public_key.encrypt(b)print("b_enc: ",b_enc.ciphertext())print("同態(tài)加")print("a + b = ",a+b)c_enc = a_enc + b_encprint("c_enc = a_enc + b_enc: ",c_enc.ciphertext())c_dec = private_key.decrypt(c_enc)print("c_dec = a + b: ",c_dec)print("同態(tài)數(shù)乘")print("a * b = ",a*b)c1_enc = a * b_encprint("c1_enc = a * b_enc: ",c1_enc.ciphertext())c2_enc = b * a_encprint("c2_enc = b * a_enc: ",c2_enc.ciphertext())c1_dec = private_key.decrypt(c1_enc)c2_dec = private_key.decrypt(c2_enc)print("c1_dec = a * b: ",c1_dec)print("c2_dec = b * a: ",c2_dec)

運(yùn)行結(jié)果：

這段代碼展示了如何使用 Paillier 同態(tài)加密算法進(jìn)行基本的同態(tài)加法和數(shù)乘操作。Paillier 同態(tài)加密算法是一種加法同態(tài)加密算法，支持對(duì)密文的加法和數(shù)乘操作。

BGN方案

BGN是一種同態(tài)加密方案，是Bonel h等人在2005提出的一種具有全同態(tài)性質(zhì)的加密方案。和傳統(tǒng)的僅能支持單同態(tài)的elgamal和paillier加密方案不一樣，BGN能夠同時(shí)支持加同態(tài)和一次乘同態(tài)運(yùn)算。

1.選擇橢圓曲線和生成元：

2.選擇一個(gè)橢圓曲線 E?和一個(gè)生成元 P，使得 E?的階為 q，且 q?是一個(gè)大素?cái)?shù)。

3.選擇一個(gè)隨機(jī)的私鑰 s，范圍在 1?到 q?1?之間。

4.計(jì)算公鑰 Ppub=sP。

生成密鑰對(duì)：

公鑰：(E,P,Pp?ub)

私鑰：s

加密算法

選擇隨機(jī)數(shù)：

選擇一個(gè)隨機(jī)數(shù) r，范圍在 1?到 q?1?之間。

加密消息：

對(duì)于消息 m，計(jì)算密文 C：

C=(rP,rPp?ub+mP)

其中，C?是一個(gè)二元組，第一個(gè)元素是 rP，第二個(gè)元素是 rPp?ub+mP。解密算法

解密密文：

對(duì)于密文 C=(C1?,C2?)，計(jì)算：mP=C2??sC1?

由于 C1?=rP?和 C2?=rPp?ub+mP，可以推導(dǎo)出：

mP=(rPp?ub+mP)?s(rP)=r(sP)+mP?s(rP)=mP

通過橢圓曲線上的點(diǎn) mP?恢復(fù)消息 m。

?同態(tài)加法

同態(tài)加法：

對(duì)于兩個(gè)密文 C1?=(C11?,C12?)?和 C2?=(C21?,C22?)，計(jì)算：

C1?+C2?=(C11?+C21?,C12?+C22?)

解密結(jié)果為：

m1?+m2?=(C12?+C22?)?s(C11?+C21?)=(m1?P+m2?P)=(m1+m2)P

同態(tài)數(shù)乘

同態(tài)數(shù)乘：

對(duì)于一個(gè)密文 C=(C1?,C2?)?和一個(gè)標(biāo)量 k，計(jì)算：

kC=(kC1?,kC2?)

解密結(jié)果為：

km=k(C2??sC1?)=k(mP)=(km)P

代碼示例：

from ecdsa import NIST384p, SigningKey, VerifyingKeyfrom ecdsa.util import randrange_from_seed__trytryagainimport os# 生成密鑰對(duì)def generate_keys():sk = SigningKey.generate(curve=NIST384p)vk = sk.verifying_keyreturn sk, vk# 加密消息def encrypt(vk, m):# 生成一個(gè)在有效范圍內(nèi)的隨機(jī)數(shù) rr = randrange_from_seed__trytryagain(os.urandom(32), NIST384p.order)C1 = r * NIST384p.generatorC2 = (r * vk.pubkey.point) + (m * NIST384p.generator)return C1, C2# 解密消息def decrypt(sk, C1, C2):# 計(jì)算 -sC1neg_sC1 = -(sk.privkey.secret_multiplier * C1)# 計(jì)算 C2 + (-sC1)mP = C2 + neg_sC1# 通過橢圓曲線上的點(diǎn) mP 恢復(fù)消息 mm = mP.x() % NIST384p.orderreturn m# 同態(tài)加法def homomorphic_add(C1, C2, D1, D2):return C1 + D1, C2 + D2# 同態(tài)數(shù)乘def homomorphic_mul(C1, C2, k):return k * C1, k * C2# 主程序if __name__ == "__main__":# 生成密鑰對(duì)sk, vk = generate_keys()print("公鑰:", vk.to_string().hex())print("私鑰:", sk.to_string().hex())# 加密消息m1 = 15m2 = 20C1, C2 = encrypt(vk, m1)D1, D2 = encrypt(vk, m2)print("C1:", C1.x(), C1.y())print("C2:", C2.x(), C2.y())print("D1:", D1.x(), D1.y())print("D2:", D2.x(), D2.y())# 同態(tài)加法E1, E2 = homomorphic_add(C1, C2, D1, D2)m3 = decrypt(sk, E1, E2)print("同態(tài)加法結(jié)果:", m3)# 同態(tài)數(shù)乘k = 3F1, F2 = homomorphic_mul(C1, C2, k)m4 = decrypt(sk, F1, F2)print("同態(tài)數(shù)乘結(jié)果:", m4)

運(yùn)行結(jié)果：

BGN 同態(tài)加密方案通過橢圓曲線上的點(diǎn)運(yùn)算實(shí)現(xiàn)了對(duì)密文的加法和數(shù)乘操作。通過生成密鑰對(duì)、加密消息、解密消息、同態(tài)加法和同態(tài)數(shù)乘，可以實(shí)現(xiàn)對(duì)密文的高效計(jì)算。

Gentry 方案

提出者及背景：2009 年，由 Craig Gentry提出，這是全同態(tài)加密領(lǐng)域的重要突破，解決了自公鑰加密發(fā)明以來一直困擾科學(xué)家們的難題。

（在傳統(tǒng)加密中，數(shù)據(jù)一旦加密，就很難在密文狀態(tài)下進(jìn)行各種類型的計(jì)算。例如，對(duì)于常規(guī)的 RSA 或 AES 加密，加密后的數(shù)據(jù)只能進(jìn)行有限的操作，如存儲(chǔ)、傳輸?shù)?。而全同態(tài)加密允許在密文上直接進(jìn)行任意次數(shù)的加法和乘法等計(jì)算，并且解密后的結(jié)果與在明文上進(jìn)行相同計(jì)算再解密的結(jié)果相同。）

Gentry 方案之前，全同態(tài)加密的概念雖然被提出，但一直沒有有效的實(shí)現(xiàn)方式。Gentry 利用基于理想格的復(fù)雜數(shù)學(xué)結(jié)構(gòu)，設(shè)計(jì)出了首個(gè)可行的全同態(tài)加密方案。

核心原理：基于理想格的數(shù)學(xué)對(duì)象，利用 “雙盲” 設(shè)計(jì)，可以檢測(cè)加密漏洞并進(jìn)行修復(fù)，而不會(huì)造成信息泄露。

方案特點(diǎn)：最初的方案依賴矩陣和矢量進(jìn)行加密，計(jì)算復(fù)雜，實(shí)用性不強(qiáng)。但它為后續(xù)全同態(tài)加密方案的研究奠定了基礎(chǔ)，具有開創(chuàng)性意義。

局限性：隨著計(jì)算步驟的增加，連續(xù)加密的計(jì)算結(jié)果質(zhì)量下降，需要系統(tǒng)實(shí)現(xiàn)一定量的計(jì)算來進(jìn)行數(shù)據(jù)清理實(shí)現(xiàn)全同態(tài)，且計(jì)算復(fù)雜。

BGV 方案

提出者及背景：由 Brakerski、Gentry 和 Vaikuntanathan 提出，是第二代全同態(tài)加密方案中的重要代表。

核心原理：基于更弱的假設(shè)來提高性能和安全性，使用 LWE 或 RLWE 問題構(gòu)建一個(gè)基本的 GLWE 加密方案，再利用 “重線性化” 和 “維度縮減” 技術(shù)進(jìn)行改進(jìn)，還使用了 “模數(shù)切換” 技術(shù)來實(shí)現(xiàn)同態(tài)加法和同態(tài)乘法操作并有效減少計(jì)算復(fù)雜度和存儲(chǔ)需求。

方案特點(diǎn)：不需要 Gentry 的自舉過程，提供了基于 LWE 或 RLWE 問題的 FHE 方案選擇，在選擇適當(dāng)?shù)姆桨笗r(shí)具有更大靈活性，其安全性和效率都有一定的提升。

局限性：雖然避免了自舉過程，但在實(shí)際應(yīng)用中，對(duì)于大規(guī)模數(shù)據(jù)和復(fù)雜計(jì)算，其性能仍有待進(jìn)一步提高。

BFV 方案

提出者及背景：最初的 LWE 形式由 Brakerski 給出，后在此基礎(chǔ)上給出了更實(shí)用的 RLWE 形式，是第二代同態(tài)加密中的核心方案之一，微軟的全同態(tài)加密軟件 SEAL 最初就是實(shí)現(xiàn)的 BFV 方案。

核心原理：在明文空間的高 bit 位編碼信息，使用的編碼結(jié)構(gòu)，通過密鑰生成、加密、解密和同態(tài)運(yùn)算等算法來實(shí)現(xiàn)同態(tài)加密。

方案特點(diǎn)：同態(tài)加法相對(duì)簡(jiǎn)單，就是向量加法。同態(tài)乘法較為復(fù)雜，需要引入 “重線性化” 技術(shù)將乘法破壞的解密結(jié)構(gòu)恢復(fù)成線性結(jié)構(gòu)。

局限性：乘法運(yùn)算的復(fù)雜性導(dǎo)致其在處理復(fù)雜計(jì)算時(shí)效率可能較低，且重線性化過程可能會(huì)引入一定的誤差和計(jì)算開銷。

GSW 方案

提出者及背景：由 Gentry、Sahai 和 Waters 提出，是一種基于近似特征向量的全同態(tài)加密方案。

核心原理：利用近似特征向量的相關(guān)性質(zhì)，將加密、解密和同態(tài)運(yùn)算等操作與矩陣的運(yùn)算相結(jié)合，通過對(duì)密文進(jìn)行特定的矩陣變換來實(shí)現(xiàn)同態(tài)計(jì)算。

方案特點(diǎn)：同態(tài)運(yùn)算更加高效，為矩陣的加、乘運(yùn)算，且不會(huì)引起密文維度的膨脹，無需借助其他技術(shù)來控制密文維度的增長(zhǎng)，密文噪聲的控制更加簡(jiǎn)潔、有效。

局限性：不支持 SIMD 同態(tài)操作，自舉實(shí)現(xiàn)依賴的安全假設(shè)強(qiáng)度較第二代有所弱化，且困難問題的近似因子僅為維度 n 的多項(xiàng)式。

這些方案在同態(tài)加密領(lǐng)域的發(fā)展中逐代遞進(jìn)，從Gentry的首次證明FHE的存在性，到BGV、BFV和GSW方案的不斷優(yōu)化和簡(jiǎn)化，逐步提高了同態(tài)加密的效率和實(shí)用性。每個(gè)方案都在前一個(gè)方案的基礎(chǔ)上進(jìn)行了改進(jìn)，引入了新的技術(shù)和方法。

CKKS方案

CKKS方案是由Jung Hee Cheon、Kyoohyung Han、Duhyeong Kim、Moon Sung Lee和Yongsoo Song在2019年提出的一種同態(tài)加密方案。

它是第一個(gè)支持復(fù)數(shù)運(yùn)算的同態(tài)加密方案。這使得它在處理復(fù)數(shù)和多項(xiàng)式運(yùn)算時(shí)非常高效，特別適用于需要進(jìn)行復(fù)數(shù)運(yùn)算的應(yīng)用場(chǎng)景，如信號(hào)處理、圖像處理和機(jī)器學(xué)習(xí)。CKKS方案基于環(huán)上學(xué)習(xí)帶誤差問題（Ring-LWE），這是一種高效的構(gòu)造方法，減少了密文的大小和計(jì)算復(fù)雜度。同時(shí)，CKKS方案引入了多模數(shù)技術(shù)，支持在不同模數(shù)下進(jìn)行同態(tài)操作，提高了靈活性和效率。

算法步驟

1.選擇參數(shù)：

選擇一個(gè)合適的環(huán) R?和一個(gè)模數(shù) q。

選擇一個(gè)生成元 g?和一個(gè)隨機(jī)的私鑰 s。

2.生成公鑰：

計(jì)算公鑰 h=gsmodq。

生成密鑰對(duì) (h,s)。

加密算法

選擇一個(gè)隨機(jī)數(shù) r。

加密消息：

對(duì)于消息 m，計(jì)算密文 C：

C=(r·g,r·h+m)modq

解密算法

解密密文：

對(duì)于密文 C=(C1,C2)，計(jì)算：

m=C2??s·C1?modq

同態(tài)加法

同態(tài)加法：

對(duì)于兩個(gè)密文 C1?=(C11,C12) 和 C2?=(C21,C22)，計(jì)算：

C1?+C2?=(C11?+C21?,C12?+C22?)modq

同態(tài)數(shù)乘

同態(tài)數(shù)乘：

對(duì)于一個(gè)密文 C=(C1,C2) 和一個(gè)標(biāo)量 k，計(jì)算：

kC=(k·C1,k·C2)modq

代碼示例：

import tenseal as ts# 生成密鑰對(duì)def generate_keys():# 創(chuàng)建 CKKS 上下文context = ts.context(ts.SCHEME_TYPE.CKKS, poly_modulus_degree=8192, coeff_mod_bit_sizes=[60, 40, 40, 60])# 生成密鑰context.generate_galois_keys()context.global_scale = 2 ** 40return context# 加密消息def encrypt(context, message):# 創(chuàng)建張量tensor = ts.plain_tensor(message)# 加密張量encrypted_tensor = ts.ckks_tensor(context, tensor)return encrypted_tensor# 解密消息def decrypt(context, encrypted_tensor):# 解密張量decrypted_tensor = encrypted_tensor.decrypt()return decrypted_tensor# 同態(tài)加法def homomorphic_add(encrypted_tensor1, encrypted_tensor2):return encrypted_tensor1 + encrypted_tensor2# 同態(tài)數(shù)乘def homomorphic_mul(encrypted_tensor, scalar):return encrypted_tensor * scalar# 主程序if __name__ == "__main__":# 生成密鑰對(duì)context = generate_keys()print("密鑰生成完成")# 加密消息message1 = [1, 2, 3, 4]message2 = [5, 6, 7, 8]encrypted_tensor1 = encrypt(context, message1)encrypted_tensor2 = encrypt(context, message2)print("消息加密完成")# 同態(tài)加法encrypted_sum = homomorphic_add(encrypted_tensor1, encrypted_tensor2)decrypted_sum = decrypt(context, encrypted_sum)print("同態(tài)加法結(jié)果:", decrypted_sum.tolist())# 同態(tài)數(shù)乘scalar = 3encrypted_mul = homomorphic_mul(encrypted_tensor1, scalar)decrypted_mul = decrypt(context, encrypted_mul)print("同態(tài)數(shù)乘結(jié)果:", decrypted_mul.tolist())

運(yùn)行結(jié)果：

這段代碼實(shí)現(xiàn)了一個(gè)基于 CKKS 同態(tài)加密方案的示例，支持對(duì)密文的加法和數(shù)乘操作。通過生成密鑰對(duì)、加密消息、解密消息、同態(tài)加法和同態(tài)數(shù)乘，可以實(shí)現(xiàn)對(duì)密文的高效計(jì)算。

---

?本篇簡(jiǎn)單介紹了隨著同態(tài)加密的發(fā)展而產(chǎn)生的幾種同態(tài)加密算法，同態(tài)加密的發(fā)展是向著高效化、功能化的方向前進(jìn)的，其應(yīng)用前景十分廣闊。通過對(duì)同態(tài)加密的了解，我們一定能夠?qū)崿F(xiàn)更高效的技術(shù)。

本篇借鑒來源于Kimi 是一個(gè)有著超大“內(nèi)存”的智能助手，可以一口氣讀完二十萬字的小說，還會(huì)上網(wǎng)沖浪，快來跟他聊聊吧

同態(tài)加密技術(shù)概覽-CSDN博客?