You are looking at a specific version 20140530:123641 of this paper. See the latest version.

Paper 2014/394

Relational Hash

Avradip Mandal and Arnab Roy

Abstract

Traditional cryptographic hash functions allow one to easily check whether the original plain-texts 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 plain-texts were related or not. We formalize various natural security notions for the relational hash primitive - 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 these linear relational hash schemes we develop relational hashes for detecting proximity in terms of hamming distance. These proximity relational hashing scheme can be adapted to a privacy preserving biometric authentication scheme. We also introduce the notion of \emph{relational encryption}, which is a regular semantically secure public key encryption for any adversary which only has access to the public key. However, a semi-trusted entity can be given a relational key using which it can discover relations among ciphertexts, but still cannot decrypt and recover the plaintexts.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Preprint. MINOR revision.
Keywords
Probabilistic Hash FunctionsBiometric AuthenticationFunctional Encryption
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
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.