[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

: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\)


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)

留言

張貼留言

這個網誌中的熱門文章