|author||Phillipp Schoppmann <firstname.lastname@example.org>||Mon Nov 29 18:05:44 2021|
|committer||Phillipp Schoppmann <email@example.com>||Mon Nov 29 18:28:12 2021|
Internal change PiperOrigin-RevId: 412917167
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
beta. Evaluating each key on any point
x in the DPF domain results in an additive secret share of
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.