Search

Hash functions have been used to address security requirements such as integrity, message authentication and non-repudiation. In WSNs, these functions are also used to preserve sensor nodes' identity (ID) anonymity, i.e., they are used to generate and verify dynamic pseudonyms that are used to identify sensor nodes in a communication session. In this latter application, there is an open issue as to how long the output of a hash function (i.e. hash value) we should use in pseudonym generation. The longer the hash value, the longer is the pseudonym, thus the harder it is to guess a pseudonym that is generated by using a hash function. On the other hand, the use of a longer hash value also means that the bandwidth and energy costs in transmitting the pseudonym will be higher. As sensor nodes typically have limited resources and are battery powered, the balance between the protection level of ID anonymity and performance and energy costs incurred in providing such a protection is an open issue. This paper inves- tigates the use of hash value truncation in preserving ID anonymity in WSNs and the impact of hash value truncation on four criteria attributes (security against brute force attacks, probability of pseudonym collisions, energy trade- off and end-to-end packet delivery delay). It reports the possible impacts of other factors including the type and usage of hash functions, sensor node capabilities, adversary capabilities, ability to resolve pseudonym collisions, network density and data collection rate. The results show that the impacts of these factors may be contradictory. Therefore, the determination of an optimal level of hash value truncation should consider all trade-offs brought by these factors.

This paper presents a memory-constrained hash join algorithm (PaMeCo Join) designed to operate with main-memory column-store database systems. Whilst RAM has become more affordable and the popularity of main-memory database systems continues to grow, we recognize that RAM is a finite resource and that database systems rarely have an excess of memory available to them. Therefore, we design PaMeCo to operate within an arbitrary memory limitation by processing the input relations by parts, and by using a compact hash table that represents the contained tuples in a compact format. Coupled with a radix-clustering system that lowers memory latencies, we find that PaMeCo can offer competitive performance levels to other contemporary hash join algorithms in an unconstrained environment, while being up to three times faster than a high-performing hash join when memory constraints are applied.

We analyze the computational collision problem on a hash algorithm based on chaotic tent map, and then present an improvement of the original algorithm in this paper. More specifically, we utilize message extension to enhance the correlation of plaintexts in the message and aggregation operation to improve the correlation of sequences of message blocks, which significantly increase the sensitivity between message and hash values, thereby greatly resisting the collision. Finally, we evaluate the performance of the improved algorithm by computer simulation, and the results show that it can resist the computational collision and can satisfy the requirements of a more secure hash algorithm.

Non-cryptographic hash functions have been investigated to identify their pseudo-random nature when employed in the implementation of hash tables for real-time storage and look-up of uniform resource locators. Statistical studies have been performed on the sequences generated using five widely used non-cryptographic hash functions: (1) CRC, (2) Adler, (3) DJBX33A, (4) FNV, and (5) Murmur. The comparative analysis of tested non-cryptographic hash functions shows that the Adler hash function is not suitable for hash table implementation, whereas, the rest of non-cryptographic hash functions exhibit similar and better randomizing features which make them an attractive choice for hash table implementation.

Hash tables are widely used in network applications, as they can achieve O(1) query, insert, and delete operations at moderate loads. However, at high loads, collisions are prevalent in the table, which increases the access time and induces non-deterministic performance. Slow rates and non-determinism can considerably hurt the performance and scalability of hash tables in the multi-threaded parallel systems such as ASIC/FPGA and multi-core. So it is critical to keep the hash operations faster and more deterministic. This paper presents a novel fast collision-free hashing scheme using Discriminative Bloom Filters (DBFs) to achieve fast and deterministic hash table lookup. DBF is a compact summary stored in on-chip memory. It is composed of an array of parallel Bloom filters organized by the discriminator. Each element lookup performs parallel membership checks on the on-chip DBF to produce a possible discriminator value. Then, the element plus the discriminator value is hashed to a possible bucket in an off-chip hash table for validating the match. This DBF-based scheme requires one off-chip memory access per lookup as well as less off-chip memory usage. Experiments show that our scheme achieves up to 8.5-fold reduction in the number of off-chip memory accesses per lookup than previous schemes.

