Homomorphic Hashing

Homomorphic hashing in Typescript

Title
Table of Contents
Background
Development
- Benchmarks
- Tests
- Linting
- Docs
Contributing
License
See Also

Background

Bellare, Goldreich, and Goldwasser introduced the concept of an “incremental” (homomorphic) hash function, and subsequently proposed the "randomize-then-combine" paradigm for constructing a set homomorphic (a.k.a. “incremental”) hash function, which was further extended to the multiset hash setting by Clarke et al. For an input set S = {x1,...,xn} ∈ P({0, 1}∗), a commutative group G with operation ◦, and an underlying hash function h : {0, 1}∗ → G modeled as a random oracle, the set homomorphic hash H is defined as H(S) = h(x1) ◦ h(x2) ◦ ··· ◦ h(xn). Using this paradigm, Bellare and Micciancio and others describe various instantiations of H: AdHash, MuHash, and LtHash. AdHash is generally considered impractical due to the extremely large hash code sizes required for sufficient security. Conversely, MuHash has shown a good deal of promise, and is based on multiplication modulo a prime. LtHash is a relatively simple lattice-based alternative to MuHash, though it does have a relatively suboptimal output size compared with some alternatives based on elliptic curves, such as the elliptic curve multiset hash (ECMH).

Usage

import { utf8ToBytes } from "npm:@noble/hashes/utils";
import {
  assert,
  assertEquals,
} from "https://deno.land/std@0.91.0/testing/asserts.ts";
import { RistrettoMultisetHash } from "./ecmh.ts";

Deno.test("main", () => {
  const hash = RistrettoMultisetHash.default();
  const elements = ["apple", "banana", "kiwi"];
  hash.insert(utf8ToBytes(elements[0]));
  hash.insert(utf8ToBytes(elements[1]));
  hash.insert(utf8ToBytes(elements[2]));
  hash.remove(utf8ToBytes(elements[1]));
  const hashBis = RistrettoMultisetHash.default();
  hashBis.insert(utf8ToBytes(elements[0]));
  hashBis.insert(utf8ToBytes(elements[2]));

  assert(hash.equals(hashBis));
  assertEquals(hash.digest(), hashBis.digest());
  assertEquals(hash.digest().byteLength, 32);
});

Development

Benchmarks

TODO

Tests

deno test

Linting

deno lint

Docs

deno doc mod.ts

Auto-deployed to https://carsonfarmer.github.io/hhash-ts/

Contributing

PRs accepted.

Small note: If editing the README, please conform to the standard-readme specification.

License

Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except in compliance with the License. You may obtain a copy of the License at

http://www.apache.org/licenses/LICENSE-2.0

Unless required by applicable law or agreed to in writing, software distributed under the License is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the License for the specific language governing permissions and limitations under the License.

carsonfarmer/hhash-ts