ryan/libdpf
1
0
Fork 0
Code Issues Pull requests Projects Releases Packages Wiki Activity Actions
libdpf/party/flows_extreme.cpp
Ryan Henry 0d22946a0e Checkpoint the party/runtime stack before share-program and malicious-mode work. 
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>
2026-09-28 05:59:19 -06:00

1080 lines
37 KiB
C++
Raw Permalink Blame History

/// @file party/flows_extreme.cpp
/// @brief Extreme grotto / DCF / geneval / DS / complex-beaver party flows.
/// @details Amalgamated into run.cpp (do not compile as a second TU).
#include "cases.hpp"
#include "dist_ds.hpp"
#include "flow_util.hpp"
#include "key_io.hpp"
#include "registry.hpp"
#include <algorithm>
#include <array>
#include <cstdint>
#include <cstring>
#include <limits>
#include <memory>
#include <string>
#include <tuple>
#include <type_traits>
#include <vector>
#include "simde/simde/x86/avx2.h"
#include "dpf/beaver.hpp"
#include "dpf/dcf.hpp"
#include "dpf/dpf_key.hpp"
#include "dpf/eval_full.hpp"
#include "dpf/eval_interval.hpp"
#include "dpf/eval_point.hpp"
#include "dpf/eval_sequence.hpp"
#include "dpf/eval_unified.hpp"
#include "dpf/geneval.hpp"
#include "dpf/incremental.hpp"
#include "dpf/prg_aes.hpp"
#include "grotto/constant_lut.hpp"
#include "grotto/offset_horner.hpp"
#include "grotto/prefix_parity.hpp"
namespace dpf
{
namespace party
{
namespace extreme
{
using util::Counter;
using util::evaluate_online;
using util::install_and_bind_u64;
using util::open_additive;
using util::open_subtractive;
using util::require;
using util::role;
using util::share_bits;
using util::trio;
using util::u64;
// ---- helpers ----
bool open_xor_bit(trio & net, role self, bool mine)
{
role peer = self == role::p0 ? role::p1 : role::p0;
bool theirs = net.exchange_with(peer, mine);
return mine ^ theirs;
}
struct Pad
{
std::uint64_t n = 1;
simde__m128i block()
{
auto v = simde_mm_set_epi64x(static_cast<long long>(n),
static_cast<long long>(n * 9 + 3));
n += 2;
return v;
}
std::uint8_t bit() { return static_cast<std::uint8_t>(n++ & 1u); }
};
HEDLEY_PRAGMA(GCC diagnostic push)
HEDLEY_PRAGMA(GCC diagnostic ignored "-Wignored-attributes")
ds_randomness<simde__m128i (*)(), Pad> make_ds_rng()
{
return {uniform_sample<simde__m128i>, Pad{}};
}
HEDLEY_PRAGMA(GCC diagnostic pop)
template <typename T, std::size_t N>
int piece_containing(T alpha, const std::array<T, N> & ends)
{
for (std::size_t i = 0; i + 1 < N; ++i)
{
if (alpha >= ends[i] && alpha < ends[i + 1])
return static_cast<int>(i);
}
return static_cast<int>(N - 1);
}
u64 expect_cmp(int kind, std::uint8_t x, std::uint8_t alpha, u64 beta)
{
// kind: 0=lt 1=leq 2=gt 3=geq
bool hit = false;
if (kind == 0)
hit = x < alpha;
else if (kind == 1)
hit = x <= alpha;
else if (kind == 2)
hit = x > alpha;
else
hit = x >= alpha;
return hit ? beta : 0u;
}
// ============================================================================
// Extreme beaver: large vectors, nested products, mixed batches
// ============================================================================
template <std::size_t N>
int beaver_dot_extreme_n(role self, trio & net)
{
beavers::session<u64> s;
std::vector<beavers::session<u64>::wire> xs, ys;
std::vector<u64> secrets;
u64 expect = 0;
for (std::size_t i = 0; i < N; ++i)
{
xs.push_back(s.input());
ys.push_back(s.input());
u64 a = static_cast<u64>(i * 17 + 3);
u64 b = static_cast<u64>((N - i) * 11 + 5);
secrets.push_back(a);
secrets.push_back(b);
expect += a * b;
}
auto z = s.dot(xs, ys);
if (self == role::p2)
{
require(s.round_of(z) == 1, "dot extreme round");
Counter rng;
s.sample(rng);
net::deal_session(net, s);
return 0;
}
std::vector<beavers::session<u64>::wire> inputs;
inputs.reserve(2 * N);
for (std::size_t i = 0; i < N; ++i)
{
inputs.push_back(xs[i]);
inputs.push_back(ys[i]);
}
install_and_bind_u64(s, net, self, inputs, secrets);
evaluate_online(s, net, self);
auto o = open_additive(net, self, s.value_party(z));
if (self == role::p0)
require(o == expect, "dot extreme");
return 0;
}
int beaver_nested_dots(role self, trio & net)
{
// (x·y) * (u·v) — two-round nested product of dots
constexpr std::size_t N = 8;
beavers::session<u64> s;
std::vector<beavers::session<u64>::wire> xs, ys, us, vs;
std::vector<u64> xsec, ysec, usec, vsec;
u64 xy = 0, uv = 0;
for (std::size_t i = 0; i < N; ++i)
{
xs.push_back(s.input());
ys.push_back(s.input());
us.push_back(s.input());
vs.push_back(s.input());
u64 a = i + 1, b = i + 2, c = i + 3, d = i + 4;
xsec.push_back(a);
ysec.push_back(b);
usec.push_back(c);
vsec.push_back(d);
xy += a * b;
uv += c * d;
}
auto d0 = s.dot(xs, ys);
auto d1 = s.dot(us, vs);
auto z = s(d0 * d1);
if (self == role::p2)
{
require(s.round_of(d0) == 1 && s.round_of(d1) == 1, "inner dots");
require(s.round_of(z) == 2, "nested round");
Counter rng;
s.sample(rng);
net::deal_session(net, s);
return 0;
}
std::vector<beavers::session<u64>::wire> inputs = xs;
inputs.insert(inputs.end(), ys.begin(), ys.end());
inputs.insert(inputs.end(), us.begin(), us.end());
inputs.insert(inputs.end(), vs.begin(), vs.end());
std::vector<u64> secrets = xsec;
secrets.insert(secrets.end(), ysec.begin(), ysec.end());
secrets.insert(secrets.end(), usec.begin(), usec.end());
secrets.insert(secrets.end(), vsec.begin(), vsec.end());
install_and_bind_u64(s, net, self, inputs, secrets);
evaluate_online(s, net, self);
auto o = open_additive(net, self, s.value_party(z));
if (self == role::p0)
require(o == xy * uv, "nested dots");
return 0;
}
int beaver_tuple_cascade(role self, trio & net)
{
// Cascade of triples and squares on a 6-tuple
beavers::session<u64> s;
auto a = s.input();
auto b = s.input();
auto c = s.input();
auto d = s.input();
auto e = s.input();
auto f = s.input();
auto p = s.product(a, b, c);
auto q = s(d * d);
auto r = s(e * f);
auto z = s(p * q + r * a + b * c * d);
const u64 A = 2, B = 3, C = 5, D = 7, E = 11, F = 13;
const u64 expect = (A * B * C) * (D * D) + (E * F) * A + B * C * D;
if (self == role::p2)
{
Counter rng;
s.sample(rng);
net::deal_session(net, s);
return 0;
}
install_and_bind_u64(s, net, self, {a, b, c, d, e, f}, {A, B, C, D, E, F});
evaluate_online(s, net, self);
auto o = open_additive(net, self, s.value_party(z));
if (self == role::p0)
require(o == expect, "cascade");
return 0;
}
int beaver_mixed_batch_poly(role self, trio & net)
{
// Many independent products + one dense Horner + one mux in one session
beavers::session<u64> s;
constexpr std::size_t K = 16;
std::vector<beavers::session<u64>::wire> xs, ys, outs;
std::vector<u64> secrets;
u64 expect_sum = 0;
for (std::size_t i = 0; i < K; ++i)
{
xs.push_back(s.input());
ys.push_back(s.input());
u64 a = static_cast<u64>(i + 2);
u64 b = static_cast<u64>(3 * i + 1);
secrets.push_back(a);
secrets.push_back(b);
outs.push_back(s(xs.back() * ys.back()));
expect_sum += a * b;
}
auto t = s.input();
secrets.push_back(4u);
auto h = s.horner(t, {u64{1}, u64{2}, u64{3}, u64{4}, u64{5}});
auto bit = s.input();
auto lo = s.input();
auto hi = s.input();
secrets.push_back(1u);
secrets.push_back(9u);
secrets.push_back(42u);
auto mx = s.mux(bit, hi, lo); // bit=1 → hi
auto total = outs[0];
for (std::size_t i = 1; i < K; ++i)
total = s(total + outs[i]);
auto z = s(total + h + mx);
const u64 x = 4;
const u64 horner = 1 + 2 * x + 3 * x * x + 4 * x * x * x + 5 * x * x * x * x;
const u64 expect = expect_sum + horner + 42u;
if (self == role::p2)
{
Counter rng;
s.sample(rng);
net::deal_session(net, s);
return 0;
}
std::vector<beavers::session<u64>::wire> inputs;
for (std::size_t i = 0; i < K; ++i)
{
inputs.push_back(xs[i]);
inputs.push_back(ys[i]);
}
inputs.push_back(t);
inputs.push_back(bit);
inputs.push_back(lo);
inputs.push_back(hi);
install_and_bind_u64(s, net, self, inputs, secrets);
evaluate_online(s, net, self);
auto o = open_additive(net, self, s.value_party(z));
if (self == role::p0)
require(o == expect, "mixed batch");
return 0;
}
int beaver_factored_multilinear(role self, trio & net)
{
// Multilinear over 4 bits expanded: product of (1 + a_i * x_i)
beavers::session<u64> s;
auto x0 = s.input();
auto x1 = s.input();
auto x2 = s.input();
auto x3 = s.input();
auto z = s((1 + 2 * x0) * (1 + 3 * x1) * (1 + 5 * x2) * (1 + 7 * x3));
const u64 X0 = 1, X1 = 1, X2 = 0, X3 = 1;
const u64 expect = (1 + 2 * X0) * (1 + 3 * X1) * (1 + 5 * X2) * (1 + 7 * X3);
if (self == role::p2)
{
Counter rng;
s.sample(rng);
net::deal_session(net, s);
return 0;
}
install_and_bind_u64(s, net, self, {x0, x1, x2, x3}, {X0, X1, X2, X3});
evaluate_online(s, net, self);
auto o = open_additive(net, self, s.value_party(z));
if (self == role::p0)
require(o == expect, "multilinear");
return 0;
}
// ============================================================================
// DCF extreme: dense queries, blocked, interval / full / sequence / IP
// ============================================================================
template <int Kind>
int dcf_dense_grid(role self, trio & net)
{
using Input = std::uint8_t;
const Input alpha = 0x73;
const Input x0 = 0x19;
const Input x1 = static_cast<Input>(alpha ^ x0);
const u64 beta = 13;
std::vector<Input> pts;
for (int x = 0; x < 256; x += 4)
pts.push_back(static_cast<Input>(x));
for (int d = -3; d <= 3; ++d)
{
int v = static_cast<int>(alpha) + d;
if (v >= 0 && v < 256)
pts.push_back(static_cast<Input>(v));
}
pts.push_back(0);
pts.push_back(255);
std::sort(pts.begin(), pts.end());
pts.erase(std::unique(pts.begin(), pts.end()), pts.end());
auto on = [&](const auto & key) {
const u64 mask = key.cmp().mask;
std::vector<u64> mine;
mine.reserve(pts.size());
for (Input x : pts)
mine.push_back(share_bits(eval_point(cmp, key, x)) & mask);
auto opened = open_additive(net, self, mine);
if (self == role::p0)
{
for (std::size_t i = 0; i < pts.size(); ++i)
require((opened[i] & mask)
== expect_cmp(Kind, pts[i], alpha, beta),
"dense grid");
}
};
const auto expect = encoded_xor_point(x0, x1);
if constexpr (Kind == 0)
require_opened(dist_with_cmp_key<prg::aes128, prg::aes128, true>(net, self, x0, x1, lt(beta), on, on),
self, expect);
else if constexpr (Kind == 1)
require_opened(dist_with_cmp_key<prg::aes128, prg::aes128, true>(net, self, x0, x1, leq(beta), on, on),
self, expect);
else if constexpr (Kind == 2)
require_opened(dist_with_cmp_key<prg::aes128, prg::aes128, true>(net, self, x0, x1, gt(beta), on, on),
self, expect);
else
require_opened(dist_with_cmp_key<prg::aes128, prg::aes128, true>(net, self, x0, x1, geq(beta), on, on),
self, expect);
return 0;
}
template <int Kind>
int dcf_full_domain(role self, trio & net)
{
using Input = std::uint8_t;
const Input alpha = 0x40;
const Input x0 = 0x23;
const Input x1 = static_cast<Input>(alpha ^ x0);
const u64 beta = 9;
auto on = [&](const auto & key) {
const u64 mask = key.cmp().mask;
auto full = eval_full(cmp, key);
require(full.size() == 256u, "full size");
std::vector<u64> mine(256);
for (std::size_t i = 0; i < 256; ++i)
mine[i] = share_bits(full[i]) & mask;
auto opened = open_additive(net, self, mine);
if (self == role::p0)
{
for (int x = 0; x < 256; ++x)
require((opened[static_cast<std::size_t>(x)] & mask)
== expect_cmp(
Kind, static_cast<Input>(x), alpha, beta),
"full domain");
}
};
const auto expect = encoded_xor_point(x0, x1);
if constexpr (Kind == 0)
require_opened(dist_with_cmp_key<prg::aes128, prg::aes128, true>(net, self, x0, x1, lt(beta), on, on),
self, expect);
else if constexpr (Kind == 1)
require_opened(dist_with_cmp_key<prg::aes128, prg::aes128, true>(net, self, x0, x1, leq(beta), on, on),
self, expect);
else if constexpr (Kind == 2)
require_opened(dist_with_cmp_key<prg::aes128, prg::aes128, true>(net, self, x0, x1, gt(beta), on, on),
self, expect);
else
require_opened(dist_with_cmp_key<prg::aes128, prg::aes128, true>(net, self, x0, x1, geq(beta), on, on),
self, expect);
return 0;
}
int dcf_blocked_interval_ip(role self, trio & net)
{
using Input = std::uint8_t;
const Input alpha = 100;
const Input x0 = 0x35;
const Input x1 = static_cast<Input>(alpha ^ x0);
const u64 beta = 6;
const u64 if_false = 1;
auto on = [&](const auto & key) {
const u64 mask = key.cmp().mask;
const Input from = 90, to = 110;
auto buf = make_output_buffer(cmp, key, from, to);
eval_interval(cmp, key, from, to, buf);
std::vector<u64> mine;
for (Input x = from; x <= to; ++x)
mine.push_back(share_bits(buf[x - from]) & mask);
auto opened = open_additive(net, self, mine);
if (self == role::p0)
{
for (std::size_t i = 0; i < mine.size(); ++i)
{
Input x = static_cast<Input>(from + i);
u64 want = x < alpha ? beta : if_false;
require((opened[i] & mask) == want, "blocked interval");
}
}
std::vector<u64> w(static_cast<std::size_t>(to - from + 1), 1u);
u64 ip = eval_inner_product(cmp, key, from, to, w) & mask;
auto oip = open_additive(net, self, ip) & mask;
if (self == role::p0)
{
u64 want_ip = 0;
for (Input x = from; x <= to; ++x)
want_ip =
(want_ip + (x < alpha ? beta : if_false)) & mask;
require(oip == want_ip, "blocked ip");
}
std::array<Input, 5> pts{{0, 99, 100, 101, 255}};
auto seq = make_output_buffer(cmp, key, pts.size());
auto path = make_basic_path_memoizer(key);
eval_sequence(cmp, key, pts.begin(), pts.end(), seq, path);
std::vector<u64> smine;
for (std::size_t i = 0; i < pts.size(); ++i)
smine.push_back(share_bits(seq[i]) & mask);
auto sopen = open_additive(net, self, smine);
if (self == role::p0)
{
for (std::size_t i = 0; i < pts.size(); ++i)
require((sopen[i] & mask)
== (pts[i] < alpha ? beta : if_false),
"blocked seq");
}
};
require_opened(dist_with_cmp_key<prg::aes128, prg::aes128, true>(net, self, x0, x1,
block_width<4>(lt(beta, if_false)), on, on),
self, encoded_xor_point(x0, x1));
return 0;
}
// ============================================================================
// Grotto: signed prefix/segment, XOR prefix, LUT, offset Horner, geneval Horner
// ============================================================================
int grotto_signed_prefix_dense(role self, trio & net)
{
using Input = std::uint8_t;
const Input alpha = 0x3c;
const Input x0 = 0x17;
const Input x1 = static_cast<Input>(alpha ^ x0);
const u64 beta = 1;
std::array<Input, 16> ends{{0, 1, 2, 10, 20, 40, alpha - 1, alpha, alpha + 1,
100, 150, 200, 220, 240, 254, 255}};
auto on = [&](const auto & key) {
const u64 mask = key.cmp().mask;
auto pref = grotto::signed_prefix_parities(key, ends);
std::vector<u64> mine(ends.size());
for (std::size_t i = 0; i < ends.size(); ++i)
mine[i] = pref[i] & mask;
auto opened = open_additive(net, self, mine);
std::vector<u64> pts(ends.size());
for (std::size_t i = 0; i < ends.size(); ++i)
pts[i] = share_bits(eval_point(cmp, key, ends[i])) & mask;
auto opt_all = open_additive(net, self, pts);
if (self == role::p0)
{
for (std::size_t i = 0; i < ends.size(); ++i)
{
require((opened[i] & mask)
== (ends[i] > alpha ? beta : 0u),
"signed prefix");
require((opt_all[i] & mask) == (ends[i] > alpha ? beta : 0u),
"prefix vs point");
}
}
};
require_opened(dist_with_cmp_key<prg::aes128, prg::aes128, true>(net, self, x0, x1, gt(beta), on, on),
self, encoded_xor_point(x0, x1));
return 0;
}
int grotto_signed_segment_onehot(role self, trio & net)
{
using Input = std::uint8_t;
const Input alpha = 40;
const Input x0 = 0x31;
const Input x1 = static_cast<Input>(alpha ^ x0);
const std::array<Input, 8> ends{{0, 1, 10, 40, 80, 120, 200, 255}};
auto on = [&](const auto & key) {
const u64 mask = key.cmp().mask;
auto seg = grotto::signed_segment_parities(key, ends);
std::vector<u64> mine(ends.size());
for (std::size_t i = 0; i < ends.size(); ++i)
mine[i] = seg[i] & mask;
auto opened = open_additive(net, self, mine);
if (self == role::p0)
{
const int hot = piece_containing(alpha, ends);
u64 sum = 0;
for (std::size_t i = 0; i < ends.size(); ++i)
{
u64 bit = opened[i] & mask;
sum = (sum + bit) & mask;
require(bit
== (i == static_cast<std::size_t>(hot) ? 1u : 0u),
"segment onehot");
}
require(sum == 1u, "segment sum");
}
};
require_opened(dist_with_cmp_key<prg::aes128, prg::aes128, true>(net, self, x0, x1, gt(u64{1}), on, on),
self, encoded_xor_point(x0, x1));
return 0;
}
int grotto_xor_prefix_parity(role self, trio & net)
{
using Input = std::uint8_t;
const Input alpha = 0x55;
const Input x0 = 0x1c;
const Input x1 = static_cast<Input>(alpha ^ x0);
const std::array<Input, 8> ends{{0, 1, 16, 64, 128, 200, 254, 255}};
auto on = [&](const auto & key) {
auto [pref, new_first] = grotto::prefix_parities(key, ends);
(void)new_first;
for (std::size_t i = 0; i < ends.size(); ++i)
{
bool open = open_xor_bit(net, self, pref[i]);
if (self == role::p0)
(void)open;
}
auto segs = grotto::segment_parities(key, ends);
int hot = -1;
for (std::size_t i = 0; i < ends.size(); ++i)
{
bool bit_value = open_xor_bit(net, self, segs[i]);
if (self == role::p0 && bit_value)
{
require(hot < 0, "xor multi hot");
hot = static_cast<int>(i);
}
}
if (self == role::p0)
require(hot == piece_containing(alpha, ends), "xor segment hot");
};
require_tree_prefix(dist_with_point_key<prg::aes128, prg::aes128, true>(net, self, x0, x1, bit::one, on, on),
self, verifiable_tree_prefix<prg::aes128, prg::aes128, bit>(x0, x1));
return 0;
}
int grotto_signum_lut(role self, trio & net)
{
// Evaluate signum LUT at several signed alphas via signed_segment.
// Walks share one mux sink (count = alphas). Segment opens collapse into
// one packed vector exchange after every keygen.
const std::array<std::int8_t, 7> alphas{{-100, -1, 0, 1, 40, 127, -128}};
auto lut = grotto::make_exact_constant_lut<std::int8_t>(
grotto::exact_constant::signum, 0);
require(lut.bounds.size() == 3u, "signum bounds");
std::array<std::int8_t, 3> ends{};
for (std::size_t i = 0; i < 3; ++i)
ends[i] = lut.bounds[i];
constexpr std::size_t n = alphas.size();
std::vector<u64> seg_shares;
seg_shares.reserve(n * 3);
u64 mask = 0;
std::unique_ptr<dpf::net::RoundSink> sink;
if (self != role::p2)
{
using pair_type = dist::comparison_pair_t<prg::aes128, prg::aes128,
std::int8_t, decltype(gt(u64{1}))>;
constexpr std::size_t depth = pair_type::first_type::key_type::depth;
sink = net.batch(n, dpf::net::ds_walk_slot_bytes(depth, false));
}
for (std::size_t i = 0; i < n; ++i)
{
const std::int8_t alpha = alphas[i];
if (self == role::p2)
{
require_opened(dist_with_cmp_key<prg::aes128, prg::aes128, true>(
net, self, alpha, std::int8_t{0}, gt(u64{1}),
[](const auto &) {}, [](const auto &) {}),
self, encoded_xor_point(alpha, std::int8_t{0}));
continue;
}
auto on = [&](const auto & key) {
mask = key.cmp().mask;
auto seg = grotto::signed_segment_parities(key, ends);
for (std::size_t j = 0; j < 3; ++j)
seg_shares.push_back(seg[j] & mask);
};
if (self == role::p0)
{
auto result = dist::comparison_party<role::p0, prg::aes128,
prg::aes128, false, true>(
net, alpha, gt(u64{1}), sink.get(), i);
on(result.dpf_key);
require_opened(std::optional<std::int8_t>{result.opened_point},
self, encoded_xor_point(alpha, std::int8_t{0}));
}
else
{
auto result = dist::comparison_party<role::p1, prg::aes128,
prg::aes128, false, true>(
net, std::int8_t{0}, gt(u64{1}), sink.get(), i);
on(result.dpf_key);
require_opened(std::optional<std::int8_t>{result.opened_point},
self, encoded_xor_point(alpha, std::int8_t{0}));
}
}
if (self == role::p2)
return 0;
auto opened = open_additive(net, self, seg_shares);
if (self == role::p0)
{
for (std::size_t i = 0; i < n; ++i)
{
u64 acc = 0;
for (std::size_t j = 0; j < 3; ++j)
{
acc += (opened[i * 3 + j] & mask)
* static_cast<u64>(lut.values[j]);
}
const std::int8_t alpha = alphas[i];
const std::int64_t want =
alpha < 0 ? -1 : (alpha > 0 ? 1 : 0);
require(static_cast<std::int64_t>(acc) == want, "signum lut");
}
}
return 0;
}
template <std::size_t Degree, typename Input>
int dist_offset_horner(role self, trio & net, Input center0, Input center1,
Input center, Input eta, const std::vector<Input> & knots,
const std::vector<std::array<u64, Degree + 1>> & coeff,
const char * failure)
{
const auto pieces =
grotto::offset_horner_detail::prepare_pieces<Degree>(
knots, coeff, eta);
std::vector<Input> shifted(pieces.size());
std::vector<std::array<u64, Degree + 1>> ordered(pieces.size());
std::vector<std::int64_t> kappa(pieces.size());
for (std::size_t i = 0; i < pieces.size(); ++i)
{
shifted[i] = pieces[i].knot;
ordered[i] = pieces[i].coeff;
kappa[i] = pieces[i].kappa;
}
std::array<std::vector<u64>, Degree + 1> segments;
u64 payload = 1;
for (std::size_t m = 0; m <= Degree; ++m)
{
const u64 power = payload;
auto on = [&](const auto & key) {
const u64 wrap_share = self == role::p0 ? power : 0ULL;
segments[m] = grotto::offset_horner_detail::segments_of(
key, shifted, wrap_share);
};
require_opened(dist_with_cmp_key<prg::aes128, prg::aes128, true>(
net, self, center0, center1, gt(power), on, on),
self, encoded_xor_point(center0, center1));
payload *= center;
}
if (self == role::p2)
return 0;
const auto shares =
grotto::offset_horner_detail::contributions<Degree>(
segments, ordered, kappa);
u64 share = 0;
for (u64 term : shares)
share += term;
const u64 open = open_additive(net, self, share);
if (self == role::p0)
{
require(open
== grotto::offset_horner_clear<Degree>(
center, knots, coeff, eta),
failure);
}
return 0;
}
template <std::size_t Degree>
int grotto_offset_horner_deg(role self, trio & net)
{
using Input = std::uint8_t;
const Input center = 3;
const Input eta = 4;
const std::vector<Input> knots{0};
std::vector<std::array<u64, Degree + 1>> coeff(1);
const u64 raw[4] = {5, 0, 1, 2};
for (std::size_t k = 0; k <= Degree; ++k)
coeff[0][k] = k < 4 ? raw[k] : 0u;
const Input c0 = 0x11;
const Input c1 = static_cast<Input>(center ^ c0);
return dist_offset_horner<Degree>(
self, net, c0, c1, center, eta, knots, coeff, "offset horner");
}
int grotto_offset_horner_multipiece(role self, trio & net)
{
constexpr std::size_t D = 3;
using Input = std::uint8_t;
const Input center = 12;
const Input eta = 3;
const std::vector<Input> knots{0, 10, 50};
std::vector<std::array<u64, D + 1>> coeff{
{{1, 0, 0, 0}},
{{0, 2, 0, 0}},
{{7, 0, 0, 1}},
};
const Input c0 = 0x25;
const Input c1 = static_cast<Input>(center ^ c0);
return dist_offset_horner<D>(
self, net, c0, c1, center, eta, knots, coeff, "oh multipiece");
}
int grotto_geneval_offset_horner(role self, trio & net)
{
constexpr std::size_t D = 3;
using Input = std::uint8_t;
const Input center = 3;
const Input eta = 4;
const Input c0 = 0x11;
const Input c1 = static_cast<Input>(center ^ c0);
const std::vector<Input> knots{0};
std::vector<std::array<u64, D + 1>> coeff{{{5, 0, 1, 2}}};
return dist_offset_horner<D>(
self, net, c0, c1, center, eta, knots, coeff, "geneval oh");
}
// ============================================================================
// Geneval / DS extreme
// ============================================================================
int geneval_true_point_shares(role self, trio & net)
{
using Input = std::uint8_t;
const Input alpha = 0x2a;
const Input x0 = 0x10;
const Input x1 = static_cast<Input>(alpha ^ x0);
const u64 beta = 77;
const Input off_x = static_cast<Input>(alpha ^ 0x80);
auto on = [&](const auto & key) {
std::vector<u64> mine{
share_bits(*eval_point(key, alpha)),
share_bits(*eval_point(key, off_x))};
auto opened = open_subtractive(net, self, mine);
if (self == role::p0)
{
require(opened[0] == beta, "geneval on");
require(opened[1] == 0u, "geneval off");
}
};
require_tree_prefix(dist_with_point_key<prg::aes128, prg::aes128, true>(net, self, x0, x1, beta, on, on),
self, verifiable_tree_prefix<prg::aes128, prg::aes128, u64>(x0, x1));
return 0;
}
int geneval_interval_dense(role self, trio & net)
{
using Input = std::uint8_t;
const Input alpha = 50;
const Input x0 = 7;
const Input x1 = static_cast<Input>(alpha ^ x0);
const u64 beta = 3;
const Input from = 40, to = 60;
auto on = [&](const auto & key) {
std::vector<u64> mine;
mine.reserve(static_cast<std::size_t>(to - from) + 1u);
for (unsigned x = from;; ++x)
{
mine.push_back(share_bits(*eval_point(key, static_cast<Input>(x))));
if (x == to)
break;
}
auto out = open_subtractive(net, self, mine);
if (self == role::p0)
{
for (std::size_t i = 0; i < out.size(); ++i)
{
const Input x = static_cast<Input>(from + i);
require(out[i] == (x == alpha ? beta : 0u), "geneval interval");
}
}
};
require_tree_prefix(dist_with_point_key<prg::aes128, prg::aes128, true>(net, self, x0, x1, beta, on, on),
self, verifiable_tree_prefix<prg::aes128, prg::aes128, u64>(x0, x1));
return 0;
}
int geneval_cmp_dense_gt(role self, trio & net)
{
using Input = std::uint8_t;
const Input alpha = 40;
const Input x0 = 0x11;
const Input x1 = static_cast<Input>(alpha ^ x0);
const u64 beta = 7;
const std::vector<Input> ends{0, 1, 10, 39, 40, 41, 100, 200, 255};
auto on = [&](const auto & key) {
const u64 mask = key.cmp().mask;
std::vector<u64> mine;
mine.reserve(ends.size());
for (Input x : ends)
mine.push_back(share_bits(eval_point(cmp, key, x)) & mask);
auto opened = open_additive(net, self, mine);
if (self == role::p0)
{
for (std::size_t i = 0; i < ends.size(); ++i)
require((opened[i] & mask)
== (ends[i] > alpha ? beta : 0u),
"geneval cmp");
}
};
require_opened(dist_with_cmp_key<prg::aes128, prg::aes128, true>(net, self, x0, x1, gt(beta), on, on),
self, encoded_xor_point(x0, x1));
return 0;
}
template <int Kind>
int geneval_cmp_kind(role self, trio & net)
{
using Input = std::uint8_t;
const Input alpha = 100;
const Input x0 = 3;
const Input x1 = static_cast<Input>(alpha ^ x0);
const u64 beta = 5;
const std::vector<Input> ends{0, 50, 99, 100, 101, 150, 255};
auto run = [&](auto spec) {
auto on = [&](const auto & key) {
const u64 mask = key.cmp().mask;
std::vector<u64> mine;
mine.reserve(ends.size());
for (Input x : ends)
mine.push_back(share_bits(eval_point(cmp, key, x)) & mask);
auto opened = open_additive(net, self, mine);
if (self == role::p0)
{
for (std::size_t i = 0; i < ends.size(); ++i)
require((opened[i] & mask)
== expect_cmp(Kind, ends[i], alpha, beta),
"geneval cmp kind");
}
};
require_opened(dist_with_cmp_key<prg::aes128, prg::aes128, true>(net, self, x0, x1, spec, on, on),
self, encoded_xor_point(x0, x1));
};
if constexpr (Kind == 0)
run(lt(beta));
else if constexpr (Kind == 1)
run(leq(beta));
else if constexpr (Kind == 2)
run(gt(beta));
else
run(geq(beta));
return 0;
}
int ds_cmp_many_points(role self, trio & net)
{
using Input = std::uint8_t;
const Input alpha = 77;
const Input x0 = 3;
const Input x1 = static_cast<Input>(alpha ^ x0);
const u64 beta = 11;
std::vector<Input> pts;
for (int x = 0; x < 256; x += 5)
pts.push_back(static_cast<Input>(x));
pts.push_back(76);
pts.push_back(77);
pts.push_back(78);
std::sort(pts.begin(), pts.end());
pts.erase(std::unique(pts.begin(), pts.end()), pts.end());
auto on = [&](const auto & key) {
const u64 mask = key.cmp().mask;
std::vector<u64> mine;
for (Input x : pts)
mine.push_back(share_bits(eval_point(cmp, key, x)) & mask);
auto opened = open_additive(net, self, mine);
if (self == role::p0)
{
for (std::size_t i = 0; i < pts.size(); ++i)
require((opened[i] & mask)
== (pts[i] > alpha ? beta : 0u),
"ds cmp");
}
};
require_opened(dist_with_cmp_key<prg::aes128, prg::aes128, true>(net, self, x0, x1, gt(beta), on, on),
self, encoded_xor_point(x0, x1));
return 0;
}
int ds_vs_geneval_cmp_agree(role self, trio & net)
{
using Input = std::uint8_t;
const Input alpha = 40;
const Input x0 = 0x11;
const Input x1 = static_cast<Input>(alpha ^ x0);
const u64 beta = 7;
const std::vector<Input> ends{0, 1, 10, 40, 200, 255};
auto on = [&](const auto & key) {
const u64 mask = key.cmp().mask;
std::vector<u64> first;
std::vector<u64> second;
for (Input x : ends)
{
first.push_back(share_bits(eval_point(cmp, key, x)) & mask);
second.push_back(share_bits(eval_point(cmp, key, x)) & mask);
}
const auto first_open = open_additive(net, self, first);
const auto second_open = open_additive(net, self, second);
if (self == role::p0)
{
for (std::size_t i = 0; i < ends.size(); ++i)
{
const u64 want = ends[i] > alpha ? beta : 0u;
require((first_open[i] & mask) == want, "first open");
require((second_open[i] & mask) == want, "second open");
}
}
};
require_opened(dist_with_cmp_key<prg::aes128, prg::aes128, true>(net, self, x0, x1, gt(beta), on, on),
self, encoded_xor_point(x0, x1));
return 0;
}
int geneval_arith_point_true(role self, trio & net)
{
using Input = std::uint8_t;
const Input alpha = 0x90;
const Input x0 = 0x30;
const Input x1 = static_cast<Input>(alpha - x0); // additive
const u64 beta = 19;
const Input off_x = static_cast<Input>(alpha + 1);
auto on_key = [&](const auto & key) {
std::vector<u64> mine{
share_bits(*eval_point(key, alpha)),
share_bits(*eval_point(key, off_x))};
auto opened = open_subtractive(net, self, mine);
if (self == role::p0)
{
require(opened[0] == beta, "geneval arith on");
require(opened[1] == 0u, "geneval arith off");
}
};
require_tree_prefix(
dist_with_point_key<prg::aes128, prg::aes128, true>(
net, self, x0, x1, beta, on_key, on_key, false, true),
self, verifiable_tree_prefix<prg::aes128, prg::aes128, u64>(
alpha, Input{}, true));
return 0;
}
// ============================================================================
// Registration
// ============================================================================
#define REG(name, tags, fn, benchable) \
register_flow(flow{#name, tags, fn, benchable})
} // namespace extreme
void register_extreme_flows()
{
using namespace extreme;
// Complex beaver
REG(beaver_dot_n64, "beaver dot extreme bench", beaver_dot_extreme_n<64>, true);
REG(beaver_dot_n128, "beaver dot extreme bench", beaver_dot_extreme_n<128>, true);
REG(beaver_nested_dots, "beaver poly extreme bench", beaver_nested_dots, true);
REG(beaver_tuple_cascade, "beaver poly extreme bench", beaver_tuple_cascade, true);
REG(beaver_mixed_batch_poly, "beaver poly horner mux extreme bench",
beaver_mixed_batch_poly, true);
REG(beaver_factored_multilinear, "beaver poly extreme bench",
beaver_factored_multilinear, true);
// DCF dense / full / blocked
REG(dcf_dense_lt, "dcf extreme bench", dcf_dense_grid<0>, true);
REG(dcf_dense_leq, "dcf extreme bench", dcf_dense_grid<1>, true);
REG(dcf_dense_gt, "dcf extreme bench", dcf_dense_grid<2>, true);
REG(dcf_dense_geq, "dcf extreme bench", dcf_dense_grid<3>, true);
REG(dcf_full_lt, "dcf extreme bench", dcf_full_domain<0>, true);
REG(dcf_full_leq, "dcf extreme bench", dcf_full_domain<1>, true);
REG(dcf_full_gt, "dcf extreme bench", dcf_full_domain<2>, true);
REG(dcf_full_geq, "dcf extreme bench", dcf_full_domain<3>, true);
REG(dcf_blocked_interval_ip, "dcf blocked extreme bench",
dcf_blocked_interval_ip, true);
// Grotto
REG(grotto_signed_prefix_dense, "grotto dcf extreme bench",
grotto_signed_prefix_dense, true);
REG(grotto_signed_segment_onehot, "grotto dcf extreme bench",
grotto_signed_segment_onehot, true);
REG(grotto_xor_prefix_parity, "grotto dpf extreme bench",
grotto_xor_prefix_parity, true);
REG(grotto_signum_lut, "grotto lut extreme bench", grotto_signum_lut, true);
REG(grotto_offset_horner_d1, "grotto horner extreme bench",
grotto_offset_horner_deg<1>, true);
REG(grotto_offset_horner_d2, "grotto horner extreme bench",
grotto_offset_horner_deg<2>, true);
REG(grotto_offset_horner_d3, "grotto horner extreme bench",
grotto_offset_horner_deg<3>, true);
REG(grotto_offset_horner_multipiece, "grotto horner extreme bench",
grotto_offset_horner_multipiece, true);
REG(grotto_geneval_offset_horner, "grotto geneval horner extreme bench",
grotto_geneval_offset_horner, true);
// Geneval / DS
REG(geneval_true_point_shares, "geneval extreme bench",
geneval_true_point_shares, true);
REG(geneval_interval_dense, "geneval extreme bench",
geneval_interval_dense, true);
REG(geneval_cmp_dense_gt, "geneval dcf extreme bench",
geneval_cmp_dense_gt, true);
REG(geneval_cmp_lt, "geneval dcf extreme bench", geneval_cmp_kind<0>, true);
REG(geneval_cmp_leq, "geneval dcf extreme bench", geneval_cmp_kind<1>, true);
REG(geneval_cmp_gt, "geneval dcf extreme bench", geneval_cmp_kind<2>, true);
REG(geneval_cmp_geq, "geneval dcf extreme bench", geneval_cmp_kind<3>, true);
REG(geneval_arith_point_true, "geneval extreme bench",
geneval_arith_point_true, true);
REG(ds_cmp_many_points, "ds dcf extreme bench", ds_cmp_many_points, true);
REG(ds_vs_geneval_cmp_agree, "ds geneval dcf extreme bench",
ds_vs_geneval_cmp_agree, true);
}
#undef REG
} // namespace party
} // namespace dpf
Reference in a new issue View git blame Copy permalink