We propose a new hash function, the unique permutation hash function, and a performance analysis of its hash computation. We denote the cost of a hash function h by C"h(k,N), which stands for the expected number of table entries that are checked when inserting the (k+1)^s^t key into a hash table of size N, where k out of N table entries are filled by previous insertions. A hash function maps a key to a permutation of the table locations. A hash function, h, is simple uniform if items are equally likely to be hashed to any table location (in the first trial). A hash function, h, is random or strong uniform if the probability of any permutation to be a probe sequence, when using h, is 1N!, where N is the size of the table. We show that the unique permutation hash function is not only a simple uniform hash function but also a random hash function, i.e., strong uniform, and therefore has the optimal cost. Namely, each probe sequence is equally likely to be chosen when the keys are uniformly chosen. Our hash function ensures that each empty table location has the same probability to be assigned by a uniformly chosen key. We also show that the expected time for computing the unique permutation hash function is O(1) and the expected number of table locations that are checked before an empty location is found during insertion (or search) is also O(1) for constant load factors @a

This paper proposes a new chaotic keyed hash function based on a single 4-dimensional chaotic cat map whose irregular outputs are used to compute a hash value. The suggested scheme is fast, efficient and flexible. It takes an input message of arbitrary length and returns a hash value of a fixed length n , where n is a multiple of 32 (by convention, n is usually one of the numbers 128, 160, 256, 512, and 1024). Simulation results are presented to demonstrate the suggested hashing scheme’s high sensitivity to the original message and the secret key, as well as its strong capability for confusion and diffusion, and very strong collision resistance. In comparison with existing work, especially those based on chaotic maps, the proposed scheme exhibits superior performance.

In this paper, we present a novel keyed hash function based on a dynamic lookup table of functions. More specifically, we first exploit the piecewise linear chaotic map (PWLCM) with secret keys used for producing four 32-bit initial buffers and then elaborate the lookup table of functions used for selecting composite functions associated with messages. Next, we convert the divided message blocks into ASCII code values, check the equivalent indices and then find the associated composite functions in the lookup table of functions. For each message block, the four buffers are reassigned by the corresponding composite function and then the lookup table of functions is dynamically updated. After all the message blocks are processed, the final 128-bit hash value is obtained by cascading the last reassigned four buffers. Finally, we evaluate our hash function and the results demonstrate that the proposed hash algorithm has good statistical properties, strong collision resistance, high efficiency, and better statistical performance compared with existing chaotic hash functions.

We show that when memory is bounded, i.e. memory buckets are finite, dynamic hash tables that allow insertions and deletions behave significantly worse than their static counterparts that only allow insertions. This behavior differs from previous results in which, when memory is unbounded, the two models behave similarly. We show the decrease in performance in dynamic hash tables using several hash-table schemes. We also provide tight upper and lower bounds on the achievable overflow fractions in these schemes. Finally, we propose an architecture with content-addressable memory (CAM), which mitigates this decrease in performance.

We present a local level-set method based on the hash table data structure, which allows the storage of only a band of grid points adjacent to the interface while providing an O(1) access to the data. We discuss the details of the construction of the hash table data structure as well as the advection and reinitialization schemes used for our implementation of the level-set method. We propose two dimensional numerical examples and compare the results to those obtained with a quadtree data structure. Our study indicates that the method is straightforward to implement but suffers from limitations that make it less efficient than the quadtree data structure.

Building a high performance IP packet forwarding (PF) engine remains a challenge due to increasingly stringent throughput requirements and the growing size of IP forwarding tables. The router has to match the incoming packet's IP address against all entries in the forwarding table. The matching process has to be done at increasingly higher wire speed; hence, scalability and low power consumption are critical for PF engines. Various hash table based schemes have been considered for use in PF engines. Set associative memory can be used for hardware implementations of hash tables with the property that each bucket of a hash table can be searched in a single memory cycle. However, the classic hashing downsides, such as collisions and worst case memory access time have to be dealt with. While open addressing hash tables, in general, provide good average case search performance, their memory utilization and worst case performance can degrade quickly due to collisions (that lead to bucket overflows). The two standard solutions to the overflow problem are either to use predefined probing (e.g., linear or quadratic probing) or to use multiple hash functions. This work presents two new simple hash schemes that extend both aforementioned solutions to tackle the overflow problem efficiently. The first scheme is a hash probing scheme that is called Content-based HAsh Probing (CHAP). As the name suggests, CHAP, based on the content of the hash table, avoids the classical side effects of predefined hash probing methods (i.e., primary and secondary clustering phenomena) and at the same time reduces the overflow. The second scheme, called Progressive Hashing (PH), is a general multiple hash scheme that reduces the overflow as well. The basic idea of PH is to split the prefixes into groups where each group is assigned one hash function, then reuse some hash functions in a progressive fashion to reduce the overflow. Both schemes are amenable to high-performance hardware implementations with low overflow and constant worst-case memory access time. We show by experimenting with real IP lookup tables and synthetic traces that both schemes outperform other existing hashing schemes.

