More robust hashing: cuckoo hashing with a stash

DOI10.1137/080728743MaRDI QIDQ5901158zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Adam Kirsch, Michael Mitzenmacher, Udi Wieder

Publication date 6 September 2010

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://semanticscholar.org/paper/05c721f47d9a53a5739c88a14cb36baf12d2b0fa

zbMATH Keywords

cuckoo hashinghash tableprobabilistic analysis

Mathematics Subject Classification ID

Data structures (68P05) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87) Graph theory (including graph drawing) in computer science (68R10) Randomized algorithms (68W20)

Recommendations

• More Robust Hashing: Cuckoo Hashing with a Stash
• A further analysis of cuckoo hashing with a stash and random graphs of excess r
• Weaknesses of Cuckoo Hashing with a Simple Universal Hash Class: The Case of Large Universes

Cited in

(22)

• Alibi: a flaw in cuckoo-hashing based hierarchical ORAM schemes and a solution
• PSI from PaXoS: fast, malicious private set intersection
• Oblivious key-value stores and amplification for private set intersection
• SSE and SSD: page-efficient searchable symmetric encryption
• A faster algorithm for cuckoo insertion and bipartite matching in large graphs
• Hardness-preserving reductions via cuckoo hashing
• Generalized cuckoo hashing with a stash, revisited
• Oblivious RAM with worst-case logarithmic overhead
• Privacy-preserving access of outsourced data via oblivious RAM simulation
• Dynamic proofs of retrievability via oblivious RAM
• A further analysis of cuckoo hashing with a stash and random graphs of excess r
• Privacy-preserving group data access via stateless oblivious RAM simulation
• More Robust Hashing: Cuckoo Hashing with a Stash
• Tight tradeoffs in searchable symmetric encryption
• Adaptive Cuckoo Filters
• 3-party distributed ORAM from oblivious set membership
• Cuckoo hashing in cryptography: optimal parameters, robustness and applications
• OptORAMa: Optimal oblivious RAM
• DORAM revisited: maliciously secure RAM-MPC with logarithmic overhead
• 3-party secure computation for RAMs: optimal and concretely efficient
• Cuckoo commitments: registration-based encryption and key-value map commitments for large spaces
• Insertion time of random walk cuckoo hashing below the peeling threshold

This page was built for publication: More robust hashing: cuckoo hashing with a stash

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5901158)