Cryptology ePrint Archive: Report 2009/021

Comparing With RSA

Julien Cathalo and David Naccache and Jean-Jacques Quisquater

Abstract: A multi-set (MS) is a set where an element can occur more than once. MS hash functions (MSHFs) map MSs of arbitrary cardinality to fixed-length strings.

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)

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]