Cryptology ePrint Archive: Report 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.

Category / Keywords: Probabilistic Hash Functions, Functional Encryption, Biometric Authentication

Original Publication (with major differences): IACR-CRYPTO-2015

Date: received 29 May 2014, last revised 11 Jun 2015

Contact author: arnabr at gmail com

Available format(s): PDF | BibTeX Citation

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.

Version: 20150612:022220 (All versions of this report)

Short URL: ia.cr/2014/394

Discussion forum: Show discussion | Start new discussion