Abstract as per original application
(English/Chinese): |
This project investigates a composition framework that will facilitate the modular design and analysis of differential oblivious mechanisms under various distributed and adversarial models. The leakage of sensitive information through memory access patterns on even encrypted data necessitates the study of oblivious mechanisms. While achieving perfect obliviousness is possible via oblivious RAM constructions, the first drawback is the famous Goldreich-Ostrovksy theoretical logarithmic lower bound on the computational overhead required for access pattern obfuscation. The second limitation is that the number of memory accesses made by a mechanism for every input must be artificially inflated to the worst-case scenario.
Inspired by the widely acclaimed notion of differential privacy (DP), the principal investigator has previously proposed the differentially oblivious (DO) notion to apply the same randomized treatment for access patterns, i.e., for two neighboring inputs that are close to each other, the two corresponding distributions of access patterns observed by the adversary will also be close to each other in the DP sense. Indeed, the relaxed DO notion from perfect obliviousness can resolve two issues. First, certain lower bounds on the computation costs can be circumvented, an example of which is stable oblivious sorting with short keys. Second, the DO notion makes it possible to increase the running times slightly such that the adversary cannot distinguish between similar inputs.
Despite the clear potential of the DO notion, currently there is no convenient way to achieve composition results that are analogous to the well-known DP composition theorems, which provide DP guarantees when several DP components are combined together, even when one component depends on the result of another one. A main goal of this project is to develop theoretical foundations to achieve modular composition such that when several DO components are combined, the resulting mechanism is also guaranteed to be DO with parameters that are attained for existing DP composition.
We believe that such a powerful modular composition framework for DO mechanisms will bring insights into existing DO mechanisms and can be applied to more general problems. By considering general topology to connect different DO components and allowing adversaries of different types, we will design distributed DO protocols in multi-user and multi-server settings. This project will develop the techniques that facilitate the modular design of DO mechanisms, which have the potential to be as accessible and popular as the DP notion.
本項目將研究一個有助於在各種分佈式和對抗模型下進行模塊化設計和分析的複合框架。考慮到即使是加密數據的內存訪問模式亦會導致敏感信息的洩漏，因此對無識機制的研究顯得必要。 雖然完美的無識性或可借助無識隨機訪問存儲架構實現，但是該方案面臨的第一個缺點便是關於訪問模式混淆所需計算開銷上著名的 Goldreich-Ostrovksy 理論對數下界，第二便是該機制對每一次輸入進行的內存訪問次數必須人為地放大至最壞情況。
受到廣受好評的差分隱私概念的啟發，本項目的主要研究者先前曾提出差分無識的概念，並對訪問模式應用同樣的隨機化處理，即是，對於兩個彼此相近的相鄰輸入，對手觀察到的對應的兩個訪問模式分佈在差分隱私意義下亦將彼此相近。事實上，從完美無識性出發得到的放鬆後的差分無識概念可以解決兩個問題：第一，其可以規避一些計算成本的下界，其中一個例子便是針對短鍵的穩定無識排序；第二，差分無識的概念使得通過稍微增加運行時間以令到對手無法區分相似的輸入成為可能。
儘管差分無識具有如此明顯的潛力，但目前仍無一個有如著名的差分隱私複合定理一般簡便的複合方法，該差分隱私複合定理可以將多個具有差分隱私性質的部件進行複合，並保證複合以後的差分隱私性質，即使這些部件之間可能存在一些部件依賴其他一些部件運行結果的情況。本項目的一個主要目標便是為差分無識的模塊化複合提供理論基礎，使得當多個具有差分無識性質的部件組合在一起時，所得到的機制仍能保證具有一定的差分無識性質，並且相關的參數與目前現有的差分隱私複合定理的參數一致。
我們相信，如此強大的差分無識機制模塊化複合框架將會為現有的差分無識機制帶來新的見解，並且該框架可以被應用到更加普遍的問題上。通過考慮連接不同差分無識部件的一般化拓撲結構，以及考慮不同類型的對手，我們亦將會在多用戶及多伺服器的背景下設計分佈式差分無識協議。本項目將開發有助於差分無識機制模塊化設計的相關技術，這些技術將有機會如差分隱私概念一般便利和流行。
|
