CryptoDB
Ling Ren
Publications
Year
Venue
Title
2023
CRYPTO
Practical Settlement Bounds for Longest-Chain Consensus
Abstract
Nakamoto's longest-chain consensus paradigm now powers the bulk of the
world's cryptocurrencies and distributed finance infrastructure. An
emblematic property of longest-chain consensus is that it provides
probabilistic settlement guarantees that strengthen over time. This
makes the exact relationship between settlement error and settlement
latency a critical aspect of the protocol that both users and system
designers must understand to make informed decisions.
A recent line of work has finally provided a satisfactory rigorous
accounting of this relationship for proof-of-work longest-chain
protocols, but those techniques do not appear to carry over to the
proof-of-stake setting.
This article develops a new analytic approach for establishing such
settlement guarantees that yields explicit, rigorous settlement bounds
for proof-of-stake longest-chain protocols, placing them on equal
footing with their proof-of-work counterparts. Our techniques apply
with some adaptations to the proof-of-work setting where they provide
improvements to the state-of-the-art settlement bounds for
proof-of-work protocols.
2022
JOFC
Locality-Preserving Oblivious RAM
Abstract
Oblivious RAMs, introduced by Goldreich and Ostrovsky [JACM’96], compile any RAM program into one that is “memory oblivious,” i.e., the access pattern to the memory is independent of the input. All previous ORAM schemes, however, completely break the locality of data accesses (for instance, by shuffling the data to pseudorandom positions in memory). In this work, we initiate the study of locality-preserving ORAMs —ORAMs that preserve locality of the accessed memory regions, while leaking only the lengths of contiguous memory regions accessed. Our main results demonstrate the existence of a locality-preserving ORAM with polylogarithmic overhead both in terms of bandwidth and locality. We also study the trade-off between locality, bandwidth and leakage, and show that any scheme that preserves locality and does not leak the lengths of the contiguous memory regions accessed, suffers from prohibitive bandwidth. To further improve the parameters, we also consider a weaker notion of a File ORAM, which supports accesses to predefined non-overlapping regions. Assuming one-way functions, we present a computationally secure File ORAM that has a work overhead and locality of roughly $$O(\log ^2 N)$$ O ( log 2 N ) , while ignoring $$\log \log N$$ log log N factors. To the best of our knowledge, before our work, the only works combining locality and obliviousness were for symmetric searchable encryption [e.g., Cash and Tessaro (EUROCRYPT’14), Asharov et al. (STOC’16)]. Symmetric search encryption ensures obliviousness if each keyword is searched only once, whereas ORAM provides obliviousness to any input program. Thus, our work generalizes that line of work to the much more challenging task of preserving locality in ORAMs.
2019
EUROCRYPT
Locality-Preserving Oblivious RAM
📺
Abstract
Oblivious RAMs, introduced by Goldreich and Ostrovsky [JACM’96], compile any RAM program into one that is “memory oblivious”, i.e., the access pattern to the memory is independent of the input. All previous ORAM schemes, however, completely break the locality of data accesses (for instance, by shuffling the data to pseudorandom positions in memory).In this work, we initiate the study of locality-preserving ORAMs—ORAMs that preserve locality of the accessed memory regions, while leaking only the lengths of contiguous memory regions accessed. Our main results demonstrate the existence of a locality-preserving ORAM with poly-logarithmic overhead both in terms of bandwidth and locality. We also study the tradeoff between locality, bandwidth and leakage, and show that any scheme that preserves locality and does not leak the lengths of the contiguous memory regions accessed, suffers from prohibitive bandwidth.To the best of our knowledge, before our work, the only works combining locality and obliviousness were for symmetric searchable encryption [e.g., Cash and Tessaro (EUROCRYPT’14), Asharov et al. (STOC’16)]. Symmetric search encryption ensures obliviousness if each keyword is searched only once, whereas ORAM provides obliviousness to any input program. Thus, our work generalizes that line of work to the much more challenging task of preserving locality in ORAMs.
Program Committees
- Asiacrypt 2020
- Asiacrypt 2019
Coauthors
- Ittai Abraham (1)
- Gilad Asharov (2)
- T.-H. Hubert Chan (2)
- Srinivas Devadas (4)
- Christopher W. Fletcher (2)
- Peter Gaži (1)
- Kartik Nayak (3)
- Rafael Pass (2)
- Benny Pinkas (1)
- Alexander Russell (1)
- Elaine Shi (3)
- Marten van Dijk (1)
- Daniel Wichs (1)
- Hanshen Xiao (1)