Comparing with RSA
(2009) Cryptography and Coding. 12th IMA International Conference Cryptography and Coding 2009 — Location: Cirencester, UK (15.December.2009)
Files
No attached file found for this publication.
Details
- Authors
- 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 (O(n log n)) and comparing them linearly. We show how MS hash functions can be turned into a quasi-linear-time, quasi-constant-space integer set equality test. An interesting advantage of the proposed algorithm is its ability to compare MSs without sorting them. This can prove useful when comparing very large files which are read-only or otherwise hard to sort (e.g. on tapes, distributed across web-sites etc).
- Affiliations
Citations
Cathalo, J., Quisquater, J.-J., & Naccache, D. (2009). Comparing with RSA. In Parker, M.G.; (ed.), Cryptography and Coding. 12th IMA International Conference Cryptography and Coding 2009 (p. p. 326-335). Springer verlag. https://hdl.handle.net/2078.5/231101