95 lines
3.2 KiB
C++
95 lines
3.2 KiB
C++
|
/// @file dpf/it_dpf3.hpp
|
|||
|
|
/// @brief Information-theoretic 3-server distributed point function.
|
|||
|
|
/// @details Statistically private among three servers: any one key is
|
|||
|
|
/// independent of `(α, β)`, and the **sum** of all three evaluations
|
|||
|
|
/// is the point function (Boyle–Gilboa–Ishai–Kolobov, ePrint 2023/028).
|
|||
|
|
/// Distinct from the computational `(2,3)` Shamir key `make_dpf3`
|
|||
|
|
/// (ePrint 2024/1658), where any two shares reconstruct. Domain
|
|||
|
|
/// `uint8_t`, payload `uint64_t`. For this domain size the share is a
|
|||
|
|
/// full additive truth table (no GGM correction words); the paper's
|
|||
|
|
/// matching-vector packing targets asymptotically large `N`.
|
|||
|
|
/// @see dpf/dpf3.hpp, examples/applications/it_pir3.cpp, examples/applications/pir3.cpp
|
|||
|
|
/// @copyright Copyright (c) 2019-2026 Ryan Henry and [others](@ref authors)
|
|||
|
|
/// @license Released under a GNU General Public v2.0 (GPLv2) license.
|
|||
|
|
|
|||
|
|
#ifndef LIBDPF_INCLUDE_DPF_IT_DPF3_HPP__
|
|||
|
|
#define LIBDPF_INCLUDE_DPF_IT_DPF3_HPP__
|
|||
|
|
|
|||
|
|
#include <array>
|
|||
|
|
#include <cstddef>
|
|||
|
|
#include <cstdint>
|
|||
|
|
#include <tuple>
|
|||
|
|
#include <utility>
|
|||
|
|
|
|||
|
|
#include "hedley/hedley.h"
|
|||
|
|
|
|||
|
|
#include "dpf/random.hpp"
|
|||
|
|
#include "dpf/secret_share.hpp"
|
|||
|
|
|
|||
|
|
namespace dpf
|
|||
|
|
{
|
|||
|
|
|
|||
|
|
/// @brief One evaluator's key for the information-theoretic 3-server DPF.
|
|||
|
|
struct it_dpf3_key
|
|||
|
|
{
|
|||
|
|
static constexpr std::size_t domain_size = 256;
|
|||
|
|
using input_type = std::uint8_t;
|
|||
|
|
using output_type = std::uint64_t;
|
|||
|
|
|
|||
|
|
std::uint8_t party = 0;
|
|||
|
|
std::array<output_type, domain_size> share{};
|
|||
|
|
};
|
|||
|
|
|
|||
|
|
/// @brief Three additive keys for `f_{α,β}` on `{0..255} → uint64_t`.
|
|||
|
|
/// @details `eval_it_dpf3(k0,x) + eval_it_dpf3(k1,x) + eval_it_dpf3(k2,x)` equals
|
|||
|
|
/// `β` at `x = α` and `0` elsewhere (wrapping `uint64_t` arithmetic).
|
|||
|
|
/// \complexity O(N) samples for domain size `N = 256`. Key size is `N` words
|
|||
|
|
/// per party (truth-table share), not subpolynomial.
|
|||
|
|
HEDLEY_WARN_UNUSED_RESULT
|
|||
|
|
inline auto make_it_dpf3(std::uint8_t alpha, std::uint64_t beta)
|
|||
|
|
{
|
|||
|
|
it_dpf3_key k0;
|
|||
|
|
it_dpf3_key k1;
|
|||
|
|
it_dpf3_key k2;
|
|||
|
|
k0.party = 0;
|
|||
|
|
k1.party = 1;
|
|||
|
|
k2.party = 2;
|
|||
|
|
for (std::size_t x = 0; x < it_dpf3_key::domain_size; ++x)
|
|||
|
|
{
|
|||
|
|
const std::uint64_t secret =
|
|||
|
|
(static_cast<std::uint8_t>(x) == alpha) ? beta : 0;
|
|||
|
|
auto [a, b, c] = additively_share3(secret);
|
|||
|
|
k0.share[x] = a.raw();
|
|||
|
|
k1.share[x] = b.raw();
|
|||
|
|
k2.share[x] = c.raw();
|
|||
|
|
}
|
|||
|
|
return std::make_tuple(std::move(k0), std::move(k1), std::move(k2));
|
|||
|
|
}
|
|||
|
|
|
|||
|
|
/// @brief One additive share of `f_{α,β}(x)`.
|
|||
|
|
/// \complexity O(1).
|
|||
|
|
HEDLEY_ALWAYS_INLINE
|
|||
|
|
HEDLEY_NO_THROW
|
|||
|
|
HEDLEY_WARN_UNUSED_RESULT
|
|||
|
|
constexpr std::uint64_t eval_it_dpf3(const it_dpf3_key & key,
|
|||
|
|
std::uint8_t x) noexcept
|
|||
|
|
{
|
|||
|
|
return key.share[x];
|
|||
|
|
}
|
|||
|
|
|
|||
|
|
/// @brief `sum_x eval_it_dpf3(key, x) * weights[x]` over the whole domain.
|
|||
|
|
/// \complexity O(N) multiply-adds, `N = 256`.
|
|||
|
|
template <typename Weights>
|
|||
|
|
HEDLEY_WARN_UNUSED_RESULT
|
|||
|
|
auto eval_it_dpf3_inner_product(const it_dpf3_key & key, Weights && weights)
|
|||
|
|
{
|
|||
|
|
std::uint64_t acc = 0;
|
|||
|
|
for (std::size_t x = 0; x < it_dpf3_key::domain_size; ++x)
|
|||
|
|
acc += key.share[x] * static_cast<std::uint64_t>(weights[x]);
|
|||
|
|
return acc;
|
|||
|
|
}
|
|||
|
|
|
|||
|
|
} // namespace dpf
|
|||
|
|
|
|||
|
|
#endif // LIBDPF_INCLUDE_DPF_IT_DPF3_HPP__
|