# IT Security 2 (Ch13~Ch15)

## Chapter 13: Biometrics
### :cactus: Positive/ Negative Recognition
- :droplet: Positive recognition: **Authentication**
- 系統驗證是不是此人
- PIN, password, smart card...
> 是不是Bob?
- :droplet: Negative recognition: **Identification**
- 系統建立此人是否符合 (即使那個人否認)
- identifying criminals, social welfare double dippers
- PIN, password 在此不適合用
> 是誰?
### :cactus: Biometric System
- :droplet: 定義
- 蒐集biometric data
- extract a salient(顯著的) feature set
- 比較 database
- 執行 action
- :droplet: Inter/ Intra class variation
- biometric trait 通常不會百分之百相似
- 因為
- 使用者特徵改變
- 環境改變
- 使用者和機器互動方式不同
- :ice_cream: Intra-class variation
- 同個使用者的差異
- :ice_cream: Inter-class variation
- 不同使用者間的差異
- Useful features set 通常 Inter 越高 Intra 越低
- :droplet: Performance Measurement
- **False Accept Rate (FAR) = False Match Rate (FMR)**
- 不是本人卻被接受
- **False Reject Rate (FRR) = False Non-Match Rate (FNMR)**
- 是本人卻被拒絕
- **t:** threshold
- FAR 和 FRR 的取捨被 t 決定
- :droplet: Receiver Operating Characteristics
- biometric system 的正確性
- 根據 FAR 和 FRR 對於不同的 t
- :droplet: Doddington's zoo
- :sheep: **Sheep**
- match well
- low false accepts and false reject rates
- :goat: **Goats**
- high false reject rate
- :camel: **Lambs**
- high false match rate
- :wolf: **Wolves**
- good at impersonation
- :bulb: 如果可以**分類** data，每個data可以被用不同的方式處理
- :droplet: Failure to enroll rate
- 衡量為什麼使用者不能被enroll
- 失敗通常因為 system 拒絕 **poor quality inputs**
- 高失敗導致 **high quality inputs** 但要降低acceptance，使用者要repeat enrollment process
### :cactus: Characteristics
- :cake: Universality
- 每個個體都有的特徵
- :cake: Uniqueness
- 每個個體都不同
- :cake: Permanence
- 長期不變
- :cake: Measurability
- 可取得(acquirable)、可數位化(Digitizable)
- :cake: Performance
- 正確且用需要的資源符合應用限制
- :cake: Acceptability
- 個體願意提供
- :cake: Unfakeability (?)
- 不能偽裝成其他人
### :cactus: Vulnerabilities
- :volcano: Circumvention (規避)
- 攻擊者取得database資料並修改
- :volcano: Covert Acquisition
- 取得別的使用者的 biometric information
- :volcano: Collusion and Coercion (強迫)
- 聯合其他合法使用者
- :volcano: Denial of Service
- 拒絕合法的使用者
- 產生許多 noise 破壞系統
- :volcano: Repudiation
- 攻擊者可以說自己資料被偷了 (假裝使用者)
### :cactus: Risks for users
- :ferris_wheel: not secure
- 不用取得使用者授權就能得到
- :ferris_wheel: cannot be revoked
- 如果被惡意使用，無法撤回
- :ferris_wheel: secondary use
- 如果有第二個應用，則自己的identity可能被追蹤
### :cactus: Attacks
- :droplet: spoofing
- 假造 biometric sample
- 使通過
- 使不通過
- :droplet: sensors
- 調包或破壞sensors
- :droplet: segmentation
- 使系統只觀察到某特定 features
- :droplet: replay
- 攔截 output 再利用
- :droplet: malware-based attacks
- 調包extractor
- :droplet: attacks against feature extraction
- 如果攻擊者知道algorithm，可以偽造假的features
- :droplet: attacks against quality control
- 用 **lamb** 污染 template data set
- 以降低 threshold
- :droplet: data storage
- template 需要加密
- 不能 insert 假的資料
- 不能 unauthorized 刪除
- :droplet: availability of templates in plaintext
- 通常需要 plaintext access
- 與傳統 passwords 的 salted 和 hashed 不同
### :cactus: Spoof Detection
- :droplet: Fingerprints
- 用膠假造
- 偵測：
- 汗 (persiration)
- 手的反光度 (reflection)
- 溫度
- 脈搏 (pulse)
- :droplet: Irises
- 圖片
- contact lens
- 3D
- 偵測：
- reaction to light
- blink/ move eyes
- :droplet: Face
- 圖片
- 保障：
- 給反應
- blink/ move

