This paper introduces a new RSA-based MSHF. The new function is efficient and produces small hashes. We prove that the proposed MSHF is collision-resistant under the assumption of unforgeability of deterministic RSA signatures.
In many practical applications, programmers need to compare two (unordered) sets of integers. A trivial solution consists in sorting both sets ($\mathcal{O}(n \log n)$) and comparing them linearly. We show how MS hash functions can be turned into a linear-time, constant-space integer set equality test.
Category / Keywords: public-key cryptography / RSA, Set Equality Problem Date: received 9 Jan 2009 Contact author: david naccache at ens fr Available format(s): PDF | BibTeX Citation Version: 20090113:055139 (All versions of this report) Short URL: ia.cr/2009/021 Discussion forum: Show discussion | Start new discussion