# 隱私計算技術
## 1.簡介
隱私計算是一系列技術的統稱，主要目標是在**不暴露原始數據**的情況下，允許多方安全地計算數據的結果。這類技術在數據安全、機密計算、聯邦學習等領域具有廣泛應用。
## 2.同態加密
### 2-1.介紹
同態加密是一種加密方式，主要目的是可以對密文做計算，且己算出來的結果解密後是明文預期的計算結果
簡單來說，我們可以考慮兩個群G和H，兩個群中有自己的運算。所謂的同態加密，指的就是在G中的運算，藉由傳到Ｈ裡面的元素做運算
例如我們想在G中計算 $x \times y$ 因某些原因要到H做計算$f(x)\times f(y)$ 而H再把運算後的結果傳回G，G再用本身擁有的解密函數解密得到$x\times y$以上就是同態加密的流程
### 2-2.構造
構造一個同態加密是容易的
假設:兩個空間都是實數，運算是加法。令$f(x)=3x$則$f(x)$是一種加法的同態加密。
因為
$$f(x+y)=3(x+y)=f(x)+f(y)$$
### 2-3.問題
* 構造一個同態加密是容易，但如果一旦被知道加密方法，則有可能被回推出原本的明文，所以同態加密須具備一個特性**當沒有一些關鍵訊息時，經過加密的密文是很難回推明文的**。對此，密碼學會引入一些有共識某類型很難解的數學問題，而作者會留下特定的竅門，讓這個困難的問題變得好解，也就是所謂的解密函數。
* 此外，好的解密函數通常都帶有語意安全的特性
### 2-4.語意安全
密碼學正式定義語意安全為：
對於任何兩個明文 $m_0$ 和 $m_1$，如果攻擊者無法僅憑密文判斷哪一個是被加密的訊息，那麼這個加密系統就具有語意安全性。
### 2-5.全同態加密
#### 2-5-1.定義:
* 全同態加密可讓資料在加密狀態下進行**多種運算**

#### 2-5-2.應用:
- 可在**不洩漏資料**的前提下進行完整運算
- 適合應用於**醫療、金融、機器學習**等敏感資料領域
- 能實現**隱私保護的資料共享與合作計算**

#### 2-5-3.CKKS：支援近似計算的全同態加密
CKKS是一種**支援近似運算**的全同態加密方案，專門設計來處理**浮點數與機器學習**中的實數計算。不同於傳統FHE系統只支援整數運算，CKKS能讓你對加密後的實數做**加法與乘法**，且結果仍然接近正確。
#### 2-5-4.CKKS實作

#include<bits/stdc++.h>
#include<random>
#define endl '\n'
using namespace std;
class CKKS{
	private:
		long long public_key, private_key, modulus;
		double scale;
		mt19937 rng;
		uniform_int_distribution<int> dis;
	public:
		CKKS(double scale_factor = 1e4)
			: scale(scale_factor),
			  modulus((1ULL<<63)-1), //避免溢位
			  rng(random_device{}()),
			  dis(-10,10){}
		void keygen(){
			uniform_int_distribution<long long> dist(1e5, 1e6);
			private_key = dist(rng);
			public_key = private_key*3;
		} 
		long long encrypt(double value){
       		long long scaled = static_cast<long long>(round(value*scale));
        	int noise = dis(rng);
        	return (scaled*public_key+noise)%modulus;
    	}
    	double decrypt(long long ciphertext){
        	long long recovered = (ciphertext%private_key)%modulus;
        	return static_cast<double>(recovered) / scale;
    	}
    	long long add(long long ct1, long long ct2){
       		return (ct1+ct2)%modulus;
    	}
    	long long mul(long long ct1, long long ct2){
        	return (ct1*ct2)%modulus;
    	}
}; 

### 2-6.半同態加密
#### 2-6-1.定義:
* 半同態加密可讓資料在加密狀態下進行**單一運算**

#### 2-6-2.RSA上的應用:
RSA 擁有 **乘法同態** 的性質：

若：
- $E(m_1) = m_1^e \mod n$
- $E(m_2) = m_2^e \mod n$

則：
- $E(m_1) \cdot E(m_2) = (m_1 \cdot m_2)^e \mod n$

也就是：
- $E(m_1 \cdot m_2) = E(m_1) \cdot E(m_2)$

