如何（以及為什么）亂碼您的電路

你在一個(gè)偏遠(yuǎn)的島嶼上遭遇海難，需要逃跑。其他幸存者之一發(fā)現(xiàn)了一個(gè)廢棄的簡易機(jī)場，里面有一架似乎仍處于工作狀態(tài)的小型飛機(jī)。不幸的是，您和其他幸存者的總重量可能會(huì)超過飛機(jī)的最大起飛重量W。.MAX.要確定嘗試起飛是否意味著生存或死亡的機(jī)會(huì)，您需要知道所有幸存者的總重量。

雖然這是緊急情況，但你不希望要求任何人向任何人透露他們的體重——甚至不要向你自己透露。您將如何確定幸存者的總體重，同時(shí)確保沒有人了解其他人的體重？

停頓片刻，考慮幸存者如何解決問題。請記住，沒有人可以了解其他人的體重。我們將很快介紹一個(gè)候選解決方案。

這是一類更廣泛的問題的示例：當(dāng)一組參與者對函數(shù)的輸入必須保持私有時(shí)，他們?nèi)绾斡?jì)算函數(shù)的輸出？

一個(gè)簡單的解決方案是將所有私有輸入提供給某個(gè)受信任的第三方（TTP），然后第三方將計(jì)算函數(shù)并將輸出分發(fā)給參與者。不幸的是，TTP 在現(xiàn)實(shí)世界中往往與數(shù)學(xué)世界中的幸存者（他們以前從未見過）一樣罕見。例如，如果患者記錄在某些集中機(jī)構(gòu)共享和匯總，則可以加速醫(yī)學(xué)研究，但HIPAA隱私保護(hù)要求記錄保持私密。

如果權(quán)重閾值函數(shù)的輸入不需要保持私密，我們可以很容易地用一張草稿紙解決問題。如果幸存者逃脫，他們可以繼續(xù)構(gòu)建一個(gè)實(shí)現(xiàn)權(quán)重閾值函數(shù)的電路：在輸入設(shè)定的權(quán)重和閾值時(shí)，輸出組合權(quán)重是否超過閾值。本博客將介紹亂碼電路，這是輸入必須保持私有情況的一般解決方案。

但首先，讓我們回到幸存者身上——他們需要一個(gè)簡單的解決方案，在偏遠(yuǎn)的島嶼上快速工作。

在他們可用的物資最少的情況下，幸存者提出了以下協(xié)議：

每個(gè)幸存者都會(huì)得到一張白紙，每個(gè)人都站成一圈。

你首先寫下一個(gè)隨機(jī)數(shù)R，它顯然比每個(gè)人的總權(quán)重大得多，然后將你的權(quán)重添加到R。你只用總和撕下那部分紙，把它交給你左邊的幸存者。

每個(gè)幸存者都增加了他們的體重W我到他們收到的數(shù)字，并僅將他們的權(quán)重添加到數(shù)字中的結(jié)果傳遞給下一個(gè)幸存者。

當(dāng)您從右側(cè)的幸存者那里收到最終數(shù)字時(shí)，您減去您最初選擇的隨機(jī)數(shù) R 以恢復(fù)所有幸存者的總權(quán)重 WTT。
值得慶幸的是，對于幸存者來說，WTT

審核編輯：郭婷