Variationally universal hashing

The strongest well-known measure for the quality of a universal hash-function family H is its being ε-strongly universal, which measures, for randomly chosen h ∈ H, one's inability to guess h (m′) even if h (m) is known for some m ≠ m′. We give example applications in which this measure is too...

Full description

Saved in:
Bibliographic Details
Main Authors: Ted Krovetz, Phillip Rogaway
Format: Journal
Published: 2018
Subjects:
Online Access:https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=33745661204&origin=inward
http://cmuir.cmu.ac.th/jspui/handle/6653943832/61605
Tags: Add Tag
No Tags, Be the first to tag this record!
Institution: Chiang Mai University
id th-cmuir.6653943832-61605
record_format dspace
spelling th-cmuir.6653943832-616052018-09-11T08:55:53Z Variationally universal hashing Ted Krovetz Phillip Rogaway Computer Science The strongest well-known measure for the quality of a universal hash-function family H is its being ε-strongly universal, which measures, for randomly chosen h ∈ H, one's inability to guess h (m′) even if h (m) is known for some m ≠ m′. We give example applications in which this measure is too weak, and we introduce a stronger measure for the quality of a hash-function family, ε-variationally universal, which measures one's inability to distinguish h (m′) from a random value even if h (m) is known for some m ≠ m′. We explain the utility of this notion and provide an approach for constructing efficiently computable ε-VU hash-function families. © 2006 Elsevier B.V. All rights reserved. 2018-09-11T08:55:53Z 2018-09-11T08:55:53Z 2006-10-16 Journal 00200190 2-s2.0-33745661204 10.1016/j.ipl.2005.11.026 https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=33745661204&origin=inward http://cmuir.cmu.ac.th/jspui/handle/6653943832/61605
institution Chiang Mai University
building Chiang Mai University Library
country Thailand
collection CMU Intellectual Repository
topic Computer Science
spellingShingle Computer Science
Ted Krovetz
Phillip Rogaway
Variationally universal hashing
description The strongest well-known measure for the quality of a universal hash-function family H is its being ε-strongly universal, which measures, for randomly chosen h ∈ H, one's inability to guess h (m′) even if h (m) is known for some m ≠ m′. We give example applications in which this measure is too weak, and we introduce a stronger measure for the quality of a hash-function family, ε-variationally universal, which measures one's inability to distinguish h (m′) from a random value even if h (m) is known for some m ≠ m′. We explain the utility of this notion and provide an approach for constructing efficiently computable ε-VU hash-function families. © 2006 Elsevier B.V. All rights reserved.
format Journal
author Ted Krovetz
Phillip Rogaway
author_facet Ted Krovetz
Phillip Rogaway
author_sort Ted Krovetz
title Variationally universal hashing
title_short Variationally universal hashing
title_full Variationally universal hashing
title_fullStr Variationally universal hashing
title_full_unstemmed Variationally universal hashing
title_sort variationally universal hashing
publishDate 2018
url https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=33745661204&origin=inward
http://cmuir.cmu.ac.th/jspui/handle/6653943832/61605
_version_ 1681425651845824512