## Chapter 14: Secure Multi-Party-Computation (SMPC)
### :cactus: Goal
- Traditional
- trust
- insecure channel
- Multi-party computation
- do **NOT** trust
- distributed
- private
### :cactus: Millionaire Problem
- :droplet: Problem
- if $i \geq j$ ?
- $\begin{cases}{y_A=y_B=1 \iff j \leq i} \\ {y_A=y_B=0 \iff j>i} \end{cases}$
- :droplet: Solution
- 假設 $1<i,j<10$
1. :boy: **B** 有 $j$ million
> 隨機選擇 $N$-bit 的 $x$
> 計算 $E_A(x)$
> 把 $E_A(x)-j+1$ 傳給 :girl: **A**
2. :girl: **A** 有 $i$ million
> 對於 $u=1,...,10$ 計算
> $y_u=D_A(E_A(x)-j+u)$
> > 若 $u=j$，則 $y_u=x$
>
> 隨機選則 $N/2$-bit 的質數 $p$
> 對於 $u=1,...,10$ 計算
> $z_u=y_u\text{ mod }p$
> > 若 $u=j$，$z_u=x\text{ mod }p$
>
> 把 $p,z_1,...z_i,z_{i}+1,...,z_{10}+1$ 傳給 :boy: **B**
> > 若 $z_u$ 的差沒有超過2
> > 重新選擇 $p$
> > 確保 $z_a+1 \neq z_b$

3. :boy: **B**
> 檢查第 $j$ 個值是否等於 $x\text{ mod }p$
> 如果是: $j \leq i$
> else: $j>i$
> 告訴 :girl: **A** 結果

*Note:*
$\begin{cases}
{\text{if }j\text{ in }(z_1,...,z_i),} \\
{\Rightarrow z_j=y_j=D_A(E_A(x))\text{ mod }p=x\text{ mod }p}\\
{\Rightarrow j^{\text{ th}}=x\text{ mod }p}\\
{\Rightarrow j \leq i} \\
{\text{other }z_u=y_u\text{ mod }p=D_A(E_A(x)-j+u)\text{ mod }p}\\
{\Rightarrow \text{unknown to B}} \\
{\text{if }j\text{ in }(z_{i+1}+1,...,z_{10}+1),} \\
{\Rightarrow z_{i+1}+1=y_{i+1}+1=D_A(E_A(x)-j+i+1)+1\text{ mod }p}\\
{\Rightarrow \text{unknown to B}} \\
\end{cases}$
可以是 random order，**B** 只要檢查 $x\text{ mod }p$ 是否在裡面

- :droplet: Leakage
- 定義
:girl: **A** 的回傳值 $w_u=\begin{cases}
{z_u \text{ , if }u\leq i} \\
{z_u+1 \text{ , if }u>i}
\end{cases}$
- 若存在 $u^*$ 使得 $w_{u^*},w_{u^*+1}$ 差**剛好 2**，且 $w_{u^*}<w_{u^*+1}$
則 :boy: **B** 可以知道 $i\neq u^*$
因為 $w_i<w_{i+1}$ 永遠不會差 2 :question:
### :cactus: Semi-honest & malicious
- :droplet: **Semi-honest** (honest-but-curious/ passive)
- follow protocol
- 但想知道更多 information
- :droplet: **Malicious**
- 違反protocol
- 使違反 unattractive
- 說謊
- 無法避免
### :cactus: Correctness & Security
- :droplet: **Correctness**
- 正確計算 function $f$
- 像有trusted third party一樣
- :droplet: **Security**
- 違反者不能得到更多訊息 (從input/ 結果得知)
- example
- 三人投票，一人說no，兩人說yes
- 則說no的會知道其他人說yes
- :droplet: Terms
- :watermelon: *Distance*
- 兩個在 set $X$ 中離散機率分佈 $A,B$ 的 Distance為
- $\frac{1}{2}\times \sum_x(|Pr(A=x)-Pr(B=x)|)$
- :watermelon: *Probability ensemble*
- ensemble $A_i, (i \in I)$ 是一個離散機率分佈的set
- :watermelon: *negligible*
- 一個函數 $f(n)$ 逐漸小於多項式 $p$ 的倒數
- for each $p(n),\ \exists\ m_p$ such that
$|f(n)|<\frac{1}{p(n)}, \forall n>m_p$
- :watermelon: *equal*
- ensembles $A_i, B_i$ are equal
- :watermelon: *statistically close*
- $\text{dist}(A_i,B_i)$ 對所有 $I$ 中的 $i$ 是 *negligible function*
- :watermelon: *computationally indistinguishable* $A_i\approx B_i$
- 對所有 probabilistic polynomial-time algorithm $D$
$|Pr(D(A_i)=1)-Pr(D(B_i)=1)|$ 對 $i$ 是 *negligible function*

