Abstract as per original application
(English/Chinese): |
This project will investigate distributed protocols that preserve security and privacy even when the participants or the communication network behave adversarially. We will consider various distributed settings, in which the common theme is to achieve security and privacy, while maintaining communication efficiency at the same time.
The most relaxed setting that we will consider is when all parties are honest, and the adversary can observe but not corrupt data. The massively parallel computation (MPC) model is proposed to capture parallel frameworks such as MapReduce and Hadoop that handle massive data. In this model, data needs to be distributed among many machines that can process their portions locally during each round, after which they can communicate with one another. Since communication between machines is often the bottleneck for performance, communication and round complexity are the metrics to be optimized in the MPC model. In addition to developing algorithms in the MPC model, a major goal is to investigate the notion of differentially oblivious MPC algorithms, whose communication patterns between machines do not reveal sensitive information about the input data.
Under the Byzantine model, each user can behave arbitrarily, which is often the case in smart contract and blockchain applications. In a distributed protocol, often users need to commit their data on the blockchain in some phase, before the next phase can proceed. As each phase can be modeled as one round of communication, the performance of such protocols is measured by their round complexity. Using our preliminary results on Byzantine agreement, each phase of such protocols can be modeled by our commit-reveal paradigm. Using cryptographic tools and concepts in game theory, we will consider protocols in which an honest player’s utility will not be harmed, even if all other players collude against that player.
In a noisy communication network, transmitted bits might be corrupted. The goal here is to design a correcting mechanism whose communication overhead degrades gracefully with respect to the corruption rate. In oblivious storage applications, the servers are honest but curious about the data stored on them by the clients. The additional challenge in these scenarios is that corrupted instructions from clients in previous rounds should not compromise data privacy in subsequent rounds.
In conclusion, this project will develop theoretical tools that bring insights on achieving both privacy and communication efficiency for distributed protocols, which have practical impacts on blockchain protocols and oblivious storage systems.
本課題將研究在參與者或通信網絡本身具有對抗性行為時仍能保證安全性與隱私性的分布式協議。我們將考慮多種分布式的情形，其中共同的核心目標是在保持通信效率的同時實現安全性和隱私性。條件最為寬鬆的一種情形是各通信方都是誠實的，而對手可以觀察到但不能破壞數據。人們提出大規模並行計算（massively parallel computation，MPC）模型以刻畫諸如MapReduce和Hadoop的處理大量數據的並行框架。在此模型中，數據需要在許多計算機之間分發，這些計算機可以在各輪通信間於本地處理各自的部分，然後彼此通信。由於機器之間的通信通常是性能的瓶頸，所以通信複雜度和輪次複雜度是MPC模型中要優化的指標。除了在MPC模型中設計算法外，我們的另一主要目標是研究差分無記憶的MPC算法這一概念，在這類算法中，機器之間的通信模式不會洩露有關輸入數據的敏感信息。在拜占庭模型下，每位用戶的行為可以是任意的；在智能合約和區塊鏈應用場景中通常是這種情況。在分布式協議中，用戶通常需要在某個階段將其數據提交到區塊鏈上，然後才能執行後續步驟。每個階段都可以被看作是一輪通信，因此協議的性能由其輪次複雜度來衡量。應用我們關於拜占庭協議的初步結果，此類協議的每個階段可以使用我們的提交展示範式來描述。使用密碼學工具和博弈論中的概念，我們將考慮那種即使除一位誠實玩家外的所有玩家串通起來與之對抗，該誠實玩家的利益也不會受到損害的協議。在含有噪聲的通信網絡中，傳輸的比特可能被損壞。我們的目標是設計一種糾錯機制，該機制的通信開銷隨損壞率的下降而適當降低。在無記憶存儲的應用中，服務器雖然誠實，但會希望獲取客戶端存儲在其上的數據。在該場景下的另一個難題則是在前幾輪中來自客戶端的被識破的指令不應損害後幾輪中的數據隱私。總之，本課題將開發理論工具，為在分布式協議上實現隱私性和通信效率提供深刻見解；這將對區塊鏈協議和無記憶存儲系統的實際應用產生深遠影響。
|
