Skip to content

An Implementation of Incremental Distributed Point Functions in C++

License

Notifications You must be signed in to change notification settings

google/distributed_point_functions

An Implementation of Incremental Distributed Point Functions in C++ Build status

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

About Incremental Distributed Point Functions

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.

Building/Running Tests

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 //...

Security

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

Disclaimer

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

About

An Implementation of Incremental Distributed Point Functions in C++

Resources

License

Code of conduct

Security policy

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published