Results 1 to 10 of about 195,517 (211)
The universality of iterated hashing over variable-length strings [PDF]
Discrete Applied Mathematics 160 (4-5), 604--617 (2012), 2010 Iterated hash functions process strings recursively, one character at a time. At each iteration, they compute a new hash value from the preceding hash value and the next character. We prove that iterated hashing can be pairwise independent, but never 3-wise independent. We show that it can be almost universal over strings much longer than the number of
Daniel Lemire
arxiv +6 more sources
Regular and almost universal hashing: an efficient implementation [PDF]
Software: Practice and Experience 47 (10), 2017, 2016 Random hashing can provide guarantees regarding the performance of data structures such as hash tables---even in an adversarial setting. Many existing families of hash functions are universal: given two data objects, the probability that they have the same hash value is low given that we pick hash functions at random.
Dmytro Ivanchykhin +2 more
arxiv +7 more sources
Variationally universal hashing [PDF]
Information Processing Letters, 2006 The strongest well-known measure for the quality of a universal hash-function family H is its being e-strongly universal, which measures, for randomly chosen h ∈ H, one's inability to guess h(m') even if h(m) is known for some m ≠ m' We give example applications in which this measure is too weak, and we introduce a stronger measure for the quality of a
Ted Krovetz, Phillip Rogaway
openalex +4 more sources
QKD parameter estimation by two-universal hashing [PDF]
Quantum, 2023 This paper proposes and proves security of a QKD protocol which uses two-universal hashing instead of random sampling to estimate the number of bit flip and phase flip errors.
Dimiter Ostrev
doaj +3 more sources
Multimixer-128: Universal Keyed Hashing Based on Integer Multiplication
IACR Transactions on Symmetric Cryptology, 2023 In this paper we introduce a new keyed hash function based on 32-bit integer multiplication that we call Multimixer-128. In our approach, we follow the key-then-hash parallel paradigm. So, we first add a variable length input message to a secret key and
Koustabh Ghosh +2 more
doaj +3 more sources
Universal Hashing and Multiple Authentication [PDF]
, 1996 In this paper, we study unconditionally secure codes that provide authentication without secrecy. Our point of view is the universal hashing approach pioneered by Wegman and Carter in 1981. We first compare several recent universal-hashing based constructions for authentication codes.
Mustafa Atıcı, D. R. Stinson
openalex +3 more sources
Hash Property and Fixed-rate Universal Coding Theorems [PDF]
IEEE Transactions on Information Theory, vol. 56, no. 6, pp.
2688-2698, June 2010. Corrections: IEEE Transactions on Information Theory,
vol. 58, no. 5, pp. 3305-3307, May 2012, 2008 The aim of this paper is to prove the achievability of fixed-rate universal coding problems by using our previously introduced notion of hash property. These problems are the fixed-rate lossless universal source coding problem and the fixed-rate universal channel coding problem.
Jun Muramatsu, Shigeki Miyake
arxiv +3 more sources
The computational complexity of universal hashing [PDF]
Proceedings of the twenty-second annual ACM symposium on Theory of computing - STOC '90, 1990 AbstractAny implementation of Carter-Wegman universal hashing from n-bit strings to m-bit strings requires a time-space tradeoff of TS=Ω(nm). The bound holds in the general boolean branching program model and, thus, in essentially any model of computation.
Yishay Mansour +2 more
openalex +5 more sources
Separating hash families with large universe [PDF]
arXiv, 2023 Separating hash families are useful combinatorial structures which generalize several well-studied objects in cryptography and coding theory. Let $p_t(N, q)$ denote the maximum size of universe for a $t$-perfect hash family of length $N$ over an alphabet of size $q$.
Wei, Xin, Zhang, Xiande, Ge, Gennian
arxiv +3 more sources
Construction of universal one-way hash functions: Tree hashing revisited
Discrete Applied Mathematics, 2007 AbstractWe present a binary tree based parallel algorithm for extending the domain of a universal one-way hash function (UOWHF). For t⩾2, our algorithm extends the domain from the set of all n-bit strings to the set of all ((2t-1)(n-m)+m)-bit strings, where m is the length of the message digest. The associated increase in key length is 2m bits for t=2;
Palash Sarkar
openalex +3 more sources