src/algorithms/privacy/rappor.h

// Copyright 2020 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_RAPPOR_H_
#define COBALT_SRC_ALGORITHMS_PRIVACY_RAPPOR_H_

#include <random>
#include <vector>

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

namespace cobalt {

// Given a representation of a bitvector, ApplyRapporNoise flips each bit of the vector
// independently with some probability and returns the result.
//
// The input bitvector should be represented as a list |indices| of the positions of the "1" bits,
// together with the |max_index| of the vector (i.e., the total length of the vector, minus 1).
//
// For example, the bit vector 01000110 is represented as the list |indices| = {1, 5, 6} together
// with |max_index| = 7.
//
// The argument |p| is the probability that an individual bit is flipped. Randomness is obtained
// from |gen|, which must be implemented by a cryptographically secure random number generator.
//
// The output is a list of the indices of the the "1" bits in the modified bitvector. Each element
// of this list is less than or equal to |max_index|.
std::vector<uint64_t> ApplyRapporNoise(const std::vector<uint64_t>& indices, uint64_t max_index,
                                       double p, SecureBitGeneratorInterface<uint32_t>* gen);

// Given a |raw_count| of set bits from a population of |num_contributions| total contributed bits,
// encoded with a RAPPOR noise parameter of |p|, estimate the true count. (See Erlingsson, Pihur,
// Korolova, "RAPPOR: Randomized Aggregatable Privacy-Preserving Ordinal Response" section 4, taking
// f = 1.) The estimated true count is not clipped to the valid range. The returned value can be
// negative or in excess of num_contributions.
double DebiasRapporCount(uint64_t raw_count, uint64_t num_contributions, double p);

}  // namespace cobalt

#endif  // COBALT_SRC_ALGORITHMS_PRIVACY_RAPPOR_H_