value_type_helpers.h | Explore in Territory

/*
 * Copyright 2021 Google LLC
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *      http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

#ifndef DISTRIBUTED_POINT_FUNCTIONS_DPF_INTERNAL_VALUE_TYPE_HELPERS_H_
#define DISTRIBUTED_POINT_FUNCTIONS_DPF_INTERNAL_VALUE_TYPE_HELPERS_H_

#include <stdint.h>

#include <algorithm>
#include <array>
#include <limits>
#include <string>
#include <tuple>
#include <type_traits>
#include <vector>

#include "absl/base/config.h"
#include "absl/log/absl_check.h"
#include "absl/meta/type_traits.h"
#include "absl/numeric/int128.h"
#include "absl/status/status.h"
#include "absl/status/statusor.h"
#include "absl/strings/str_cat.h"
#include "absl/strings/str_format.h"
#include "absl/strings/string_view.h"
#include "absl/utility/utility.h"
#include "dpf/distributed_point_function.pb.h"
#include "dpf/int_mod_n.h"
#include "dpf/tuple.h"
#include "dpf/xor_wrapper.h"
#include "google/protobuf/repeated_field.h"

// Contains a collection of helper functions for different DPF value types. This
// includes functions for converting between Value protos and the corresponding
// C++ objects, as well as functions for sampling values from uniformly random
// byte strings.
//
// This file contains the templated declarations, instantiations for all
// supported types, as well as type-independent function declarations.
namespace distributed_point_functions {
namespace dpf_internal {

// A helper struct containing declarations for all templated functions we need.
// This is needed since C++ doesn't support partial function template
// specialization, and should be specialized for all supported types.
template <typename T, typename = void>
struct ValueTypeHelper { … };

/******************************************************************************/
// Type traits                                                                //
/******************************************************************************/

// Type trait for all supported types. Used to provide meaningful error messages
// in std::enable_if template guards.
template <typename T>
struct is_supported_type { … };
is_supported_type_v;

// Checks if the template parameter can be converted directly from a string of
// bytes.
template <typename T>
struct can_be_converted_directly { … };
can_be_converted_directly_v;

// Returns the total number of bits in a T.
template <typename T,
          typename = absl::enable_if_t<can_be_converted_directly_v<T>>>
static constexpr int TotalBitSize() { … }

/******************************************************************************/
// Integer Helpers                                                            //
/******************************************************************************/

// Type trait for all integer types we support, i.e., 8 to 128 bit types.
is_unsigned_integer;
is_unsigned_integer_v;

// Converts the given Value::Integer to an absl::uint128. Used as a helper
// function in `ConvertValueTo` and `ValueTypesAreEqual`.
//
// Returns INVALID_ARGUMENT if `in` is not a simple integer or IntModN.
absl::StatusOr<absl::uint128> ValueIntegerToUint128(const Value::Integer& in);

// Converts an absl::uint128 to a Value::Integer. Used as a helper function in
// ToValue.
Value::Integer Uint128ToValueInteger(absl::uint128 input);

// Checks if the given value is in range of T, and if so, returns it converted
// to T.
//
// Otherwise returns INVALID_ARGUMENT.
template <typename T, typename = absl::enable_if_t<is_unsigned_integer_v<T>>>
absl::StatusOr<T> Uint128To(absl::uint128 in) { … }

// Implementation of ValueTypeHelper for integers.
ValueTypeHelper<T, absl::enable_if_t<is_unsigned_integer_v<T>>>;

/******************************************************************************/
// IntModN Helpers                                                            //
/******************************************************************************/

ValueTypeHelper<dpf_internal::IntModNImpl<BaseInteger, ModulusType, kModulus>, void>;

/******************************************************************************/
// Tuple Helpers                                                              //
/******************************************************************************/

// Helper struct for computing the bit size of a tuple type at compile time
// without C++17 fold expressions.
template <typename FirstElementType, typename... ElementType>
struct TupleBitSizeHelper { … };
TupleBitSizeHelper<ElementType>;

ValueTypeHelper<Tuple<ElementType...>, void>;

