作者：Annchain
（本文一切著作權歸annchain技術團隊所有，未經許可，不得轉載。若需轉載請聯系頁尾二維碼。）
安全多方計算(Secure Multi-Party Computation，SMPC)一直是我們的重點研究内容，其相關理論和技術滿足了如隐私保護、區塊鍊、機器學習等諸多前沿領域的安全計算需求，其實踐化研究更是目前資訊技術發展的總體趨勢之一。接下來我們将開一個關于安全多方計算的專欄，介紹SMPC領域的相關基礎協定、研究現狀，并對其核心技術進行一些探讨，以抛磚引玉。本文是該專欄的首篇，将簡要地介紹姚期智先生在1986年所提的一個安全兩方計算的通用協定(以下稱“Yao’s兩方協定”)。
安全兩方計算
安全兩方計算是指兩個參與方，在保護各自秘密輸入的前提下，共同合作完成某個功能函數的計算任務，并最終得到各自正确的計算結果。安全兩方計算是多方計算的一種特例，其隻涉及兩個參與方。較之于多方計算，安全兩方計算模型相對簡單，比如其不存在多方計算場景的“不誠實的大多數”(dishonest majority)問題。現實世界中僅涉及兩個實體的應用場景很多，比如基因比對、人臉識别、音樂檢索等模式比對問題，安全兩方計算協定尤适用于這些具體場景的模組化分析。
安全兩方計算是安全計算領域裡的核心内容之一，它既是構造多方協定的基礎，也可直接運用于解決現實世界中實際問題。目前，安全兩方計算協定(甚至多方計算協定)的主流設計架構仍基于姚期智先生最早提出的基于混淆電路的兩方計算通用協定。
混淆電路(Garbled Circuits)
混淆電路是姚期智先生的安全兩方計算通用協定中的核心技術，用于構造加密版本的電路，以實作所有非電路輸出的線路上資訊不洩露，又稱為加密電路、亂碼電路。目前，混淆電路已發展成構造上層安全協定的密碼學工具，被廣泛加以研究，包括對電路的優化設計、在如水印、委托計算等諸多應用中的推廣、等等。
任一個多項式時間的功能函數
都存在一個與之對應的布爾電路
，可描述為電路
計算
。電路
由衆多的門電路(如或門、與門、非門等)連接配接組成，其門電路的輸入線路可以是函數
的輸入變量，也可以是其他門電路的輸出線路。
不失一般性，假設所連接配接的門電路均是二進一出的，記為門電路
，其兩個輸入線路分别為
，則其輸出線路值為
，該輸出線路值可能為下一個門電路的輸入。電路
的計算由輸入值确定的門電路開始，按照電路拓撲一層一層往下計算，最後總能在電路所有輸出線路上得到最終輸出結果。采用這種原始的計算方式，電路
上各線路的值均為明文形式的比特值或。
為了實作安全計算，姚期智先生提出了一種方法對電路計算過程中所有門電路上的計算值進行加密，即每一條線路
，随機選取兩個值
和
分别與比特值和一一對應，稱為混淆密鑰。顯然，若不知道混淆密鑰，觀察者并不能确定該線路上呈現的某一混淆值所對應的比特值，而僅能以的機率猜測正确。
對電路
的每一條線路都選取一對随機混淆密鑰，所構造的電路稱為混淆電路(Garbled Circuits)，記為
。接下來，為了解決
中各個門電路的計算問題，這裡使用了“雙重加密”方式，即對每個門電路，分别将兩輸入線路上的混淆值作為加密密鑰，加密這兩個輸入混淆值所對應的輸出混淆值，得出該門電路的“加密計算表”。
中所有門電路的“加密計算表”将形成
的混淆表。
以
為“或”門為例進行說明，假設其輸入線路
、輸出線路
上的随機混淆密鑰分别為
，
和
，由或門的真值表可求得其加密計算表如下：(其中
表示以
為密鑰對進行第一次加密，再以
為密鑰對所得中間結果進行第二次加密)。
由
的加密計算表可知，分别給定輸入線路上的混淆值後，将唯一确定該表中的一行，即通過兩次解密運算得到輸出線路上的混淆值，若該輸出值為下一個門電路的輸入，則下一個門電路也可進行的計算。這裡需注意的是加密計算表中各行應随機排序後存儲，否則将因位置而洩露門電路的輸入資訊。
根據混淆電路
的混淆表，在獲得每條輸入線路的混淆值後，可按電路的拓撲一層一層地解密，進而在一片混沌中完成整個電路的運算。另外，
在最終輸出的各個線路上，需要儲存各輸出線路上的随機混淆值與其對應真實值的映射關系，可稱為“輸出解密表”，否則由于混亂值的相同分布将難以解得最終的計算結果。
Yao’s兩方協定
姚期智先生在1986年提出了一個安全兩方計算的通用協定，本文稱為Yao’s兩方協定，該協定是基于混亂電路(Garbled Circuits)和OT協定設計的，并被證明在半誠實敵手模型下是安全的。
現假設有兩個參與方
，各自擁有私有資料
，這兩個參與方希望在不洩露自己私有資料的前提下計算函數值
。Yao’s兩方協定的架構如下所述：
1. 将函數
轉化成其計算電路
；
2. 不失一般性，令
構造電路
的混淆電路
，并将
的混淆表(由所有門電路的加密計算表組成)發送給
；
3.
将自己的私有資料
轉化成
電路中相應輸入線路上的混淆值，并發給
；
4.
和
之間通過逐比特執行二選一的茫然傳輸協定(1-out-of-2 oblivious transfer)，即
提供
電路中
私有資料
所對應輸入線路的混淆密鑰對，經過多次茫然傳輸協定後，
得到
所對應的混淆值；
5.
使用所得的所有輸入混淆值，正确計算
，得到最終結果
，并将結果告訴
。
結語
Yao’s兩方協定是SMPC設計的通用架構之一，之後許多研究以Yao’s協定為基礎進行優化改進，以設計高效的多方協定，适應現實世界中各類應用場景的特定需要。
此外，SMPC協定的設計架構還有很多，不同架構在安全性、效率、通信消耗等各方面有不同的權衡，各有千秋。比如，我們的安多方産品所采用并改進SPDZ協定架構，是基于秘密分享設計的，且在效率和通信消耗方面較優的一個SMPC協定。後續我們将陸續分享對上述所列技術點的探讨，敬請期待！
Annchain（衆安鍊）是由衆安科技和衆安-複旦區塊鍊與資訊安全聯合實驗室自主研發，國内首個基于DAG架構并支援智能合約的高性能通用區塊鍊平台。作為工信部指導的中國區塊鍊技術和産業發展論壇兩大開源項目之一，Annchain立足于中國，緻力于助力中國搶占區塊鍊全球話語權。
Annchain專注于易用、高效、安全和隐私等關鍵特性，兼具子產品化和高度可定制的特點。目前已在數十家生态夥伴的商業場景中落地，場景涵蓋農業溯源、珠寶溯源、資産通證化、公益、醫療資料共享、廣告分發平台等。開發者可基于Annchain高效建構适合自身的區塊鍊應用，期待更多夥伴加入我們一起探索新應用。
衆安科技
衆安資訊技術服務有限公司（簡稱“衆安科技”）成立于2016年11月2日，是由螞蟻金服、騰訊、中國平安發起設立的衆安保險旗下的全資科技子公司，專注于區塊鍊、人工智能、密碼學、物聯網等前沿技術研究。衆安科技彙聚了行業内的頂尖科研人才，其中區塊鍊團隊規模近200人，多數來自于各頂尖區塊鍊團隊。
衆安-複旦區塊鍊與資訊安全聯合實驗室
衆安-複旦區塊鍊與資訊安全聯合實驗室是國内首個高校與企業聯合組建的專一區塊鍊實驗室，專注于區塊鍊相關技術的底層理論研究。同時，實驗室聯合複旦大學、上海衆人資訊技術有限公司成立了上海區塊鍊工程研究中心。中心伴随建構長效的産學研用合作機制的同時，支撐開展增強的密碼學能力，高性能區塊鍊（如Annchain）等，為行業提供示範。
更多關于annchain：
www.annchain.io
Github: github.com/annchain
Twitter: https://twitter.com/Annchain007
Facebook: https://www.facebook.com/Annchain-295110641341258
TelegramGroup: t.me/Annchain
TelegramChannel: t.me/AnnchainChannel
掃碼備注昵稱+研發方向
加入annchain技術社群