Secure Robust Hash Functions and Their Applications in Non-Interactive Communications

Secure Robust Hash Functions and Their Applications in Non-Interactive Communications

Qiming Li (Institute for Infocomm Research, Singapore) and Sujoy Roy (Institute for Infocomm Research, Singapore)
DOI: 10.4018/978-1-4666-1758-2.ch009


A robust hash function allows different parties to extract a consistent key from a common fuzzy source, e.g., an image gone through noisy channels, which can then be used to establish a cryptographic session key among the parties without the need for interactions. These functions are useful in various communication scenarios, where the security notions are different. The authors study these different security notions in this paper and focus on forgery attacks, where the objective of the attack is to compute the extracted key (hash value) of a given message. This paper will examine information-theoretical security against forgery under chosen message attacks. The authors prove that it is not possible due to the entropy of the hash value of a given message can be reduced arbitrarily when sufficient message/hash pairs have been observed. In this regard, the authors give a computationally secure scheme, where it is computationally infeasible to compute the hash value even when its entropy may not be high.
Chapter Preview

Swaminathan et al. (2006) give a security model for analyzing the security of a robust hash, where they use differential entropy as a measure of security for randomized image features. It is also suggested that the security of a hashing scheme should be measured by the conditional entropy of the hashing key, when the hashing algorithm, and pairs of images and their hashes are known. We formalize this notion and show that such information-theoretic security is impossible.

The robust hash proposed by Swaminathan et al. (2006) is specifically designed for an authentication application. There are existing works that analyze security models for authentication application scenarios. Some examples of proposed scenarios are as follows. Ge et al. (2006) analyze a scenario where sends a message and an approximate message authentication code (AMAC) to for verification. The AMAC serves as a keyed similarity-preserving function. Another scenario as discussed by Li and Chang (2006) is when sends a message, some helper data and a cryptographic MAC to, where the noise during communication can be corrected using the helper data. In both cases, and share a secret key. If public-private key pairs are used instead of secret keys in these scenarios, it would become a digital signature. Another scenario focusing on key extraction is studied by Dodis et al. (2004) where and have access to content and its corrupted version respectively. extracts a key and some helper data which is sent to . uses and the helper data to generate another key , and if and are close enough. In all the above three scenarios there is need for communication between and. In the scenario proposed in this paper there is no communication between and.

Complete Chapter List

Search this Book: