Project Details
Funding Scheme : General Research Fund
Project Number : 17200418
Project Title(English) : Private and I/O-Efficient Concurrent Data Structures and Parallel Algorithms 
Project Title(Chinese) : 隱私及輸入/輸出高效的並行數據結構與算法 
Principal Investigator(English) : Dr Chan, Hubert Tsz Hong 
Principal Investigator(Chinese) : 陳子康 
Department : Department of Computer Science
Institution : The University of Hong Kong
Co - Investigator(s) :
Panel : Engineering
Subject Area : Computing Science & Information Technology
Exercise Year : 2018 / 19
Fund Approved : 693,000
Project Status : On-going
Completion Date : 9-5-2022
Abstract as per original application
This project will explore the theoretical foundations and applications of private data structures and algorithms, whose goal is to prevent the leakage of sensitive information through the data access pattern, which cannot be obscured by just using encryption. We will extend existing private storage models to capture practical aspects such as concurrency and I/O (input/output)-efficiency. Since the design of modern architectures ubiquitously employs parallelism and memory hierarchy, our models will have impacts on real-world applications such as multi-core processors and outsourced cloud platforms. Moreover, we will develop more relaxed security notions to achieve tradeoffs between performance and privacy levels. The classical oblivious RAM (ORAM) proposed by Goldreich and Ostrovsky allows data to be accessed obliviously such that the access pattern does not leak any information other than the length of the operation sequence. Even though the performance of ORAM has been improved in the past decade, the model does not readily support parallel architectures. To rectify the situation, the oblivious parallel RAM (OPRAM) has been proposed in a recent TCC 2016 paper. In our preliminary results that will appear in the upcoming TCC 2017 and ASIACRYPT 2017, we have achieved OPRAMs whose performance matches the state-of-the-art ORAMs. Our preliminary results inspire us to go beyond OPRAMs and further investigate private concurrent data structures supporting multiple requests and their parallel implementations. Besides parallelism, memory hierarchy plays a major role in practice. Our preliminary results on I/O-efficient cache-agnostic oblivious sorting algorithms, which will appear in the upcoming SODA 2018, equip us with powerful techniques to further explore the I/O-efficiency of our private mechanisms. Furthermore, we will also explore new notions of privacy in storage schemes that allow users to balance between their privacy preference and performance guarantee. Specifically, our recently developed techniques enable us to tackle the following challenging areas: (1) Explore concurrency and parallelism in private data structures and algorithms. We will design some basic oblivious parallel algorithms as fundamental building blocks for storage schemes, and study the tradeoff between depth and total work. (2) Achieve I/O-efficiency for private mechanisms. For instance, we will consider cache-agnostic subroutines in our private schemes that can achieve optimal I/O-efficiency without explicitly knowing the parameters of the underlying architecture. (3) Study more general notions of security in storage schemes. Going beyond conventional ORAMs, we will consider differential privacy as a more relaxed security requirement to allow better performance in practice.
此項目將探索隱私數據結構與算法的理論基礎與應用,旨在通過數據存取模式防止敏感信息的洩露,該目標不能僅通過加密完成。我們將延展已有的隱私存儲模型來刻畫實際應用中的特徵,例如並行性與輸入/輸出高效性。由於現代結構設計普適採用了並行性與分級存儲器體系,我們的模型將對包括多核處理器、外包雲平台在內的多項實際應用中產生重要的影響。此外,我們發展更鬆弛的安全概念,以在性能與隱私級別中進行平衡。由Goldreich和Ostrovsky提出的經典不經意隨機存取器(ORAM)使得數據可以被不經意的存取,其中存儲模式不會洩露除運算序列長度以外的任何信息。 儘管在過去的十年中,ORAM的性能被提升,該模型並不能直接的支持並行結構。為了改變以上情況,不經意並行隨機存取器(OPRAM)在最近的TCC2016論文中被提出。在我們即將發表的TCC2017及ASIACRYPT2017論文中,我們得到了與最先進ORAM性能相同的OPRAM。這些初步成果啓發我們在OPRAM之外進一步探索支持多任務的隱私並行數據結構與他們的並行實現。除了並行性,分級存儲器體系在實際應用中也發揮著重要的作用。在即將發表的SODA2018論文中,我們提出了輸入/輸出高效、緩存不可知不經意排序算法,該成果給與我們強大的技術以繼續探索隱私機制中的輸入/輸出高效性。進一步,我們將探索在存儲方案中的新隱私概念,允許用戶在隱私偏好與性能保障中進行平衡。特別的,我們最近發展的技術使得我們可以克服以下挑戰:(1)在隱私數據結構與算法中探索並行性。我們將設計基礎的不經意並行算法作為存儲方案的基石,並研究深度與總工作之間的平衡。(2)在隱私機制中達到輸入/輸出高效性。例如,我們將考慮隱私方案中緩存不可知子程序,使得算法可以在沒有底層結構變量信息的情況下達到最優輸入/輸出高效性。 (3)研究存儲方案中更一般的安全概念。超越傳統ORAM,我們將考慮可微分隱私作為更鬆弛的安全要求,以在實際應用中取得更好的性能。
Research Outcome
Layman's Summary of
Completion Report:
Not yet submitted