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

Abstract

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
Top

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 978-1-4666-1758-2.ch009.m29 sends a message and an approximate message authentication code (AMAC) to 978-1-4666-1758-2.ch009.m30 for verification. The AMAC serves as a keyed similarity-preserving function. Another scenario as discussed by Li and Chang (2006) is when 978-1-4666-1758-2.ch009.m31 sends a message, some helper data and a cryptographic MAC to978-1-4666-1758-2.ch009.m32, where the noise during communication can be corrected using the helper data. In both cases, 978-1-4666-1758-2.ch009.m33 and 978-1-4666-1758-2.ch009.m34 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 978-1-4666-1758-2.ch009.m35 and 978-1-4666-1758-2.ch009.m36 have access to content 978-1-4666-1758-2.ch009.m37 and its corrupted version 978-1-4666-1758-2.ch009.m38 respectively. 978-1-4666-1758-2.ch009.m39 extracts a key 978-1-4666-1758-2.ch009.m40 and some helper data which is sent to 978-1-4666-1758-2.ch009.m41. 978-1-4666-1758-2.ch009.m42 uses 978-1-4666-1758-2.ch009.m43 and the helper data to generate another key 978-1-4666-1758-2.ch009.m44, and 978-1-4666-1758-2.ch009.m45 if 978-1-4666-1758-2.ch009.m46 and 978-1-4666-1758-2.ch009.m47 are close enough. In all the above three scenarios there is need for communication between 978-1-4666-1758-2.ch009.m48 and978-1-4666-1758-2.ch009.m49. In the scenario proposed in this paper there is no communication between 978-1-4666-1758-2.ch009.m50 and978-1-4666-1758-2.ch009.m51.

Complete Chapter List

Search this Book:
Reset