Hash join is used to join large, unordered relations and operates independently of the data distributions of the join relations. Real-world data sets are not uniformly distributed and often contain significant skew. Although partition skew has been studied for hash joins, no prior work has examined how exploiting data skew can improve the performance of hash join. In this paper, we present histojoin, a join algorithm that uses histograms to identify data skew and improve join performance. Experimental results show that for skewed data sets histojoin performs significantly fewer I/O operations and is faster by 10-60% than hybrid hash join.

A novel chaotic hash algorithm based on a network structure formed by 16 chaotic maps is proposed. The original message is first padded with zeros to make the length a multiple of four. Then it is divided into a number of blocks each contains 4 bytes. In the hashing process, the blocks are mixed together by the chaotic map network since the initial value and the control parameter of each tent map are dynamically determined by the output of its neighbors. To enhance the confusion and diffusion effect, the cipher block chaining (CBC) mode is adopted in the algorithm. Theoretic analyses and numerical simulations both show that the proposed hash algorithm possesses good statistical properties, strong collision resistance and high flexibility, as required by practical keyed hash functions.

We consider a two-tier content distribution system for distributing massive content, consisting of an infrastructure content distribution network (CDN) and a large number of ordinary clients. The nodes of the infrastructure network form a structured, distributed-hash-table-based (DHT) peer-to-peer (P2P) network. Each file is first placed in the CDN, and possibly, is replicated among the infrastructure nodes depending on its popularity. In such a system, it is particularly pressing to have proper load-balancing mechanisms to relieve server or network overload. The subject of the paper is on popularity-based file replication techniques within the CDN using multiple hash functions. Our strategy is to set aside a large number of hash functions. When the demand for a file exceeds the overall capacity of the current servers, a previously unused hash function is used to obtain a new node ID where the file will be replicated. The central problems are how to choose an unused hash function when replicating a file and how to choose a used hash function when requesting the file. Our solution to the file replication problem is to choose the unused hash function with the smallest index, and our solution to the file request problem is to choose a used hash function uniformly at random. Our main contribution is that we have developed a set of distributed, robust algorithms to implement the above solutions and we have evaluated their performance. In particular, we have analyzed a random binary search algorithm for file request and a random gap removal algorithm for failure recovery.

In light of recent shift towards shared-memory systems in parallel explicit model checking, we explore relative advantages and disadvantages of shared versus private hash tables. Since usage of shared state storage allows for techniques unavailable in distributed memory, these are evaluated, both theoretically and practically, in a prototype implementation. Experimental data is presented to assess practical utility of those techniques, compared to static partitioning of state space, more traditional in distributed memory algorithms.

Incremental hash functions have gained much attention due to their incremental property, i.e. hashes of updated messages can be speedily computed from previous hashes without having to re-hash the message as was the case in conventional hash functions. In this paper, we first show how collisions can be obtained in such incremental hash functions that are based on pair block chaining, highlighting that more caution should be taken into its design process. We then identify some design and implementation criteria for such incremental hash functions.

Hash tables are one of the most commonly used data structures in computing applications. They are used for example to organize a data set such that searches can be performed efficiently. The data stored in a hash table is commonly stored in memory and can suffer errors. To ensure that data stored in a memory is not corrupted when it suffers errors, Error Correction Codes (ECCs) are commonly used. In this research note a scheme to efficiently implement ECCs for the entries stored in hash tables is presented. The main idea is to use an ECC as the hash function that is used to construct the table. This eliminates the need to store the parity bits for the entries in the memory as they are implicit in the hash table construction thus reducing the implementation cost.

