Paper 2009/021

Comparing With RSA

Julien Cathalo, 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.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Published elsewhere. Unknown where it was published
Keywords
RSASet Equality Problem
Contact author(s)
david naccache @ ens fr
History
2009-01-13: received
Short URL
https://ia.cr/2009/021
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2009/021,
      author = {Julien Cathalo and David Naccache and Jean-Jacques Quisquater},
      title = {Comparing With RSA},
      howpublished = {Cryptology ePrint Archive, Paper 2009/021},
      year = {2009},
      note = {\url{https://eprint.iacr.org/2009/021}},
      url = {https://eprint.iacr.org/2009/021}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.