| dc.description | A multiset hash function associates a hash value to arbitrary collections of objects with possible repetitions. Such a hash function is said to be homomorphic, or incremental, when the hash of the union of two collections is easy to compute from the hashes of the two collections themselves: it is usually their sum under a suitable group operation. In particular, hash values of large collections can be computed incrementally and/or in parallel. This makes homomorphic hashing a very useful primitive, with applications ranging from database integrity verification to streaming set/multiset comparison and network coding. Unfortunately, constructions of homomorphic hash functions proposed in the literature are hampered by two main drawbacks. They tend to be much longer than usual hash functions at the same security level (e.g. to achieve a collision resistance of 2128, they are several thousand bits long, as opposed to 256 bits for usual hash functions), and they are also quite slow. In this paper, we introduce the Elliptic Curve Multiset Hash (ECMH), which combines a usual bit string-valued hash function like BLAKE2 with an efficient encoding into binary elliptic curves to overcome both difficulties. On the one hand, the size of ECMH digests is essentially optimal: 2m-bit hash values provide O(2(m)) collision resistance. On the other hand, we demonstrate a highly-efficient software implementation of ECMH, which our thorough empirical evaluation shows to be capable of processing over 3 million set elements per second on a 4 GHz Intel Haswell machine at the 128 bit security level-many times faster than previous practical methods. While incremental hashing based on elliptic curves has been considered previously (Brown, D.R.L. (2008) The encrypted elliptic curve hash. IACR Cryptology ePrint Archive, 2008, 12.), the proposed method was less efficient, susceptible to timing attacks, and potentially patent-encumbered (Brown, D. and Yamada, A. (2007) Method and apparatus for performing validation of elliptic curve public keys. US Patent, 7, 257, 709.), and no practical implementation was demonstrated. | |
