Internal change

PiperOrigin-RevId: 391593021
diff --git a/dcf/BUILD b/dcf/BUILD
new file mode 100644
index 0000000..4087937
--- /dev/null
+++ b/dcf/BUILD
@@ -0,0 +1,46 @@
+load("@io_bazel_rules_go//proto:def.bzl", "go_proto_library")
+load("@rules_cc//cc:defs.bzl", "cc_library")
+load("@rules_proto//proto:defs.bzl", "proto_library")
+
+package(
+    default_visibility = ["//:__subpackages__"],
+)
+
+licenses(["notice"])
+
+cc_library(
+    name = "distributed_comparison_function",
+    srcs = ["distributed_comparison_function.cc"],
+    hdrs = ["distributed_comparison_function.h"],
+    deps = [
+        ":distributed_comparison_function_cc_proto",
+        "//dpf:distributed_point_function",
+        "//dpf:distributed_point_function_cc_proto",
+        "//dpf:status_macros",
+        "@com_google_absl//absl/status:statusor",
+    ],
+)
+
+proto_library(
+    name = "distributed_comparison_function_proto",
+    srcs = ["distributed_comparison_function.proto"],
+    deps = [
+        "//dpf:distributed_point_function_proto",
+    ],
+)
+
+cc_proto_library(
+    name = "distributed_comparison_function_cc_proto",
+    deps = [":distributed_comparison_function_proto"],
+)
+
+cc_test(
+    name = "distributed_comparison_function_test",
+    srcs = ["distributed_comparison_function_test.cc"],
+    deps = [
+        ":distributed_comparison_function",
+        "//dpf/internal:status_matchers",
+        "@com_github_google_googletest//:gtest_main",
+        "@com_google_absl//absl/random",
+    ],
+)
diff --git a/dcf/distributed_comparison_function.cc b/dcf/distributed_comparison_function.cc
new file mode 100644
index 0000000..798a77e
--- /dev/null
+++ b/dcf/distributed_comparison_function.cc
@@ -0,0 +1,102 @@
+// 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.
+
+#include "third_party/distributed_point_functions/dcf/distributed_comparison_function.h"
+
+#include "third_party/distributed_point_functions/dpf/status_macros.h"
+
+namespace distributed_point_functions {
+
+namespace {
+
+void SetToZero(Value& value) {
+  if (value.value_case() == Value::kInteger) {
+    value.mutable_integer()->set_value_uint64(0);
+  } else if (value.value_case() == Value::kIntModN) {
+    value.mutable_int_mod_n()->set_value_uint64(0);
+  } else if (value.value_case() == Value::kTuple) {
+    for (int i = 0; i < value.tuple().elements_size(); ++i) {
+      SetToZero(*(value.mutable_tuple()->mutable_elements(i)));
+    }
+  }
+}
+
+}  // namespace
+
+DistributedComparisonFunction::DistributedComparisonFunction(
+    DcfParameters parameters, std::unique_ptr<DistributedPointFunction> dpf)
+    : parameters_(std::move(parameters)), dpf_(std::move(dpf)) {}
+
+absl::StatusOr<std::unique_ptr<DistributedComparisonFunction>>
+DistributedComparisonFunction::Create(const DcfParameters& parameters) {
+  // A DCF with a single-element domain doesn't make sense.
+  if (parameters.parameters().log_domain_size() < 1) {
+    return absl::InvalidArgumentError("A DCF must have log_domain_size >= 1");
+  }
+
+  // We don't support the legacy element_bitsize field in DCFs.
+  if (!parameters.parameters().has_value_type()) {
+    return absl::InvalidArgumentError(
+        "parameters.value_type must be set for "
+        "DistributedComparisonFunction::Create");
+  }
+
+  // Create parameter vector for the incremental DPF.
+  std::vector<DpfParameters> dpf_parameters(
+      parameters.parameters().log_domain_size());
+  for (int i = 0; i < static_cast<int>(dpf_parameters.size()); ++i) {
+    dpf_parameters[i].set_log_domain_size(i);
+    *(dpf_parameters[i].mutable_value_type()) =
+        parameters.parameters().value_type();
+  }
+
+  // Check that parameters are valid. We can use the DPF proto validator
+  // directly.
+  DPF_RETURN_IF_ERROR(
+      dpf_internal::ProtoValidator::ValidateParameters(dpf_parameters));
+
+  // Create incremental DPF.
+  DPF_ASSIGN_OR_RETURN(
+      std::unique_ptr<DistributedPointFunction> dpf,
+      DistributedPointFunction::CreateIncremental(dpf_parameters));
+
+  return absl::WrapUnique(
+      new DistributedComparisonFunction(parameters, std::move(dpf)));
+}
+
+absl::StatusOr<std::pair<DcfKey, DcfKey>>
+DistributedComparisonFunction::GenerateKeys(absl::uint128 alpha,
+                                            const Value& beta) {
+  const int log_domain_size = parameters_.parameters().log_domain_size();
+  std::vector<Value> dpf_values(log_domain_size, beta);
+  for (int i = 0; i < log_domain_size; ++i) {
+    // beta_i = 0 if alpha_i == 0, and beta otherwise.
+    bool current_bit =
+        (alpha & (absl::uint128{1} << (log_domain_size - i - 1))) != 0;
+    if (!current_bit) {
+      SetToZero(dpf_values[i]);
+    }
+  }
+
+  std::pair<DcfKey, DcfKey> result;
+  DPF_ASSIGN_OR_RETURN(
+      std::tie(*(result.first.mutable_key()), *(result.second.mutable_key())),
+      dpf_->GenerateKeysIncremental(
+          alpha >> 1,  // We can ignore the last bit of alpha, since it is
+                       // encoded in dpf_values.back().
+          dpf_values));
+  return result;
+}
+
+}  // namespace distributed_point_functions
diff --git a/dcf/distributed_comparison_function.h b/dcf/distributed_comparison_function.h
new file mode 100644
index 0000000..0d9885c
--- /dev/null
+++ b/dcf/distributed_comparison_function.h
@@ -0,0 +1,124 @@
+/*
+ * 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 THIRD_PARTY_DISTRIBUTED_POINT_FUNCTIONS_DCF_DISTRIBUTED_COMPARISON_FUNCTION_H_
+#define THIRD_PARTY_DISTRIBUTED_POINT_FUNCTIONS_DCF_DISTRIBUTED_COMPARISON_FUNCTION_H_
+
+#include <memory>
+
+#include "third_party/absl/status/statusor.h"
+#include "third_party/distributed_point_functions/dcf/distributed_comparison_function.proto.h"
+#include "third_party/distributed_point_functions/dpf/distributed_point_function.h"
+#include "third_party/distributed_point_functions/dpf/distributed_point_function.proto.h"
+
+namespace distributed_point_functions {
+
+class DistributedComparisonFunction {
+ public:
+  static absl::StatusOr<std::unique_ptr<DistributedComparisonFunction>> Create(
+      const DcfParameters& parameters);
+
+  // Creates keys for a DCF that evaluates to shares of `beta` on any input x <
+  // `alpha`, and shares of 0 otherwise.
+  //
+  // Returns INVALID_ARGUMENT if `alpha` or `beta` do not match the
+  // DcfParameters passed at construction.
+  //
+  // Overload for explicit Value proto.
+  absl::StatusOr<std::pair<DcfKey, DcfKey>> GenerateKeys(absl::uint128 alpha,
+                                                         const Value& beta);
+
+  // Template for automatic conversion to Value proto. Disabled if the argument
+  // is convertible to `absl::uint128` or `Value` to make overloading
+  // unambiguous.
+  template <typename T,
+            typename = std::enable_if_t<!std::is_convertible_v<T, Value> &&
+                                        dpf_internal::is_supported_type_v<T>>>
+  absl::StatusOr<std::pair<DcfKey, DcfKey>> GenerateKeys(absl::uint128 alpha,
+                                                         const T& beta) {
+    absl::StatusOr<Value> value = dpf_->ToValue(beta);
+    if (!value.ok()) {
+      return value.status();
+    }
+    return GenerateKeys(alpha, *value);
+  }
+
+  // Evaluates a DcfKey at the given point `x`.
+  //
+  // Returns INVALID_ARGUMENT if `key` or `x` do not match the parameters passed
+  // at construction.
+  template <typename T>
+  absl::StatusOr<T> Evaluate(const DcfKey& key, absl::uint128 x);
+
+  // DistributedComparisonFunction is neither copyable nor movable.
+  DistributedComparisonFunction(const DistributedComparisonFunction&) = delete;
+  DistributedComparisonFunction& operator=(
+      const DistributedComparisonFunction&) = delete;
+
+ private:
+  DistributedComparisonFunction(DcfParameters parameters,
+                                std::unique_ptr<DistributedPointFunction> dpf);
+
+  const DcfParameters parameters_;
+  const std::unique_ptr<DistributedPointFunction> dpf_;
+};
+
+// Implementation details.
+
+template <typename T>
+absl::StatusOr<T> DistributedComparisonFunction::Evaluate(const DcfKey& key,
+                                                          absl::uint128 x) {
+  const int log_domain_size = parameters_.parameters().log_domain_size();
+  T result{};
+
+  absl::StatusOr<EvaluationContext> ctx =
+      dpf_->CreateEvaluationContext(key.key());
+  if (!ctx.ok()) {
+    return ctx.status();
+  }
+
+  int previous_bit = 0;
+  for (int i = 0; i < log_domain_size; ++i) {
+    absl::StatusOr<std::vector<T>> expansion_i;
+    if (i == 0) {
+      expansion_i = dpf_->EvaluateNext<T>({}, *ctx);
+    } else {
+      absl::uint128 prefix = 0;
+      if (log_domain_size < 128) {
+        prefix = x >> (log_domain_size - i + 1);
+      }
+      expansion_i =
+          dpf_->EvaluateNext<T>(absl::MakeConstSpan(&prefix, 1), *ctx);
+    }
+    if (!expansion_i.ok()) {
+      return expansion_i.status();
+    }
+
+    int current_bit = static_cast<int>(
+        (x & (absl::uint128{1} << (log_domain_size - i - 1))) != 0);
+    // We only add the current value along the path if the current bit of x is
+    // 0.
+    if (current_bit == 0) {
+      result += (*expansion_i)[previous_bit];
+    }
+    previous_bit = current_bit;
+  }
+  return result;
+}
+
+}  // namespace distributed_point_functions
+
+#endif  // THIRD_PARTY_DISTRIBUTED_POINT_FUNCTIONS_DCF_DISTRIBUTED_COMPARISON_FUNCTION_H_
diff --git a/dcf/distributed_comparison_function.proto b/dcf/distributed_comparison_function.proto
new file mode 100644
index 0000000..3bec71a
--- /dev/null
+++ b/dcf/distributed_comparison_function.proto
@@ -0,0 +1,32 @@
+// 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.
+
+syntax = "proto3";
+
+package distributed_point_functions;
+
+import "third_party/distributed_point_functions/dpf/distributed_point_function.proto";
+
+// For faster allocations of sub-messages.
+option cc_enable_arenas = true;
+
+// The parameters for a DCF have the same form as for a DPF.
+message DcfParameters {
+  DpfParameters parameters = 1;
+}
+
+// A DCF key is just a special DpfKey.
+message DcfKey {
+  DpfKey key = 1;
+}
\ No newline at end of file
diff --git a/dcf/distributed_comparison_function_test.cc b/dcf/distributed_comparison_function_test.cc
new file mode 100644
index 0000000..e16029a
--- /dev/null
+++ b/dcf/distributed_comparison_function_test.cc
@@ -0,0 +1,178 @@
+// 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.
+
+#include "third_party/distributed_point_functions/dcf/distributed_comparison_function.h"
+
+#include "testing/base/public/gmock.h"
+#include "testing/base/public/gunit.h"
+#include "third_party/absl/random/random.h"
+#include "third_party/distributed_point_functions/dpf/internal/status_matchers.h"
+
+namespace distributed_point_functions {
+
+namespace {
+
+// Helper function that recursively sets all elements of a tuple to 42.
+template <typename T0>
+static void SetTo42(T0& x) {
+  x = T0(42);
+}
+template <typename T0, typename... Tn>
+static void SetTo42(T0& x0, Tn&... xn) {
+  SetTo42(x0);
+  SetTo42(xn...);
+}
+template <typename... Tn>
+static void SetTo42(Tuple<Tn...>& x) {
+  std::apply([](auto&... in) { SetTo42(in...); }, x.value());
+}
+
+TEST(DcfTest, CreateFailsWithZeroLogDomainSize) {
+  DcfParameters parameters;
+  parameters.mutable_parameters()
+      ->mutable_value_type()
+      ->mutable_integer()
+      ->set_bitsize(32);
+
+  parameters.mutable_parameters()->set_log_domain_size(0);
+
+  EXPECT_THAT(DistributedComparisonFunction::Create(parameters),
+              dpf_internal::StatusIs(absl::StatusCode::kInvalidArgument,
+                                     "A DCF must have log_domain_size >= 1"));
+}
+
+template <typename T, int log_domain_size>
+class DcfTestParameters {
+ public:
+  using ValueType = T;
+  static constexpr int kLogDomainSize = log_domain_size;
+};
+
+template <typename T>
+struct DcfTest : public testing::Test {
+  void SetUp() {
+    DcfParameters parameters;
+    parameters.mutable_parameters()->set_log_domain_size(T::kLogDomainSize);
+    *(parameters.mutable_parameters()->mutable_value_type()) =
+        dpf_internal::ToValueType<typename T::ValueType>();
+
+    DPF_ASSERT_OK_AND_ASSIGN(dcf_,
+                             DistributedComparisonFunction::Create(parameters));
+  }
+
+  std::unique_ptr<DistributedComparisonFunction> dcf_;
+};
+
+using MyIntModN = IntModN<uint32_t, 4294967291u>;  // 2**32 - 5.
+using DcfTestTypes = ::testing::Types<
+    DcfTestParameters<uint32_t, 1>, DcfTestParameters<uint32_t, 2>,
+    DcfTestParameters<uint32_t, 5>, DcfTestParameters<absl::uint128, 5>,
+    DcfTestParameters<Tuple<uint32_t, uint32_t>, 5>,
+    DcfTestParameters<Tuple<uint32_t, absl::uint128>, 5>,
+    DcfTestParameters<Tuple<MyIntModN, MyIntModN>, 5> >;
+
+TYPED_TEST_SUITE(DcfTest, DcfTestTypes);
+
+TYPED_TEST(DcfTest, CreateWorks) {
+  EXPECT_THAT(this->dcf_, testing::Ne(nullptr));
+}
+
+TYPED_TEST(DcfTest, GenEval) {
+  using ValueType = typename TypeParam::ValueType;
+  const absl::uint128 domain_size = absl::uint128{1}
+                                    << TypeParam::kLogDomainSize;
+  ValueType beta;
+  SetTo42(beta);
+  for (absl::uint128 alpha = 0; alpha < domain_size; ++alpha) {
+    // Generate keys.
+    DcfKey key_0, key_1;
+    DPF_ASSERT_OK_AND_ASSIGN(std::tie(key_0, key_1),
+                             this->dcf_->GenerateKeys(alpha, beta));
+
+    // Evaluate on every point in the domain.
+    for (absl::uint128 x = 0; x < domain_size; ++x) {
+      DPF_ASSERT_OK_AND_ASSIGN(
+          ValueType result_0,
+          this->dcf_->template Evaluate<ValueType>(key_0, x));
+      DPF_ASSERT_OK_AND_ASSIGN(
+          ValueType result_1,
+          this->dcf_->template Evaluate<ValueType>(key_1, x));
+      if (x < alpha) {
+        EXPECT_EQ(ValueType(result_0 + result_1), beta)
+            << "x=" << x << ", alpha=" << alpha;
+      } else {
+        EXPECT_EQ(ValueType(result_0 + result_1), ValueType{})
+            << "x=" << x << ", alpha=" << alpha;
+      }
+    }
+  }
+}
+
+TEST(DcfTest, WorksCorrectlyOnUint64TWithLargeDomain) {
+  using ValueType = uint64_t;
+  const absl::uint128 domain_size = absl::uint128{1} << 64;
+  ValueType beta;
+  SetTo42(beta);
+  absl::uint128 alpha = 50;
+
+  DcfParameters parameters;
+  parameters.mutable_parameters()->set_log_domain_size(64);
+  *(parameters.mutable_parameters()->mutable_value_type()) =
+      dpf_internal::ToValueType<uint64_t>();
+
+  DPF_ASSERT_OK_AND_ASSIGN(auto dcf,
+                           DistributedComparisonFunction::Create(parameters));
+
+  // Generate keys.
+  DcfKey key_0, key_1;
+  DPF_ASSERT_OK_AND_ASSIGN(std::tie(key_0, key_1),
+                           dcf->GenerateKeys(alpha, beta));
+
+  // Evaluate on every point in the domain smaller than alpha.
+  for (absl::uint128 x = 0; x < alpha; ++x) {
+    DPF_ASSERT_OK_AND_ASSIGN(ValueType result_0,
+                             dcf->template Evaluate<ValueType>(key_0, x));
+    DPF_ASSERT_OK_AND_ASSIGN(ValueType result_1,
+                             dcf->template Evaluate<ValueType>(key_1, x));
+    EXPECT_EQ(ValueType(result_0 + result_1), beta)
+        << "x=" << x << ", alpha=" << alpha;
+  }
+
+  // Evaluate on 100 random points in the domain.
+  absl::BitGen rng;
+  absl::uniform_int_distribution<uint64_t> dist;
+  const int kNumEvaluationPoints = 100;
+  std::vector<absl::uint128> evaluation_points(kNumEvaluationPoints);
+  for (int i = 0; i < kNumEvaluationPoints - 1; ++i) {
+    evaluation_points[i] =
+        absl::MakeUint128(dist(rng), dist(rng)) % domain_size;
+    DPF_ASSERT_OK_AND_ASSIGN(
+        uint64_t result_0,
+        dcf->template Evaluate<ValueType>(key_0, evaluation_points[i]));
+    DPF_ASSERT_OK_AND_ASSIGN(
+        ValueType result_1,
+        dcf->template Evaluate<ValueType>(key_1, evaluation_points[i]));
+    if (evaluation_points[i] < alpha) {
+      EXPECT_EQ(ValueType(result_0 + result_1), beta)
+          << "x=" << evaluation_points[i] << ", alpha=" << alpha;
+    } else {
+      EXPECT_EQ(ValueType(result_0 + result_1), ValueType{})
+          << "x=" << evaluation_points[i] << ", alpha=" << alpha;
+    }
+  }
+}
+
+}  // namespace
+
+}  // namespace distributed_point_functions
diff --git a/dcf/fss_gates/BUILD b/dcf/fss_gates/BUILD
new file mode 100644
index 0000000..ca4f1a4
--- /dev/null
+++ b/dcf/fss_gates/BUILD
@@ -0,0 +1,71 @@
+# This package contains implementation of various Function Secret Sharing (FSS)
+# gates as specified in https://eprint.iacr.org/2020/1392. The implementation
+# uses the Distributed Comparison Function (as implemented in
+# distributed_comparison_function.cc) as a central component.
+
+load("@io_bazel_rules_go//proto:def.bzl", "go_proto_library")
+load("@rules_cc//cc:defs.bzl", "cc_library")
+load("@rules_proto//proto:defs.bzl", "proto_library")
+
+package_group(
+    name = "allowlist",
+    packages = [
+        "//...",
+        "//privacy/blinders/cpp/...",
+        "//third_party/privacy_sandbox_aggregation/...",
+    ],
+)
+
+package(
+    default_visibility = [":allowlist"],
+)
+
+licenses(["notice"])
+
+# Multiple Interval Containment
+
+cc_library(
+    name = "multiple_interval_containment",
+    srcs = ["multiple_interval_containment.cc"],
+    hdrs = ["multiple_interval_containment.h"],
+    deps = [
+        ":multiple_interval_containment_cc_proto",
+        "//dcf:distributed_comparison_function",
+        "//dpf:distributed_point_function_cc_proto",
+        "//dpf:status_macros",
+        "//prng:basic_rng",
+        "@com_google_absl//absl/numeric:int128",
+        "@com_google_absl//absl/status",
+        "@com_google_absl//absl/status:statusor",
+    ],
+)
+
+proto_library(
+    name = "multiple_interval_containment_proto",
+    srcs = ["multiple_interval_containment.proto"],
+    deps = [
+        "//dcf:distributed_comparison_function_proto",
+        "//dpf:distributed_point_function_proto",
+    ],
+)
+
+cc_proto_library(
+    name = "multiple_interval_containment_cc_proto",
+    deps = [":multiple_interval_containment_proto"],
+)
+
+cc_test(
+    name = "multiple_interval_containment_test",
+    srcs = ["multiple_interval_containment_test.cc"],
+    deps = [
+        ":multiple_interval_containment",
+        ":multiple_interval_containment_cc_proto",
+        "//dpf:distributed_point_function_cc_proto",
+        "//dpf:status_macros",
+        "//dpf/internal:status_matchers",
+        "//dpf/internal:value_type_helpers",
+        "//prng:basic_rng",
+        "@com_github_google_googletest//:gtest_main",
+        "@com_google_absl//absl/numeric:int128",
+    ],
+)
diff --git a/dcf/fss_gates/multiple_interval_containment.cc b/dcf/fss_gates/multiple_interval_containment.cc
new file mode 100644
index 0000000..c8553ec
--- /dev/null
+++ b/dcf/fss_gates/multiple_interval_containment.cc
@@ -0,0 +1,278 @@
+// 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.
+
+#include "third_party/distributed_point_functions/dcf/fss_gates/multiple_interval_containment.h"
+
+#include <utility>
+
+#include "third_party/absl/numeric/int128.h"
+#include "third_party/absl/status/status.h"
+#include "third_party/absl/status/statusor.h"
+#include "third_party/distributed_point_functions/dcf/distributed_comparison_function.h"
+#include "third_party/distributed_point_functions/dcf/fss_gates/multiple_interval_containment.proto.h"
+#include "third_party/distributed_point_functions/dpf/distributed_point_function.proto.h"
+#include "third_party/distributed_point_functions/dpf/status_macros.h"
+#include "third_party/distributed_point_functions/prng/basic_rng.h"
+
+namespace distributed_point_functions {
+namespace fss_gates {
+
+absl::StatusOr<std::unique_ptr<MultipleIntervalContainmentGate>>
+MultipleIntervalContainmentGate::Create(const MicParameters& mic_parameters) {
+  // Declaring the parameters for a Distributed Comparison Function (DCF).
+  DcfParameters dcf_parameters;
+
+  // Return error if log_group_size is not between 0 and 127.
+  if (mic_parameters.log_group_size() < 0 ||
+      mic_parameters.log_group_size() > 127) {
+    return absl::InvalidArgumentError(
+        "log_group_size should be in > 0 and < 128");
+  }
+
+  // Setting N = 2 ^ log_group_size.
+  absl::uint128 N = absl::uint128(1) << mic_parameters.log_group_size();
+
+  for (int i = 0; i < mic_parameters.intervals_size(); i++) {
+    // Return error if some interval is empty.
+    if (!mic_parameters.intervals(i).has_lower_bound() ||
+        !mic_parameters.intervals(i).has_upper_bound()) {
+      return absl::InvalidArgumentError("Intervals should be non-empty");
+    }
+
+    absl::uint128 p = absl::MakeUint128(
+        mic_parameters.intervals(i).lower_bound().value_uint128().high(),
+        mic_parameters.intervals(i).lower_bound().value_uint128().low());
+
+    absl::uint128 q = absl::MakeUint128(
+        mic_parameters.intervals(i).upper_bound().value_uint128().high(),
+        mic_parameters.intervals(i).upper_bound().value_uint128().low());
+
+    // Return error if the intervals are not valid group elements.
+    if (p < 0 || p >= N) {
+      return absl::InvalidArgumentError(
+          "Interval bounds should be between 0 and 2^log_group_size");
+    }
+
+    // Return error if the intervals are not valid group elements.
+    if (q < 0 || q >= N) {
+      return absl::InvalidArgumentError(
+          "Interval bounds should be between 0 and 2^log_group_size");
+    }
+
+    // Return error if lower bound of an interval is less that its
+    // upper bound.
+    if (p > q) {
+      return absl::InvalidArgumentError(
+          "Interval upper bounds should be >= lower bound");
+    }
+  }
+
+  // Setting the `log_domain_size` of the DCF to be same as the
+  // `log_group_size` of the Multiple Interval Containment Gate.
+  dcf_parameters.mutable_parameters()->set_log_domain_size(
+      mic_parameters.log_group_size());
+
+  // Setting the output ValueType of the DCF so that it can store 128 bit
+  // integers.
+  *(dcf_parameters.mutable_parameters()->mutable_value_type()) =
+      dpf_internal::ToValueType<absl::uint128>();
+
+  // Creating a DCF with appropriate parameters.
+  DPF_ASSIGN_OR_RETURN(std::unique_ptr<DistributedComparisonFunction> dcf,
+                       DistributedComparisonFunction::Create(dcf_parameters));
+
+  return absl::WrapUnique(
+      new MultipleIntervalContainmentGate(mic_parameters, std::move(dcf)));
+}
+
+MultipleIntervalContainmentGate::MultipleIntervalContainmentGate(
+    MicParameters mic_parameters,
+    std::unique_ptr<DistributedComparisonFunction> dcf)
+    : mic_parameters_(std::move(mic_parameters)), dcf_(std::move(dcf)) {}
+
+absl::StatusOr<std::pair<MicKey, MicKey>> MultipleIntervalContainmentGate::Gen(
+    absl::uint128 r_in, std::vector<absl::uint128> r_out) {
+  if (r_out.size() != mic_parameters_.intervals_size()) {
+    return absl::InvalidArgumentError(
+        "Count of output masks should be equal to the number of intervals");
+  }
+
+  // Setting N = 2 ^ log_group_size.
+  absl::uint128 N = absl::uint128(1) << mic_parameters_.log_group_size();
+
+  // Checking whether r_in is a group element.
+  if (r_in < 0 || r_in >= N) {
+    return absl::InvalidArgumentError(
+        "Input mask should be between 0 and 2^log_group_size");
+  }
+
+  // Checking whether each element of r_out is a group element.
+  for (int i = 0; i < r_out.size(); i++) {
+    if (r_out[i] < 0 || r_out[i] >= N) {
+      return absl::InvalidArgumentError(
+          "Output mask should be between 0 and 2^log_group_size");
+    }
+  }
+
+  // The following code is commented using their Line numbering in
+  // https://eprint.iacr.org/2020/1392 Fig. 14 Gen procedure.
+
+  // Line 1
+  absl::uint128 gamma = (N - 1 + r_in) % N;
+
+  // Line 2
+
+  DcfKey key_0, key_1;
+
+  absl::uint128 alpha = gamma;
+  absl::uint128 beta = 1;
+
+  DPF_ASSIGN_OR_RETURN(std::tie(key_0, key_1),
+                       this->dcf_->GenerateKeys(alpha, beta));
+
+  MicKey k0, k1;
+
+  // Part of Line 7
+  *(k0.mutable_dcfkey()) = key_0;
+  *(k1.mutable_dcfkey()) = key_1;
+
+  // Line 3
+  for (int i = 0; i < mic_parameters_.intervals_size(); i++) {
+    absl::uint128 p = absl::MakeUint128(
+        mic_parameters_.intervals(i).lower_bound().value_uint128().high(),
+        mic_parameters_.intervals(i).lower_bound().value_uint128().low());
+
+    absl::uint128 q = absl::MakeUint128(
+        mic_parameters_.intervals(i).upper_bound().value_uint128().high(),
+        mic_parameters_.intervals(i).upper_bound().value_uint128().low());
+
+    // Line 4
+    absl::uint128 q_prime = (q + 1) % N;
+
+    absl::uint128 alpha_p = (p + r_in) % N;
+
+    absl::uint128 alpha_q = (q + r_in) % N;
+
+    absl::uint128 alpha_q_prime = (q + 1 + r_in) % N;
+
+    // Line 5 - This computes the correction term for the output of the gate,
+    // and the logic and proof of its correctness is described in
+    // https://eprint.iacr.org/2020/1392 Lemma 1, Lemma 2 and Theorem 3.
+    absl::uint128 z =
+        r_out[i] + (alpha_p > alpha_q ? 1 : 0) + (alpha_p > p ? -1 : 0) +
+        (alpha_q_prime > q_prime ? 1 : 0) + (alpha_q == (N - 1) ? 1 : 0);
+    z = z % N;
+
+    const absl::string_view kSampleSeed = absl::string_view();
+    DPF_ASSIGN_OR_RETURN(
+        auto rng, distributed_point_functions::BasicRng::Create(kSampleSeed));
+    DPF_ASSIGN_OR_RETURN(absl::uint128 z_0, rng->Rand128());
+
+    z_0 = z_0 % N;
+
+    absl::uint128 z_1 = (z - z_0) % N;
+
+    // Part of Line 7
+    Value_Integer* k0_output_mask_share = k0.add_output_mask_share();
+
+    k0_output_mask_share->mutable_value_uint128()->set_high(
+        absl::Uint128High64(z_0));
+    k0_output_mask_share->mutable_value_uint128()->set_low(
+        absl::Uint128Low64(z_0));
+
+    Value_Integer* k1_output_mask_share = k1.add_output_mask_share();
+
+    k1_output_mask_share->mutable_value_uint128()->set_high(
+        absl::Uint128High64(z_1));
+    k1_output_mask_share->mutable_value_uint128()->set_low(
+        absl::Uint128Low64(z_1));
+  }
+
+  // Line 8
+  return std::pair<MicKey, MicKey>(k0, k1);
+}
+
+absl::StatusOr<std::vector<absl::uint128>>
+MultipleIntervalContainmentGate::Eval(MicKey k, absl::uint128 x) {
+  // Setting N = 2 ^ log_group_size
+  absl::uint128 N = absl::uint128(1) << mic_parameters_.log_group_size();
+
+  // Checking whether x is a group element
+  if (x < 0 || x >= N) {
+    return absl::InvalidArgumentError(
+        "Masked input should be between 0 and 2^log_group_size");
+  }
+
+  std::vector<absl::uint128> res;
+
+  // The following code is commented using their Line numbering in
+  // https://eprint.iacr.org/2020/1392 Fig. 14 Eval procedure.
+
+  // Line 2
+  for (int i = 0; i < mic_parameters_.intervals_size(); i++) {
+    absl::uint128 p = absl::MakeUint128(
+        mic_parameters_.intervals(i).lower_bound().value_uint128().high(),
+        mic_parameters_.intervals(i).lower_bound().value_uint128().low());
+
+    absl::uint128 q = absl::MakeUint128(
+        mic_parameters_.intervals(i).upper_bound().value_uint128().high(),
+        mic_parameters_.intervals(i).upper_bound().value_uint128().low());
+
+    // Line 3
+
+    absl::uint128 q_prime = (q + 1) % N;
+
+    // Line 4
+    absl::uint128 x_p = (x + N - 1 - p) % N;
+
+    absl::uint128 x_q_prime = (x + N - 1 - q_prime) % N;
+
+    // Line 5
+
+    absl::uint128 s_p;
+
+    DPF_ASSIGN_OR_RETURN(s_p, dcf_->Evaluate<absl::uint128>(k.dcfkey(), x_p));
+
+    s_p = s_p % N;
+
+    // Line 6
+
+    absl::uint128 s_q_prime;
+
+    DPF_ASSIGN_OR_RETURN(s_q_prime,
+                         dcf_->Evaluate<absl::uint128>(k.dcfkey(), x_q_prime));
+
+    s_q_prime = s_q_prime % N;
+
+    // Line 7
+
+    absl::uint128 y;
+
+    absl::uint128 z =
+        absl::MakeUint128(k.output_mask_share(i).value_uint128().high(),
+                          k.output_mask_share(i).value_uint128().low());
+
+    y = (k.dcfkey().key().party() ? ((x > p ? 1 : 0) - (x > q_prime ? 1 : 0))
+                                  : 0) -
+        s_p + s_q_prime + z;
+
+    res.push_back(y % N);
+  }
+
+  // Line 9
+  return res;
+}
+
+}  // namespace fss_gates
+}  // namespace distributed_point_functions
diff --git a/dcf/fss_gates/multiple_interval_containment.h b/dcf/fss_gates/multiple_interval_containment.h
new file mode 100644
index 0000000..863a1d0
--- /dev/null
+++ b/dcf/fss_gates/multiple_interval_containment.h
@@ -0,0 +1,92 @@
+// 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 THIRD_PARTY_DISTRIBUTED_POINT_FUNCTIONS_DCF_FSS_GATES_MULTIPLE_INTERVAL_CONTAINMENT_H_
+#define THIRD_PARTY_DISTRIBUTED_POINT_FUNCTIONS_DCF_FSS_GATES_MULTIPLE_INTERVAL_CONTAINMENT_H_
+#include <vector>
+
+#include "third_party/absl/numeric/int128.h"
+#include "third_party/absl/status/statusor.h"
+#include "third_party/distributed_point_functions/dcf/distributed_comparison_function.h"
+#include "third_party/distributed_point_functions/dcf/fss_gates/multiple_interval_containment.proto.h"
+#include "third_party/distributed_point_functions/dpf/status_macros.h"
+
+namespace distributed_point_functions {
+namespace fss_gates {
+
+// Implements the Multiple Interval Containment gate as specified in
+// https://eprint.iacr.org/2020/1392 (Fig. 14). Such a gate is specified by
+// input and output group Z_{2 ^ n} where n is the bit length and a sequence
+// of `m` public intervals {p_i, q_i}_{i \in [m]}. The Key generation procedure
+// produces two keys, k_0 and k_1, corresponding to Party 0 and Party 1
+// respectively. Evaluating each key on any point `x` in the input group results
+// in an additive secret share of m values {y_i}_{i \in [m]} where y_i = `1`, if
+// `p_i <= x <= q_i`, and 0 otherwise.
+
+class MultipleIntervalContainmentGate {
+ public:
+  // Factory method : creates and returns a MultipleIntervalContainmentGate
+  // initialized with appropriate parameters.
+  static absl::StatusOr<std::unique_ptr<MultipleIntervalContainmentGate>>
+  Create(const MicParameters& mic_parameters);
+
+  // MultipleIntervalContainmentGate is neither copyable nor movable.
+  MultipleIntervalContainmentGate(const MultipleIntervalContainmentGate&) =
+      delete;
+  MultipleIntervalContainmentGate& operator=(
+      const MultipleIntervalContainmentGate&) = delete;
+
+  // This method generates Multiple Interval Containment Gate a pair of keys
+  // using `r_in` and `r_out` as the input mask and output masks respectively.
+  // The implementation of this method is identical to Gen procedure specified
+  // in https://eprint.iacr.org/2020/1392 (Fig. 14). Note that although the
+  // datatype of r_in and r_out is absl::uint128, but they will be interpreted
+  // as an element in the input and output group Z_{2 ^ n} respectively. This
+  // reinterpretion in the group is achieved simply by taking mod of r_in and
+  // r_out with the size of group i.e. 2^{log_group_size}.
+
+  // This method expects that the size of r_out vector be exactly same as the
+  // number of public intervals in the MicParameters. This is because for
+  // each interval in MIC, we will need an independent output mask to hide
+  // the actual cleartext output of the MIC on that interval. This method
+  // will return InvalidArgumentError.
+
+  // Returns INVALID_ARGUMENT if the size of r_out vector does not match the
+  // number of intervals specified during construction.
+  absl::StatusOr<std::pair<MicKey, MicKey>> Gen(
+      absl::uint128 r_in, std::vector<absl::uint128> r_out);
+
+  // This method evaluates the Multiple Interval Containment Gate key k
+  // on input domain point `x`. The output is returned as a 128 bit string
+  // and needs to be interpreted as an element in the output group Z_{2 ^ n}.
+  absl::StatusOr<std::vector<absl::uint128>> Eval(MicKey k, absl::uint128 x);
+
+ private:
+  // Parameters needed for specifying a Multiple Interval Containment Gate.
+  const MicParameters mic_parameters_;
+
+  // Private constructor, called by `Create`
+  MultipleIntervalContainmentGate(
+      MicParameters mic_parameters,
+      std::unique_ptr<DistributedComparisonFunction> dcf);
+
+  // Pointer to a Distributed Comparison Function which will be internally
+  // invoked by Gen and Eval.
+  std::unique_ptr<DistributedComparisonFunction> dcf_;
+};
+
+}  // namespace fss_gates
+}  // namespace distributed_point_functions
+
+#endif  // THIRD_PARTY_DISTRIBUTED_POINT_FUNCTIONS_DCF_FSS_GATES_MULTIPLE_INTERVAL_CONTAINMENT_H_
diff --git a/dcf/fss_gates/multiple_interval_containment.proto b/dcf/fss_gates/multiple_interval_containment.proto
new file mode 100644
index 0000000..c1fcf66
--- /dev/null
+++ b/dcf/fss_gates/multiple_interval_containment.proto
@@ -0,0 +1,60 @@
+// 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.
+
+syntax = "proto3";
+
+package distributed_point_functions.fss_gates;
+
+import "third_party/distributed_point_functions/dcf/distributed_comparison_function.proto";
+import "third_party/distributed_point_functions/dpf/distributed_point_function.proto";
+
+// Represents an interval on the group G = Z_N.
+message Interval {
+  // Represents the lower limit of the interval. This corresponds to `p_i`
+  // used in https://eprint.iacr.org/2020/1392 (Fig. 14).
+  Value.Integer lower_bound = 1;
+
+  // Represents the upper limit of the interval. This corresponds to `q_i`
+  // used in https://eprint.iacr.org/2020/1392 (Fig. 14).
+  Value.Integer upper_bound = 2;
+}
+
+message MicParameters {
+  // Represents the bit length of the input to the Multiple Interval Containment
+  // gate. This corresponds to `n` used in https://eprint.iacr.org/2020/1392
+  // (Fig. 14). Here we assume that if `n` is the input bit-length, then the
+  // input and output group of the gate is implicitly Z_N where N = 2^n, and
+  // hence the variable name "log_group_size". Maximum allowed log_group_size
+  // is 127 and minimum value should be at least the number of bits required to
+  // store each interval boundary.
+  int32 log_group_size = 1;
+
+  // Represents a sequence of public intervals. This corresponds to `{p_i, q_i}`
+  // used in https://eprint.iacr.org/2020/1392 (Fig. 14).
+  repeated Interval intervals = 2;
+}
+
+// Represents a key for Multiple Interval Containment gate. This corresponds to
+//`k_b` used in https://eprint.iacr.org/2020/1392 (Fig. 14). The key implicitly
+// corresponds to the MicParameters used to generate this key.
+message MicKey {
+  // Represents a Distributed Comparison Function Key. This corresponds to
+  //`k_b^(N - 1)` used in https://eprint.iacr.org/2020/1392 (Fig. 14).
+  DcfKey dcfkey = 1;
+
+  // Represents output mask shares corresponding to each of the m different
+  // intervals. This corresponds to `{z_i,b}_i` used in
+  // https://eprint.iacr.org/2020/1392 (Fig. 14).
+  repeated Value.Integer output_mask_share = 2;
+}
diff --git a/dcf/fss_gates/multiple_interval_containment_test.cc b/dcf/fss_gates/multiple_interval_containment_test.cc
new file mode 100644
index 0000000..6f0a3c0
--- /dev/null
+++ b/dcf/fss_gates/multiple_interval_containment_test.cc
@@ -0,0 +1,542 @@
+// 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.
+
+#include "third_party/distributed_point_functions/dcf/fss_gates/multiple_interval_containment.h"
+
+#include <cstdint>
+#include <vector>
+
+#include "testing/base/public/gmock.h"
+#include "testing/base/public/gunit.h"
+#include "third_party/absl/numeric/int128.h"
+#include "third_party/distributed_point_functions/dcf/fss_gates/multiple_interval_containment.proto.h"
+#include "third_party/distributed_point_functions/dpf/distributed_point_function.proto.h"
+#include "third_party/distributed_point_functions/dpf/internal/status_matchers.h"
+#include "third_party/distributed_point_functions/dpf/internal/value_type_helpers.h"
+#include "third_party/distributed_point_functions/dpf/status_macros.h"
+#include "third_party/distributed_point_functions/prng/basic_rng.h"
+
+namespace distributed_point_functions {
+namespace fss_gates {
+namespace {
+
+using ::testing::Test;
+
+TEST(MICTest, GenAndEvalSucceedsForSmallGroup) {
+  MicParameters mic_parameters;
+  const int group_size = 64;
+  const uint64 interval_count = 5;
+
+  // Setting input and output group to be Z_{2^64}
+  mic_parameters.set_log_group_size(group_size);
+
+  // Setting up the lower bound and upper bounds for intervals
+  std::vector<absl::uint128> ps{10, 23, 45, 66, 15};
+  std::vector<absl::uint128> qs{45, 30, 100, 250, 15};
+
+  for (int i = 0; i < interval_count; ++i) {
+    Interval* interval = mic_parameters.add_intervals();
+
+    interval->mutable_lower_bound()->mutable_value_uint128()->set_low(
+        absl::Uint128Low64(ps[i]));
+
+    interval->mutable_upper_bound()->mutable_value_uint128()->set_low(
+        absl::Uint128Low64(qs[i]));
+  }
+
+  // Creating a MIC gate
+  DPF_ASSERT_OK_AND_ASSIGN(
+      std::unique_ptr<MultipleIntervalContainmentGate> MicGate,
+      MultipleIntervalContainmentGate::Create(mic_parameters));
+
+  MicKey key_0, key_1;
+
+  // Initializing the input and output masks uniformly at random;
+  const absl::string_view kSampleSeed = absl::string_view();
+  DPF_ASSERT_OK_AND_ASSIGN(
+      auto rng, distributed_point_functions::BasicRng::Create(kSampleSeed));
+
+  absl::uint128 N = absl::uint128(1) << mic_parameters.log_group_size();
+
+  DPF_ASSERT_OK_AND_ASSIGN(absl::uint128 r_in, rng->Rand64());
+  r_in = r_in % N;
+
+  std::vector<absl::uint128> r_outs;
+
+  for (int i = 0; i < interval_count; ++i) {
+    DPF_ASSERT_OK_AND_ASSIGN(absl::uint128 r_out, rng->Rand64());
+    r_out = r_out % N;
+    r_outs.push_back(r_out);
+  }
+
+  // Generating MIC gate keys
+  DPF_ASSERT_OK_AND_ASSIGN(std::tie(key_0, key_1), MicGate->Gen(r_in, r_outs));
+
+  // Inside this loop we will test the Evaluation of the MIC gate on
+  // input values ranging between [0, 400)
+  for (uint64 i = 0; i < 400; i++) {
+    std::vector<absl::uint128> res_0, res_1;
+
+    // Evaluating MIC gate key_0 on masked input i + r_in
+    DPF_ASSERT_OK_AND_ASSIGN(res_0, MicGate->Eval(key_0, (i + r_in) % N));
+
+    // Evaluating MIC gate key_1 on masked input i + r_in
+    DPF_ASSERT_OK_AND_ASSIGN(res_1, MicGate->Eval(key_1, (i + r_in) % N));
+
+    // Reconstructing the actual output of the MIC gate by adding together
+    // the secret shared output res_0 and res_1, and then subtracting out
+    // the output mask r_out
+    for (int j = 0; j < interval_count; j++) {
+      absl::uint128 result = (res_0[j] + res_1[j] - r_outs[j]) % N;
+
+      // If the input i lies inside the j^th interval, then the expected
+      // output of MIC gate is 1, and 0 otherwise
+      if (i >= ps[j] && i <= qs[j]) {
+        EXPECT_EQ(result, 1);
+      } else {
+        EXPECT_EQ(result, 0);
+      }
+    }
+  }
+}
+
+TEST(MICTest, GenAndEvalSucceedsForLargeGroup) {
+  MicParameters mic_parameters;
+  const int group_size = 127;
+  const uint64 interval_count = 3;
+  const absl::uint128 two_power_127 = absl::uint128(1) << 127;
+  const absl::uint128 two_power_126 = absl::uint128(1) << 126;
+
+  // Setting input and output group to be Z_{2^127}
+  mic_parameters.set_log_group_size(group_size);
+
+  // Setting up the lower bound and upper bounds for intervals
+
+  std::vector<absl::uint128> ps{two_power_126, two_power_127 - 1,
+                                two_power_127 - 3};
+  std::vector<absl::uint128> qs{two_power_126 + 3, two_power_127 - 1,
+                                two_power_127 - 2};
+
+  std::vector<absl::uint128> x{two_power_126 - 1, two_power_126,
+                               two_power_126 + 1, two_power_126 + 2,
+                               two_power_126 + 3, two_power_126 + 4,
+                               two_power_127 - 4, two_power_127 - 3,
+                               two_power_127 - 2, two_power_127 - 1};
+
+  for (int i = 0; i < interval_count; ++i) {
+    Interval* interval = mic_parameters.add_intervals();
+
+    interval->mutable_lower_bound()->mutable_value_uint128()->set_high(
+        absl::Uint128High64(ps[i]));
+    interval->mutable_lower_bound()->mutable_value_uint128()->set_low(
+        absl::Uint128Low64(ps[i]));
+
+    interval->mutable_upper_bound()->mutable_value_uint128()->set_high(
+        absl::Uint128High64(qs[i]));
+    interval->mutable_upper_bound()->mutable_value_uint128()->set_low(
+        absl::Uint128Low64(qs[i]));
+  }
+
+  // Creating a MIC gate
+  DPF_ASSERT_OK_AND_ASSIGN(
+      std::unique_ptr<MultipleIntervalContainmentGate> MicGate,
+      MultipleIntervalContainmentGate::Create(mic_parameters));
+
+  MicKey key_0, key_1;
+
+  absl::uint128 N = absl::uint128(1) << mic_parameters.log_group_size();
+
+  // Initializing the input and output masks uniformly at random;
+  const absl::string_view kSampleSeed = absl::string_view();
+  DPF_ASSERT_OK_AND_ASSIGN(
+      auto rng, distributed_point_functions::BasicRng::Create(kSampleSeed));
+
+  DPF_ASSERT_OK_AND_ASSIGN(absl::uint128 r_in, rng->Rand128());
+
+  r_in = r_in % N;
+
+  std::vector<absl::uint128> r_outs;
+
+  for (int i = 0; i < interval_count; ++i) {
+    DPF_ASSERT_OK_AND_ASSIGN(absl::uint128 r_out, rng->Rand128());
+    r_out = r_out % N;
+    r_outs.push_back(r_out);
+  }
+
+  // Generating MIC gate keys
+  DPF_ASSERT_OK_AND_ASSIGN(std::tie(key_0, key_1), MicGate->Gen(r_in, r_outs));
+
+  // Inside this loop we will test the Evaluation of the MIC gate on
+  // input values in the vicinity of interval boundaries which are hardcoded
+  // in the vector x.
+  for (uint64 i = 0; i < x.size(); i++) {
+    std::vector<absl::uint128> res_0, res_1;
+
+    // Evaluating MIC gate key_0 on masked input
+    DPF_ASSERT_OK_AND_ASSIGN(res_0, MicGate->Eval(key_0, (x[i] + r_in) % N));
+
+    // Evaluating MIC gate key_1 on masked input
+    DPF_ASSERT_OK_AND_ASSIGN(res_1, MicGate->Eval(key_1, (x[i] + r_in) % N));
+
+    // Reconstructing the actual output of the MIC gate by adding together
+    // the secret shared output res_0 and res_1, and then subtracting out
+    // the output mask r_out
+    for (int j = 0; j < interval_count; j++) {
+      absl::uint128 result = (res_0[j] + res_1[j] - r_outs[j]) % N;
+
+      // If the input lies inside the j^th interval, then the expected
+      // output of MIC gate is 1, and 0 otherwise
+      if (x[i] >= ps[j] && x[i] <= qs[j]) {
+        EXPECT_EQ(result, 1);
+      } else {
+        EXPECT_EQ(result, 0);
+      }
+    }
+  }
+}
+
+TEST(MICTest, CreateFailsWith128bitGroup) {
+  MicParameters mic_parameters;
+  const int group_size = 128;
+  const uint64 interval_count = 5;
+
+  // Setting input and output group to be Z_{2^128}
+  mic_parameters.set_log_group_size(group_size);
+
+  // Setting up the lower bound and upper bounds for intervals
+  std::vector<absl::uint128> ps{10, 23, 45, 66, 15};
+  std::vector<absl::uint128> qs{45, 30, 100, 250, 15};
+
+  for (int i = 0; i < interval_count; ++i) {
+    Interval* interval = mic_parameters.add_intervals();
+
+    interval->mutable_lower_bound()->mutable_value_uint128()->set_low(
+        absl::Uint128Low64(ps[i]));
+
+    interval->mutable_upper_bound()->mutable_value_uint128()->set_low(
+        absl::Uint128Low64(qs[i]));
+  }
+
+  EXPECT_THAT(
+      MultipleIntervalContainmentGate::Create(mic_parameters),
+      dpf_internal::StatusIs(absl::StatusCode::kInvalidArgument,
+                             "log_group_size should be in > 0 and < 128"));
+}
+
+TEST(MICTest, CreateFailsForIntervalBoundariesOutsideGroup) {
+  MicParameters mic_parameters;
+  const int group_size = 20;
+  const uint64 interval_count = 1;
+  const absl::uint128 two_power_20 = absl::uint128(1) << 20;
+
+  // Setting input and output group to be Z_{2^20}
+  mic_parameters.set_log_group_size(group_size);
+
+  // Setting up the lower bound and upper bounds for intervals
+  std::vector<absl::uint128> ps{4};
+  std::vector<absl::uint128> qs{two_power_20};
+
+  for (int i = 0; i < interval_count; ++i) {
+    Interval* interval = mic_parameters.add_intervals();
+
+    interval->mutable_lower_bound()->mutable_value_uint128()->set_low(
+        absl::Uint128Low64(ps[i]));
+
+    interval->mutable_upper_bound()->mutable_value_uint128()->set_low(
+        absl::Uint128Low64(qs[i]));
+  }
+
+  EXPECT_THAT(MultipleIntervalContainmentGate::Create(mic_parameters),
+              dpf_internal::StatusIs(
+                  absl::StatusCode::kInvalidArgument,
+                  "Interval bounds should be between 0 and 2^log_group_size"));
+}
+
+TEST(MICTest, CreateFailsForInvalidIntervalBoundaries) {
+  MicParameters mic_parameters;
+  const int group_size = 20;
+  const uint64 interval_count = 1;
+
+  // Setting input and output group to be Z_{2^20}
+  mic_parameters.set_log_group_size(group_size);
+
+  // Setting up the lower bound and upper bounds for intervals
+  std::vector<absl::uint128> ps{4};
+  std::vector<absl::uint128> qs{3};
+
+  for (int i = 0; i < interval_count; ++i) {
+    Interval* interval = mic_parameters.add_intervals();
+
+    interval->mutable_lower_bound()->mutable_value_uint128()->set_low(
+        absl::Uint128Low64(ps[i]));
+
+    interval->mutable_upper_bound()->mutable_value_uint128()->set_low(
+        absl::Uint128Low64(qs[i]));
+  }
+
+  EXPECT_THAT(
+      MultipleIntervalContainmentGate::Create(mic_parameters),
+      dpf_internal::StatusIs(absl::StatusCode::kInvalidArgument,
+                             "Interval upper bounds should be >= lower bound"));
+}
+
+TEST(MICTest, CreateFailsForEmptyInterval) {
+  MicParameters mic_parameters;
+  const int group_size = 20;
+  const uint64 interval_count = 1;
+
+  // Setting input and output group to be Z_{2^20}
+  mic_parameters.set_log_group_size(group_size);
+
+  // Setting up the lower bound and upper bounds for intervals
+  std::vector<absl::uint128> ps{};
+  std::vector<absl::uint128> qs{3};
+
+  for (int i = 0; i < interval_count; ++i) {
+    Interval* interval = mic_parameters.add_intervals();
+
+    // Only setting upper bound (and skipping lower bound)
+    interval->mutable_upper_bound()->mutable_value_uint128()->set_low(
+        absl::Uint128Low64(qs[i]));
+  }
+
+  EXPECT_THAT(MultipleIntervalContainmentGate::Create(mic_parameters),
+              dpf_internal::StatusIs(absl::StatusCode::kInvalidArgument,
+                                     "Intervals should be non-empty"));
+}
+
+TEST(MICTest, GenFailsForIncorrectNumberOfOutputMasks) {
+  MicParameters mic_parameters;
+  const int group_size = 64;
+  const uint64 interval_count = 5;
+
+  // Setting input and output group to be Z_{2^64}
+  mic_parameters.set_log_group_size(group_size);
+
+  // Setting up the lower bound and upper bounds for intervals
+  std::vector<absl::uint128> ps{10, 23, 45, 66, 15};
+  std::vector<absl::uint128> qs{45, 30, 100, 250, 15};
+
+  for (int i = 0; i < interval_count; ++i) {
+    Interval* interval = mic_parameters.add_intervals();
+
+    interval->mutable_lower_bound()->mutable_value_uint128()->set_low(
+        absl::Uint128Low64(ps[i]));
+
+    interval->mutable_upper_bound()->mutable_value_uint128()->set_low(
+        absl::Uint128Low64(qs[i]));
+  }
+
+  // Creating a MIC gate
+  DPF_ASSERT_OK_AND_ASSIGN(
+      std::unique_ptr<MultipleIntervalContainmentGate> MicGate,
+      MultipleIntervalContainmentGate::Create(mic_parameters));
+
+  MicKey key_0, key_1;
+
+  absl::uint128 N = absl::uint128(1) << mic_parameters.log_group_size();
+
+  // Initializing the input and output masks uniformly at random;
+  const absl::string_view kSampleSeed = absl::string_view();
+  DPF_ASSERT_OK_AND_ASSIGN(
+      auto rng, distributed_point_functions::BasicRng::Create(kSampleSeed));
+
+  DPF_ASSERT_OK_AND_ASSIGN(absl::uint128 r_in, rng->Rand64());
+  r_in = r_in % N;
+
+  std::vector<absl::uint128> r_outs;
+
+  // Setting only (interval_count - 1) many output masks
+  for (int i = 0; i < interval_count - 1; ++i) {
+    DPF_ASSERT_OK_AND_ASSIGN(absl::uint128 r_out, rng->Rand64());
+    r_out = r_out % N;
+    r_outs.push_back(r_out);
+  }
+
+  // Generating MIC gate keys
+  EXPECT_THAT(
+      MicGate->Gen(r_in, r_outs),
+      dpf_internal::StatusIs(
+          absl::StatusCode::kInvalidArgument,
+          "Count of output masks should be equal to the number of intervals"));
+}
+
+TEST(MICTest, GenFailsForInputMaskOutsideGroup) {
+  MicParameters mic_parameters;
+  const int group_size = 10;
+  const uint64 interval_count = 1;
+
+  // Setting input and output group to be Z_{2^10}
+  mic_parameters.set_log_group_size(group_size);
+
+  // Setting up the lower bound and upper bounds for intervals
+  std::vector<absl::uint128> ps{10};
+  std::vector<absl::uint128> qs{45};
+
+  for (int i = 0; i < interval_count; ++i) {
+    Interval* interval = mic_parameters.add_intervals();
+
+    interval->mutable_lower_bound()->mutable_value_uint128()->set_low(
+        absl::Uint128Low64(ps[i]));
+
+    interval->mutable_upper_bound()->mutable_value_uint128()->set_low(
+        absl::Uint128Low64(qs[i]));
+  }
+
+  // Creating a MIC gate
+  DPF_ASSERT_OK_AND_ASSIGN(
+      std::unique_ptr<MultipleIntervalContainmentGate> MicGate,
+      MultipleIntervalContainmentGate::Create(mic_parameters));
+
+  MicKey key_0, key_1;
+
+  absl::uint128 N = absl::uint128(1) << mic_parameters.log_group_size();
+
+  const absl::string_view kSampleSeed = absl::string_view();
+  DPF_ASSERT_OK_AND_ASSIGN(
+      auto rng, distributed_point_functions::BasicRng::Create(kSampleSeed));
+
+  // Fixing r_in to be an element outside group
+  absl::uint128 r_in = 2048;
+
+  std::vector<absl::uint128> r_outs;
+
+  // Initializing the output masks uniformly at random;
+  for (int i = 0; i < interval_count; ++i) {
+    DPF_ASSERT_OK_AND_ASSIGN(absl::uint128 r_out, rng->Rand64());
+    r_out = r_out % N;
+    r_outs.push_back(r_out);
+  }
+
+  // Generating MIC gate keys
+  EXPECT_THAT(MicGate->Gen(r_in, r_outs),
+              dpf_internal::StatusIs(
+                  absl::StatusCode::kInvalidArgument,
+                  "Input mask should be between 0 and 2^log_group_size"));
+}
+
+TEST(MICTest, GenFailsForOutputMaskOutsideGroup) {
+  MicParameters mic_parameters;
+  const int group_size = 10;
+  const uint64 interval_count = 1;
+
+  // Setting input and output group to be Z_{2^10}
+  mic_parameters.set_log_group_size(group_size);
+
+  // Setting up the lower bound and upper bounds for intervals
+  std::vector<absl::uint128> ps{10};
+  std::vector<absl::uint128> qs{45};
+
+  for (int i = 0; i < interval_count; ++i) {
+    Interval* interval = mic_parameters.add_intervals();
+
+    interval->mutable_lower_bound()->mutable_value_uint128()->set_low(
+        absl::Uint128Low64(ps[i]));
+
+    interval->mutable_upper_bound()->mutable_value_uint128()->set_low(
+        absl::Uint128Low64(qs[i]));
+  }
+
+  // Creating a MIC gate
+  DPF_ASSERT_OK_AND_ASSIGN(
+      std::unique_ptr<MultipleIntervalContainmentGate> MicGate,
+      MultipleIntervalContainmentGate::Create(mic_parameters));
+
+  MicKey key_0, key_1;
+
+  absl::uint128 N = absl::uint128(1) << mic_parameters.log_group_size();
+
+  const absl::string_view kSampleSeed = absl::string_view();
+  DPF_ASSERT_OK_AND_ASSIGN(
+      auto rng, distributed_point_functions::BasicRng::Create(kSampleSeed));
+
+  // Initializing the input masks uniformly at random;
+  DPF_ASSERT_OK_AND_ASSIGN(absl::uint128 r_in, rng->Rand64());
+  r_in = r_in % N;
+
+  std::vector<absl::uint128> r_outs;
+
+  // Fixing the output masks to be elements outside group;
+  for (int i = 0; i < interval_count; ++i) {
+    absl::uint128 r_out = 2048;
+    r_outs.push_back(r_out);
+  }
+
+  // Generating MIC gate keys
+  EXPECT_THAT(MicGate->Gen(r_in, r_outs),
+              dpf_internal::StatusIs(
+                  absl::StatusCode::kInvalidArgument,
+                  "Output mask should be between 0 and 2^log_group_size"));
+}
+
+TEST(MICTest, EvalFailsForMaskedInputOutsideGroup) {
+  MicParameters mic_parameters;
+  const int group_size = 64;
+  const uint64 interval_count = 1;
+
+  // Setting input and output group to be Z_{2^64}
+  mic_parameters.set_log_group_size(group_size);
+
+  // Setting up the lower bound and upper bounds for intervals
+  std::vector<absl::uint128> ps{10};
+  std::vector<absl::uint128> qs{45};
+
+  for (int i = 0; i < interval_count; ++i) {
+    Interval* interval = mic_parameters.add_intervals();
+
+    interval->mutable_lower_bound()->mutable_value_uint128()->set_low(
+        absl::Uint128Low64(ps[i]));
+
+    interval->mutable_upper_bound()->mutable_value_uint128()->set_low(
+        absl::Uint128Low64(qs[i]));
+  }
+
+  // Creating a MIC gate
+  DPF_ASSERT_OK_AND_ASSIGN(
+      std::unique_ptr<MultipleIntervalContainmentGate> MicGate,
+      MultipleIntervalContainmentGate::Create(mic_parameters));
+
+  MicKey key_0, key_1;
+
+  // Initializing the input and output masks uniformly at random;
+  const absl::string_view kSampleSeed = absl::string_view();
+  DPF_ASSERT_OK_AND_ASSIGN(
+      auto rng, distributed_point_functions::BasicRng::Create(kSampleSeed));
+
+  absl::uint128 N = absl::uint128(1) << mic_parameters.log_group_size();
+
+  DPF_ASSERT_OK_AND_ASSIGN(absl::uint128 r_in, rng->Rand64());
+  r_in = r_in % N;
+
+  std::vector<absl::uint128> r_outs;
+
+  for (int i = 0; i < interval_count; ++i) {
+    DPF_ASSERT_OK_AND_ASSIGN(absl::uint128 r_out, rng->Rand64());
+    r_out = r_out % N;
+    r_outs.push_back(r_out);
+  }
+
+  // Generating MIC gate keys
+  DPF_ASSERT_OK_AND_ASSIGN(std::tie(key_0, key_1), MicGate->Gen(r_in, r_outs));
+
+  // Calling Eval on a masked input which is not a group element
+  EXPECT_THAT(MicGate->Eval(key_0, absl::uint128(1) << 72),
+              dpf_internal::StatusIs(
+                  absl::StatusCode::kInvalidArgument,
+                  "Masked input should be between 0 and 2^log_group_size"));
+}
+
+}  // namespace
+}  // namespace fss_gates
+}  // namespace distributed_point_functions
diff --git a/prng/BUILD b/prng/BUILD
new file mode 100644
index 0000000..f0bb248
--- /dev/null
+++ b/prng/BUILD
@@ -0,0 +1,40 @@
+load("@io_bazel_rules_go//proto:def.bzl", "go_proto_library")
+
+package(
+    default_visibility = ["//:__subpackages__"],
+)
+
+licenses(["notice"])
+
+cc_library(
+    name = "prng",
+    hdrs = ["prng.h"],
+    deps = [
+        "//dpf:status_macros",
+        "@com_google_absl//absl/status:statusor",
+        "@com_google_absl//absl/strings",
+    ],
+)
+
+cc_library(
+    name = "basic_rng",
+    hdrs = ["basic_rng.h"],
+    deps = [
+        ":prng",
+        "@boringssl//:crypto",
+        "@com_google_absl//absl/memory",
+        "@com_google_absl//absl/numeric:int128",
+        "@com_google_absl//absl/strings",
+    ],
+)
+
+cc_test(
+    name = "basic_rng_test",
+    srcs = ["basic_rng_test.cc"],
+    deps = [
+        ":basic_rng",
+        "//dpf/internal:status_matchers",
+        "@com_github_google_googletest//:gtest_main",
+        "@com_google_absl//absl/numeric:int128",
+    ],
+)
diff --git a/prng/basic_rng.h b/prng/basic_rng.h
new file mode 100644
index 0000000..72572dc
--- /dev/null
+++ b/prng/basic_rng.h
@@ -0,0 +1,88 @@
+// 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 THIRD_PARTY_DISTRIBUTED_POINT_FUNCTIONS_PRNG_BASIC_RNG_H_
+#define THIRD_PARTY_DISTRIBUTED_POINT_FUNCTIONS_PRNG_BASIC_RNG_H_
+
+#include "third_party/absl/memory/memory.h"
+#include "third_party/absl/numeric/int128.h"
+#include "third_party/absl/strings/string_view.h"
+#include "third_party/distributed_point_functions/prng/prng.h"
+#include "third_party/openssl/rand.h"
+
+namespace distributed_point_functions {
+
+// Basic RNG class that uses RAND_bytes from OpenSSL to sample randomness.
+// BasicRng does not require a seed internally.
+class BasicRng : public SecurePrng {
+ public:
+  // Create a BasicRng object.
+  // Returns an INTERNAL error code if the creation fails.
+  static absl::StatusOr<std::unique_ptr<BasicRng>> Create(
+      absl::string_view seed) {
+    return absl::make_unique<BasicRng>();
+  }
+
+  // Sample 8 bits of randomness using OpenSSL RAND_bytes.
+  // Returns an INTERNAL error code if the sampling fails.
+  absl::StatusOr<uint8_t> Rand8() override {
+    unsigned char rand[1];
+    int success = RAND_bytes(rand, 1);
+    if (!success) {
+      return absl::InternalError(
+          "BasicRng::Rand8() - Failed to create randomness");
+    }
+    return static_cast<uint8_t>(rand[0]);
+  }
+
+  // Sample 64 bits of randomness using OPENSSL RAND_bytes.
+  // Returns an INTERNAL error code if the sampling fails.
+  absl::StatusOr<uint64_t> Rand64() override {
+    unsigned char rand[8];
+    int success = RAND_bytes(rand, 8);
+    if (!success) {
+      return absl::InternalError(
+          "BasicRng::Rand64() - Failed to create randomness");
+    }
+    uint64_t rand_uint64 = 0;
+    for (int i = 0; i < 8; i++) {
+      rand_uint64 += static_cast<uint64_t>(rand[8 - i]) << (8 * i);
+    }
+    return rand_uint64;
+  }
+
+  // Sample 128 bits of randomness using OPENSSL RAND_bytes.
+  // Returns an INTERNAL error code if the sampling fails.
+  absl::StatusOr<absl::uint128> Rand128() override {
+    unsigned char rand[16];
+    int success = RAND_bytes(rand, 16);
+    if (!success) {
+      return absl::InternalError(
+          "BasicRng::Rand128() - Failed to create randomness");
+    }
+    absl::uint128 rand_uint128 = 0;
+    for (int i = 0; i < 16; i++) {
+      rand_uint128 += static_cast<absl::uint128>(rand[8 - i]) << (8 * i);
+    }
+    return rand_uint128;
+  }
+
+  // BasicRng does not use seeds.
+  static absl::StatusOr<std::string> GenerateSeed() { return std::string(); }
+  static int SeedLength() { return 0; }
+};
+
+}  // namespace distributed_point_functions
+
+#endif  // THIRD_PARTY_DISTRIBUTED_POINT_FUNCTIONS_PRNG_BASIC_RNG_H_
diff --git a/prng/basic_rng_test.cc b/prng/basic_rng_test.cc
new file mode 100644
index 0000000..2d4dc29
--- /dev/null
+++ b/prng/basic_rng_test.cc
@@ -0,0 +1,63 @@
+// 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.
+
+#include "third_party/distributed_point_functions/prng/basic_rng.h"
+
+#include "testing/base/public/gmock.h"
+#include "testing/base/public/gunit.h"
+#include "third_party/absl/numeric/int128.h"
+#include "third_party/distributed_point_functions/dpf/internal/status_matchers.h"
+
+namespace distributed_point_functions {
+namespace {
+
+using ::testing::Test;
+
+const absl::string_view kSampleSeed = absl::string_view();
+
+class BasicRngTest : public Test {};
+
+TEST_F(BasicRngTest, Test8BitRand) {
+  DPF_ASSERT_OK_AND_ASSIGN(auto rng, BasicRng::Create(kSampleSeed));
+
+  // Two random 8 bit strings have 1/256 probability of being equal. Instead,
+  // we check that 8 consecutively generated strings are not all equal.
+  bool equal = true;
+  DPF_ASSERT_OK_AND_ASSIGN(uint8_t prev, rng->Rand8());
+  for (int i = 0; i < 8; ++i) {
+    DPF_ASSERT_OK_AND_ASSIGN(uint8_t next, rng->Rand8());
+    if (next != prev) {
+      equal = false;
+    }
+    prev = next;
+  }
+  EXPECT_FALSE(equal);
+}
+
+TEST_F(BasicRngTest, Test64BitRand) {
+  DPF_ASSERT_OK_AND_ASSIGN(auto rng, BasicRng::Create(kSampleSeed));
+  DPF_ASSERT_OK_AND_ASSIGN(uint64_t r1, rng->Rand64());
+  DPF_ASSERT_OK_AND_ASSIGN(uint64_t r2, rng->Rand64());
+  EXPECT_NE(r1, r2);
+}
+
+TEST_F(BasicRngTest, Test128BitRand) {
+  DPF_ASSERT_OK_AND_ASSIGN(auto rng, BasicRng::Create(kSampleSeed));
+  DPF_ASSERT_OK_AND_ASSIGN(absl::uint128 r1, rng->Rand128());
+  DPF_ASSERT_OK_AND_ASSIGN(absl::uint128 r2, rng->Rand128());
+  EXPECT_NE(r1, r2);
+}
+
+}  // namespace
+}  // namespace distributed_point_functions
diff --git a/prng/prng.h b/prng/prng.h
new file mode 100644
index 0000000..e5bbf99
--- /dev/null
+++ b/prng/prng.h
@@ -0,0 +1,39 @@
+// 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 THIRD_PARTY_DISTRIBUTED_POINT_FUNCTIONS_PRNG_PRNG_H_
+#define THIRD_PARTY_DISTRIBUTED_POINT_FUNCTIONS_PRNG_PRNG_H_
+
+#include "third_party/absl/status/statusor.h"
+#include "third_party/absl/strings/string_view.h"
+#include "third_party/distributed_point_functions/dpf/status_macros.h"
+
+namespace distributed_point_functions {
+
+// An interface for a secure pseudo-random number generator.
+class SecurePrng {
+ public:
+  virtual absl::StatusOr<uint8_t> Rand8() = 0;
+  virtual absl::StatusOr<uint64_t> Rand64() = 0;
+  virtual absl::StatusOr<absl::uint128> Rand128() = 0;
+  virtual ~SecurePrng() = default;
+  static absl::StatusOr<std::unique_ptr<SecurePrng>> Create(
+      absl::string_view seed);
+  static absl::StatusOr<std::string> GenerateSeed();
+  static int SeedLength();
+};
+
+}  // namespace distributed_point_functions
+
+#endif  // THIRD_PARTY_DISTRIBUTED_POINT_FUNCTIONS_PRNG_PRNG_H_