### :cactus: SMC definition
- :droplet: First Attemp
- 計算 $f(X_A,X_B)$ 是安全的
- 如果有 **Simulator algorithm** $S_A, S_B$
- Correctness
- $(y_A,y_B)\approx f(x_A,x_B)$
- Security
- $\text{view}_A(\text{real protocol})\approx S_A(x_A,y_A)$
$\text{view}_B(\text{real protocol})\approx S_B(x_B,y_B)$
- corrupt party 的 view 可以由他的 input/output simulate
- 不能用在 randomized functionaility
- $f(b)$，其中 $b$ 是 random bit
- A 隨機選 random bit
- A 送 $b$ 給 B
- A 輸出 $b$
- 正確但 **insecure** 因為 B 不能知道任何訊息
- :droplet: 定義
- Security
- $\text{view}_A(\text{real protocol},y_B)\approx (S_A(x_A,y_A),y_B)$
$\text{view}_B(\text{real protocol},y_A)\approx (S_B(x_B,y_B),y_A)$
> 如果違反者的 view 跟 honest 的人的 output 相關
> simulator 可以 capture 此相關性

### :cactus: Homomorphic Encryption
- :droplet: Semantic Secure
- 實驗流程
1. $A$ 選擇一組 plaintext $(m_0,m_1)$
2. 隨機選擇 $b\in \{0,1\}$
計算 $c=E(m_b)$
傳給 $A$
3. $A$ 猜測 $b'\in \{0,1\}$
4. $\text{return}\begin{cases}
{1, \text{if }b'=b} \\
{0, \text{otherwise}}
\end{cases}$
- *semantic secure* $\iff$ 任何 polynomial-time 的 $A$，存在一個 *negligible function* $\mu$ 使得
$Pr[b=b']-\frac{1}{2} \leq \mu(n)$
> 需要 $E$ 是 *probabilistic*
- :droplet: Homomorphic Encryption
- plaintext $(\mathbb{P},+)$
- ciphertext $(\mathbb{C},\otimes)$
- $E: \mathbb{P}\rightarrow \mathbb{C}$
- *additively homomorphic*
- $E(m_1+m_2)=E(m_1)\otimes E(m_2)$
- fully homomorphic encryption
- additively and multiplicatively
- :droplet: Paillier
- public key: $(N,g)$
- $N$ is a RSA modulus
- $g\in\mathbb{Z}_{N^2}^*$
- plaintext $(\mathbb{Z}_N,+)$
- ciphertext $(\mathbb{Z}_{N^2}^*,\cdot)$
- $E(m,r)=g^mr^N\text{ mod }N^2$
- $r\in\mathbb{Z}_{N}^*$
- Homomorphic addition
- $E(m_1)+_hE(m_2):=E(m_1)\cdot E(m_2)=E(m_1+m_2)$
- Homomorphic scalarm multiplication
- $a\times_hE(m):=(E(m))^a=E(a\times m)\text{ for }a\in\mathbb{Z}\text{\\}\{0\}$
- Ciphertext blinding
- $Blind(E(m)):=E(m)+_hE(0)$
### :cactus: Private equality checking
- :droplet: Goal
- $B$ 和 $A$ 想要 $A$ 確認是否 $a=b$
- :droplet: Protocol
1. :girl: $A$
> 計算 $E(-a)$
2. :boy: $B$
> 選擇隨機數 $r$
> 計算 $E(b)$
> 計算 $E(b-a)$
> 計算 $E(r(b-a))$
> 計算 $E(r(b-a)+b)$
> > 皆用 additively homomorphic
3. :girl: $A$
> 解密 $E(r(b-a)+b)$
> 若為 $b==a$ ，則 $a=b$
> 反之為一隨機數

### :cactus: Private set intersection
- :droplet: Goal
- $B$ 和 $A$ 想要 $A$ 找出 $S_A\cap S_B$
- :droplet: Protocol
1. :girl: $A$
> 計算多項式 $f(X)=\Pi(X-a_i)(i=1,...,k)=X^k+a_{k-1}X^{k-1}+...+a_0$
> 計算 $E(a_i)$ 並傳給 $B$
2. :boy: $B$
> 選擇隨機數 $r_i (i=1,...,k)$
> 計算 $c_i=E(r_if(b_i)+b_i)$ 並傳給 $A$
> > $A$ 和 $B$ 的 set 個數相等為 $k$
3. :girl: $A$
> 解密 $E(r_if(b_i)+b_i)$
> 看哪個對應到自己的 $a_i$
> > $f(b_i)=0$ 如果 $b_i=a_j$

### :cactus: Binary Less-Than Protocol
- :droplet: Threshold Paillier
- Idea: split the private key
- 用 **Shamir's secret sharing**
- :droplet: Less than with shared output
- Goal: $A$ 知道 $o_A$，$B$ 知道 $o_B$
$o_A\oplus o_B$ 隱含 $b<b'$
(但 $A,B$ 都不知道 $b,b'$)
- Idea: $b<b' \iff b'(1-b)=1$
- Assumption:
$\pi_{Mult}(E(x),E(y))=E(x\cdot y)$
所有人可以知道結果但不能知道 $x,y$
- :droplet: Protocol
1. :girl: $A$ :boy: $B$
> input: $E(b),E(b')$
> 計算 $\pi_{Mult}(E(1-b),E(b'))=E(c)$
2. :boy: $B$
> $o_B\leftarrow_{rnd}\{0,1\}$
> $E(c'):=\begin{cases}{blind(E(c))\text{ , if }o_b=0}\\
{blind(E(1-c))\text{ , otherwise}}\end{cases}$
3. :girl: $A$ :boy: $B$
> 解密 $E(c')$
> 只有 :girl: $A$ 知道 $c'$
> :girl: 設 $o_A=c'$
> :girl: $A$ output $o_A$
> :boy: $B$ output $o_B$

## Chapter 15: E-Voting
### :cactus: Security of (E)-Voting
- :secret: was each vote **captured** correctly?
- :secret: was each vote **counted** correctly?
- :secret: Can the tally be independently verified?
- :secret: Is each vote anonymous
- :secret: Can anyone sell their vote?
- :secret: Can voters be coered(被要脅) to vote in a particular way?
- :droplet: 其他voting的優點
- :revolving_hearts: Optical scanners
- 避免miscounting
- :revolving_hearts: Direct recording electronic voting system
- 減少 voters' error
- 使 different disabilities 也可以投
- :revolving_hearts: Internet voting
- convenient
- disabilities

### :cactus: Three Ballot Voting
- paper based system 用電子計票
- :droplet: Goal
- **不用 cryptography** 但盡可能達到越多 security properties
> 因 cryptography 難理解，難被大家信任
- :droplet: basic idea
- 三張選票
- 不想要的候選人三張加總為1票
- 想要的候選人三張加總為2票
- 

- :droplet: operation
- 投票者可以拿一張的選票備份
- 檢查serial number
- fake vote可以有最多1/3的機率被檢查到(如果voters都有檢查備份)
- :droplet: weakness
- 需要trust裝置
- votes pattern 的選擇要夠random
- Usability 差: 即使MIT學生也覺得confused
- serial number 被禁止：不能 link 選票和人

### :cactus: Bingo Voting
- based on **trusted random number generator**
- 用 voting machine
- coercion(強迫) impossible
- cryptographic protocols
- :droplet: Commitment scheme
1. commitment
- commitment $c$ 由 message $m$ 計算而來
- 由 $c$ 不能得知 $m$
2. open/ unveil
- $m$ 和 random number 公布
- 每個人都可以 check $c$ 是 $m$ 的 commitment
- commitment 的性質
- **Hiding:** 由 $c$ 不能知道 $m$
- **Blinding:** 給定 $c$ 和 $m$，不能知道另一個 $m'\neq m$ 使得 commitment 為 $c$
- **Pedersen Commitments**
- 基於 discrete logarithm problem
- 要 commit $m$ 及 random number $r$
- $c=h^mg^r$
- binding property:
- 假設有 $m',r'$
- $c=h^{m'}g^{r'}$
- $log_g(h)=(r-r')(m-m')^{-1}\text{ mod }q$
- committing entity 知道 $log_g(h)$
- hiding property:
- $r$ random
- $g^r$ random
- $c=h^mg^r$ random
- 因此不能從 $c$ 知道 $m$
- **Masking**
- 新的 commitment
- 隨機一 $s$
- 計算 $c'=cg^s$
- $c'=h^mg^{r+s}$
- :droplet: Voting
- voter在機器前選擇自己的候選人
- 對那個候選人產生一組新的 random number
- 機器印出候選人和 random number 的 pair
- 其餘沒有被選到的候選人的 random number 為機器原本就產生的
- 檢查 receipt 中有被改過的 random number 就是自己選的候選人
- :droplet: Counting
- 公開沒有被選到的候選人的 Dummy-votes
- :droplet: Pederson commitments in Bingo Voting
- 證明只有 $L-1$ 組 dummy votes 被用
( $L$ 為候選人個數)
- 公布 $C=(P,r)$ 真正選擇的候選人
- 和 $L-1$ (list1) 的 commitment
- 用 **Mask** 產生 list2
- 再 **Mask** 一次產生 list3
- 擲銅板決定公布 list1 / list2 的關係或 list2 / list3 的關係
- :droplet: Problems
- 使用者要相信 cryptographic protocol
- implementation 可能會有非預期的漏洞 (需要 open source)

### :cactus: Scantegrity
- 
- :droplet: how it work?
- 用 human readible 和 machine readible serial number
- 得到 serial number 之後可以驗票
- 選票上的 letter 不能和候選人相關
- 公開後可以知道 serial number 和選擇的 letter
- sereal number: $1234$
- letter: $A$
- candidate: $Bob$