Ryan Henry
0d22946a0e
Ship the TLS mesh, composer, Beaver/Yao/leaf MPC, prep/online paths, apps, and docs so the tree is pushable before elevating share_expr, security_mode, and prep resume. Co-authored-by: Cursor <cursoragent@cursor.com>
94 lines
3.2 KiB
C++
94 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__
|