International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Paper: Comparing With RSA

Authors:
Julien Cathalo
David Naccache
Jean-Jacques Quisquater
Download:
URL: http://eprint.iacr.org/2009/021
Search ePrint
Search Google
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.
BibTeX
@misc{eprint-2009-18240,
  title={Comparing With RSA},
  booktitle={IACR Eprint archive},
  keywords={public-key cryptography / RSA, Set Equality Problem},
  url={http://eprint.iacr.org/2009/021},
  note={ david.naccache@ens.fr 14253 received 9 Jan 2009},
  author={Julien Cathalo and David Naccache and Jean-Jacques Quisquater},
  year=2009
}