File Download
There are no files associated with this item.
Links for fulltext
(May Require Subscription)
- Publisher Website: 10.1137/1.9781611975482.150
- Scopus: eid_2-s2.0-85065864205
Supplementary
-
Citations:
- Scopus: 0
- Appears in Collections:
Conference Paper: Foundations of Differentially Oblivious Algorithms
Title | Foundations of Differentially Oblivious Algorithms |
---|---|
Authors | |
Issue Date | 2019 |
Publisher | Society for Industrial and Applied Mathematics. |
Citation | Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2019), San Diego, CA, USA, 6-9 January 2019, p. 2448-2467 How to Cite? |
Abstract | It is well-known that a program's memory access pattern can leak information about its input. To thwart such leakage, most existing works adopt the technique of oblivious RAM (ORAM) simulation. Such an obliviousness notion has stimulated much debate. Although ORAM techniques have significantly improved over the past few years, the concrete overheads are arguably still undesirable for real-world systems — part of this overhead is in fact inherent due to a well-known logarithmic ORAM lower bound by Goldreich and Ostrovsky. To make matters worse, when the program's runtime or output length depend on secret inputs, it may be necessary to perform worst-case padding to achieve full obliviousness and thus incur possibly super-linear overheads.
Inspired by the elegant notion of differential privacy, we initiate the study of a new notion of access pattern privacy, which we call “(∊, δ)-differential obliviousness”. We separate the notion of (∊, δ)-differential obliviousness from classical obliviousness by considering several fundamental algorithmic abstractions including sorting small-length keys, merging two sorted lists, and range query data structures (akin to binary search trees). We show that by adopting differential obliviousness with reasonable choices of ∊ and δ, not only can one circumvent several impossibilities pertaining to full obliviousness, one can also, in several cases, obtain meaningful privacy with little overhead relative to the non-private baselines (i.e., having privacy “almost for free”). On the other hand, we show that for very demanding choices of ∊ and δ, the same lower bounds for oblivious algorithms would be preserved for (∊, δ)-differential obliviousness. |
Persistent Identifier | http://hdl.handle.net/10722/290708 |
DC Field | Value | Language |
---|---|---|
dc.contributor.author | Chan, HTH | - |
dc.contributor.author | Chung, KM | - |
dc.contributor.author | Maggs, BM | - |
dc.contributor.author | Shi, E | - |
dc.date.accessioned | 2020-11-02T05:46:00Z | - |
dc.date.available | 2020-11-02T05:46:00Z | - |
dc.date.issued | 2019 | - |
dc.identifier.citation | Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2019), San Diego, CA, USA, 6-9 January 2019, p. 2448-2467 | - |
dc.identifier.uri | http://hdl.handle.net/10722/290708 | - |
dc.description.abstract | It is well-known that a program's memory access pattern can leak information about its input. To thwart such leakage, most existing works adopt the technique of oblivious RAM (ORAM) simulation. Such an obliviousness notion has stimulated much debate. Although ORAM techniques have significantly improved over the past few years, the concrete overheads are arguably still undesirable for real-world systems — part of this overhead is in fact inherent due to a well-known logarithmic ORAM lower bound by Goldreich and Ostrovsky. To make matters worse, when the program's runtime or output length depend on secret inputs, it may be necessary to perform worst-case padding to achieve full obliviousness and thus incur possibly super-linear overheads. Inspired by the elegant notion of differential privacy, we initiate the study of a new notion of access pattern privacy, which we call “(∊, δ)-differential obliviousness”. We separate the notion of (∊, δ)-differential obliviousness from classical obliviousness by considering several fundamental algorithmic abstractions including sorting small-length keys, merging two sorted lists, and range query data structures (akin to binary search trees). We show that by adopting differential obliviousness with reasonable choices of ∊ and δ, not only can one circumvent several impossibilities pertaining to full obliviousness, one can also, in several cases, obtain meaningful privacy with little overhead relative to the non-private baselines (i.e., having privacy “almost for free”). On the other hand, we show that for very demanding choices of ∊ and δ, the same lower bounds for oblivious algorithms would be preserved for (∊, δ)-differential obliviousness. | - |
dc.language | eng | - |
dc.publisher | Society for Industrial and Applied Mathematics. | - |
dc.relation.ispartof | Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2019) | - |
dc.title | Foundations of Differentially Oblivious Algorithms | - |
dc.type | Conference_Paper | - |
dc.identifier.email | Chan, HTH: hubert@cs.hku.hk | - |
dc.identifier.authority | Chan, HTH=rp01312 | - |
dc.identifier.doi | 10.1137/1.9781611975482.150 | - |
dc.identifier.scopus | eid_2-s2.0-85065864205 | - |
dc.identifier.hkuros | 318355 | - |
dc.identifier.spage | 2448 | - |
dc.identifier.epage | 2467 | - |
dc.publisher.place | Philadelphia, PA | - |
dc.identifier.eisbn | 9781611975482 | - |