Paper 2014/394

Relational Hash

Avradip Mandal and Arnab Roy

Abstract

Traditional cryptographic hash functions allow one to easily check whether the original plaintexts are equal or not, given a pair of hash values. Probabilistic hash functions extend this concept where given a probabilistic hash of a value and the value itself, one can efficiently check whether the hash corresponds to the given value. However, given distinct probabilistic hashes of the same value it is not possible to check whether they correspond to the same value. In this work we introduce a new cryptographic primitive called \emph{Relational Hash} using which, given a pair of (relational) hash values, one can determine whether the original plaintexts were related or not. We formalize various natural security notions for the Relational Hash primitive - one-wayness, twin one-wayness, unforgeability and oracle simulatibility. We develop a Relational Hash scheme for discovering linear relations among bit-vectors (elements of $\FF_2^n$) and $\FF_p$-vectors. Using the linear Relational Hash schemes we develop Relational Hashes for detecting proximity in terms of hamming distance. The proximity Relational Hashing schemes can be adapted to a privacy preserving biometric identification scheme, as well as a privacy preserving biometric authentication scheme secure against passive adversaries.

Note: This is the full version of the article ``Relational Hash: Probabilistic Hash for Verifying Relations, Secure against Forgery and More'', which appears in proceedings of CRYPTO 2015.

Metadata
Available format(s)
PDF
Publication info
A major revision of an IACR publication in CRYPTO 2015
Keywords
Probabilistic Hash FunctionsFunctional EncryptionBiometric Authentication
Contact author(s)
arnabr @ gmail com
History
2015-06-12: revised
2014-05-30: received
See all versions
Short URL
https://ia.cr/2014/394
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2014/394,
      author = {Avradip Mandal and Arnab Roy},
      title = {Relational Hash},
      howpublished = {Cryptology ePrint Archive, Paper 2014/394},
      year = {2014},
      note = {\url{https://eprint.iacr.org/2014/394}},
      url = {https://eprint.iacr.org/2014/394}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.