什麼是MPC MPC 全稱 Multi-Party Computation，即多方計算，是解決某些問題的協議（或者說方案）的總稱。這些問題通常涉及多個參與方（party，例如多家公司），每個參與方持有一定的隱私數據（例如公司的財產），希望不公開這些數據，但又可以利用這些數據計算某一函數（例如求最大值：哪個公司財產最多），每個參與方獲得相應的計算結果（可能相同，可能不同）。 我們經常聽到"安全多方計算"或者"多方安全計算"，就是要求一個 MPC 的協議是安全的，安全性的基本要求：一是隱私性，即不能洩露任何一方的隱私數據；二是正確性，即保證計算的結果是正確的。此外，還有其他要求例如公平性、輸入的獨立性、保證輸出送達等。通常我們提到 MPC 就是指安全 MPC，顯然一個不安全的協議不會受到青睞。 MPC 能幹什麼 MPC 具有廣泛的實際應用潛力，從安全的統計分析，到更特定的領域，例如，電子政務，金融監管，生物醫學計算，在保護數據安全的同時，實現聯合數據分析、數據安全查詢、數據可信交換等。 接下來，我們通過一個"比武招親"故事介紹一下 MPC 的幾個例子及相關概念（再次聲明不傳播任何價值觀念！）。故事是這樣的，地主家有個漂亮女兒，到了適婚年齡，地主想要找一良婿，便貼出了招親告示。 百萬富翁問題：MPC 的經典問題 告示一經張貼，便引來了很多男士。地主設置第一關：考察各位男士的收入情況。當然這些男士並不會樂意去公開自己的收入，怎麼辦？借助MPC整數比較協議。在不洩漏隱私的情況下可以比較收入的高低。 這一問題最早是由計算機科學家、圖靈獎獲得者姚期智教授通過百萬富翁問題提出的：兩個百萬富翁和想知道他們誰更富有，但他們都不想讓對方知道自己財富的任何信息。在雙方都不公開財富信息的情況下，如何比較兩個人的財富多少，並給出可信證明。姚教授通過混淆電路（garbling circle）給出了一種解決辦法，近年來也有一些基於同態加密的方案提出，有興趣的讀者可以查閱相關資料。 最初百萬富翁問題可以看作是兩方計算，當擴展到多個富翁，就是我們經常聽到的拍賣問題。多個參與方分別出價，出價最高（或最低）者即為拍賣的獲勝者。 MPC 可以很好的解決這一問題，計算出最高（低）值，但不洩露其他出價。 隱私集合求交（Private Set Intersection，PSI） 回到比武招親的故事，地主給女兒招親，當然要找一個興趣愛好與女兒相投的男士。例如：禮、樂、射、禦、書、數，等等。如何在不洩露彼此興趣愛好的情況下，找出二人的共同愛好？這一問題可以通過 PSI 來解決。 PSI 是 MPC 的一個分支。 PSI是指，參與雙方在不洩露任何額外信息的情況下，得到雙方持有的隱私數據的交集。在這裡，額外的信息指的是除了雙方的數據交集以外的任何信息。 PSI 在現實場景中非常有用，比如在縱向聯邦學習（機器學習）中做數據對齊，或是在社交軟件中，通過通訊錄做好友發現，計算廣告的實際效果等。目前已有一些解決方案，例如利用不經意偽隨機函數（Oblivious Pseudorandom Function），參與方利用自己的數據計算函數值，然後公開函數值進行比對即可。 不經意傳輸（Oblivious Transfer，OT）：MPC的重要組件 通過前兩關，有一位候選人 Bob 挺到了最後，成為地主女婿的候選人。地主為 Bob 準備了兩份生辰八字，一份是地主自己的，一份是地主夫人的。地主只能給 Bob 看其中一份，但是 Bob 並不想洩露自己看了地主還是地主夫人的生辰八字 怎麼辦？可以藉助 OT 協議。 […]

Read more of this post