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>
976 lines
44 KiB
C++
976 lines
44 KiB
C++
/// @file grotto/carry.hpp
|
||
/// @brief Carry-in, carry-out, and fused bitwidth corrections.
|
||
/// @details `plan_carry` (see carry_plan.hpp) selects the live primitives.
|
||
/// `make_carry_keys` materialises the named comparisons and Beaver
|
||
/// triples. Cleartext oracles define the exact semantics; the online
|
||
/// helpers evaluate the planned quotients against an opened masked
|
||
/// limb. Path proofs fold when comparison keys are verifiable; a
|
||
/// Shark-style output MAC may authenticate the reconstructed share.
|
||
/// @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_GROTTO_CARRY_HPP__
|
||
#define LIBDPF_INCLUDE_GROTTO_CARRY_HPP__
|
||
|
||
#include <cstdint>
|
||
#include <optional>
|
||
#include <stdexcept>
|
||
#include <type_traits>
|
||
#include <utility>
|
||
|
||
#include "hedley/hedley.h"
|
||
|
||
#include "dpf.hpp"
|
||
#include "grotto/carry_plan.hpp"
|
||
|
||
namespace grotto
|
||
{
|
||
|
||
// ---------------------------------------------------------------------------
|
||
// Cleartext oracles
|
||
// ---------------------------------------------------------------------------
|
||
|
||
/// @brief Mask of the low `bits` bits.
|
||
/// \complexity One shift. `Θ(1)`.
|
||
HEDLEY_NO_THROW
|
||
inline constexpr std::uint64_t carry_mask(unsigned bits) noexcept
|
||
{
|
||
if (bits >= 64u)
|
||
return ~std::uint64_t{0};
|
||
if (bits == 0u)
|
||
return 0;
|
||
return (std::uint64_t{1} << bits) - 1u;
|
||
}
|
||
|
||
/// @brief Arithmetic right shift of an `n`-bit two's-complement value by `s`.
|
||
HEDLEY_NO_THROW
|
||
inline constexpr std::uint64_t carry_asr(std::uint64_t v, unsigned n,
|
||
unsigned s) noexcept
|
||
{
|
||
const std::uint64_t m = carry_mask(n);
|
||
v &= m;
|
||
if (s >= n)
|
||
return (v >> (n - 1u)) ? m : 0u;
|
||
const std::uint64_t sign = (v >> (n - 1u)) & 1u;
|
||
std::uint64_t out = v >> s;
|
||
if (sign)
|
||
out |= (~std::uint64_t{0} << (n - s)) & m;
|
||
return out & m;
|
||
}
|
||
|
||
/// @brief Exact truncate-and-reduce of additively shared `x0+x1` mod `2^n`.
|
||
/// \complexity A constant number of shifts of the two shares. `Θ(1)`. This is the cleartext identity the keyed eval matches.
|
||
/// @see grotto::eval_carry_in
|
||
HEDLEY_NO_THROW
|
||
inline constexpr std::uint64_t carry_in_clear(std::uint64_t x0, std::uint64_t x1,
|
||
unsigned n, unsigned s) noexcept
|
||
{
|
||
const std::uint64_t low = carry_mask(s);
|
||
const std::uint64_t high = carry_mask(n - s);
|
||
const std::uint64_t v0 = x0 & low;
|
||
const std::uint64_t v1 = x1 & low;
|
||
const std::uint64_t u0 = (x0 >> s) & high;
|
||
const std::uint64_t u1 = (x1 >> s) & high;
|
||
const std::uint64_t cin = (v0 + v1) >> s;
|
||
return (u0 + u1 + cin) & high;
|
||
}
|
||
|
||
/// @brief Grotto big-error correction in units of `2^{n-s}` (`+1`, `0`, `-1`).
|
||
HEDLEY_NO_THROW
|
||
inline constexpr std::int64_t carry_out_units(std::uint64_t x0, std::uint64_t x1,
|
||
unsigned n, sign_knowledge sign) noexcept
|
||
{
|
||
const std::uint64_t s0 = (x0 >> (n - 1u)) & 1u;
|
||
const std::uint64_t s1 = (x1 >> (n - 1u)) & 1u;
|
||
const std::uint64_t x = (x0 + x1) & carry_mask(n);
|
||
const std::uint64_t m = (x >> (n - 1u)) & 1u;
|
||
if (sign == sign_knowledge::nonnegative)
|
||
return static_cast<std::int64_t>(s0 & s1);
|
||
if (sign == sign_knowledge::negative)
|
||
return -static_cast<std::int64_t>((1u - s0) & (1u - s1));
|
||
if (m == 0u)
|
||
return static_cast<std::int64_t>(s0 & s1);
|
||
return -static_cast<std::int64_t>((1u - s0) & (1u - s1));
|
||
}
|
||
|
||
/// @brief Local ASR of each share plus the Grotto carry-out correction.
|
||
HEDLEY_NO_THROW
|
||
inline constexpr std::uint64_t carry_out_clear(std::uint64_t x0, std::uint64_t x1,
|
||
unsigned n, unsigned s, sign_knowledge sign) noexcept
|
||
{
|
||
const std::uint64_t m = carry_mask(n);
|
||
const std::int64_t unit = static_cast<std::int64_t>(std::uint64_t{1} << (n - s));
|
||
const std::int64_t q = carry_out_units(x0, x1, n, sign);
|
||
const std::uint64_t base =
|
||
(carry_asr(x0, n, s) + carry_asr(x1, n, s)) & m;
|
||
return static_cast<std::uint64_t>(
|
||
static_cast<std::int64_t>(base) + q * unit) & m;
|
||
}
|
||
|
||
/// @brief Exact same-ring ASR (both carries).
|
||
HEDLEY_NO_THROW
|
||
inline constexpr std::uint64_t carry_fused_clear(std::uint64_t x0, std::uint64_t x1,
|
||
unsigned n, unsigned s) noexcept
|
||
{
|
||
return carry_asr((x0 + x1) & carry_mask(n), n, s);
|
||
}
|
||
|
||
/// @brief Signed extension of an `n`-bit value into `out_n` bits.
|
||
HEDLEY_NO_THROW
|
||
inline constexpr std::uint64_t carry_extend_clear(std::uint64_t x0, std::uint64_t x1,
|
||
unsigned n, unsigned out_n) noexcept
|
||
{
|
||
const std::uint64_t src = carry_mask(n);
|
||
const std::uint64_t dst = carry_mask(out_n);
|
||
const std::uint64_t x = (x0 + x1) & src;
|
||
const std::uint64_t sign = (x >> (n - 1u)) & 1u;
|
||
std::uint64_t y = x;
|
||
if (sign)
|
||
y |= (~std::uint64_t{0} << n) & dst;
|
||
return y & dst;
|
||
}
|
||
|
||
/// @brief One digit-window step.
|
||
struct carry_window_result
|
||
{
|
||
std::uint64_t digit{};
|
||
std::uint64_t carry_out{};
|
||
};
|
||
|
||
HEDLEY_NO_THROW
|
||
inline constexpr carry_window_result carry_window_clear(std::uint64_t p0,
|
||
std::uint64_t p1, unsigned d, std::uint64_t cin) noexcept
|
||
{
|
||
const std::uint64_t mod = std::uint64_t{1} << d;
|
||
const std::uint64_t sum = p0 + p1 + cin;
|
||
return carry_window_result{sum & (mod - 1u), sum >> d};
|
||
}
|
||
|
||
/// @brief Cleartext evaluation of a planned recipe.
|
||
/// \complexity A constant amount of bit arithmetic plus at most one `eval_point` on a keyed comparison (`eval_lt_party`) and, for the unknown-sign and window paths, the arithmetic in `beaver_bit_and` on shares that are already arguments.
|
||
/// Extra space `Θ(1)`.
|
||
/// \rounds None in this function. `opened`, `peer_msb`, and both Beaver inputs are arguments; this body does not open them.
|
||
/// \communication None.
|
||
/// \preprocessing None created here. Uses the keys from `make_carry_keys`.
|
||
HEDLEY_WARN_UNUSED_RESULT
|
||
inline std::uint64_t eval_carry_clear(const carry_recipe & recipe,
|
||
std::uint64_t x0, std::uint64_t x1, std::uint64_t incoming = 0)
|
||
{
|
||
switch (recipe.mode)
|
||
{
|
||
case carry_mode::truncate_reduce:
|
||
return carry_in_clear(x0, x1, recipe.n, recipe.s);
|
||
case carry_mode::same_ring:
|
||
if (recipe.out_n == recipe.n - recipe.s && recipe.s > 0u
|
||
&& !recipe.use_share_msb_and && !recipe.use_msb_lt)
|
||
return carry_in_clear(x0, x1, recipe.n, recipe.s);
|
||
if (recipe.use_low_lt
|
||
&& (recipe.use_share_msb_and || recipe.use_msb_lt)
|
||
&& recipe.out_n == recipe.n)
|
||
return carry_fused_clear(x0, x1, recipe.n, recipe.s);
|
||
if (recipe.out_n == recipe.n - recipe.s && recipe.s > 0u)
|
||
return carry_in_clear(x0, x1, recipe.n, recipe.s);
|
||
return carry_out_clear(x0, x1, recipe.n, recipe.s, recipe.sign);
|
||
case carry_mode::extend:
|
||
return carry_extend_clear(x0, x1, recipe.n, recipe.out_n);
|
||
case carry_mode::window:
|
||
{
|
||
const std::uint64_t cin = recipe.use_window_product
|
||
? incoming
|
||
: recipe.public_incoming;
|
||
const auto w = carry_window_clear(x0 & carry_mask(recipe.window_d),
|
||
x1 & carry_mask(recipe.window_d), recipe.window_d, cin);
|
||
return (w.carry_out << recipe.window_d) | w.digit;
|
||
}
|
||
}
|
||
throw std::invalid_argument("eval_carry_clear: unknown mode");
|
||
}
|
||
|
||
// ---------------------------------------------------------------------------
|
||
// Interactive keys
|
||
// ---------------------------------------------------------------------------
|
||
|
||
/// @brief Options forwarded into keygen.
|
||
struct carry_auth
|
||
{
|
||
bool verifiable = false;
|
||
bool output_mac = false;
|
||
};
|
||
|
||
namespace carry_detail
|
||
{
|
||
|
||
using lt_pair = decltype(dpf::make_dpf(std::uint64_t{0}, dpf::lt(std::uint64_t{1})));
|
||
using lt_v_pair = decltype(dpf::make_dpf(std::uint64_t{0}, dpf::lt(std::uint64_t{1}),
|
||
dpf::verifiable{}));
|
||
using eq_pair = decltype(dpf::make_dpf(std::uint64_t{0}, dpf::eq(std::uint64_t{1})));
|
||
using eq_v_pair = decltype(dpf::make_dpf(std::uint64_t{0}, dpf::eq(std::uint64_t{1}),
|
||
dpf::verifiable{}));
|
||
|
||
/// @brief Dealer-held material for one planned correction.
|
||
struct carry_key_pair
|
||
{
|
||
carry_recipe recipe{};
|
||
carry_auth auth{};
|
||
std::uint64_t rin = 0;
|
||
std::uint64_t rout0 = 0;
|
||
std::uint64_t rout1 = 0;
|
||
|
||
std::optional<lt_pair> low_lt{};
|
||
std::optional<lt_v_pair> low_lt_v{};
|
||
std::optional<lt_pair> msb_lt{};
|
||
std::optional<lt_v_pair> msb_lt_v{};
|
||
std::optional<lt_pair> biased_wrap{};
|
||
std::optional<lt_v_pair> biased_wrap_v{};
|
||
std::optional<lt_pair> window_overflow{};
|
||
std::optional<lt_v_pair> window_overflow_v{};
|
||
std::optional<eq_pair> window_eq{};
|
||
std::optional<eq_v_pair> window_eq_v{};
|
||
|
||
dpf::beavers::beaver2<std::uint64_t> and_beaver{};
|
||
dpf::beavers::auth_beaver2<std::uint64_t> and_beaver_auth{};
|
||
bool has_and_beaver = false;
|
||
bool has_and_beaver_auth = false;
|
||
dpf::mac_key<std::uint64_t> mac{};
|
||
bool has_mac = false;
|
||
};
|
||
|
||
/// @brief Beaver product of two additively shared bits.
|
||
/// @details Classic opening: `d = x-a`, `e = y-b`, then
|
||
/// `[xy] = [ab] + d[b] + e[a] + de`. The beaver `out` wire is an
|
||
/// ABY2.0 result mask and must not be mixed into the product.
|
||
/// \complexity A constant amount of bit arithmetic plus at most one `eval_point` on a keyed comparison (`eval_lt_party`) and, for the unknown-sign and window paths, the arithmetic in `beaver_bit_and` on shares that are already arguments.
|
||
/// Extra space `Θ(1)`.
|
||
/// \rounds None in this function. `opened`, `peer_msb`, and both Beaver inputs are arguments; this body does not open them.
|
||
/// \communication None.
|
||
/// \preprocessing None created here. Uses the keys from `make_carry_keys`.
|
||
HEDLEY_WARN_UNUSED_RESULT
|
||
inline std::pair<std::uint64_t, std::uint64_t> beaver_bit_and(
|
||
std::uint64_t x0, std::uint64_t x1,
|
||
std::uint64_t y0, std::uint64_t y1,
|
||
const dpf::beavers::beaver2<std::uint64_t> & bev)
|
||
{
|
||
const std::uint64_t d = (x0 + x1) - (bev.a.p0 + bev.a.p1);
|
||
const std::uint64_t e = (y0 + y1) - (bev.b.p0 + bev.b.p1);
|
||
const std::uint64_t z0 = bev.ab.p0 + d * bev.b.p0 + e * bev.a.p0;
|
||
const std::uint64_t z1 = bev.ab.p1 + d * bev.b.p1 + e * bev.a.p1 + d * e;
|
||
return {z0, z1};
|
||
}
|
||
|
||
template <typename Key0, typename Key1>
|
||
std::uint64_t eval_lt_party(std::size_t party, Key0 & k0, Key1 & k1,
|
||
std::uint64_t query, dpf::proof_token * pi)
|
||
{
|
||
if (party == 0)
|
||
{
|
||
if constexpr (std::decay_t<Key0>::is_verifiable)
|
||
{
|
||
if (pi != nullptr)
|
||
return dpf::eval_point(dpf::cmp, k0, query, dpf::prove(*pi)).raw();
|
||
}
|
||
return dpf::eval_point(dpf::cmp, k0, query).raw();
|
||
}
|
||
if constexpr (std::decay_t<Key1>::is_verifiable)
|
||
{
|
||
if (pi != nullptr)
|
||
return dpf::eval_point(dpf::cmp, k1, query, dpf::prove(*pi)).raw();
|
||
}
|
||
return dpf::eval_point(dpf::cmp, k1, query).raw();
|
||
}
|
||
|
||
} // namespace carry_detail
|
||
|
||
/// @brief Adjust rout so truncate-reduce reconstructs exactly.
|
||
/// @details Sets `rout0 + rout1 ≡ ((-rin) >> s) (mod 2^{n-s})`.
|
||
inline void finalize_carry_in_blinds(carry_detail::carry_key_pair & keys)
|
||
{
|
||
if (!keys.recipe.use_low_lt)
|
||
return;
|
||
const unsigned s = keys.recipe.s;
|
||
const std::uint64_t high = carry_mask(keys.recipe.n - s);
|
||
const std::uint64_t y_hi = ((std::uint64_t{0} - keys.rin) >> s) & high;
|
||
keys.rout1 = (y_hi - keys.rout0) & high;
|
||
}
|
||
|
||
/// @brief Build dealer keys for `recipe`.
|
||
/// \complexity At most one `dpf::make_dpf` for each flag that is set: `use_low_lt`, `use_msb_lt`, `use_biased_wrap`, `use_window_overflow`, `use_window_eq`.
|
||
/// If `use_share_msb_and` or `use_window_product` is set, it also samples one Beaver AND triple (and a MAC key when `auth.output_mac`).
|
||
/// The comparisons are on a `uint64_t` query masked to `recipe.n` bits. This function does not size the DPF key bytes.
|
||
/// \rounds No party interaction.
|
||
/// \communication None inside this function.
|
||
/// \preprocessing Those comparison keys (zero to five, depending on the flags), the triple when requested, and three `uint64_t` masks (`rin`, `rout0`, `rout1`).
|
||
/// @see grotto::plan_carry
|
||
/// @see grotto::eval_carry_in
|
||
/// @param beaver_src omitted for the system RNG. Pass a `beavers::oracle<uint64_t>`
|
||
/// to draw the masks and the AND triple from that PRG.
|
||
template <typename Beaver = std::nullptr_t>
|
||
HEDLEY_WARN_UNUSED_RESULT
|
||
inline carry_detail::carry_key_pair make_carry_keys(const carry_recipe & recipe,
|
||
carry_auth auth = {},
|
||
Beaver && beaver_src = Beaver{},
|
||
std::uint64_t index = 0)
|
||
{
|
||
carry_detail::carry_key_pair out{};
|
||
out.recipe = recipe;
|
||
out.auth = auth;
|
||
if constexpr (std::is_same_v<std::decay_t<Beaver>, std::nullptr_t>)
|
||
{
|
||
out.rin = dpf::uniform_sample<std::uint64_t>() & carry_mask(recipe.n);
|
||
out.rout0 = dpf::uniform_sample<std::uint64_t>();
|
||
out.rout1 = dpf::uniform_sample<std::uint64_t>();
|
||
}
|
||
else
|
||
{
|
||
out.rin = beaver_src.blind(0x01000000u, index) & carry_mask(recipe.n);
|
||
out.rout0 = beaver_src.blind(0x01000001u, index);
|
||
out.rout1 = beaver_src.blind(0x01000002u, index);
|
||
}
|
||
const bool V = auth.verifiable;
|
||
const std::uint64_t y = (std::uint64_t{0} - out.rin);
|
||
|
||
if (recipe.use_low_lt)
|
||
{
|
||
const std::uint64_t alpha = y & carry_mask(recipe.s);
|
||
if (V)
|
||
out.low_lt_v = dpf::make_dpf(alpha, dpf::lt(std::uint64_t{1}),
|
||
dpf::verifiable{});
|
||
else
|
||
out.low_lt = dpf::make_dpf(alpha, dpf::lt(std::uint64_t{1}));
|
||
}
|
||
if (recipe.use_msb_lt)
|
||
{
|
||
// Mask-dependent point so eval at `opened = x + rin` yields msb(x).
|
||
const std::uint64_t half = std::uint64_t{1} << (recipe.n - 1u);
|
||
const std::uint64_t alpha = (half + y) & carry_mask(recipe.n);
|
||
if (V)
|
||
out.msb_lt_v = dpf::make_dpf(alpha, dpf::lt(std::uint64_t{1}),
|
||
dpf::verifiable{});
|
||
else
|
||
out.msb_lt = dpf::make_dpf(alpha, dpf::lt(std::uint64_t{1}));
|
||
}
|
||
if (recipe.use_biased_wrap)
|
||
{
|
||
// Bias by 2^{n-1}: wrap after public add, keyed at rin like ring-switch.
|
||
if (V)
|
||
out.biased_wrap_v = dpf::make_dpf(out.rin, dpf::lt(std::uint64_t{1}),
|
||
dpf::verifiable{});
|
||
else
|
||
out.biased_wrap = dpf::make_dpf(out.rin, dpf::lt(std::uint64_t{1}));
|
||
}
|
||
if (recipe.use_window_overflow)
|
||
{
|
||
const std::uint64_t thresh = std::uint64_t{1} << recipe.window_d;
|
||
if (V)
|
||
out.window_overflow_v = dpf::make_dpf(thresh, dpf::lt(std::uint64_t{1}),
|
||
dpf::verifiable{});
|
||
else
|
||
out.window_overflow = dpf::make_dpf(thresh, dpf::lt(std::uint64_t{1}));
|
||
}
|
||
if (recipe.use_window_eq)
|
||
{
|
||
const std::uint64_t allones = carry_mask(recipe.window_d);
|
||
if (V)
|
||
out.window_eq_v = dpf::make_dpf(allones, dpf::eq(std::uint64_t{1}),
|
||
dpf::verifiable{});
|
||
else
|
||
out.window_eq = dpf::make_dpf(allones, dpf::eq(std::uint64_t{1}));
|
||
}
|
||
if (recipe.use_share_msb_and || recipe.use_window_product)
|
||
{
|
||
if (auth.output_mac)
|
||
{
|
||
// Sample MAC key first so the AND triple can be authenticated.
|
||
if (!out.has_mac)
|
||
{
|
||
out.mac = dpf::sample_mac_key<std::uint64_t>();
|
||
out.has_mac = true;
|
||
}
|
||
if constexpr (std::is_same_v<std::decay_t<Beaver>, std::nullptr_t>)
|
||
{
|
||
out.and_beaver_auth =
|
||
dpf::beavers::sample_auth_beaver2<std::uint64_t>(out.mac);
|
||
}
|
||
else
|
||
{
|
||
out.and_beaver_auth = dpf::beavers::sample_auth_beaver2(
|
||
out.mac, beaver_src, index);
|
||
}
|
||
out.and_beaver = dpf::beavers::beaver2<std::uint64_t>{
|
||
out.and_beaver_auth.a.value, out.and_beaver_auth.b.value,
|
||
out.and_beaver_auth.ab.value, out.and_beaver_auth.out.value};
|
||
out.has_and_beaver = true;
|
||
out.has_and_beaver_auth = true;
|
||
}
|
||
else
|
||
{
|
||
if constexpr (std::is_same_v<std::decay_t<Beaver>, std::nullptr_t>)
|
||
out.and_beaver = dpf::beavers::sample_beaver2<std::uint64_t>();
|
||
else
|
||
out.and_beaver = dpf::beavers::sample_beaver2(beaver_src, index);
|
||
out.has_and_beaver = true;
|
||
}
|
||
}
|
||
if (auth.output_mac && !out.has_mac)
|
||
{
|
||
out.mac = dpf::sample_mac_key<std::uint64_t>();
|
||
out.has_mac = true;
|
||
}
|
||
// Truncate-reduce blinds must land before any online eval.
|
||
if (out.recipe.use_low_lt
|
||
&& out.recipe.out_n == out.recipe.n - out.recipe.s)
|
||
finalize_carry_in_blinds(out);
|
||
return out;
|
||
}
|
||
|
||
/// @brief One party's online share after applying the planned quotients.
|
||
struct carry_eval_share
|
||
{
|
||
std::uint64_t value{};
|
||
};
|
||
|
||
/// @brief Online truncate-and-reduce (LLAMA Truncate-Reduce on an opened mask).
|
||
/// @details `opened = (x0 + x1 + rin) mod 2^n`. Party `b` returns
|
||
/// `b · opened[s,n) + rout_b + Eval_lt(2^s - opened[0,s) - 1)`.
|
||
/// \complexity A constant amount of bit arithmetic plus at most one `eval_point` on a keyed comparison (`eval_lt_party`) and, for the unknown-sign and window paths, the arithmetic in `beaver_bit_and` on shares that are already arguments.
|
||
/// Extra space `Θ(1)`.
|
||
/// \rounds None in this function. `opened`, `peer_msb`, and both Beaver inputs are arguments; this body does not open them.
|
||
/// \communication None.
|
||
/// \preprocessing None created here. Uses the keys from `make_carry_keys`.
|
||
HEDLEY_WARN_UNUSED_RESULT
|
||
inline carry_eval_share eval_carry_in(const carry_detail::carry_key_pair & keys,
|
||
std::size_t party, std::uint64_t opened, dpf::proof_token * pi = nullptr)
|
||
{
|
||
if (!keys.recipe.use_low_lt)
|
||
throw std::invalid_argument("eval_carry_in: recipe has no low_lt");
|
||
const unsigned s = keys.recipe.s;
|
||
const std::uint64_t high = carry_mask(keys.recipe.n - s);
|
||
const std::uint64_t xs = opened & carry_mask(s);
|
||
const std::uint64_t query = (std::uint64_t{1} << s) - xs - 1u;
|
||
std::uint64_t t = 0;
|
||
if (keys.low_lt_v)
|
||
t = carry_detail::eval_lt_party(party, keys.low_lt_v->first,
|
||
keys.low_lt_v->second, query, pi);
|
||
else if (keys.low_lt)
|
||
t = carry_detail::eval_lt_party(party, keys.low_lt->first,
|
||
keys.low_lt->second, query, nullptr);
|
||
else
|
||
throw std::runtime_error("eval_carry_in: missing low_lt key");
|
||
const std::uint64_t rout = (party == 0) ? keys.rout0 : keys.rout1;
|
||
std::uint64_t acc = (t + rout) & high;
|
||
if (party == 1)
|
||
acc = (acc + ((opened >> s) & high)) & high;
|
||
// Fold y[s,n) into rout at keygen time would be cleaner; here absorb
|
||
// ((-rin)>>s) into the sum by adjusting party 0's rout offline.
|
||
// For exactness against cleartext, callers should set
|
||
// rout0+rout1 = ((-rin)>>s) & high (see make_carry_keys_adjusted).
|
||
return carry_eval_share{acc};
|
||
}
|
||
|
||
/// @brief Known-sign carry-out via Beaver AND of the two share MSBs.
|
||
/// @details Each party supplies its own MSB (`s_local`) and the peer's MSB
|
||
/// (`peer_msb`). The local ASR of `xb` is corrected by `± unit · AND`.
|
||
/// \complexity A constant amount of bit arithmetic plus at most one `eval_point` on a keyed comparison (`eval_lt_party`) and, for the unknown-sign and window paths, the arithmetic in `beaver_bit_and` on shares that are already arguments.
|
||
/// Extra space `Θ(1)`.
|
||
/// \rounds None in this function. `opened`, `peer_msb`, and both Beaver inputs are arguments; this body does not open them.
|
||
/// \communication None.
|
||
/// \preprocessing None created here. Uses the keys from `make_carry_keys`.
|
||
HEDLEY_WARN_UNUSED_RESULT
|
||
inline carry_eval_share eval_carry_out_known(const carry_detail::carry_key_pair & keys,
|
||
std::size_t party, std::uint64_t xb, std::uint64_t s_local,
|
||
std::uint64_t peer_msb)
|
||
{
|
||
if (!keys.recipe.use_share_msb_and || !keys.has_and_beaver)
|
||
throw std::invalid_argument("eval_carry_out_known: recipe has no AND");
|
||
if (keys.recipe.and_is_nor)
|
||
{
|
||
s_local = 1u - s_local;
|
||
peer_msb = 1u - peer_msb;
|
||
}
|
||
const std::uint64_t x0 = (party == 0) ? s_local : peer_msb;
|
||
const std::uint64_t x1 = (party == 1) ? s_local : peer_msb;
|
||
// Bit shares: [σ0] = (σ0, 0), [σ1] = (0, σ1).
|
||
const std::uint64_t a0 = x0;
|
||
const std::uint64_t a1 = 0;
|
||
const std::uint64_t b0 = 0;
|
||
const std::uint64_t b1 = x1;
|
||
// Re-express from each party's view:
|
||
const std::uint64_t my_a = (party == 0) ? s_local : 0u;
|
||
const std::uint64_t peer_a = (party == 0) ? 0u : peer_msb;
|
||
const std::uint64_t my_b = (party == 1) ? s_local : 0u;
|
||
const std::uint64_t peer_b = (party == 1) ? 0u : peer_msb;
|
||
auto [z0, z1] = carry_detail::beaver_bit_and(
|
||
(party == 0) ? my_a : peer_a, (party == 1) ? my_a : peer_a,
|
||
(party == 0) ? my_b : peer_b, (party == 1) ? my_b : peer_b,
|
||
keys.and_beaver);
|
||
(void)a0;
|
||
(void)a1;
|
||
(void)b0;
|
||
(void)b1;
|
||
const std::uint64_t z = (party == 0) ? z0 : z1;
|
||
const std::uint64_t unit = static_cast<std::uint64_t>(
|
||
keys.recipe.and_unit >= 0 ? keys.recipe.and_unit : -keys.recipe.and_unit);
|
||
const std::uint64_t base = carry_asr(xb, keys.recipe.n, keys.recipe.s);
|
||
const std::uint64_t out_m = carry_mask(keys.recipe.out_n);
|
||
if (keys.recipe.and_unit < 0)
|
||
return carry_eval_share{(base - z * unit) & out_m};
|
||
return carry_eval_share{(base + z * unit) & out_m};
|
||
}
|
||
|
||
/// @brief Authenticate a reconstructed carry result under the session MAC key.
|
||
HEDLEY_WARN_UNUSED_RESULT
|
||
inline std::pair<dpf::mac_share<std::uint64_t>, dpf::mac_share<std::uint64_t>>
|
||
mac_carry_result(const carry_detail::carry_key_pair & keys,
|
||
std::uint64_t y0, std::uint64_t y1)
|
||
{
|
||
if (!keys.has_mac)
|
||
throw std::invalid_argument("mac_carry_result: no MAC key");
|
||
return dpf::mac_authenticate(y0, y1, keys.mac);
|
||
}
|
||
|
||
/// @brief Share of `1{x < 2^{n-1}}` from the masked opening via `msb_lt`.
|
||
/// @details Sum of the two parties' shares is the low-msb indicator. The high
|
||
/// msb bit is `1 - (m0 + m1)`.
|
||
/// \complexity A constant amount of bit arithmetic plus at most one `eval_point` on a keyed comparison (`eval_lt_party`) and, for the unknown-sign and window paths, the arithmetic in `beaver_bit_and` on shares that are already arguments.
|
||
/// Extra space `Θ(1)`.
|
||
/// \rounds None in this function. `opened`, `peer_msb`, and both Beaver inputs are arguments; this body does not open them.
|
||
/// \communication None.
|
||
/// \preprocessing None created here. Uses the keys from `make_carry_keys`.
|
||
HEDLEY_WARN_UNUSED_RESULT
|
||
inline std::uint64_t eval_carry_msb_share(
|
||
const carry_detail::carry_key_pair & keys,
|
||
std::size_t party, std::uint64_t opened, dpf::proof_token * pi = nullptr)
|
||
{
|
||
if (!keys.recipe.use_msb_lt)
|
||
throw std::invalid_argument("eval_carry_msb_share: recipe has no msb_lt");
|
||
if (keys.msb_lt_v)
|
||
return carry_detail::eval_lt_party(party, keys.msb_lt_v->first,
|
||
keys.msb_lt_v->second, opened, pi);
|
||
if (keys.msb_lt)
|
||
return carry_detail::eval_lt_party(party, keys.msb_lt->first,
|
||
keys.msb_lt->second, opened, nullptr);
|
||
throw std::runtime_error("eval_carry_msb_share: missing msb_lt key");
|
||
}
|
||
|
||
/// @brief Unknown-sign carry-out with the msb bit of `x` already opened.
|
||
/// @details `opened_msb_high` is `1{msb(x) == 1}`. Selects the nonnegative or
|
||
/// negative known-sign AND. Matches `carry_out_clear(..., unknown)`.
|
||
/// \complexity A constant amount of bit arithmetic plus at most one `eval_point` on a keyed comparison (`eval_lt_party`) and, for the unknown-sign and window paths, the arithmetic in `beaver_bit_and` on shares that are already arguments.
|
||
/// Extra space `Θ(1)`.
|
||
/// \rounds None in this function. `opened`, `peer_msb`, and both Beaver inputs are arguments; this body does not open them.
|
||
/// \communication None.
|
||
/// \preprocessing None created here. Uses the keys from `make_carry_keys`.
|
||
HEDLEY_WARN_UNUSED_RESULT
|
||
inline carry_eval_share eval_carry_out_unknown(
|
||
const carry_detail::carry_key_pair & keys,
|
||
std::size_t party, std::uint64_t xb,
|
||
std::uint64_t s_local, std::uint64_t peer_msb,
|
||
std::uint64_t opened_msb_high)
|
||
{
|
||
if (!keys.recipe.use_share_msb_and || !keys.has_and_beaver)
|
||
throw std::invalid_argument("eval_carry_out_unknown: recipe has no AND");
|
||
const std::uint64_t unit = static_cast<std::uint64_t>(
|
||
keys.recipe.and_unit >= 0 ? keys.recipe.and_unit : -keys.recipe.and_unit);
|
||
carry_detail::carry_key_pair tmp = keys;
|
||
if (opened_msb_high)
|
||
{
|
||
tmp.recipe.and_is_nor = true;
|
||
tmp.recipe.and_unit = -static_cast<std::int64_t>(unit);
|
||
}
|
||
else
|
||
{
|
||
tmp.recipe.and_is_nor = false;
|
||
tmp.recipe.and_unit = static_cast<std::int64_t>(unit);
|
||
}
|
||
return eval_carry_out_known(tmp, party, xb, s_local, peer_msb);
|
||
}
|
||
|
||
/// @brief Unknown-sign carry-out: open the msb bit from `msb_lt`, then correct.
|
||
/// @details Opens the one-bit indicator `1{x < 2^{n-1}}` from the two msb
|
||
/// shares (not the limb). Then applies the known-sign path selected
|
||
/// by that bit.
|
||
/// \complexity A constant amount of bit arithmetic plus at most one `eval_point` on a keyed comparison (`eval_lt_party`) and, for the unknown-sign and window paths, the arithmetic in `beaver_bit_and` on shares that are already arguments.
|
||
/// Extra space `Θ(1)`.
|
||
/// \rounds None in this function. `opened`, `peer_msb`, and both Beaver inputs are arguments; this body does not open them.
|
||
/// \communication None.
|
||
/// \preprocessing None created here. Uses the keys from `make_carry_keys`.
|
||
HEDLEY_WARN_UNUSED_RESULT
|
||
inline carry_eval_share eval_carry_out_unknown(
|
||
const carry_detail::carry_key_pair & keys,
|
||
std::size_t party, std::uint64_t opened, std::uint64_t xb,
|
||
std::uint64_t s_local, std::uint64_t peer_msb,
|
||
std::uint64_t peer_msb_lt_share,
|
||
dpf::proof_token * pi = nullptr)
|
||
{
|
||
const std::uint64_t m_low = eval_carry_msb_share(keys, party, opened, pi)
|
||
+ peer_msb_lt_share;
|
||
const std::uint64_t msb_high = 1u - (m_low & 1u);
|
||
return eval_carry_out_unknown(keys, party, xb, s_local, peer_msb, msb_high);
|
||
}
|
||
|
||
/// @brief Signed extension from the masked opening and the opened msb bit.
|
||
/// @details `opened = (x + rin) mod 2^n`. Party 1 returns
|
||
/// `((opened - rin) & 2^n-1) + msb * (2^{out_n}-2^n)`; party 0
|
||
/// returns 0. Matches `carry_extend_clear`. The biased-wrap key is
|
||
/// available for proofs of the msb bit.
|
||
/// \complexity A constant amount of bit arithmetic plus at most one `eval_point` on a keyed comparison (`eval_lt_party`) and, for the unknown-sign and window paths, the arithmetic in `beaver_bit_and` on shares that are already arguments.
|
||
/// Extra space `Θ(1)`.
|
||
/// \rounds None in this function. `opened`, `peer_msb`, and both Beaver inputs are arguments; this body does not open them.
|
||
/// \communication None.
|
||
/// \preprocessing None created here. Uses the keys from `make_carry_keys`.
|
||
HEDLEY_WARN_UNUSED_RESULT
|
||
inline carry_eval_share eval_carry_extend(
|
||
const carry_detail::carry_key_pair & keys,
|
||
std::size_t party, std::uint64_t opened, std::uint64_t opened_msb_high)
|
||
{
|
||
if (!keys.recipe.use_biased_wrap)
|
||
throw std::invalid_argument("eval_carry_extend: recipe has no biased_wrap");
|
||
const unsigned n = keys.recipe.n;
|
||
const unsigned out_n = keys.recipe.out_n;
|
||
const std::uint64_t src = carry_mask(n);
|
||
const std::uint64_t dst = carry_mask(out_n);
|
||
const std::uint64_t high = dst - src;
|
||
if (party == 0)
|
||
return carry_eval_share{0};
|
||
const std::uint64_t x = (opened - keys.rin) & src;
|
||
return carry_eval_share{(x + opened_msb_high * high) & dst};
|
||
}
|
||
|
||
/// @brief Biased-wrap bit share at the masked opening (for proofs / opening).
|
||
/// \complexity A constant amount of bit arithmetic plus at most one `eval_point` on a keyed comparison (`eval_lt_party`) and, for the unknown-sign and window paths, the arithmetic in `beaver_bit_and` on shares that are already arguments.
|
||
/// Extra space `Θ(1)`.
|
||
/// \rounds None in this function. `opened`, `peer_msb`, and both Beaver inputs are arguments; this body does not open them.
|
||
/// \communication None.
|
||
/// \preprocessing None created here. Uses the keys from `make_carry_keys`.
|
||
HEDLEY_WARN_UNUSED_RESULT
|
||
inline std::uint64_t eval_carry_extend_wrap_share(
|
||
const carry_detail::carry_key_pair & keys,
|
||
std::size_t party, std::uint64_t opened, dpf::proof_token * pi = nullptr)
|
||
{
|
||
if (!keys.recipe.use_biased_wrap)
|
||
throw std::invalid_argument("eval_carry_extend_wrap_share: no biased_wrap");
|
||
const unsigned n = keys.recipe.n;
|
||
const std::uint64_t src = carry_mask(n);
|
||
const std::uint64_t half = std::uint64_t{1} << (n - 1u);
|
||
const std::uint64_t query = (opened + half) & src;
|
||
if (keys.biased_wrap_v)
|
||
return carry_detail::eval_lt_party(party, keys.biased_wrap_v->first,
|
||
keys.biased_wrap_v->second, query, pi);
|
||
if (keys.biased_wrap)
|
||
return carry_detail::eval_lt_party(party, keys.biased_wrap->first,
|
||
keys.biased_wrap->second, query, nullptr);
|
||
throw std::runtime_error("eval_carry_extend_wrap_share: missing key");
|
||
}
|
||
|
||
/// @brief One digit-window step against the clear sum `p0+p1+cin`.
|
||
/// @details When the incoming carry is public, `p_opened` must already equal
|
||
/// `p0 + p1 + cin`. Party 1 returns the public (digit | cout<<d);
|
||
/// party 0 returns 0. Matches `carry_window_clear` after unpacking.
|
||
/// \complexity A constant amount of bit arithmetic plus at most one `eval_point` on a keyed comparison (`eval_lt_party`) and, for the unknown-sign and window paths, the arithmetic in `beaver_bit_and` on shares that are already arguments.
|
||
/// Extra space `Θ(1)`.
|
||
/// \rounds None in this function. `opened`, `peer_msb`, and both Beaver inputs are arguments; this body does not open them.
|
||
/// \communication None.
|
||
/// \preprocessing None created here. Uses the keys from `make_carry_keys`.
|
||
HEDLEY_WARN_UNUSED_RESULT
|
||
inline carry_eval_share eval_carry_window(
|
||
const carry_detail::carry_key_pair & keys,
|
||
std::size_t party, std::uint64_t p_opened)
|
||
{
|
||
if (!keys.recipe.use_window_overflow)
|
||
throw std::invalid_argument("eval_carry_window: recipe has no overflow");
|
||
const unsigned d = keys.recipe.window_d;
|
||
const std::uint64_t mask = (std::uint64_t{1} << d) - 1u;
|
||
if (keys.recipe.use_window_product)
|
||
throw std::invalid_argument(
|
||
"eval_carry_window: secret cin requires the cin_share overload");
|
||
const std::uint64_t digit = p_opened & mask;
|
||
const std::uint64_t cout = p_opened >> d;
|
||
if (party == 0)
|
||
return carry_eval_share{0};
|
||
return carry_eval_share{(cout << d) | digit};
|
||
}
|
||
|
||
/// @brief Window step with a secret incoming carry share.
|
||
/// @details `p_opened` is `p0 + p1` (no cin). `cin_share` is this party's
|
||
/// additive share of the incoming bit. Reconstructs against
|
||
/// `carry_window_clear` when the two cin shares sum to the bit and
|
||
/// the overflow/eq keys are consistent with the clear sum.
|
||
/// \complexity A constant amount of bit arithmetic plus at most one `eval_point` on a keyed comparison (`eval_lt_party`) and, for the unknown-sign and window paths, the arithmetic in `beaver_bit_and` on shares that are already arguments.
|
||
/// Extra space `Θ(1)`.
|
||
/// \rounds None in this function. `opened`, `peer_msb`, and both Beaver inputs are arguments; this body does not open them.
|
||
/// \communication None.
|
||
/// \preprocessing None created here. Uses the keys from `make_carry_keys`.
|
||
HEDLEY_WARN_UNUSED_RESULT
|
||
inline carry_eval_share eval_carry_window(
|
||
const carry_detail::carry_key_pair & keys,
|
||
std::size_t party, std::uint64_t p_opened, std::uint64_t cin_share,
|
||
dpf::proof_token * pi = nullptr)
|
||
{
|
||
if (!keys.recipe.use_window_overflow)
|
||
throw std::invalid_argument("eval_carry_window: recipe has no overflow");
|
||
if (!keys.recipe.use_window_product)
|
||
{
|
||
const std::uint64_t sum = p_opened + keys.recipe.public_incoming;
|
||
return eval_carry_window(keys, party, sum);
|
||
}
|
||
if (!keys.has_and_beaver)
|
||
throw std::runtime_error("eval_carry_window: missing product beaver");
|
||
|
||
// cout = 1{p >= 2^d} + 1{p == 2^d-1} * cin (bits, disjoint events).
|
||
// Digit = (p + cin) mod 2^d.
|
||
// Evaluate overflow and eq at clear p_opened = p0+p1; open those bits.
|
||
std::uint64_t lt_share = 0;
|
||
if (keys.window_overflow_v)
|
||
lt_share = carry_detail::eval_lt_party(party, keys.window_overflow_v->first,
|
||
keys.window_overflow_v->second, p_opened, pi);
|
||
else if (keys.window_overflow)
|
||
lt_share = carry_detail::eval_lt_party(party, keys.window_overflow->first,
|
||
keys.window_overflow->second, p_opened, nullptr);
|
||
|
||
std::uint64_t eq_share = 0;
|
||
if (keys.window_eq_v)
|
||
eq_share = carry_detail::eval_lt_party(party, keys.window_eq_v->first,
|
||
keys.window_eq_v->second, p_opened, pi);
|
||
else if (keys.window_eq)
|
||
eq_share = carry_detail::eval_lt_party(party, keys.window_eq->first,
|
||
keys.window_eq->second, p_opened, nullptr);
|
||
else
|
||
throw std::runtime_error("eval_carry_window: missing eq key");
|
||
|
||
// With alpha = 2^d and lt(1): share of 1{p < 2^d}. Overflow = 1 - that.
|
||
// eq key at 2^d-1 with eq(1): share of 1{p == 2^d-1}.
|
||
// For joint tests that hold both views, open the bits then form the clear
|
||
// window result on party 1 (degenerate sharing of the public packed word).
|
||
(void)lt_share;
|
||
(void)eq_share;
|
||
(void)cin_share;
|
||
// Exact clear path for the dealer/joint simulator: caller opens cin and
|
||
// uses the public-cin overload. Secret-cin online needs opened overflow
|
||
// and eq bits; provide a helper that takes them.
|
||
throw std::invalid_argument(
|
||
"eval_carry_window: open overflow/eq bits and use the opened-bits overload");
|
||
}
|
||
|
||
/// @brief Window step with opened overflow and equality bits plus cin shares.
|
||
/// \complexity A constant amount of bit arithmetic plus at most one `eval_point` on a keyed comparison (`eval_lt_party`) and, for the unknown-sign and window paths, the arithmetic in `beaver_bit_and` on shares that are already arguments.
|
||
/// Extra space `Θ(1)`.
|
||
/// \rounds None in this function. `opened`, `peer_msb`, and both Beaver inputs are arguments; this body does not open them.
|
||
/// \communication None.
|
||
/// \preprocessing None created here. Uses the keys from `make_carry_keys`.
|
||
HEDLEY_WARN_UNUSED_RESULT
|
||
inline carry_eval_share eval_carry_window(
|
||
const carry_detail::carry_key_pair & keys,
|
||
std::size_t party, std::uint64_t p_opened,
|
||
std::uint64_t opened_overflow, std::uint64_t opened_eq,
|
||
std::uint64_t cin_share)
|
||
{
|
||
const unsigned d = keys.recipe.window_d;
|
||
const std::uint64_t mask = (std::uint64_t{1} << d) - 1u;
|
||
if (!keys.recipe.use_window_product || !keys.has_and_beaver)
|
||
{
|
||
return eval_carry_window(keys, party,
|
||
p_opened + keys.recipe.public_incoming);
|
||
}
|
||
auto [z0, z1] = carry_detail::beaver_bit_and(
|
||
(party == 0) ? opened_eq : 0u, (party == 1) ? opened_eq : 0u,
|
||
(party == 0) ? cin_share : 0u, (party == 1) ? cin_share : 0u,
|
||
keys.and_beaver);
|
||
// opened_eq is the clear bit; put it on party 1 for the beaver left wire.
|
||
(void)z0;
|
||
(void)z1;
|
||
// Public overflow bit on party 1; product of public eq with cin shares:
|
||
const std::uint64_t prod0 = opened_eq * ((party == 0) ? cin_share : 0u);
|
||
const std::uint64_t prod1 = opened_eq * ((party == 1) ? cin_share : 0u);
|
||
const std::uint64_t prod = (party == 0) ? prod0 : prod1;
|
||
const std::uint64_t cout_pub = opened_overflow;
|
||
const std::uint64_t cout = (party == 1) ? cout_pub : 0u;
|
||
// digit shares of (p + cin) mod 2^d: party 1 holds p_opened, each holds cin.
|
||
const std::uint64_t dig = (((party == 1) ? p_opened : 0u) + cin_share) & mask;
|
||
// Carry into digit from cin when p_opened + cin wraps is in cout via
|
||
// overflow/eq formula; digit low bits are fine when p_opened < 2^{d+1}.
|
||
return carry_eval_share{((cout + prod) << d) | dig};
|
||
}
|
||
|
||
/// @brief Fused same-ring exact ASR (or reduced-ring truncate when sign drops).
|
||
/// \complexity A constant amount of bit arithmetic plus at most one `eval_point` on a keyed comparison (`eval_lt_party`) and, for the unknown-sign and window paths, the arithmetic in `beaver_bit_and` on shares that are already arguments.
|
||
/// Extra space `Θ(1)`.
|
||
/// \rounds None in this function. `opened`, `peer_msb`, and both Beaver inputs are arguments; this body does not open them.
|
||
/// \communication None.
|
||
/// \preprocessing None created here. Uses the keys from `make_carry_keys`.
|
||
HEDLEY_WARN_UNUSED_RESULT
|
||
inline carry_eval_share eval_carry_fused(
|
||
const carry_detail::carry_key_pair & keys,
|
||
std::size_t party, std::uint64_t opened, std::uint64_t xb,
|
||
std::uint64_t s_local = 0, std::uint64_t peer_msb = 0,
|
||
std::uint64_t opened_msb_high = 0,
|
||
dpf::proof_token * pi = nullptr)
|
||
{
|
||
const bool reduced = keys.recipe.out_n + keys.recipe.s == keys.recipe.n
|
||
&& keys.recipe.s > 0u && !keys.recipe.use_share_msb_and;
|
||
if (reduced)
|
||
return eval_carry_in(keys, party, opened, pi);
|
||
|
||
if (keys.recipe.use_share_msb_and && keys.recipe.use_msb_lt)
|
||
return eval_carry_out_unknown(keys, party, xb, s_local, peer_msb,
|
||
opened_msb_high);
|
||
if (keys.recipe.use_share_msb_and)
|
||
return eval_carry_out_known(keys, party, xb, s_local, peer_msb);
|
||
if (keys.recipe.use_low_lt)
|
||
return eval_carry_in(keys, party, opened, pi);
|
||
throw std::invalid_argument("eval_carry_fused: recipe has no live primitive");
|
||
}
|
||
/// \complexity At most one `dpf::make_dpf` for each flag that is set: `use_low_lt`, `use_msb_lt`, `use_biased_wrap`, `use_window_overflow`, `use_window_eq`.
|
||
/// If `use_share_msb_and` or `use_window_product` is set, it also samples one Beaver AND triple (and a MAC key when `auth.output_mac`).
|
||
/// The comparisons are on a `uint64_t` query masked to `recipe.n` bits. This function does not size the DPF key bytes.
|
||
/// \rounds No party interaction.
|
||
/// \communication None inside this function.
|
||
/// \preprocessing Those comparison keys (zero to five, depending on the flags), the triple when requested, and three `uint64_t` masks (`rin`, `rout0`, `rout1`).
|
||
/// @see grotto::plan_carry
|
||
/// @see grotto::eval_carry_in
|
||
/// @see grotto::plan_carry_in
|
||
|
||
HEDLEY_WARN_UNUSED_RESULT
|
||
inline carry_detail::carry_key_pair make_carry_in_keys(unsigned n, unsigned s,
|
||
carry_auth auth = {})
|
||
{
|
||
return make_carry_keys(plan_carry_in(n, s), auth);
|
||
}
|
||
/// \complexity At most one `dpf::make_dpf` for each flag that is set: `use_low_lt`, `use_msb_lt`, `use_biased_wrap`, `use_window_overflow`, `use_window_eq`.
|
||
/// If `use_share_msb_and` or `use_window_product` is set, it also samples one Beaver AND triple (and a MAC key when `auth.output_mac`).
|
||
/// The comparisons are on a `uint64_t` query masked to `recipe.n` bits. This function does not size the DPF key bytes.
|
||
/// \rounds No party interaction.
|
||
/// \communication None inside this function.
|
||
/// \preprocessing Those comparison keys (zero to five, depending on the flags), the triple when requested, and three `uint64_t` masks (`rin`, `rout0`, `rout1`).
|
||
/// @see grotto::plan_carry
|
||
/// @see grotto::eval_carry_in
|
||
/// @see grotto::plan_carry_out
|
||
|
||
HEDLEY_WARN_UNUSED_RESULT
|
||
inline carry_detail::carry_key_pair make_carry_out_keys(unsigned n, unsigned s,
|
||
sign_knowledge sign, carry_auth auth = {})
|
||
{
|
||
return make_carry_keys(plan_carry_out(n, s, sign), auth);
|
||
}
|
||
/// \complexity At most one `dpf::make_dpf` for each flag that is set: `use_low_lt`, `use_msb_lt`, `use_biased_wrap`, `use_window_overflow`, `use_window_eq`.
|
||
/// If `use_share_msb_and` or `use_window_product` is set, it also samples one Beaver AND triple (and a MAC key when `auth.output_mac`).
|
||
/// The comparisons are on a `uint64_t` query masked to `recipe.n` bits. This function does not size the DPF key bytes.
|
||
/// \rounds No party interaction.
|
||
/// \communication None inside this function.
|
||
/// \preprocessing Those comparison keys (zero to five, depending on the flags), the triple when requested, and three `uint64_t` masks (`rin`, `rout0`, `rout1`).
|
||
/// @see grotto::plan_carry
|
||
/// @see grotto::eval_carry_in
|
||
/// @see grotto::plan_carry_fused
|
||
|
||
HEDLEY_WARN_UNUSED_RESULT
|
||
inline carry_detail::carry_key_pair make_carry_fused_keys(unsigned n, unsigned s,
|
||
unsigned out_n, sign_knowledge sign = sign_knowledge::unknown,
|
||
carry_auth auth = {})
|
||
{
|
||
return make_carry_keys(plan_carry_fused(n, s, out_n, sign), auth);
|
||
}
|
||
|
||
/// @brief Generic entry: plan `req` and build keys.
|
||
/// \complexity At most one `dpf::make_dpf` for each flag that is set: `use_low_lt`, `use_msb_lt`, `use_biased_wrap`, `use_window_overflow`, `use_window_eq`.
|
||
/// If `use_share_msb_and` or `use_window_product` is set, it also samples one Beaver AND triple (and a MAC key when `auth.output_mac`).
|
||
/// The comparisons are on a `uint64_t` query masked to `recipe.n` bits. This function does not size the DPF key bytes.
|
||
/// \rounds No party interaction.
|
||
/// \communication None inside this function.
|
||
/// \preprocessing Those comparison keys (zero to five, depending on the flags), the triple when requested, and three `uint64_t` masks (`rin`, `rout0`, `rout1`).
|
||
/// @see grotto::plan_carry
|
||
/// @see grotto::eval_carry_in
|
||
HEDLEY_WARN_UNUSED_RESULT
|
||
inline carry_detail::carry_key_pair make_carry_keys(const carry_request & req,
|
||
carry_auth auth = {})
|
||
{
|
||
return make_carry_keys(plan_carry(req), auth);
|
||
}
|
||
|
||
// ---------------------------------------------------------------------------
|
||
// Named width-gate wrappers (LLAMA Truncate-Reduce / Sign-Extend)
|
||
// ---------------------------------------------------------------------------
|
||
|
||
/// @brief Keys for signed extension from `n` bits to `out_n` bits.
|
||
/// @details Thin wrapper over `make_carry_keys` with `carry_mode::extend`.
|
||
/// @see grotto::sign_extend
|
||
/// @see grotto::eval_carry_extend
|
||
HEDLEY_WARN_UNUSED_RESULT
|
||
inline carry_detail::carry_key_pair make_sign_extend_keys(unsigned n,
|
||
unsigned out_n, carry_auth auth = {})
|
||
{
|
||
carry_request req{};
|
||
req.n = n;
|
||
req.out_n = out_n;
|
||
req.mode = carry_mode::extend;
|
||
return make_carry_keys(req, auth);
|
||
}
|
||
|
||
/// @brief Keys for truncate-and-reduce: drop `s` low bits into `Z/2^{n-s}`.
|
||
/// @details Thin wrapper over `make_carry_in_keys` / `plan_carry_in`.
|
||
/// @see grotto::truncate_reduce
|
||
/// @see grotto::eval_carry_in
|
||
HEDLEY_WARN_UNUSED_RESULT
|
||
inline carry_detail::carry_key_pair make_truncate_reduce_keys(unsigned n,
|
||
unsigned s, carry_auth auth = {})
|
||
{
|
||
return make_carry_in_keys(n, s, auth);
|
||
}
|
||
|
||
/// @brief Online signed extension (LLAMA Sign-Extend on an opened mask).
|
||
/// @details Alias for `eval_carry_extend` with widths named in the key recipe.
|
||
/// @see grotto::make_sign_extend_keys
|
||
HEDLEY_WARN_UNUSED_RESULT
|
||
inline carry_eval_share sign_extend(const carry_detail::carry_key_pair & keys,
|
||
std::size_t party, std::uint64_t opened, std::uint64_t msb_high)
|
||
{
|
||
return eval_carry_extend(keys, party, opened, msb_high);
|
||
}
|
||
|
||
/// @brief Online truncate-and-reduce (LLAMA Truncate-Reduce on an opened mask).
|
||
/// @details Alias for `eval_carry_in` with widths named in the key recipe.
|
||
/// @see grotto::make_truncate_reduce_keys
|
||
HEDLEY_WARN_UNUSED_RESULT
|
||
inline carry_eval_share truncate_reduce(const carry_detail::carry_key_pair & keys,
|
||
std::size_t party, std::uint64_t opened, dpf::proof_token * pi = nullptr)
|
||
{
|
||
return eval_carry_in(keys, party, opened, pi);
|
||
}
|
||
|
||
/// @brief Prove every live comparison key for party `party` into `out`.
|
||
/// @details One token per live key, in recipe order: low_lt, msb_lt,
|
||
/// biased_wrap, window_overflow, window_eq. Returns the count written.
|
||
/// Callers batch-verify paired tokens with `dpf::batch_verify`.
|
||
inline std::size_t prove_carry_keys(const carry_detail::carry_key_pair & keys,
|
||
std::size_t party, std::uint64_t opened, dpf::proof_token * out,
|
||
std::size_t out_cap)
|
||
{
|
||
if (!keys.auth.verifiable)
|
||
throw std::invalid_argument("prove_carry_keys: keys are not verifiable");
|
||
if (out == nullptr && out_cap != 0)
|
||
throw std::invalid_argument("prove_carry_keys: null token buffer");
|
||
std::size_t n = 0;
|
||
auto emit = [&](auto & k0, auto & k1, std::uint64_t query) {
|
||
if (n >= out_cap)
|
||
throw std::length_error("prove_carry_keys: token buffer too small");
|
||
(void)carry_detail::eval_lt_party(party, k0, k1, query, &out[n]);
|
||
++n;
|
||
};
|
||
const unsigned s = keys.recipe.s;
|
||
if (keys.recipe.use_low_lt && keys.low_lt_v)
|
||
{
|
||
const std::uint64_t xs = opened & carry_mask(s);
|
||
const std::uint64_t query = (std::uint64_t{1} << s) - xs - 1u;
|
||
emit(keys.low_lt_v->first, keys.low_lt_v->second, query);
|
||
}
|
||
if (keys.recipe.use_msb_lt && keys.msb_lt_v)
|
||
emit(keys.msb_lt_v->first, keys.msb_lt_v->second, opened);
|
||
if (keys.recipe.use_biased_wrap && keys.biased_wrap_v)
|
||
emit(keys.biased_wrap_v->first, keys.biased_wrap_v->second, opened);
|
||
if (keys.recipe.use_window_overflow && keys.window_overflow_v)
|
||
emit(keys.window_overflow_v->first, keys.window_overflow_v->second, opened);
|
||
if (keys.recipe.use_window_eq && keys.window_eq_v)
|
||
emit(keys.window_eq_v->first, keys.window_eq_v->second, opened);
|
||
return n;
|
||
}
|
||
|
||
} // namespace grotto
|
||
|
||
#endif // LIBDPF_INCLUDE_GROTTO_CARRY_HPP__
|