Cuckoo hashing in cryptography: optimal parameters, robustness and applications

DOI10.1007/978-3-031-38551-3_7MaRDI QIDQ6149606zbMATH OpenFDO

Authors Kevin Yeo

Publication date 6 February 2024

Published in Advances in Cryptology – CRYPTO 2023 (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2306.11220

Mathematics Subject Classification ID

Data encryption (aspects in computer science) (68P25) Cryptography (94A60)

Abstract: Cuckoo hashing is a powerful primitive that enables storing items using small space with efficient querying. At a high level, cuckoo hashing maps $n$ items into $b$ entries storing at most $ell$ items such that each item is placed into one of $k$ randomly chosen entries. Additionally, there is an overflow stash that can store at most $s$ items. Many cryptographic primitives rely upon cuckoo hashing to privately embed and query data where it is integral to ensure small failure probability when constructing cuckoo hashing tables as it directly relates to the privacy guarantees. As our main result, we present a more query-efficient cuckoo hashing construction using more hash functions. For construction failure probability $epsilon$, the query overhead of our scheme is $O(1+sqrtlog(1/epsilon)/logn)$. Our scheme has quadratically smaller query overhead than prior works for any target failure probability $epsilon$. We also prove lower bounds matching our construction. Our improvements come from a new understanding of the locality of cuckoo hashing failures for small sets of items. We also initiate the study of robust cuckoo hashing where the input set may be chosen with knowledge of the hash functions. We present a cuckoo hashing scheme using more hash functions with query overhead $ildeO(loglambda)$ that is robust against poly$(lambda)$ adversaries. Furthermore, we present lower bounds showing that this construction is tight and that extending previous approaches of large stashes or entries cannot obtain robustness except with $Omega(n)$ query overhead. As applications of our results, we obtain improved constructions for batch codes and PIR. In particular, we present the most efficient explicit batch code and blackbox reduction from single-query PIR to batch PIR.

Cites work

• \textsf{Catalic}: delegated PSI cardinality with applications to contact tracing
• A Framework for Adversarially Robust Streaming Algorithms
• Adversarially robust property-preserving hash functions
• Alibi: a flaw in cuckoo-hashing based hierarchical ORAM schemes and a solution
• An Analysis of Random-Walk Cuckoo Hashing
• Automata, Languages and Programming
• Balanced allocation and dictionaries with tightly packed constant size bins
• Balanced allocations (extended abstract)
• Balls into bins made faster
• Batch codes and their applications
• Batch Codes Through Dense Graphs Without Short Cycles
• Bipartite random graphs and Cuckoo hashing
• Cuckoo hashing
• Cuckoo hashing: Further analysis
• De-amortized Cuckoo Hashing: Provable Worst-Case Performance and Experimental Results
• Efficient circuit-based PSI via cuckoo hashing
• Generalized cuckoo hashing with a stash, revisited
• Hardness-preserving reductions via cuckoo hashing
• History-Independent Cuckoo Hashing
• How robust are linear sketches to adaptive inputs?
• scientific article; zbMATH DE number 1559546 (Why is no real title available?)
• scientific article; zbMATH DE number 1857645 (Why is no real title available?)
• Lower bounds for (batch) PIR with private preprocessing
• More robust hashing: cuckoo hashing with a stash
• Multi-query Computationally-Private Information Retrieval with Constant Communication Rate
• Nearly optimal property preserving hashing
• Oblivious key-value stores and amplification for private set intersection
• Oblivious RAM Revisited
• On the (in)security of hash-based oblivious RAM and a new balancing scheme
• On the insertion time of cuckoo hashing
• OptORAMa: optimal oblivious RAM
• Privacy-preserving access of outsourced data via oblivious RAM simulation
• Private information retrieval
• Property-preserving hash functions for Hamming distance from standard assumptions
• PSI from PaXoS: fast, malicious private set intersection
• Searchable symmetric encryption: optimal locality in linear space via two-dimensional balanced allocations
• Sketching in Adversarial Environments
• Space efficient hash tables with worst case constant access time
• SSE and SSD: page-efficient searchable symmetric encryption
• Tight thresholds for Cuckoo hashing via XORSAT (extended abstract)
• Uniform Hashing in Constant Time and Optimal Space

Cited in

(7)

• Cuckoo commitments: registration-based encryption and key-value map commitments for large spaces
• Universal vector commitments
• Optimal non-adaptive cell probe dictionaries and hashing
• Weakly super-invertible matrices and constant communication dishonest majority MPC
• Deletions and dishonesty: probabilistic data structures in adversarial settings
• MetaDORAM: info-theoretic distributed ORAM with less communication
• Updatable private set intersection from symmetric-key techniques

This page was built for publication: Cuckoo hashing in cryptography: optimal parameters, robustness and applications

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