International Association for Cryptologic Research

International Association
for Cryptologic Research


Daniel Noble


Proactive Secret Sharing with Constant Communication
This paper presents the first protocols for Proactive Secret Sharing (PSS) that only require constant (in the number of parties, n) communication per party per epoch. By harnessing the power of expander graphs, we are able to obtain strong guarantees about the security of the system. We present the following PSS protocols: – A PSS protocol that provides privacy (but no robustness) against an adversary controlling O(n) parties per epoch. – A PSS protocol that provides robustness (but no privacy) against an adversary controlling O(n) parties per epoch. – A PSS protocol that provides privacy against an adversary controlling O(n^a) ) parties per epoch and provides robustness against an adversary controlling O(n^(1−a)) parties per epoch, for any constant 0 ≤ a ≤ 1. Instantiating this with a = 1/2 gives a PSS protocol that is proactively secure (private and robust) against an adversary controlling O(√n) parties per epoch. Additionally, we discuss how secure channels, whose existence is usually assumed by PSS protocols, are challenging to create in the mobile adversary setting, and we present a method to instantiate them from a weaker assumption.
Alibi: A Flaw in Cuckoo-Hashing based Hierarchical ORAM Schemes and a Solution 📺
There once was a table of hashes That held extra items in stashes It all seemed like bliss But things went amiss When the stashes were stored in the caches The first Oblivious RAM protocols introduced the ``hierarchical solution,'' (STOC '90) where the server stores a series of hash tables of geometrically increasing capacities. Each ORAM query would read a small number of locations from each level of the hierarchy, and each level of the hierarchy would be reshuffled and rebuilt at geometrically increasing intervals to ensure that no single query was ever repeated twice at the same level. This yielded an ORAM protocol with polylogarithmic overhead. Future works extended and improved the hierarchical solution, replacing traditional hashing with cuckoo hashing (ICALP '11) and cuckoo hashing with a combined stash (Goodrich et al. SODA '12). In this work, we identify a subtle flaw in the protocol of Goodrich et al. (SODA '12) that uses cuckoo hashing with a stash in the hierarchical ORAM solution. We give a concrete distinguishing attack against this type of hierarchical ORAM that uses cuckoo hashing with a \emph{combined} stash. This security flaw has propagated to at least 5 subsequent hierarchical ORAM protocols, including the recent optimal ORAM scheme, OptORAMa (Eurocrypt '20). In addition to our attack, we identify a simple fix that does not increase the asymptotic complexity. We note, however, that our attack only affects more recent \emph{hierarchical ORAMs}, but does not affect the early protocols that predate the use of cuckoo hashing, or other types of ORAM solutions (e.g. Path ORAM or Circuit ORAM).