This library contains an implementation of incremental distributed point functions, based on the following paper:

Boneh, D., Boyle, E., Corrigan-Gibbs, H., Gilboa, N., & Ishai, Y. (2020). Lightweight Techniques for Private Heavy Hitters. arXiv preprint arXiv:2012.14884. https://arxiv.org/abs/2012.14884

A distributed point function (DPF) is parameterized by an index alpha and a value beta. It consists of two algorithms: key generation and evaluation. The key generation procedure produces two keys k_a and k_b, given alpha and beta. Evaluating each key on any point x in the DPF domain results in an additive secret share of beta, if x == alpha, and a share of 0 otherwise.

Incremental DPFs additionally can be evaluated on prefixes of the index domain. More precisely, an incremental DPF is parameterized by a hierarchy of index domains, each a power of two larger than the previous. Key generation now takes a vector beta, one value beta[i] for each hierarchy level. When evaluated on a b-bit prefix of alpha, where b is the log domain size of the i-th hierarchy level, the incremental DPF returns a secret share of beta[i], otherwise a share of 0.

For more details, see the above paper, as well as the DistributedPointFunction class documentation.

This repository requires Bazel. You can install Bazel by following the instructions for your platform on the Bazel website.

Once you have installed Bazel you can clone this repository and run all tests that are included by navigating into the root folder and running:

bazel test //...

To report a security issue, please read SECURITY.md.

This is not an officially supported Google product. The code is provided as-is, with no guarantees of correctness or security.