|
|
ENQUIRE PROJECT DETAILS BY GENERAL PUBLIC |
| Project Details |
| Funding Scheme : | General Research Fund | ||||||||||||||||||||||||
| Project Number : | 17201220 | ||||||||||||||||||||||||
| Project Title(English) : | Efficient and Private Distributed Protocols against Byzantine Nodes in Noisy Communication Networks | ||||||||||||||||||||||||
| Project Title(Chinese) : | 含噪通信網絡中抵抗拜占庭節點的高效私密分布式協議 | ||||||||||||||||||||||||
| Principal Investigator(English) : | Dr Chan, Hubert Tsz Hong | ||||||||||||||||||||||||
| Principal Investigator(Chinese) : | |||||||||||||||||||||||||
| Department : | School of Computing and Data Science | ||||||||||||||||||||||||
| Institution : | The University of Hong Kong | ||||||||||||||||||||||||
| E-mail Address : | hubert@cs.hku.hk | ||||||||||||||||||||||||
| Tel : | 28578461 | ||||||||||||||||||||||||
| Co - Investigator(s) : |
|
||||||||||||||||||||||||
| Panel : | Engineering | ||||||||||||||||||||||||
| Subject Area : | Computing Science & Information Technology | ||||||||||||||||||||||||
| Exercise Year : | 2020 / 21 | ||||||||||||||||||||||||
| Fund Approved : | 845,055 | ||||||||||||||||||||||||
| Project Status : | Completed | ||||||||||||||||||||||||
| Completion Date : | 30-6-2024 | ||||||||||||||||||||||||
| Project Objectives : |
|
||||||||||||||||||||||||
| 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算法這一概念，在這類算法中，機器之間的通信模式不會洩露有關輸入數據的敏感信息。在拜占庭模型下，每位用戶的行為可以是任意的；在智能合約和區塊鏈應用場景中通常是這種情況。在分布式協議中，用戶通常需要在某個階段將其數據提交到區塊鏈上，然後才能執行後續步驟。每個階段都可以被看作是一輪通信，因此協議的性能由其輪次複雜度來衡量。應用我們關於拜占庭協議的初步結果，此類協議的每個階段可以使用我們的提交展示範式來描述。使用密碼學工具和博弈論中的概念，我們將考慮那種即使除一位誠實玩家外的所有玩家串通起來與之對抗，該誠實玩家的利益也不會受到損害的協議。在含有噪聲的通信網絡中，傳輸的比特可能被損壞。我們的目標是設計一種糾錯機制，該機制的通信開銷隨損壞率的下降而適當降低。在無記憶存儲的應用中，服務器雖然誠實，但會希望獲取客戶端存儲在其上的數據。在該場景下的另一個難題則是在前幾輪中來自客戶端的被識破的指令不應損害後幾輪中的數據隱私。總之，本課題將開發理論工具，為在分布式協議上實現隱私性和通信效率提供深刻見解；這將對區塊鏈協議和無記憶存儲系統的實際應用產生深遠影響。 |
||||||||||||||||||||||||
| Realisation of objectives: | This project aimed to advance the state of the art in secure and efficient distributed computing through three main research objectives. These objectives were as follows: first, to develop communication-efficient algorithms under the Multi-Party Computation (MPC) model that maintain privacy, even with regard to the patterns of communication between parties; second, to design distributed protocols that are resilient to Byzantine faults and fair in terms of round complexity, such that honest participants are not disadvantaged even if all others collude; and third, to construct interactive coding protocols for noisy communication networks that degrade gracefully in performance and maintain privacy even in the presence of corrupted or lost messages. The following outlines how and to what extent these objectives have been accomplished. Objective 1: Privacy-Preserving Communication-Efficient Algorithms under MPC The first objective addressed a critical challenge in secure computation. While techniques like encryption and secure multi-party computation protect the values of data, they may still leak sensitive information through access patterns and communication behaviour. To mitigate this, our work focused on the concept of differential obliviousness, which is inspired by differential privacy but designed to protect access patterns. Our starting point was the database join operation, a foundational operation in data processing. We showed that by applying the notion of differential obliviousness, it is possible to construct join algorithms that achieve near-optimal performance specific to each instance, without falling back on worst-case padding used in traditional Oblivious RAM techniques. These findings were first presented at ITC 2021. We further extended the theory in subsequent work published in the Journal of the ACM in 2022, where we provided formal definitions and analysis of differentially oblivious algorithms across various tasks, including sorting and range queries. In addition to presenting efficient algorithms, we established lower bounds that clarify the limitations of this new framework. These results create a solid foundation for practical and privacy-preserving multi-party computation protocols. Extent of achievement: This objective has been fully achieved. We introduced a new privacy framework, provided both upper and lower bounds, and demonstrated the approach’s practical viability in key computational settings. Objective 2: Fair Distributed Byzantine Protocols with Small Round Complexity The second objective focused on achieving fairness in distributed systems where some participants may act maliciously. Specifically, our goal was to ensure that the utility of honest participants remains protected even if all other participants collude. We pursued this objective through two related lines of work. First, we studied the problem of opinion dynamics in networks, where an adversary aims to bias average opinions by selectively altering agents’ resistance to persuasion. This reflects real-world scenarios where agents may be more or less stubborn in accepting influence. We examined both unbudgeted and budgeted versions of the problem, including a variant with L1-budget constraints. We showed that optimizing opinion under the L1 constraint is computationally hard. These results, presented at COCOON 2021, help illuminate the potential for adversarial manipulation and suggest how systems might defend against it. Second, we turned to the problem of leader election in distributed systems, where fairness is essential. Traditional methods achieve fairness but require many rounds of communication. In CRYPTO 2021, we proposed a class of protocols that achieve approximate game-theoretic fairness in fewer rounds. Under standard cryptographic assumptions, we demonstrated that it is possible to obtain fairness guarantees similar to those of the standard tournament-tree approach using as few as logarithmic-logarithmic rounds. This significantly improves efficiency while retaining fairness. We also contributed to the broader understanding of Byzantine Agreement, a key problem in distributed systems. In our 2023 work published in Distributed Computation, we developed protocols with subquadratic communication complexity and expected constant rounds. These protocols are resilient to adaptive adversaries, as long as certain realistic limitations are in place, such as no after-the-fact message removal. These results directly support our goal of designing protocols that remain fair and efficient even under adverse conditions. Extent of achievement: This objective has been substantially achieved. We introduced new fairness concepts, improved round efficiency, and deepened understanding of how adversaries may manipulate distributed protocols. While complete protection from collusion remains theoretically challenging, our work represents significant progress in this direction. Objective 3: Multi-Party Coding Protocols in Noisy Networks with Privacy Preservation The third objective addressed the problem of designing protocols that continue to function and maintain privacy in the presence of noise or adversarial communication disruptions. These issues are particularly relevant to large-scale systems such as federated learning and blockchain networks. First, we revisited the design of Oblivious Parallel RAM systems. These systems ensure that data access patterns do not leak sensitive information, even when executed in parallel. Our work, presented at ITC 2021, improved the expected communication overhead from previous constructions and provided an alternative with deterministic guarantees. This advancement makes perfectly oblivious computation more efficient and feasible in practical settings. Second, we tackled vector mean estimation under local differential privacy, a fundamental problem in federated analytics. We proposed algorithms tailored for sparse data, where each user contributes a vector with relatively few non-zero entries. Our algorithms achieved optimal error rates while keeping communication efficient and preserving user privacy. These contributions are particularly valuable for scalable and private data analysis. Third, we explored robust consensus protocols for permissioned blockchains, where denial-of-service and network partition attacks pose serious threats. We introduced Eges, a new consensus protocol that uses a stealth committee approach to hide the identity of actual decision-makers. This method prevents attackers from targeting key nodes and allows the system to maintain performance even under attack. Though not a classical interactive coding protocol, Eges reflects similar principles by tolerating disruptions and degrading performance gracefully. Finally, we addressed clustering in dynamic and adversarial settings. Our algorithm for k-center clustering with outliers is designed to remain effective even when points are inserted or deleted arbitrarily. This setting mimics noisy communication environments where data may be incomplete, corrupted, or frequently changing. The algorithm maintains strong approximation guarantees and low amortized update cost, aligning with the goal of graceful degradation. Extent of achievement: This objective has been fully achieved. We developed several novel constructions that ensure protocol functionality and privacy in hostile environments, spanning theoretical and applied domains. In summary, the project has successfully met its stated goals. Objective 1 was fully accomplished through the development and analysis of differentially oblivious algorithms. Objective 2 was substantially fulfilled by designing efficient and fair Byzantine protocols and exploring adversarial influence in networks. Objective 3 was fully realized through the design of robust algorithms and protocols for noisy and adversarial communication settings. The work has been supported and enriched by collaborations with leading institutions, resulting in high-impact publications and broad contributions to secure distributed computing. | ||||||||||||||||||||||||
| Summary of objectives addressed: |
|
||||||||||||||||||||||||
| Research Outcome | |||||||||||||||||||||||||
| Major findings and research outcome: | This project produced several significant contributions at the intersection of secure computation, distributed systems, and privacy-preserving communication. One major finding is the development of the differentially oblivious (DO) framework, a new notion of privacy for algorithmic access patterns. Unlike traditional Oblivious RAM (ORAM), DO allows for efficient algorithms that offer meaningful privacy without worst-case overhead. Our work showed that key primitives, such as database joins, can achieve near-optimal performance while still protecting access patterns under differential obliviousness. This result was published in ITC 2021 ("Differentially Oblivious Database Joins") and extended in JACM 2022 ("Foundations of Differentially Oblivious Algorithms"), where we formally defined the DO model and proved tight upper and lower bounds for fundamental algorithmic tasks. In the context of fair distributed protocols, we advanced the theory of game-theoretically fair leader election. Our protocol achieves approximate fairness in as few as O(log log n) rounds, a significant improvement over classical logarithmic-round solutions. These results, published in CRYPTO 2021 ("Game-Theoretic Fairness Meets Multi-party Protocols"), are the first to show that strong fairness guarantees can be preserved even under majority collusion, while maintaining low round complexity. Additionally, we explored adversarial opinion dynamics. We demonstrated the NP-hardness of optimizing susceptibility parameters under L1 budget constraints, showing the computational limits of such adversarial strategies (COCOON 2021). Further work in ACM TKDD 2022 revealed that although the objective function is non-convex, local optima coincide with global optima, enabling efficient optimization algorithms for large-scale networks. In addressing noisy and adversarial communication environments, we presented improved constructions for perfectly oblivious parallel RAM (OPRAM). Our scheme, published in ITC 2021, achieves better asymptotic overheads in both expected and deterministic settings, making OPRAM more practical for real-world use. We also introduced Eges, a consensus protocol for permissioned blockchains resilient to denial-of-service and network partition attacks. Eges ensures robust consensus via stealth committees and maintains high performance under attack conditions (Performance Evaluation 2022). Finally, our work on fully dynamic k-center clustering with outliers provides the first constant bi-criteria approximation with low amortized update costs, even under adversarial insertions and deletions (Algorithmica 2024). Collectively, these outcomes contribute novel theory, efficient algorithms, and resilient system designs, advancing secure and fair distributed computing. | ||||||||||||||||||||||||
| Potential for further development of the research and the proposed course of action: |
The research outcomes from this project lay a strong foundation for further exploration in privacy-preserving and resilient distributed systems. One promising direction is to extend the differentially oblivious framework to broader classes of algorithms, including graph processing and streaming, where communication patterns can still leak information. This could lead to practical tools for secure data analytics in multi-party and cloud settings. Building on our work in game-theoretic fairness, future efforts will focus on real-world deployment of fair protocols in decentralized platforms, such as blockchain governance and federated learning, where strategic manipulation is a tangible risk. Integrating cryptographic fairness with incentives and auditability remains an open and impactful challenge. The resilience of consensus protocols under real-world network threats also warrants continued development. We aim to enhance the scalability and energy-efficiency of protocols like Eges, making them suitable for IoT and edge computing environments. Lastly, our clustering and opinion dynamics results suggest broader applications in robust machine learning, where adversarial robustness, efficiency, and fairness must coexist. The proposed course of action includes strengthening interdisciplinary collaborations and pursuing targeted prototypes to validate these methods in operational systems, such as secure data platforms and collaborative AI frameworks. | ||||||||||||||||||||||||
| Layman's Summary of Completion Report: | This research project aimed to enhance the security, fairness, and reliability of modern digital systems, particularly those involving multiple participants who may not all be trustworthy. In many computing environments today, sensitive data is processed and transmitted across multiple machines. Even when the data itself is encrypted, the patterns of communication can unintentionally reveal private information. Our research developed new methods to conceal these patterns, offering strong privacy protection with minimal performance cost. We also addressed the challenge of fairness in group decision-making, such as selecting a leader in a distributed system. We designed protocols that ensure honest participants are not disadvantaged, even if a majority of others attempt to cheat. These protocols are also efficient, requiring fewer communication steps than traditional methods. In addition, we created tools to maintain accurate results and system agreement even in the presence of network disruptions, attacks, or corrupted messages. This ensures that systems can function correctly and securely under real-world conditions. The outcomes of this project have broad relevance for technologies such as secure cloud computing, online collaboration, federated learning, and blockchain. They contribute to building digital infrastructure that protects individual privacy, promotes fairness, and remains robust against adversarial threats. | ||||||||||||||||||||||||
| Research Output | |||||||||||||||||||||||||
| Peer-reviewed journal publication(s) arising directly from this research project : (* denotes the corresponding author) |
|
||||||||||||||||||||||||
| Recognized international conference(s) in which paper(s) related to this research project was/were delivered : |
|
||||||||||||||||||||||||
| Other impact (e.g. award of patents or prizes, collaboration with other research institutions, technology transfer, etc.): |
|||||||||||||||||||||||||
| SCREEN ID: SCRRM00542 |