Universal classes of hash functions
From MaRDI portal
Publication:1259907
DOI10.1016/0022-0000(79)90044-8zbMath0412.68090OpenAlexW2052207834WikidataQ29542266 ScholiaQ29542266MaRDI QIDQ1259907
J. Lawrence Carter, Mark N. Wegman
Publication date: 1979
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0022-0000(79)90044-8
Data structures (68P05) Information storage and retrieval of data (68P20) Discrete mathematics in relation to computer science (68R99)
Related Items
Packing a Knapsack of Unknown Capacity, Quantum Speedup for Graph Sparsification, Cut Approximation, and Laplacian Solving, A Lattice-Based Certificateless Public Key Encryption with Equality Test in Standard Model, The complexity of generating test instances, Sorting and searching revisted, Nearly Optimal Static Las Vegas Succinct Dictionary, The complexity of graph connectivity, Trans-dichotomous algorithms without multiplication — some upper and lower bounds, Three‐wise independent random walks can be slightly unbounded, Binary Fuse Filters: Fast and Smaller Than Xor Filters, Deterministic Massively Parallel Connectivity, Secure two-party input-size reduction: challenges, solutions and applications, Graphs, hypergraphs and hashing, One-way functions and the hardness of (probabilistic) time-bounded Kolmogorov complexity w.r.t. samplable distributions, SoftSpokenOT: quieter OT extension from small-field silent VOLE in the Minicrypt model, Universal Hashing via Integer Arithmetic Without Primes, Revisited, Hierarchical Secret Sharing Schemes Secure Against Rushing Adversary: Cheater Identification and Robustness, The complexity of the co-occurrence problem, Unnamed Item, Unnamed Item, m-Bonsai: A Practical Compact Dynamic Trie, Unnamed Item, Fast Evaluation of Union-Intersection Expressions, Decoupling with unitary approximate two-designs, Deterministic extractors for small-space sources, Practical Evaluation of Lempel-Ziv-78 and Lempel-Ziv-Welch Tries, Об одном семействе универсальных функций хеширования, Improved Explicit Hitting-Sets for ROABPs, THE PHYSICS OF QUANTUM INFORMATION: COMPLEMENTARITY, UNCERTAINTY, AND ENTANGLEMENT, Privacy amplification with asymptotically optimal entropy loss, Optimal encoding of non-stationary sources, Unnamed Item, On the Construction of (n, k)-schemes of Visual Cryptography Using a Class of Linear Hash Functions Over a Binary Field, On Optimal Probabilistic Asynchronous Byzantine Agreement, Verifiable random functions from non-interactive witness-indistinguishable proofs, Four-state non-malleable codes with explicit constant rate, Tight bounds for sliding Bloom filters, Polynomial hash functions are reliable, Efficient reliable communication over partially authenticated networks, Analysis of Robin Hood and Other Hashing Algorithms Under the Random Probing Model, With and Without Deletions, Approximation in (Poly-) Logarithmic Space, Derandomizing Isolation in Space-Bounded Settings, Keyed hash functions, Optimal Broadcast with Partial Knowledge, Security Bounds for Quantum Cryptography with Finite Resources, Unnamed Item, Round Efficient Unconditionally Secure Multiparty Computation Protocol, Tweakable Pseudorandom Permutation from Generalized Feistel Structure, Multi-partite squash operation and its application to device-independent quantum key distribution, Unnamed Item, Quantum blind signature with an offline repository, On the Security of Compressed Encodings, The Many Entropies in One-Way Functions, Oblivious transfer based on single-qubit rotations, Attacks on quantum key distribution protocols that employ non-ITS authentication, \(\text{RL}\subseteq \text{SC}\), MMH* with arbitrary modulus is always almost-universal, Combinatorial techniques for universal hashing, Algorithms for parallel memory, I: Two-level memories, Locality-preserving hash functions for general purpose parallel computation, Universal hashing and authentication codes, Recognizing Hamming graphs in linear time and space, HalftimeHash: modern hashing without 64-bit multipliers or finite fields, A probabilistic distributed algorithm for set intersection and its analysis, Locating \(P\)/poly optimally in the extended low hierarchy, NP is as easy as detecting unique solutions, A theory for memory-based learning, Quantum algorithms for the \(k\)-XOR problem, Variationally universal hashing, A fast randomized LOGSPACE algorithm for graph connectivity, Secret sharing schemes with partial broadcast channels, Study on the security of the authentication scheme with key recycling in QKD, Triangle counting in dynamic graph streams, Arthur-Merlin games: A randomized proof system, and a hierarchy of complexity classes, Linking information reconciliation and privacy amplification, A construction method for optimally universal hash families and its consequences for the existence of RBIBDs, On the existence of statistically hiding bit commitment schemes and fail-stop signatures, Exploiting storage redundancy to speed up randomized shared memory simulations, The generation of random permutations on the fly, Mathematical problems in cryptology, Simulating shared memory in real time: On the computation power of reconfigurable architectures, Graph isomorphism is in the low hierarchy, On the power of two-point based sampling, A new multi-linear universal hash family, A derandomization using min-wise independent permutations, Efficient construction of a small hitting set for combinatorial rectangles in high dimension, Simulating BPP using a general weak random source, Efficient PRAM simulation on a distributed memory machine, A note on local randomness in polynomial random number and random function generators, On the relationships between perfect nonlinear functions and universal hash families, Perfect hashing, Approximation algorithms for multiple sequence alignment, A note on universal classes of hash functions, Efficient bit sifting scheme of post-processing in quantum key distribution, Construction of a key-dependent message secure symmetric encryption scheme in the ideal cipher model, Optimal proof systems imply complete sets for promise classes, The universality of iterated hashing over variable-length strings, An improved version of cuckoo hashing: average case analysis of construction cost and search operations, On weak keys and forgery attacks against polynomial-based MAC schemes, New proofs for NMAC and HMAC: security without collision resistance, New hash functions and their use in authentication and set equality, Low-contention data structures, Energy-efficient paths in radio networks, A new multistage approach to detect subtle DDoS attacks, Simple and more efficient PRFs with tight security from LWE and matrix-DDH, Structures and lower bounds for binary covering arrays, The effect of side-information on smooth entropy., Revisiting iterated attacks in the context of decorrelation theory, Non-cryptographic primitive for pseudorandom permutation., Cache-oblivious hashing, Evaluating Bernstein-Rabin-Winograd polynomials, Using quantum key distribution for cryptographic purposes: a survey, Direct proof of security of Wegman-Carter authentication with partially known key, Explicit and efficient hash families suffice for cuckoo hashing with a stash, A practical protocol for three-party authenticated quantum key distribution, Boosting distinct random sampling for basic counting on the union of distributed streams, Fast rehashing in PRAM emulations, On quasilinear-time complexity theory, Using multiset discrimination to solve language processing problems without hashing, On the theory of average case complexity, Efficient robust secret sharing from expander graphs, Index structures for fast similarity search for binary vectors, Efficient one-sided adaptively secure computation, On rate-1 and beyond-the-birthday bound secure online ciphers using tweakable block ciphers, Improved behaviour of tries by adaptive branching, Pseudorandom generators for space-bounded computation, The computational complexity of universal hashing, Clocked adversaries for hashing, Universal hash functions for an infinite universe and hash trees, Sharp lower bounds on the extractable randomness from non-uniform sources, The optimal size of a signature, On hiding information from an oracle, Quantum hashing via \(\epsilon\)-universal hashing constructions and classical fingerprinting, Hierarchical sampling from sketches: Estimating functions over data streams, Approximate colored range and point enclosure queries, A caution on universal classes of hash functions, Encryption modes with almost free message integrity, Sorting in linear time?, Reducing complexity assumptions for statistically-hiding commitment, On the impossibility of highly-efficient blockcipher-based hash functions, Approximating hyper-rectangles: Learning and pseudorandom sets, Proving properties of interactive proofs by a generalized counting technique, New approaches for deniable authentication, \(\text{BP}_{\text{H}}\text{SPACE}(S) \subseteq \text{DSPACE}(S^{3/2})\), Min-wise independent permutations, Reliable communication over partially authenticated networks, Finding extremal sets in less than quadratic time, On the complexity of counting in the polynomial hierarchy, How to emulate shared memory, Statistical zero-knowledge languages can be recognized in two rounds, Protocols for asymmetric communication channels, Randomness in interactive proofs, Provably good pattern generators for a random pattern test, Optimal bounds for the predecessor problem and related problems, Quantum readout of Physical Unclonable Functions, Analysis of the Initial and Modified Versions of the Candidate 3GPP Integrity Algorithm 128-EIA3, ON "THE POWER OF VERIFICATION QUERIES" IN UNCONDITIONALLY SECURE MESSAGE AUTHENTICATION, A fast randomized LOGSPACE algorithm for graph connectivity, New techniques and tighter bounds for local computation algorithms, Practical and Provably-Secure Commitment Schemes from Collision-Free Hashing, Quicksort, Largest Bucket, and Min-Wise Hashing with Limited Independence, Security of Device-Independent Quantum Key Distribution Protocols, Minimum Circuit Size, Graph Isomorphism, and Related Problems, FUZZY UNIVERSAL HASHING AND APPROXIMATE AUTHENTICATION, Quantum Security Analysis via Smoothing of Renyi Entropy of Order 2, Privacy with Imperfect Randomness, Tweak-Length Extension for Tweakable Blockciphers, Shannon Entropy Versus Renyi Entropy from a Cryptographic Viewpoint, A Statistical Analysis of Probabilistic Counting Algorithms, A generic construction of fuzzy signature, Sparser Johnson-Lindenstrauss Transforms, Weak-Key and Related-Key Analysis of Hash-Counter-Hash Tweakable Enciphering Schemes, Sample(x)=(a*x<=t) Is a Distinguisher with Probability 1/8, Efficiently correcting matrix products, Secure two-party computation via cut-and-choose oblivious transfer, On Weak Keys and Forgery Attacks Against Polynomial-Based MAC Schemes, Measure-resend authenticated semi-quantum key distribution with single photons, Efficient Asymmetric Index Encapsulation Scheme for Named Data, Hardness-preserving reductions via cuckoo hashing, When Are Fuzzy Extractors Possible?, In search of mathematical primitives for deriving universal projective hash families, Unnamed Item, Entanglement of the antisymmetric state, One-way protocol for two-bit intrinsic random key distribution with entangled photon pairs, Optimizing the decoy-state BB84 QKD protocol parameters, A trade-off between collision probability and key size in universal hashing using polynomials, Quantum key distribution with PRF(Hash, Nonce) achieves everlasting security, Towards closing the security gap of Tweak-aNd-Tweak (TNT), Optimal CUR Matrix Decompositions, Composable Security in the Bounded-Quantum-Storage Model, SAMPLING IN DYNAMIC DATA STREAMS AND APPLICATIONS, Reflections on the security proofs of Boneh-Franklin identity-based encryption scheme, SECURITY OF QUANTUM KEY DISTRIBUTION, A new interactive hashing theorem, On Privacy-Preserving Biometric Authentication, Asymmetric ``4+2 protocol for quantum key distribution with finite resources, An Improved Robust Fuzzy Extractor, Dynamic Routing and Location Services in Metrics of Low Doubling Dimension, Simple fast parallel hashing, Linear Hashing Is Awesome, MMH: Software message authentication in the Gbit/second rates, MRD Hashing, Related-Key Almost Universal Hash Functions: Definitions, Constructions and Applications, On an Almost-Universal Hash Function Family with Applications to Authentication and Secrecy Codes, Bounded Independence Plus Noise Fools Products, QUANTUM KEY EVOLUTION AND ITS APPLICATIONS, Cryptanalysis and improvement in multi-party quantum key distribution protocol with new Bell states encoding mode, New collapse consequences of NP having small circuits, Quantum Key Distribution, On the (im-)possibility of extending coin toss, On b-bit min-wise hashing for large-scale regression and classification with sparse data, Authenticating ad hoc networks by comparison of short digests, A NOVEL PROTOCOL-AUTHENTICATION ALGORITHM RULING OUT A MAN-IN-THE MIDDLE ATTACK IN QUANTUM CRYPTOGRAPHY, Bounds on the efficiency of black-box commitment schemes, Modes of operations for encryption and authentication using stream ciphers supporting an initialisation vector, On the (Im-)Possibility of Extending Coin Toss, Weaknesses of Cuckoo Hashing with a Simple Universal Hash Class: The Case of Large Universes, The smooth entropy formalism for von Neumann algebras, Key-Recovery Attacks on Universal Hash Function Based MAC Algorithms, On Notions of Security for Deterministic Encryption, and Efficient Constructions without Random Oracles, Basing PRFs on Constant-Query Weak PRFs: Minimizing Assumptions for Efficient Symmetric Cryptography, Dispersing hash functions, A joint Shannon cipher and privacy amplification approach to attaining exponentially decaying information leakage, On the relationship between statistical zero-knowledge and statistical randomized encodings, Error-bounded probabilistic computations between MA and AM, Parity graph-driven read-once branching programs and an exponential lower bound for integer multiplication, The circulant hash revisited, Approximation in (Poly-) logarithmic space, Pseudorandom generators from regular one-way functions: new constructions with improved parameters, Precise evaluation of leaked information with secure randomness extraction in the presence of quantum attacker, On the complexity of constructing pseudorandom functions (especially when they don't exist), Contributory Password-Authenticated Group Key Exchange with Join Capability, Key Agreement from Close Secrets over Unsecured Channels, Новый режим аутентифицированного шифрования для произвольного блочного шифра на основе универсальной функции хэширования, Коды аутентификации с секретностью (обзор), Efficient Beyond-Birthday-Bound-Secure Deterministic Authenticated Encryption with Minimal Stretch, On the Circuit Complexity of Perfect Hashing, Collision-Free Hashing from Lattice Problems, A Sample of Samplers: A Computational Perspective on Sampling, On the Complexity of Computational Problems Regarding Distributions, Revisiting construction of online cipher in hash-ECB-hash structure, Breaking Symmetric Cryptosystems Using Quantum Period Finding, On the Relationship Between Statistical Zero-Knowledge and Statistical Randomized Encodings, Approximate counting by hashing in bounded arithmetic, RESPONSE TO "VULNERABILITY OF 'A NOVEL PROTOCOL-AUTHENTICATION ALGORITHM RULING OUT A MAN-IN-THE-MIDDLE ATTACK IN QUANTUM CRYPTOGRAPHY'", Key establishment à la Merkle in a quantum world, Security of Hash-then-CBC Key Wrapping Revisited, Optimal Broadcast with Partial Knowledge, MRD hashing., Bounds on the OBDD-size of integer multiplication via universal hashing, Error correction in quantum cryptography based on artificial neural networks, From non-adaptive to adaptive pseudorandom functions, Quantum key distribution using universal hash functions over finite fields, On the state of strength-three covering arrays
Cites Work