/******************************************************************************/
// XorWrapper Helpers                                                         //
/******************************************************************************/

ValueTypeHelper<XorWrapper<T>, void>;

/******************************************************************************/
// Free standing helpers. These should always come last. When adding          //
// additional types, add them above.                                          //
/******************************************************************************/

// Computes the number of values of type T that fit into an absl::uint128.
// Returns a value >= 1 if batching is supported, and 1 otherwise.
template <typename T,
          absl::enable_if_t<can_be_converted_directly_v<T>, int> = 0>
constexpr int ElementsPerBlock() { … }
template <typename T,
          absl::enable_if_t<!can_be_converted_directly_v<T>, int> = 0>
constexpr int ElementsPerBlock() { … }

// Creates a value of type T from the given `bytes`. If possible, converts bytes
// directly using DirectlyFromBytes. Otherwise, uses SampleAndUpdateBytes.
//
// Crashes if `bytes.size()` is too small for the output type.
template <typename T,
          absl::enable_if_t<can_be_converted_directly_v<T>, int> = 0>
T FromBytes(absl::string_view bytes) { … }
template <typename T,
          absl::enable_if_t<!can_be_converted_directly_v<T>, int> = 0>
T FromBytes(absl::string_view bytes) { … }

// Converts a `repeated Value` proto field to a std::array with element type T.
//
// Returns INVALID_ARGUMENT in case the input has the wrong size, or if the
// conversion fails.
template <typename T>
absl::StatusOr<std::array<T, ElementsPerBlock<T>()>> ValuesToArray(
    const ::google::protobuf::RepeatedPtrField<Value>& values) { … }

// Converts a given string to an array of exactly ElementsPerBlock<T>() elements
// of type T.
//
// Crashes if `bytes.size()` is too small for the output type.
template <typename T,
          absl::enable_if_t<can_be_converted_directly_v<T>, int> = 0>
std::array<T, ElementsPerBlock<T>()> ConvertBytesToArrayOf(
    absl::string_view bytes) { … }
template <typename T,
          absl::enable_if_t<!can_be_converted_directly_v<T>, int> = 0>
std::array<T, ElementsPerBlock<T>()> ConvertBytesToArrayOf(
    absl::string_view bytes) { … }

// Computes the value correction word given two seeds `seed_a`, `seed_b` for
// parties a and b, such that the element at `block_index` is equal to `beta`.
// If `invert` is true, the result is multiplied element-wise by -1. Templated
// to use the correct integer type without needing modular reduction.
//
// Returns multiple values in case of packing, and a single value otherwise.
template <typename T>
absl::StatusOr<std::vector<Value>> ComputeValueCorrectionFor(
    absl::string_view seed_a, absl::string_view seed_b, int block_index,
    const Value& beta, bool invert) { … }

// Computes the number of pseudorandom bits needed to get a uniform element of
// the given `ValueType`. For types whose elements can be bijectively mapped to
// strings (e.g., unsigned integers and tuples of integers), this is equivalent
// to the bit size of the value type. For all other types, returns the number of
// bits needed so that converting a uniform string with the given number of bits
// to an element of `value_type` results in a distribution with total variation
// distance < 2^(-`security_parameter`) from uniform.
//
// Returns INVALID_ARGUMENT in case value_type does not represent a known type,
// or if sampling with the required security parameter is not possible.
absl::StatusOr<int> BitsNeeded(const ValueType& value_type,
                               double security_parameter);

// Returns `true` if `lhs` and `rhs` describe the same types, and `false`
// otherwise.
//
// Returns INVALID_ARGUMENT if an error occurs while parsing either argument.
absl::StatusOr<bool> ValueTypesAreEqual(const ValueType& lhs,
                                        const ValueType& rhs);

}  // namespace dpf_internal
}  // namespace distributed_point_functions

#endif  // DISTRIBUTED_POINT_FUNCTIONS_DPF_INTERNAL_VALUE_TYPE_HELPERS_H_
chromium/third_party/distributed_point_functions/code/dpf/internal/value_type_helpers.h