這表示我們可以在不解密的情況下，對密文做「乘法運算」。
#### 2-6-3.應用範例
- RSA 只能支援**乘法同態**，無法處理加法與混合邏輯。
- 若使用不當，容易造成資料洩漏或被惡意重放攻擊。

## 3.差分隱私
### 3-1.介紹
差分隱私是一種保護隱私的方式，其目的為:
* **讓你無法從統計結果中推測出某一筆特定資料是否存在**
### 3-2.滿足條件
$對任意兩個只相差一筆資料的資料庫 D \) 和 \( D' \)，以及任意一個查詢結果的集合 \( S \)，一個隨機化算法 \( \mathcal{A} \) 滿足 \( \varepsilon -差分隱私，若：$

$$
\Pr[\mathcal{A}(D) \in S] \leq e^{\varepsilon} \cdot \Pr[\mathcal{A}(D') \in S]
$$
| 符號 | 意義 |
|----------------------|------------------------------------------------------|
| $(D, D' )$ | 相差一筆資料的兩個資料庫 |
| $\mathcal{A}$ | 查詢演算法，會對結果加入隨機噪音 |
| $S$ | 查詢可能的結果集合 |
| $\varepsilon$ | 隱私強度參數，越小代表越安全（但準確率可能降低) |
### 3-3.差分隱私的可組合性與組隱私
差分隱私不只單次查詢有保障，它還能夠**組合**成更大的系統，這就是「可組合性」的強大之處。
#### 3-3-1.可組合性
##### 3-3-1-1.順序組合
如果你對同一筆資料做了多次查詢，每次查詢都是$\varepsilon$-差分隱私，那麼總體的隱私損失就是這些查詢的總和。
- 如果查詢 \( t \) 次，總損失為：
- 更一般的情況：若有 \( n \) 個查詢機制，分別滿足$\varepsilon_1, \varepsilon_2, ..., \varepsilon_n$-差分隱私，
則組合結果滿足：

$$
\varepsilon_{\text{total}} = \sum_{i=1}^{n} \varepsilon_i
$$
$$
\varepsilon_{\text{total}} = t \cdot \varepsilon
$$
##### 3-3-1-2.並列組合
* 如果每個差分隱私機制用在「不同的資料子集」上（彼此不重疊），
那麼總體隱私損失只取最大的那一個：

$$
\varepsilon_{\text{total}} = \max_{i} \varepsilon_i
$$
#### 3-3-2.穩健性
若一個機制$\mathcal{A}$ 滿足 $\varepsilon$-差分隱私，
那麼無論你對其輸出做任何後處理（例如再經過函數 $F$），
差分隱私仍然**保持成立**！
#### 3-3-3.組隱私
差分隱私原本是保護「一筆資料的變化」，
但也可以擴展為保護「最多 $c$ 筆資料」的情況。

若兩個資料庫 $D_1$ 和 $D_2$ 相差最多 $c$ 筆資料，
那麼差分隱私保證：

$$
\Pr[\mathcal{A}(D_1) \in S] \leq e^{\varepsilon \cdot c} \cdot \Pr[\mathcal{A}(D_2) \in S]
$$
簡單來說：

- 若每 $c$ 筆資料用一個 $\varepsilon$-差分隱私機制保護，
- 則對每 1 筆資料而言，該機制等同於 $\varepsilon / c$-差分隱私。
## 4.拉普拉斯噪聲
### 4-1.介紹
拉普拉斯噪聲是一種差分隱私技術，用於在數據上加入隨機噪聲，**使攻擊者難以識別個別數據**，從而保護隱私。這種噪聲來自於**拉普拉斯分佈**，具有對稱長尾的特性，適合應用於差分隱私場景。
### 4-2.拉普拉斯分布
拉普拉絲分布的機率密度函數(PDF)為:
$$P(x) = \frac{1}{2b} e^{-\frac{|x - \mu|}{b}}$$
其中:
* $\mu(均值):噪聲的中心，通常設為0$
* b(尺度參數):控制噪聲的擴散程度，與**隱私參數𝜖**相關
#### 4-2-1.拉普拉斯噪聲函數圖
### 4-3.產生拉普拉斯噪聲
在差分隱私中，給定查詢函數**f(x)**，我們希望在結果上加入噪聲:
* 計算靈敏度 $\Delta f$
靈敏度 $\Delta f$ 代表函數 $f$ 在兩個相鄰數據集 $D$ 和 $D'$ 上的最大變化量：
$$
\Delta f = \max \left| f(D) - f(D') \right|
$$

* 設定隱私參數 $\epsilon$
$\epsilon$ 是隱私參數，控制隱私與準確性的平衡（$\epsilon$ 越大，隱私保護越弱，但數據準確性越高）。

* 計算噪聲尺度 $b$
$$
b = \frac{\Delta f}{\epsilon}
$$

* 加入拉普拉斯噪聲
從拉普拉斯分佈 $Laplace(0, b)$ 生成噪聲 $L$，並加到函數輸出上：
$$
f'(x) = f(x) + L
$$
### 4-4.**拉普拉斯噪聲強度的影響**
在 **差分隱私（Differential Privacy）** 中，拉普拉斯噪聲的強度由 **噪聲尺度** $b$ 控制，而噪聲尺度又取決於 **靈敏度** $\Delta f$ 和 **隱私參數** $\epsilon$：

$$
b = \frac{\Delta f}{\epsilon}
$$
2. 噪聲強度與隱私性的關係
* 當 $\epsilon$ 小（噪聲大）
- 更強的隱私保護，攻擊者更難推測真實數據。
- 但數據的可用性下降，結果可能變得不夠準確。

* 當 $\epsilon$ 大（噪聲小）
- 數據結果較精確，但隱私保護較弱，可能較容易被攻擊。

3. 噪聲強度對數據分析的影響

* 過大噪聲（小 $\epsilon$）
- 影響數據的準確性，可能導致錯誤的決策或分析結果。
- 例如在 **統計數據發布** 時，如果噪聲過大，可能會影響政府或企業的決策。

* 適中噪聲（適中 $\epsilon$）
- 平衡隱私與數據可用性，讓數據分析結果仍具參考價值。

* 過小噪聲（大 $\epsilon$）
- 可能會洩漏敏感資訊，降低隱私保護效果。
### 4-5.問題
* 為甚麼是使用拉普拉絲分布而非高斯分布?

#### 4-5-1.噪聲分布不同
- **拉普拉斯分布**：
$$
p(x \mid b) = \frac{1}{2b} \exp\left(-\frac{|x|}{b}\right)
$$
- 對稱、尖峰明顯，尾部較重（「重尾分布」）

- **高斯分布**：
$$
\mathcal{N}(0, \sigma^2)
$$
- 鐘形曲線，尾部較輕，但允許極端值
#### 4-5-2.敏感度與噪聲大小的依賴

- **拉普拉斯機制**：
- 使用 **$L_1$ 敏感度** $\Delta f$
- 噪聲尺度：
$$
b = \frac{\Delta f}{\epsilon}
$$

- **高斯機制**：
- 使用 **$L_2$ 敏感度** $\Delta_2 f$
- 噪聲標準差：
$$
\sigma \geq \frac{c \cdot \Delta_2 f}{\epsilon}
$$
- 其中 $c$ 與 $\delta$ 有關
#### 4-5-3.隱私保證
- **拉普拉斯機制**：提供 **$(\epsilon, 0)$-差分隱私**
- **高斯機制**：只能提供 **$(\epsilon, \delta)$-差分隱私**，允許小機率洩露風險
#### 4-5-4.組合性與實用性

- 在多次機制應用下，高斯機制的 $(\epsilon, \delta)$ 組合保證與拉普拉斯的 $(\epsilon, 0)$ 差距不大（在 $\delta$ 很小的情況下）。
- 高斯噪聲總和仍為高斯分布，**數學性質更好**，在統計或高維應用中更方便。
#### 4-5-5.總結
- 若你需要 **嚴格的隱私保證**（如政府統計、保守設計），建議使用 **拉普拉斯機制**。
- 若在 **實務中允許微小風險**（如機器學習中的參數更新），或資料是高維，則可考慮 **高斯機制**。
## 5.應用
**(1) 隱私保護數據發布**
- **政府統計（如人口普查）**：加上噪聲以防止個別人的數據洩露。
- **企業分析（如平均薪資）**：確保單個員工的影響不被攻擊者識破。

**(2) 智慧手機與網路數據**
- Apple 和 Google 在用戶數據收集中使用拉普拉斯噪聲，確保數據匿名化。

**(3) 機器學習與 AI**
- **聯邦學習（Federated Learning）**：在梯度更新時添加噪聲，以防止洩漏用戶數據。
## 6.實作
### 6-1.流程圖:
其中，CKKS為一種同態加密方案，主要負責**同態運算**
### 6-2.實作程式碼:

import tenseal as ts
import numpy as np

context = ts.context(
    ts.SCHEME_TYPE.CKKS,
    poly_modulus_degree=8192, #加密強度參數，越大越安全（但效能越慢）
    coeff_mod_bit_sizes=[60,40,40,60] #每層加密的 bit 長度
)
context.global_scale = 2**40
context.generate_galois_keys()

#模擬用戶端
data = [170.0, 165.5, 180.2, 175.0]
enc_vector = ts.ckks_vector(context, data)

#計算
enc_sum = enc_vector.sum()
enc_mean = enc_sum * (1.0 / len(data))

#解密
decrypted_mean = enc_mean.decrypt()[0]
print(f"同態加密後解密的平均值：{decrypted_mean:.2f}")

#加入噪聲
epsilon = 1.0  # 隱私強度參數，越小越安全
sensitivity = 1.0  # 1 個人的最大影響程度

laplace_noise = np.random.laplace(loc=0, scale=sensitivity / epsilon)
dp_mean = decrypted_mean + laplace_noise

print(f"加入差分隱私後的平均值（DP）: {dp_mean:.2f}")

### 6-3.結果圖:
## 7.困難&解決
在進行隱私計算技術的學習與實作過程中，我遇到了兩大挑戰：
### 7-1.數學證明較為複雜
隱私計算中的許多**理論基礎**，例如差分隱私的形式化定義、全同態加密的安全性假設、噪聲分布對隱私保證的影響等，往往伴隨著嚴謹的數學推導與證明。由於我目前的數學背景尚未涵蓋這些抽象的代數與機率理論，因此**我選擇先從文字與概念理解出發，透過研讀文獻中對公式的直觀解釋與應用範例，來掌握每一個數學式背後所代表的意涵**。對於證明部分，我暫時擱置，並計畫在未來數學知識更加完整後，再回頭深入研究。

### 7-2.中文資料稀缺，需自行推敲與整合
隱私計算技術屬於新興領域，許多概念（如全同態加密與RSA的關聯、拉普拉斯分布與高斯分布的選擇差異）在**中文資料中較為罕見**，或解釋不夠深入。面對這樣的困難，我採取**主動出擊**的方式：將問題拆解後搜尋英文資料與技術文獻，**反覆閱讀並與自身的疑惑比對**，嘗試從中歸納出合邏輯的答案。這樣的過程不僅加深了我的理解，也幫助我建立起一套屬於自己的密碼學筆記，讓**抽象概念具體化**，便於後續整理與應用。
## 8.心得
隱私計算技術作為一門相對新穎的領域，起初在觀看介紹影片時，我認為它是一個結構清晰、概念直觀且容易實作的技術。然而，當我真正深入學習並試圖理解其背後的運作原理後，才發現它實際上融合了密碼學、機率統計、線性代數等多個跨領域知識，學習門檻遠比我原先想像的高。

在過程中，我一度因為同時接觸太多新概念而感到沮喪，甚至有放棄的念頭。但憑藉著對程式設計的熱情與不願半途而廢的堅持，我選擇繼續鑽研。在學習與實作的來回中，我逐漸將原本模糊的觀念釐清，最終也成功完成一個本地端的加密傳訊系統作為我的實作成果。當作品完成的那一刻，我對整個隱私計算技術的認識也更加清晰與完整。

這段經歷讓我深刻體會到：**學習新知識的最佳方式，就是動手為它設計一個專屬的實作專案，透過實踐來驗證自己對理論的掌握程度。** 這不僅讓我對隱私計算有了更全面的理解，也強化了我在面對跨領域挑戰時的自學與整合能力。
## 9.參考資料

- [同態加密與工程計算](https://zhuanlan.zhihu.com/p/550796916)
- [拉普拉斯分布與高斯分布的聯繫](https://zhuanlan.zhihu.com/p/665655933)
- [隱私強化技術應用指引](https://hackmd.io/@petworks/rJ-UOh9Rn/https%3A%2F%2Fhackmd.io%2F%40petworks%2FSyfD1A7_6)
- [簡析 FHE 全同態加密](https://web3caff.com/zh_tc/archives/92128)
- [差分隱私](https://zh.wikipedia.org/zh-tw/%E5%B7%AE%E5%88%86%E9%9A%90%E7%A7%81)