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>
757 lines
26 KiB
C++
757 lines
26 KiB
C++
#include <gtest/gtest.h>
|
||
#include <tuple>
|
||
|
||
#include <cstdint>
|
||
#include <cstring>
|
||
#include <stdexcept>
|
||
#include <vector>
|
||
|
||
#include "dpf.hpp"
|
||
#include "dpf/dpf3_ds.hpp"
|
||
#include "dpf/prg_aes_ccr.hpp"
|
||
|
||
namespace
|
||
{
|
||
|
||
using dpf::fp61;
|
||
|
||
fp61 open3(fp61 a, fp61 b, fp61 c)
|
||
{
|
||
return dpf::shamir3::reconstruct(
|
||
dpf::shamir3::share{1, a}, dpf::shamir3::share{2, b},
|
||
dpf::shamir3::share{3, c});
|
||
}
|
||
|
||
/// F_DPF3CMP: complementary DCF halves (party 1 = k0, party 2 = k1).
|
||
fp61 open_cmp(std::uint64_t k0_half, std::uint64_t k1_half)
|
||
{
|
||
return dpf::reconstruct_cmp_halves(k0_half, k1_half);
|
||
}
|
||
|
||
template <typename K1, typename K2, typename K3, typename Input>
|
||
void expect_point(const K1 & k1, const K2 & k2, const K3 & k3, Input alpha,
|
||
fp61 beta)
|
||
{
|
||
for (unsigned x = 0; x < 256; ++x)
|
||
{
|
||
const fp61 got = open3(dpf::eval_point(k1, static_cast<Input>(x)),
|
||
dpf::eval_point(k2, static_cast<Input>(x)),
|
||
dpf::eval_point(k3, static_cast<Input>(x)));
|
||
if (static_cast<Input>(x) == alpha)
|
||
EXPECT_EQ(got, beta) << "x=" << x;
|
||
else
|
||
EXPECT_EQ(got.raw(), 0u) << "x=" << x;
|
||
}
|
||
}
|
||
|
||
} // namespace
|
||
|
||
TEST(Shamir3, ShareAndReconstruct)
|
||
{
|
||
const fp61 secret{123456789u};
|
||
const auto s = dpf::shamir3::share_secret(secret);
|
||
EXPECT_EQ(dpf::shamir3::reconstruct(s[0], s[1]), secret);
|
||
EXPECT_EQ(dpf::shamir3::reconstruct(s[0], s[2]), secret);
|
||
EXPECT_EQ(dpf::shamir3::reconstruct(s[1], s[2]), secret);
|
||
EXPECT_EQ(dpf::shamir3::reconstruct(s[0], s[1], s[2]), secret);
|
||
}
|
||
|
||
TEST(Shamir3, PartyScaleRoundTrip)
|
||
{
|
||
const fp61 v{0x123456789abcdefull & ((1ull << 61) - 1)};
|
||
const auto s = dpf::shamir3::share_secret(v);
|
||
for (const auto & sh : s)
|
||
{
|
||
const fp61 uns = dpf::shamir3::unscale(sh);
|
||
const fp61 back = dpf::shamir3::party_scale(
|
||
dpf::shamir3::share{sh.party, uns});
|
||
EXPECT_EQ(back, sh.value);
|
||
}
|
||
}
|
||
|
||
TEST(Dpf3, PointFullDomain)
|
||
{
|
||
using Input = std::uint8_t;
|
||
const Input alpha = 42;
|
||
const fp61 beta{99};
|
||
auto [k1, k2, k3] = dpf::make_dpf3(alpha, beta);
|
||
expect_point(k1, k2, k3, alpha, beta);
|
||
// Single key is not the clear point function.
|
||
EXPECT_NE(dpf::eval_point(k1, alpha), beta);
|
||
EXPECT_NE(dpf::eval_point(k2, alpha), beta);
|
||
EXPECT_NE(dpf::eval_point(k3, alpha), beta);
|
||
}
|
||
|
||
TEST(Dpf3, HalfTree)
|
||
{
|
||
using Input = std::uint8_t;
|
||
using Interior = dpf::prg::aes128_ccr;
|
||
using Exterior = dpf::prg::aes128;
|
||
const Input alpha = 7;
|
||
const fp61 beta{5};
|
||
auto [k1, k2, k3] = dpf::make_dpf3<Interior, Exterior>(alpha, beta);
|
||
expect_point(k1, k2, k3, alpha, beta);
|
||
}
|
||
|
||
TEST(Dpf3, VerifiableProof)
|
||
{
|
||
using Input = std::uint8_t;
|
||
const Input alpha = 11;
|
||
const fp61 beta{3};
|
||
auto [k1, k2, k3] = dpf::make_dpf3(alpha, beta, dpf::verifiable{});
|
||
auto p1 = dpf::prove_dpf3(k1, alpha);
|
||
auto p2 = dpf::prove_dpf3(k2, alpha);
|
||
auto p3 = dpf::prove_dpf3(k3, alpha);
|
||
EXPECT_TRUE(dpf::verify_dpf3(p1, p2, p3));
|
||
using arr = typename std::decay_t<decltype(k1.a.dpf_key)>::correction_seeds_array;
|
||
for (auto & cs : const_cast<arr &>(k1.a.dpf_key.correction_seeds()))
|
||
cs[0] = simde_mm_xor_si128(cs[0], simde_mm_set1_epi8(1));
|
||
auto bad = dpf::prove_dpf3(k1, alpha);
|
||
EXPECT_FALSE(dpf::verify_dpf3(bad, p2, p3));
|
||
}
|
||
|
||
TEST(Dpf3, ExtractableWeightOne)
|
||
{
|
||
using Input = std::uint8_t;
|
||
const Input alpha = 20;
|
||
const fp61 beta{7};
|
||
auto [k1, k2, k3] = dpf::make_dpf3(alpha, beta, dpf::extractable{});
|
||
EXPECT_TRUE(k1.extractable);
|
||
std::vector<fp61> s1(256), s2(256), s3(256), rs(256);
|
||
for (unsigned x = 0; x < 256; ++x)
|
||
{
|
||
s1[x] = dpf::eval_point(k1, static_cast<Input>(x));
|
||
s2[x] = dpf::eval_point(k2, static_cast<Input>(x));
|
||
s3[x] = dpf::eval_point(k3, static_cast<Input>(x));
|
||
rs[x] = dpf::uniform_sample<fp61>();
|
||
}
|
||
EXPECT_TRUE(dpf::sketch_verify3(k1, k2, k3, s1, s2, s3, rs));
|
||
s1[21] = s1[21] + beta;
|
||
s2[21] = s2[21] + beta;
|
||
s3[21] = s3[21] + beta;
|
||
EXPECT_FALSE(dpf::sketch_verify3(k1, k2, k3, s1, s2, s3, rs));
|
||
}
|
||
|
||
TEST(Dpf3, ExtractableGateRejectsPlainKeys)
|
||
{
|
||
using Input = std::uint8_t;
|
||
auto [k1, k2, k3] = dpf::make_dpf3(Input{1}, fp61{1});
|
||
std::vector<fp61> z(1, fp61{});
|
||
std::vector<fp61> rs(1, fp61{1});
|
||
EXPECT_THROW(dpf::sketch_verify3(k1, k2, k3, z, z, z, rs),
|
||
std::invalid_argument);
|
||
}
|
||
|
||
TEST(Dpf3, VerifiableExtractableProofAndSketch)
|
||
{
|
||
using Input = std::uint8_t;
|
||
const Input alpha = 33;
|
||
const fp61 beta{6};
|
||
auto [k1, k2, k3] =
|
||
dpf::make_dpf3(alpha, beta, dpf::verifiable{}, dpf::extractable{});
|
||
std::vector<fp61> s1(256), s2(256), s3(256), rs(256);
|
||
for (unsigned x = 0; x < 256; ++x)
|
||
{
|
||
s1[x] = dpf::eval_point(k1, static_cast<Input>(x));
|
||
s2[x] = dpf::eval_point(k2, static_cast<Input>(x));
|
||
s3[x] = dpf::eval_point(k3, static_cast<Input>(x));
|
||
rs[x] = dpf::uniform_sample<fp61>();
|
||
}
|
||
EXPECT_TRUE(dpf::verify_dpf3(k1, k2, k3, dpf::prove_dpf3(k1, alpha),
|
||
dpf::prove_dpf3(k2, alpha), dpf::prove_dpf3(k3, alpha), s1, s2, s3,
|
||
rs));
|
||
}
|
||
|
||
TEST(Dpf3, UpdatableInPlaceKeepsAlpha)
|
||
{
|
||
using Input = std::uint8_t;
|
||
const Input alpha = 9;
|
||
auto [k1, k2, k3] = dpf::make_dpf3(alpha, fp61{5}, dpf::updatable{});
|
||
EXPECT_TRUE(k1.updatable && k2.updatable && k3.updatable);
|
||
expect_point(k1, k2, k3, alpha, fp61{5});
|
||
|
||
dpf::update_payload(k1, k2, k3, alpha, fp61{8});
|
||
expect_point(k1, k2, k3, alpha, fp61{8});
|
||
|
||
dpf::update_payload(k1, k2, k3, alpha, fp61{0});
|
||
expect_point(k1, k2, k3, alpha, fp61{0});
|
||
|
||
dpf::update_payload(k1, k2, k3, alpha, fp61{100});
|
||
expect_point(k1, k2, k3, alpha, fp61{100});
|
||
}
|
||
|
||
TEST(Dpf3, NonUpdatableRejectsUpdate)
|
||
{
|
||
using Input = std::uint8_t;
|
||
auto [k1, k2, k3] = dpf::make_dpf3(Input{3}, fp61{1});
|
||
EXPECT_FALSE(k1.updatable);
|
||
EXPECT_THROW(dpf::update_payload(k1, k2, k3, Input{3}, fp61{2}), std::invalid_argument);
|
||
}
|
||
|
||
TEST(Dpf3, RemakeFreshTrees)
|
||
{
|
||
using Input = std::uint8_t;
|
||
const Input alpha = 15;
|
||
auto [k1, k2, k3] = dpf::remake_dpf3(alpha, fp61{44});
|
||
expect_point(k1, k2, k3, alpha, fp61{44});
|
||
auto [v1, v2, v3] = dpf::remake_dpf3(alpha, fp61{2}, dpf::verifiable{});
|
||
EXPECT_TRUE(v1.verifiable);
|
||
expect_point(v1, v2, v3, alpha, fp61{2});
|
||
}
|
||
|
||
TEST(Dpf3, VerifiableUpdatableProofSurvivesUpdate)
|
||
{
|
||
using Input = std::uint8_t;
|
||
const Input alpha = 33;
|
||
auto [k1, k2, k3] =
|
||
dpf::make_dpf3(alpha, fp61{6}, dpf::verifiable{}, dpf::updatable{});
|
||
EXPECT_TRUE(dpf::verify_dpf3(dpf::prove_dpf3(k1, alpha),
|
||
dpf::prove_dpf3(k2, alpha), dpf::prove_dpf3(k3, alpha)));
|
||
dpf::update_payload(k1, k2, k3, alpha, fp61{90});
|
||
expect_point(k1, k2, k3, alpha, fp61{90});
|
||
EXPECT_TRUE(dpf::verify_dpf3(dpf::prove_dpf3(k1, alpha),
|
||
dpf::prove_dpf3(k2, alpha), dpf::prove_dpf3(k3, alpha)));
|
||
}
|
||
|
||
TEST(Dpf3, MultipointFullDomain)
|
||
{
|
||
using Input = std::uint8_t;
|
||
const std::vector<Input> alphas{1, 2, 9, 40};
|
||
const std::vector<fp61> betas{fp61{7}, fp61{11}, fp61{3}, fp61{4}};
|
||
auto [k1, k2, k3] = dpf::make_multipoint3(alphas, betas);
|
||
for (unsigned x = 0; x < 256; ++x)
|
||
{
|
||
fp61 want{};
|
||
for (std::size_t i = 0; i < alphas.size(); ++i)
|
||
if (alphas[i] == static_cast<Input>(x))
|
||
want = betas[i];
|
||
const fp61 got = open3(
|
||
dpf::eval_multipoint(k1, static_cast<Input>(x)),
|
||
dpf::eval_multipoint(k2, static_cast<Input>(x)),
|
||
dpf::eval_multipoint(k3, static_cast<Input>(x)));
|
||
EXPECT_EQ(got, want) << "x=" << x;
|
||
}
|
||
}
|
||
|
||
TEST(Dpf3, MultipointUpdatableInPlace)
|
||
{
|
||
using Input = std::uint8_t;
|
||
const std::vector<Input> alphas{1, 2, 9, 40};
|
||
const std::vector<fp61> betas{fp61{7}, fp61{11}, fp61{3}, fp61{4}};
|
||
auto [k1, k2, k3] = dpf::make_multipoint3(alphas, betas, dpf::updatable{});
|
||
EXPECT_TRUE(k1.updatable);
|
||
const auto sigma = k1.sigma;
|
||
const auto m = k1.bucket_count;
|
||
const std::vector<fp61> betas2{fp61{1}, fp61{2}, fp61{3}, fp61{4}};
|
||
dpf::update_payload(k1, k2, k3, alphas, betas2);
|
||
EXPECT_EQ(0, std::memcmp(&k1.sigma, &sigma, sizeof(sigma)));
|
||
EXPECT_EQ(k1.bucket_count, m);
|
||
for (unsigned x = 0; x < 256; ++x)
|
||
{
|
||
fp61 want{};
|
||
for (std::size_t i = 0; i < alphas.size(); ++i)
|
||
if (alphas[i] == static_cast<Input>(x))
|
||
want = betas2[i];
|
||
const fp61 got = open3(
|
||
dpf::eval_multipoint(k1, static_cast<Input>(x)),
|
||
dpf::eval_multipoint(k2, static_cast<Input>(x)),
|
||
dpf::eval_multipoint(k3, static_cast<Input>(x)));
|
||
EXPECT_EQ(got, want) << "x=" << x;
|
||
}
|
||
}
|
||
|
||
TEST(Dpf3, MultipointNonUpdatableRejects)
|
||
{
|
||
using Input = std::uint8_t;
|
||
const std::vector<Input> alphas{3, 5};
|
||
const std::vector<fp61> betas{fp61{1}, fp61{1}};
|
||
auto [k1, k2, k3] = dpf::make_multipoint3(alphas, betas);
|
||
EXPECT_THROW(dpf::update_payload(k1, k2, k3, alphas, betas), std::invalid_argument);
|
||
}
|
||
|
||
TEST(Dpf3, MultipointSeedFlip)
|
||
{
|
||
using Input = std::uint8_t;
|
||
const std::vector<Input> alphas{3, 5, 7};
|
||
const std::vector<fp61> betas{fp61{1}, fp61{1}, fp61{1}};
|
||
auto [k1, k2, k3] = dpf::make_multipoint3(alphas, betas, dpf::verifiable{});
|
||
ASSERT_FALSE(k1.buckets.empty());
|
||
auto flip = [](auto & plus) {
|
||
using arr =
|
||
typename std::decay_t<decltype(plus.dpf_key)>::correction_seeds_array;
|
||
for (auto & cs : const_cast<arr &>(plus.dpf_key.correction_seeds()))
|
||
cs[0] = simde_mm_xor_si128(cs[0], simde_mm_set1_epi8(1));
|
||
};
|
||
for (auto & bucket : k1.buckets)
|
||
{
|
||
flip(bucket.a);
|
||
flip(bucket.b);
|
||
}
|
||
bool rejected = false;
|
||
for (std::size_t i = 0; i < k1.buckets.size(); ++i)
|
||
{
|
||
auto p1 = dpf::prove_dpf3(k1.buckets[i], Input{0});
|
||
auto p2 = dpf::prove_dpf3(k2.buckets[i], Input{0});
|
||
auto p3 = dpf::prove_dpf3(k3.buckets[i], Input{0});
|
||
if (!dpf::verify_dpf3(p1, p2, p3))
|
||
rejected = true;
|
||
}
|
||
EXPECT_TRUE(rejected);
|
||
}
|
||
|
||
TEST(Dpf3, ComparisonFullDomain)
|
||
{
|
||
using Input = std::uint8_t;
|
||
const Input thresh = 100;
|
||
const uint64_t beta = 17;
|
||
auto [k1, k2, k3] = dpf::make_dpf3_cmp(thresh, beta);
|
||
for (unsigned x = 0; x < 256; ++x)
|
||
{
|
||
const bool hot = static_cast<Input>(x) < thresh;
|
||
const auto s1 = dpf::eval_point(k1, static_cast<Input>(x));
|
||
const auto s2 = dpf::eval_point(k2, static_cast<Input>(x));
|
||
const auto s3 = dpf::eval_point(k3, static_cast<Input>(x));
|
||
EXPECT_EQ(open_cmp(s1, s2).raw(), hot ? beta : 0u) << "x=" << x;
|
||
EXPECT_EQ(open_cmp(s3, s2).raw(), hot ? beta : 0u) << "x=" << x;
|
||
EXPECT_EQ(s1, s3) << "x=" << x; // both hold k0
|
||
if (hot)
|
||
EXPECT_NE(s1, beta);
|
||
}
|
||
}
|
||
|
||
TEST(Dpf3, BlockedComparison)
|
||
{
|
||
using Input = std::uint8_t;
|
||
auto [k1, k2, k3] = dpf::make_dpf3_cmp_blocked<4>(Input{50}, 9u);
|
||
EXPECT_EQ(open_cmp(dpf::eval_point(k1, Input{10}), dpf::eval_point(k2, Input{10}))
|
||
.raw(),
|
||
9u);
|
||
EXPECT_EQ(open_cmp(dpf::eval_point(k1, Input{200}),
|
||
dpf::eval_point(k2, Input{200}))
|
||
.raw(),
|
||
0u);
|
||
}
|
||
|
||
TEST(Dpf3, IntervalFullDomain)
|
||
{
|
||
using Input = std::uint8_t;
|
||
const Input r = 10, p = 20, q = 40;
|
||
const uint64_t beta = 5;
|
||
auto [k1, k2, k3] = dpf::make_dpf3_ic(r, p, q, beta);
|
||
auto two = dpf::make_dpf(r, dpf::ic(p, q, beta));
|
||
for (unsigned x = 0; x < 256; ++x)
|
||
{
|
||
const auto want = dpf::reconstruct(
|
||
dpf::eval_point(dpf::ic, two.first, static_cast<Input>(x)),
|
||
dpf::eval_point(dpf::ic, two.second, static_cast<Input>(x)));
|
||
const fp61 got = open_cmp(
|
||
dpf::eval_point(k1, static_cast<Input>(x)),
|
||
dpf::eval_point(k2, static_cast<Input>(x)));
|
||
EXPECT_EQ(got.raw(), static_cast<uint64_t>(want)) << "x=" << x;
|
||
}
|
||
}
|
||
|
||
TEST(Dpf3, ComparisonPayloadUpdateInPlace)
|
||
{
|
||
using Input = std::uint8_t;
|
||
const Input thresh = 80;
|
||
auto [k1, k2, k3] = dpf::make_dpf3_cmp(thresh, 3u);
|
||
dpf::update_payload_cmp(k1, k2, k3, 3u, 11u);
|
||
for (unsigned x = 0; x < 256; ++x)
|
||
{
|
||
const bool hot = static_cast<Input>(x) < thresh;
|
||
const fp61 got = open_cmp(
|
||
dpf::eval_point(k1, static_cast<Input>(x)),
|
||
dpf::eval_point(k2, static_cast<Input>(x)));
|
||
EXPECT_EQ(got.raw(), hot ? 11u : 0u) << "x=" << x;
|
||
}
|
||
dpf::update_payload_cmp(k1, k2, k3, 11u, 0u);
|
||
for (unsigned x = 0; x < 256; ++x)
|
||
{
|
||
const fp61 got = open_cmp(
|
||
dpf::eval_point(k1, static_cast<Input>(x)),
|
||
dpf::eval_point(k2, static_cast<Input>(x)));
|
||
EXPECT_EQ(got.raw(), 0u) << "x=" << x;
|
||
}
|
||
}
|
||
|
||
TEST(Dpf3, ComparisonRemake)
|
||
{
|
||
using Input = std::uint8_t;
|
||
auto [k1, k2, k3] = dpf::remake_dpf3_cmp(Input{50}, 7u, 0u);
|
||
EXPECT_EQ(open_cmp(dpf::eval_point(k1, Input{10}), dpf::eval_point(k2, Input{10}))
|
||
.raw(),
|
||
7u);
|
||
}
|
||
|
||
TEST(Dpf3, DoernerShelatMatchesDealer)
|
||
{
|
||
using Input = std::uint8_t;
|
||
const Input alpha = 0x2a;
|
||
const Input x0 = 0x13;
|
||
const Input x1 = static_cast<Input>(alpha ^ x0);
|
||
const fp61 beta{77};
|
||
auto [d1, d2, d3] = dpf::make_dpf3(alpha, beta);
|
||
auto [s1, s2, s3] = dpf::make_dpf3_doerner_shelat(x0, x1, beta);
|
||
expect_point(d1, d2, d3, alpha, beta);
|
||
expect_point(s1, s2, s3, alpha, beta);
|
||
EXPECT_EQ(dpf::detail::dpf3_impl::open_xor_point(x0, x1), alpha);
|
||
}
|
||
|
||
TEST(Dpf3, DoernerShelatVerifiable)
|
||
{
|
||
using Input = std::uint8_t;
|
||
const Input alpha = 19;
|
||
const Input x0 = 7;
|
||
const Input x1 = static_cast<Input>(alpha ^ x0);
|
||
auto [k1, k2, k3] =
|
||
dpf::make_dpf3_doerner_shelat(x0, x1, fp61{4}, dpf::verifiable{});
|
||
EXPECT_TRUE(k1.verifiable);
|
||
expect_point(k1, k2, k3, alpha, fp61{4});
|
||
EXPECT_TRUE(dpf::verify_dpf3(dpf::prove_dpf3(k1, alpha),
|
||
dpf::prove_dpf3(k2, alpha), dpf::prove_dpf3(k3, alpha)));
|
||
}
|
||
|
||
TEST(Dpf3, DoernerShelatUpdatable)
|
||
{
|
||
using Input = std::uint8_t;
|
||
const Input alpha = 8;
|
||
const Input x0 = 1;
|
||
const Input x1 = static_cast<Input>(alpha ^ x0);
|
||
auto [k1, k2, k3] =
|
||
dpf::make_dpf3_doerner_shelat(x0, x1, fp61{2}, dpf::updatable{});
|
||
EXPECT_TRUE(k1.updatable);
|
||
EXPECT_FALSE(k1.verifiable);
|
||
dpf::update_payload(k1, k2, k3, alpha, fp61{55});
|
||
expect_point(k1, k2, k3, alpha, fp61{55});
|
||
}
|
||
|
||
TEST(Dpf3, DoernerShelatVerifiableUpdatableTagParity)
|
||
{
|
||
using Input = std::uint8_t;
|
||
const Input alpha = 14;
|
||
const Input x0 = 2;
|
||
const Input x1 = static_cast<Input>(alpha ^ x0);
|
||
auto [k1, k2, k3] = dpf::make_dpf3_doerner_shelat(x0, x1, fp61{3},
|
||
dpf::verifiable{}, dpf::updatable{});
|
||
EXPECT_TRUE(k1.verifiable && k1.updatable);
|
||
EXPECT_TRUE(dpf::verify_dpf3(dpf::prove_dpf3(k1, alpha),
|
||
dpf::prove_dpf3(k2, alpha), dpf::prove_dpf3(k3, alpha)));
|
||
dpf::update_payload(k1, k2, k3, alpha, fp61{11});
|
||
expect_point(k1, k2, k3, alpha, fp61{11});
|
||
}
|
||
|
||
TEST(Dpf3, DoernerShelatExtractable)
|
||
{
|
||
using Input = std::uint8_t;
|
||
const Input alpha = 12;
|
||
const Input x0 = 3;
|
||
const Input x1 = static_cast<Input>(alpha ^ x0);
|
||
auto [k1, k2, k3] =
|
||
dpf::make_dpf3_doerner_shelat(x0, x1, fp61{1}, dpf::extractable{});
|
||
EXPECT_TRUE(k1.extractable && k2.extractable && k3.extractable);
|
||
expect_point(k1, k2, k3, alpha, fp61{1});
|
||
std::vector<fp61> s1(256), s2(256), s3(256), rs(256);
|
||
for (unsigned x = 0; x < 256; ++x)
|
||
{
|
||
s1[x] = dpf::eval_point(k1, static_cast<Input>(x));
|
||
s2[x] = dpf::eval_point(k2, static_cast<Input>(x));
|
||
s3[x] = dpf::eval_point(k3, static_cast<Input>(x));
|
||
rs[x] = dpf::uniform_sample<fp61>();
|
||
}
|
||
EXPECT_TRUE(dpf::sketch_verify3(k1, k2, k3, s1, s2, s3, rs));
|
||
}
|
||
|
||
TEST(Dpf3, RemakeTagParity)
|
||
{
|
||
using Input = std::uint8_t;
|
||
auto [u1, u2, u3] = dpf::remake_dpf3(Input{1}, fp61{2}, dpf::updatable{});
|
||
EXPECT_TRUE(u1.updatable);
|
||
expect_point(u1, u2, u3, Input{1}, fp61{2});
|
||
auto [e1, e2, e3] =
|
||
dpf::remake_dpf3(Input{2}, fp61{3}, dpf::verifiable{}, dpf::extractable{});
|
||
EXPECT_TRUE(e1.verifiable && e1.extractable);
|
||
expect_point(e1, e2, e3, Input{2}, fp61{3});
|
||
}
|
||
|
||
TEST(Dpf3, MultipointVerifiableUpdatable)
|
||
{
|
||
using Input = std::uint8_t;
|
||
const std::vector<Input> alphas{4, 8, 16};
|
||
const std::vector<fp61> betas{fp61{1}, fp61{2}, fp61{3}};
|
||
auto [k1, k2, k3] = dpf::make_multipoint3(alphas, betas, dpf::verifiable{},
|
||
dpf::updatable{});
|
||
EXPECT_TRUE(k1.verifiable && k1.updatable);
|
||
const std::vector<fp61> betas2{fp61{9}, fp61{8}, fp61{7}};
|
||
dpf::update_payload(k1, k2, k3, alphas, betas2);
|
||
for (std::size_t i = 0; i < alphas.size(); ++i)
|
||
{
|
||
const fp61 got = open3(dpf::eval_multipoint(k1, alphas[i]),
|
||
dpf::eval_multipoint(k2, alphas[i]),
|
||
dpf::eval_multipoint(k3, alphas[i]));
|
||
EXPECT_EQ(got, betas2[i]);
|
||
}
|
||
}
|
||
|
||
TEST(Dpf3, AsSharePartyIndex)
|
||
{
|
||
using Input = std::uint8_t;
|
||
auto [k1, k2, k3] = dpf::make_dpf3(Input{0}, fp61{1});
|
||
const fp61 y{};
|
||
EXPECT_EQ(dpf::as_share(k1, y).party, 1);
|
||
EXPECT_EQ(dpf::as_share(k2, y).party, 2);
|
||
EXPECT_EQ(dpf::as_share(k3, y).party, 3);
|
||
}
|
||
|
||
TEST(Shamir3, InconsistentSharesThrow)
|
||
{
|
||
const auto s = dpf::shamir3::share_secret(fp61{42});
|
||
auto bad = s[2];
|
||
bad.value = bad.value + fp61{1};
|
||
EXPECT_THROW(dpf::shamir3::reconstruct(s[0], s[1], bad), std::runtime_error);
|
||
}
|
||
|
||
TEST(Dpf3, ComparisonPredicatesLeqGtGeq)
|
||
{
|
||
using Input = std::uint8_t;
|
||
const Input thresh = 100;
|
||
const uint64_t beta = 4;
|
||
auto check = [&](auto keys, auto pred) {
|
||
auto [k1, k2, k3] = keys;
|
||
for (unsigned x = 0; x < 256; ++x)
|
||
{
|
||
const bool hot = pred(static_cast<Input>(x));
|
||
const fp61 got = open_cmp(dpf::eval_point(k1, static_cast<Input>(x)),
|
||
dpf::eval_point(k2, static_cast<Input>(x)));
|
||
EXPECT_EQ(got.raw(), hot ? beta : 0u) << "x=" << x;
|
||
}
|
||
};
|
||
check(dpf::make_dpf3_cmp(thresh, dpf::leq(beta)),
|
||
[&](Input x) { return x <= thresh; });
|
||
check(dpf::make_dpf3_cmp(thresh, dpf::gt(beta)),
|
||
[&](Input x) { return x > thresh; });
|
||
check(dpf::make_dpf3_cmp(thresh, dpf::geq(beta)),
|
||
[&](Input x) { return x >= thresh; });
|
||
}
|
||
|
||
TEST(Dpf3, ComparisonUpdateFp61NotUint64Wrap)
|
||
{
|
||
// Historical bug: `(0 - 11) & ~0ull` is not −11 mod p. Updating 11 → 0
|
||
// must clear the hot lane, not leave a wraparound residue.
|
||
using Input = std::uint8_t;
|
||
const Input thresh = 60;
|
||
auto [k1, k2, k3] = dpf::make_dpf3_cmp(thresh, 11u);
|
||
dpf::update_payload_cmp(k1, k2, k3, 11u, 0u);
|
||
for (unsigned x = 0; x < 256; ++x)
|
||
{
|
||
const fp61 got = open_cmp(dpf::eval_point(k1, static_cast<Input>(x)),
|
||
dpf::eval_point(k2, static_cast<Input>(x)));
|
||
EXPECT_EQ(got.raw(), 0u) << "x=" << x;
|
||
}
|
||
}
|
||
|
||
TEST(Dpf3, PublicPiIdenticalAfterUpdate)
|
||
{
|
||
using Input = std::uint8_t;
|
||
const Input alpha = 21;
|
||
auto [k1, k2, k3] = dpf::make_dpf3(alpha, fp61{3}, dpf::updatable{});
|
||
EXPECT_EQ(k1.a.offset, k2.a.offset);
|
||
EXPECT_EQ(k2.a.offset, k3.a.offset);
|
||
EXPECT_EQ(k1.b.offset, k2.b.offset);
|
||
EXPECT_EQ(k2.b.offset, k3.b.offset);
|
||
dpf::update_payload(k1, k2, k3, alpha, fp61{70});
|
||
EXPECT_EQ(k1.a.offset, k2.a.offset);
|
||
EXPECT_EQ(k2.a.offset, k3.a.offset);
|
||
EXPECT_EQ(k1.b.offset, k2.b.offset);
|
||
EXPECT_EQ(k2.b.offset, k3.b.offset);
|
||
expect_point(k1, k2, k3, alpha, fp61{70});
|
||
}
|
||
|
||
TEST(Dpf3, ProveRejectsClearedVerifiableFlag)
|
||
{
|
||
using Input = std::uint8_t;
|
||
const Input alpha = 5;
|
||
auto [k1, k2, k3] = dpf::make_dpf3(alpha, fp61{1}, dpf::verifiable{});
|
||
k1.verifiable = false; // outer flag gate (inners remain V)
|
||
EXPECT_THROW(dpf::prove_dpf3(k1, alpha), std::invalid_argument);
|
||
(void)k2;
|
||
(void)k3;
|
||
}
|
||
|
||
TEST(Dpf3, VerifyExtractableRejectsNonExtractable)
|
||
{
|
||
using Input = std::uint8_t;
|
||
const Input alpha = 8;
|
||
auto [k1, k2, k3] = dpf::make_dpf3(alpha, fp61{2}, dpf::verifiable{});
|
||
std::vector<fp61> s1(8), s2(8), s3(8), rs(8);
|
||
for (unsigned x = 0; x < 8; ++x)
|
||
{
|
||
s1[x] = dpf::eval_point(k1, static_cast<Input>(x));
|
||
s2[x] = dpf::eval_point(k2, static_cast<Input>(x));
|
||
s3[x] = dpf::eval_point(k3, static_cast<Input>(x));
|
||
rs[x] = fp61{1};
|
||
}
|
||
EXPECT_THROW(
|
||
dpf::verify_dpf3(k1, k2, k3, dpf::prove_dpf3(k1, alpha),
|
||
dpf::prove_dpf3(k2, alpha), dpf::prove_dpf3(k3, alpha), s1, s2, s3,
|
||
rs),
|
||
std::invalid_argument);
|
||
}
|
||
|
||
TEST(Dpf3, IntervalBoundaryRelativeToR)
|
||
{
|
||
// Interval is relative to public shift `r`; x=r+p and x=r+q−1 are the
|
||
// classic edges that mis-scored in the IC example (absolute vs relative).
|
||
using Input = std::uint8_t;
|
||
const Input r = 10, p = 20, q = 40;
|
||
const uint64_t beta = 5;
|
||
auto [k1, k2, k3] = dpf::make_dpf3_ic(r, p, q, beta);
|
||
auto two = dpf::make_dpf(r, dpf::ic(p, q, beta));
|
||
for (Input x : {Input{29}, Input{30}, Input{35}, Input{49}, Input{50}})
|
||
{
|
||
const auto want = dpf::reconstruct(
|
||
dpf::eval_point(dpf::ic, two.first, x),
|
||
dpf::eval_point(dpf::ic, two.second, x));
|
||
const fp61 got = open_cmp(dpf::eval_point(k1, x), dpf::eval_point(k2, x));
|
||
EXPECT_EQ(got.raw(), static_cast<uint64_t>(want)) << "x=" << unsigned(x);
|
||
}
|
||
}
|
||
|
||
TEST(Dpf3, MultipointRemakeFreshSigma)
|
||
{
|
||
using Input = std::uint8_t;
|
||
const std::vector<Input> alphas{2, 4, 8};
|
||
const std::vector<fp61> betas{fp61{1}, fp61{2}, fp61{3}};
|
||
auto [a1, a2, a3] = dpf::make_multipoint3(alphas, betas, dpf::updatable{});
|
||
const auto sigma0 = a1.sigma;
|
||
auto [b1, b2, b3] = dpf::remake_multipoint3(alphas, betas);
|
||
EXPECT_NE(0, std::memcmp(&b1.sigma, &sigma0, sizeof(sigma0)));
|
||
for (std::size_t i = 0; i < alphas.size(); ++i)
|
||
{
|
||
EXPECT_EQ(open3(dpf::eval_multipoint(b1, alphas[i]),
|
||
dpf::eval_multipoint(b2, alphas[i]),
|
||
dpf::eval_multipoint(b3, alphas[i])),
|
||
betas[i]);
|
||
}
|
||
(void)a2;
|
||
(void)a3;
|
||
}
|
||
|
||
TEST(Dpf3, HalfTreeUpdatableUpdate)
|
||
{
|
||
using Input = std::uint8_t;
|
||
using Interior = dpf::prg::aes128_ccr;
|
||
using Exterior = dpf::prg::aes128;
|
||
const Input alpha = 55;
|
||
auto [k1, k2, k3] =
|
||
dpf::make_dpf3<Interior, Exterior>(alpha, fp61{8}, dpf::updatable{});
|
||
dpf::update_payload(k1, k2, k3, alpha, fp61{12});
|
||
expect_point(k1, k2, k3, alpha, fp61{12});
|
||
}
|
||
|
||
TEST(Dpf3, UpdatePreservesCorrectionSeeds)
|
||
{
|
||
using Input = std::uint8_t;
|
||
const Input alpha = 17;
|
||
auto [k1, k2, k3] =
|
||
dpf::make_dpf3(alpha, fp61{4}, dpf::verifiable{}, dpf::updatable{});
|
||
const auto seeds = k1.a.dpf_key.correction_seeds();
|
||
const auto root = k1.a.dpf_key.root();
|
||
dpf::update_payload(k1, k2, k3, alpha, fp61{19});
|
||
EXPECT_EQ(0, std::memcmp(seeds.data(), k1.a.dpf_key.correction_seeds().data(),
|
||
sizeof(seeds)));
|
||
EXPECT_EQ(0, std::memcmp(&root, &k1.a.dpf_key.root(), sizeof(root)));
|
||
expect_point(k1, k2, k3, alpha, fp61{19});
|
||
auto [r1, r2, r3] =
|
||
dpf::remake_dpf3(alpha, fp61{19}, dpf::verifiable{}, dpf::updatable{});
|
||
EXPECT_NE(0, std::memcmp(seeds.data(), r1.a.dpf_key.correction_seeds().data(),
|
||
sizeof(seeds)));
|
||
(void)r2;
|
||
(void)r3;
|
||
}
|
||
|
||
TEST(Dpf3, DoernerShelatVuProofAfterUpdate)
|
||
{
|
||
using Input = std::uint8_t;
|
||
const Input alpha = 22;
|
||
const Input x0 = 6;
|
||
const Input x1 = static_cast<Input>(alpha ^ x0);
|
||
auto [k1, k2, k3] = dpf::make_dpf3_doerner_shelat(x0, x1, fp61{5},
|
||
dpf::verifiable{}, dpf::updatable{});
|
||
EXPECT_TRUE(dpf::verify_dpf3(dpf::prove_dpf3(k1, alpha),
|
||
dpf::prove_dpf3(k2, alpha), dpf::prove_dpf3(k3, alpha)));
|
||
dpf::update_payload(k1, k2, k3, alpha, fp61{41});
|
||
expect_point(k1, k2, k3, alpha, fp61{41});
|
||
EXPECT_TRUE(dpf::verify_dpf3(dpf::prove_dpf3(k1, alpha),
|
||
dpf::prove_dpf3(k2, alpha), dpf::prove_dpf3(k3, alpha)));
|
||
}
|
||
|
||
TEST(Dpf3, MultipointVuProofAfterUpdate)
|
||
{
|
||
using Input = std::uint8_t;
|
||
const std::vector<Input> alphas{4, 8, 16};
|
||
const std::vector<fp61> betas{fp61{1}, fp61{2}, fp61{3}};
|
||
auto [k1, k2, k3] = dpf::make_multipoint3(alphas, betas, dpf::verifiable{},
|
||
dpf::updatable{});
|
||
const auto sigma = k1.sigma;
|
||
const std::vector<fp61> betas2{fp61{9}, fp61{8}, fp61{7}};
|
||
dpf::update_payload(k1, k2, k3, alphas, betas2);
|
||
EXPECT_EQ(0, std::memcmp(&k1.sigma, &sigma, sizeof(sigma)));
|
||
bool any = false;
|
||
for (std::size_t i = 0; i < k1.buckets.size(); ++i)
|
||
{
|
||
any = true;
|
||
EXPECT_TRUE(dpf::verify_dpf3(dpf::prove_dpf3(k1.buckets[i], Input{0}),
|
||
dpf::prove_dpf3(k2.buckets[i], Input{0}),
|
||
dpf::prove_dpf3(k3.buckets[i], Input{0})));
|
||
}
|
||
EXPECT_TRUE(any);
|
||
}
|
||
|
||
TEST(Dpf3, BlockedComparisonFullDomain)
|
||
{
|
||
using Input = std::uint8_t;
|
||
const Input thresh = 50;
|
||
const uint64_t beta = 9;
|
||
auto [k1, k2, k3] = dpf::make_dpf3_cmp_blocked<4>(thresh, beta);
|
||
for (unsigned x = 0; x < 256; ++x)
|
||
{
|
||
const bool hot = static_cast<Input>(x) < thresh;
|
||
const fp61 got = open_cmp(dpf::eval_point(k1, static_cast<Input>(x)),
|
||
dpf::eval_point(k2, static_cast<Input>(x)));
|
||
EXPECT_EQ(got.raw(), hot ? beta : 0u) << "x=" << x;
|
||
}
|
||
}
|
||
|
||
TEST(Dpf3, TagsAnyOrderIncludingExtractableUpdatable)
|
||
{
|
||
using Input = std::uint8_t;
|
||
const Input alpha = 17;
|
||
auto [k1, k2, k3] = dpf::make_dpf3(alpha, fp61{4},
|
||
dpf::extractable{}, dpf::updatable{}, dpf::verifiable{});
|
||
EXPECT_TRUE(k1.verifiable && k1.extractable && k1.updatable);
|
||
EXPECT_TRUE(k2.extractable && k3.updatable);
|
||
expect_point(k1, k2, k3, alpha, fp61{4});
|
||
dpf::update_payload(k1, k2, k3, alpha, fp61{11});
|
||
expect_point(k1, k2, k3, alpha, fp61{11});
|
||
}
|
||
|
||
TEST(Dpf3, ComparisonSpecWrappersMatchPlainPredicate)
|
||
{
|
||
using Input = std::uint8_t;
|
||
const Input thresh = 40;
|
||
const uint64_t beta = 3;
|
||
auto check = [&](auto keys) {
|
||
auto [k1, k2, k3] = keys;
|
||
for (unsigned x = 0; x < 256; ++x)
|
||
{
|
||
const bool hot = static_cast<Input>(x) > thresh;
|
||
const fp61 got = open_cmp(dpf::eval_point(k1, static_cast<Input>(x)),
|
||
dpf::eval_point(k2, static_cast<Input>(x)));
|
||
EXPECT_EQ(got.raw(), hot ? beta : 0u) << "x=" << x;
|
||
}
|
||
};
|
||
check(dpf::make_dpf3_cmp(thresh, dpf::idcf(dpf::gt(beta))));
|
||
check(dpf::make_dpf3_cmp(thresh, dpf::block_width<4>(dpf::gt(beta))));
|
||
}
|
||
|