[IT-Security-2] Secure Multi-Party-Computation (SMPC)

 Secure Multi-Party-Computation (SMPC)

Notes from RWTH Aachen University course 
“IT security 2” Wintersemester 2019/20
professor: Meyer, Ulrike Michaela

 Goal

• Traditional
  • trust
  • insecure channel
• Multi-party computation
  • do NOT trust
  • distributed
  • private

 Millionaire Problem

•  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}$

•  Solution

  • 假設 $1<i,j<10$

  1.  B 有 $j$ million

     隨機選擇 $N$-bit 的 $x$
     計算 $E_A(x)$
     把 $E_A(x)-j+1$ 傳給  A

  2.  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$ 傳給  B

     若 $z_u$ 的差沒有超過2
     重新選擇 $p$
     確保 $z_a+1 \neq z_b$

  3.  B

     檢查第 $j$ 個值是否等於 $x\text{ mod }p$
     如果是: $j \leq i$
     else: $j>i$
     告訴  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$ 是否在裡面

•  Leakage

  • 定義
     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}$
    則  B 可以知道 $i\neq u^*$
    因為 $w_i<w_{i+1}$ 永遠不會相差 2 

 Semi-honest & malicious

•  Semi-honest (honest-but-curious/ passive)
  • follow protocol
  • 但想知道更多 information
•  Malicious
  • 違反protocol
    • 使違反 unattractive
  • 說謊
    • 無法避免

 Correctness & Security

•  Correctness
  • 正確計算 function $f$
  • 像有trusted third party一樣

•  Security
  • 違反者不能得到更多訊息 (從input/ 結果得知)
  • example
    • 三人投票，一人說no，兩人說yes
    • 則說no的會知道其他人說yes
•  Terms
  •  Distance
    • 兩個在 set $X$ 中離散機率分佈 $A,B$ 的 Distance為
      • $\frac{1}{2}\times \sum_x(|Pr(A=x)-Pr(B=x)|)$
  •  Probability ensemble
    • ensemble $A_i, (i \in I)$ 是一個離散機率分佈的set
  •  negligible
    • 一個函數 $f(n)$ 逐漸小於多項式 $p$ 的倒數
    • for each $p(n),\ \exists\ m_p$ such that
      $|f(n)|<\frac{1}{p(n)}, \forall n>m_p$
  •  equal
    • ensembles $A_i, B_i$ are equal
  •  statistically close
    • $\text{dist}(A_i,B_i)$ 對所有 $I$ 中的 $i$ 是 negligible function
  •  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

 SMC definition

•  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 不能知道任何訊息
•  定義
  • 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 此相關性

 Homomorphic Encryption

•  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

•  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
•  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)$

 Private equality checking

•  Goal
  • $B$ 和 $A$ 想要 $A$ 確認是否 $a=b$
•  Protocol
  1.  $A$

     計算 $E(-a)$

  2.  $B$

     選擇隨機數 $r$
     計算 $E(b)$
     計算 $E(b-a)$
     計算 $E(r(b-a))$
     計算 $E(r(b-a)+b)$

     皆用 additively homomorphic

  3.  $A$

     解密 $E(r(b-a)+b)$
     若為 $b==a$ ，則 $a=b$
     反之為一隨機數

 Private set intersection

•  Goal
  • $B$ 和 $A$ 想要 $A$ 找出 $S_A\cap S_B$
•  Protocol
  1.  $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.  $B$

     選擇隨機數 $r_i (i=1,...,k)$
     計算 $c_i=E(r_if(b_i)+b_i)$ 並傳給 $A$

     $A$ 和 $B$ 的 set 個數相等為 $k$

  3.  $A$

     解密 $E(r_if(b_i)+b_i)$
     看哪個對應到自己的 $a_i$

     $f(b_i)=0$ 如果 $b_i=a_j$

 Binary Less-Than Protocol

•  Threshold Paillier
  • Idea: split the private key
  • 用 Shamir’s secret sharing
•  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$
•  Protocol
  1.  $A$  $B$

     input: $E(b),E(b')$
     計算 $\pi_{Mult}(E(1-b),E(b'))=E(c)$

  2.  $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.  $A$  $B$

     解密 $E(c')$
     只有  $A$ 知道 $c'$
      設 $o_A=c'$
      $A$ output $o_A$
      $B$ output $o_B$

Readings

Goldwasser: Multi-Party Computations: Past and Present

Yao: Protocols for Secure Computation

    § Contains the original Millionaires Problem description and a more general result on computing any integer-valued function on the integer-values from a bounded range

Even Goldreich Lemple: A randomized Protocol for Signing contracts 

    § Contain the description of the “One-out-of-two Oblivious Transfer”

Freedman: Efficient Private Matching and set intersection

    § Contains the private set intersection protocol (and other operations on

sets)

§ Cramer and Damgard: Multiparty Computation, an Introduction

§ Goldreich: Foudations of Cryptography, Volume 2, Chapter 7 (CS library)