A Fast Incremental Cryptographic Hash Function - Goi , Bok Min (2003)
The current trend in electronic commerce has spurred a need to guarantee the authenticity of data and user as well, in addition to the original objective of cryptography for protecting the data from disclosure. It turns out that fast cryptographic hash functions have been used extensively and become one of the most important cryptographic primitives. Although there are many fast cryptographic hash functions available in the literature, most of them use iterative constructions. They have to re-hash each message from scratch. Consequently they are inefficient for bulk hashing of messages with high similarity. In this project , we propose a new approach to construct a fast cryptographic hash function called Incremental Hash Function based on Pair Chaining and Modular Arithmetic Combining (PCIHF) by using the concept of incremental cryptography . We elaborate the setting of PCIHF which is a randomize-then-combine like paradigm in detail. The proposed PCIHF, using the existing standard hash functions, has some attractive and powerful features, especially incrementality. The time taken for updating the hash value is proportional to the amount of modifications made to the message or constant for certain text modification functions. PCIHF supports a set of message or constant for certain text modification functions. PCIHF supports a set of powerful text modification functions. It also supports multi-message manipulation and multiple blocks update operations. Some work on investigating the efficiency of PCIHF has been done in this project. The practicality of PCIHF has also been examined by comparing with a standard hash function. The security of PCIHF has been analyzed comprehensively. The reason why XOR cannot be chosen as the combining operator has been discussed. We show how the hardness of finding a second pre-image and a collision of PCIHF can be reduced to solving a standard subset sum problem and a weighted subset sum problem respectively . By this, we prove that the proposed PCIHF is not only universal oneway but also collision-free. Furthermore, since PCIHF gives a fixed size final hash value, no information is leaked during the updating process.