src/algorithms/privacy/poisson.h

// Copyright 2022 The Fuchsia Authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.

#ifndef COBALT_SRC_ALGORITHMS_PRIVACY_POISSON_H_
#define COBALT_SRC_ALGORITHMS_PRIVACY_POISSON_H_

#include <random>
#include <vector>

#include "src/algorithms/random/random.h"
#include "src/algorithms/random/strong_types.h"

namespace cobalt {

//
// ApplyPoissonNoise takes a representation of a histogram and draws from a Poisson distribution to
// add to each bucket.
//
// The input should be a zero-one histogram (or bitvector) represented as a list of |indices| of the
// position of the 1 counts, together with the |max_index| of the buckets. (i.e. the total number of
// vectors minus 1).
//
// For example, the histogram [0, 1, 1, 0] is represented as the list |indices| = {1, 2} together
// with |max_index| = 3.
//
// The argument |lambda| is the mean number added to each bucket count. Randomness is obtained from
// |gen|, which must be implemented by a cryptographically secure random number generator.
//
// The output is a list of indices with indices repeated to represent the count of the index bucket.
// Each element of this list is less than or equal to |max_index|.
std::vector<uint64_t> ApplyPoissonNoise(const std::vector<uint64_t>& indices, uint64_t max_index,
                                        PoissonParameter lambda,
                                        SecureBitGeneratorInterface<uint32_t>* gen);

// Given a |raw_count| of set bits from a population of |num_contributions| total contributed bits,
// encoded with a Poisson noise parameter of |lambda|, estimate the true count. The estimated true
// count is not clipped to the valid range. The returned value can be negative or in excess of
// num_contributions.
double DebiasPoissonCount(uint64_t raw_count, uint64_t num_contributions, PoissonParameter lambda);

}  // namespace cobalt

#endif  // COBALT_SRC_ALGORITHMS_PRIVACY_POISSON_H_