This paper presents a cryptographic key management solution to solve the access control problem in a hierarchy. Based on one-way hash functions, an efficient key assignment and derivation method is proposed. This solution uses limited number of keys and hash functions. Also, the dynamic access control problems, such as adding/deleting nodes, or modifying relationships between nodes in the hierarchy are considered and can be resolved.

Hash functions are used in authentication and cryptography, as well as for the efficient storage and retrieval of data using hashed keys. Hash functions are susceptible to undesirable collisions. To design or choose an appropriate hash function for an application, it is essential to estimate the probabilities with which these collisions can occur. In this paper we consider two problems: one of evaluating the probability of no collision at all and one of finding a bound for the probability of a collision with a particular hash value. The quality of these estimates under various values of the parameters is also discussed.

The 2D-string is one of the important data structures to represent spatial information in images and has been used to perform queries in image database systems. A 2D string can be readily converted to a set of triples which can be used to generate a perfect hash table for indexing the image database. The perfect hash table allows for O(1) retrieval in image database but the computation of the hash table itself, by the fastest heuristic algorithm, is of exponential time complexity. Every time the database is modified, the hash table needs to be recomputed. This limits the use of the hash table to applications where the image database is relatively fixed, such as the ones found on a CD-ROM. In this paper, we present an enhancement of the perfect hash table to allow for insertion and deletion in the hash table. The new hash table allows for a relatively small number of collisions and is called near-perfect hash table . It provides the flexibility of a live database while closely approximating the efficiency of retrieval with the perfect hash table as shown by the asymptotic analysis of the search procedure.

In image database systems, symbolic pictures are represented by two-dimensional (2D) strings that are converted into triples. Each triple is mapped to a unique hash address for timely retrieval of pictures, reducing the pattern-matching problem corresponding to a query to that of computation of a hash function. The values associated with the picture objects are used to compute hash addresses for triples developed from the query. Heuristics are proposed to speed up the computation of the associated values for the picture objects. Experimental results show that the new algorithm achieves almost a 90% gain, in search space, over existing algorithms to compute the associated values.

A new algorithm for generating order preserving minimal perfect hash functions is presented. The algorithm is probabilistic, involving generation of random graphs. It uses expected linear time and requires a linear number of words to represent the hash function, and thus is optimal up to constant factors. It runs very fast in practice.

We consider the operation of permuting in place the records of an open address hash table in order to correspond to a different hashing function. Our emphasis is primarily on minimizing the amount of work space used. Lower and upper bounds are derived on the unrestricted problem, that is, without making any assumptions about the probing discipline used. For the special case of linear probing, we give an algorithm which, in practice, requires no work space outside the table and which runs in linear time with respect to the table size.

This paper gives an input independent average linear time algorithm for storage and retrieval on keys. The algorithm makes a random choice of hash function from a suitable class of hash functions. Given any sequence of inputs the expected time (averaging over all functions in the class) to store and retrieve elements is linear in the length of the sequence. The number of references to the data base required by the algorithm for any input is extremely close to the theoretical minimum for any possible hash function with randomly distributed inputs. We present three suitable classes of hash functions which also can be evaluated rapidly. The ability to analyze the cost of storage and retrieval without worrying about the distribution of the input allows as corollaries improvements on the bounds of several algorithms.

An improvement of open addressing resolution schemes for hash-based files on secondary storage is defined in this paper. Linked hashing exploits the increase in compressibility of a hash file when buckets are larger, given a fixed file allocation. Both average access times and the number of records stored can significantly improve, for large files where the ratio between the key length and the record length is much less than 1.

In all hash methods, the search for a key K starts with the comparison between K and the key L stored in the table position corresponding to the hash address of K. If K ≠ L, the search proceeds through a sequence of cells. We propose here to split this sequence in two parts, to be traceed for K > L or K < L. The advantage of sequence splitting is studied for the hash techniques of chaining, and open addressing. The average numbers of probes for successful and unsuccessful searches are strongly reduced over standard methods, in particular for chaining and linear probing, at the cost of a very modest algorithm complication.