libdpf/include/dpf/shamir3.hpp

/// @file dpf/shamir3.hpp
/// @brief Degree-1 Shamir sharing over `fp61` for three evaluators.
/// @details The `(K,N) = (2,3)` case of `shamir::deal` / `shamir::reconstruct`.
///          Parties are indexed `1`, `2`, and `3`. A share of secret `s` is
///          `s_i = s + a·i` for a uniform slope `a`. Any two parties
///          reconstruct by Lagrange. Embeddings move between `fp61` and a
///          61-bit XOR string for the (2,3) point construction of
///          Zyskind, Yanai, and Pentland, ePrint 2024/1658.
/// @copyright Copyright (c) 2019-2026 Ryan Henry and [others](@ref authors)
/// @license Released under a GNU General Public v2.0 (GPLv2) license;
///          see [LICENSE.md](@ref license) for details.

#ifndef LIBDPF_INCLUDE_DPF_SHAMIR3_HPP__
#define LIBDPF_INCLUDE_DPF_SHAMIR3_HPP__

#include <array>
#include <cstdint>
#include <stdexcept>
#include <tuple>
#include <utility>

#include "hedley/hedley.h"

#include "dpf/fp61.hpp"
#include "dpf/random.hpp"
#include "dpf/secret_share.hpp"
#include "dpf/xor_wrapper.hpp"

namespace dpf
{
namespace shamir3
{

/// @brief XOR string wide enough for an `fp61` embed (low 61 bits).
using xor61 = xor_wrapper<std::uint64_t>;

/// @brief One party's share of a degree-1 Shamir secret.
struct share
{
    /// @brief Party index in `{1, 2, 3}`.
    int party = 1;
    /// @brief The field element `s + a·party`.
    fp61 value{};
};

/// @brief Modular inverse in `fp61`.
/// @param a a non-zero field element
/// @return `a^{-1}`
/// @throws std::invalid_argument if `a` is zero
HEDLEY_WARN_UNUSED_RESULT
inline fp61 inv(fp61 a)
{
    return detail::shamir_field<fp61>::inv(a);
}

/// @brief Embed a field element as a 61-bit XOR string.
/// @param a the field element
/// @return the low 61 bits as an XOR word
HEDLEY_NO_THROW
HEDLEY_CONST
HEDLEY_ALWAYS_INLINE
xor61 embed_xor(fp61 a) noexcept
{
    return xor61{a.raw()};
}

/// @brief Embed a 61-bit XOR string as a field element.
/// @param w the XOR word (high bits ignored)
/// @return `fp61` of the low 61 bits
HEDLEY_NO_THROW
HEDLEY_CONST
HEDLEY_ALWAYS_INLINE
fp61 embed_field(xor61 w) noexcept
{
    return fp61{static_cast<std::uint64_t>(w) & fp61_mod};
}

/// @brief Field-to-XOR then XOR: `embed(a) ⊕ w`.
/// @param a the field element
/// @param w the XOR string
/// @return the combined XOR string
HEDLEY_NO_THROW
HEDLEY_CONST
HEDLEY_ALWAYS_INLINE
xor61 field_xor(fp61 a, xor61 w) noexcept
{
    return embed_xor(a) + w;
}

/// @brief XOR-to-field then multiply: `embed(w) · c`.
/// @param w the XOR string
/// @param c the field scale
/// @return the product in `fp61`
HEDLEY_NO_THROW
HEDLEY_CONST
HEDLEY_ALWAYS_INLINE
fp61 xor_scale(xor61 w, fp61 c) noexcept
{
    return embed_field(w) * c;
}

/// @brief Sample a degree-1 sharing of `secret` at parties 1, 2, and 3.
/// @details `shamir::share_secret<fp61, 2, 3>`, written as runtime points
///          `1`, `2`, and `3`.
/// @param secret the cleartext secret
/// @return shares for parties 1, 2, and 3
/// \complexity O(1). One random slope and three field multiplies. No messages.
HEDLEY_WARN_UNUSED_RESULT
inline std::array<share, 3> share_secret(fp61 secret)
{
    const auto dealt = shamir::share_secret<fp61, 2, 3>(secret);
    return {
        share{1, std::get<0>(dealt).raw()},
        share{2, std::get<1>(dealt).raw()},
        share{3, std::get<2>(dealt).raw()},
    };
}

/// @brief Reconstruct from any two distinct party shares.
/// @details `shamir::reconstruct<fp61, 2, 3>` after the (2,3) party check.
/// @param a first share
/// @param b second share
/// @return the secret
/// @throws std::invalid_argument if the party indices collide or are out of range
/// \complexity O(1). Two field inverses and a handful of multiplies. The shares are already in hand; this function does not exchange them.
HEDLEY_WARN_UNUSED_RESULT
inline fp61 reconstruct(share a, share b)
{
    if (a.party == b.party || a.party < 1 || a.party > 3 || b.party < 1
        || b.party > 3)
        throw std::invalid_argument("shamir3: need two distinct parties in 1..3");
    const std::array<shamir::point_share<fp61>, 2> held{{
        shamir::point_share<fp61>{a.party, a.value},
        shamir::point_share<fp61>{b.party, b.value},
    }};
    return shamir::reconstruct<fp61, 2, 3>(held);
}

/// @brief Reconstruct from all three shares (any two suffice; this checks consistency).
/// @param a party 1 share
/// @param b party 2 share
/// @param c party 3 share
/// @return the secret
/// @throws std::invalid_argument if the party indices are wrong
/// @throws std::runtime_error if the three shares are inconsistent
/// \complexity O(1). Two field inverses and a handful of multiplies. The shares are already in hand; this function does not exchange them.
HEDLEY_WARN_UNUSED_RESULT
inline fp61 reconstruct(share a, share b, share c)
{
    const fp61 from_ab = reconstruct(a, b);
    const fp61 from_ac = reconstruct(a, c);
    if (from_ab != from_ac)
        throw std::runtime_error("shamir3: inconsistent shares");
    return from_ab;
}

/// @brief Scale a share by its party index: `value · party`.
/// @param s the share
/// @return `s.value * s.party`
HEDLEY_NO_THROW
HEDLEY_CONST
HEDLEY_ALWAYS_INLINE
fp61 party_scale(share s) noexcept
{
    return s.value * fp61{static_cast<std::uint64_t>(s.party)};
}

/// @brief Prefactor `s_i · i^{-1}` used when planting Shamir shares into VDPF+.
/// @param s the share
/// @return `s.value * inv(party)`
HEDLEY_WARN_UNUSED_RESULT
inline fp61 unscale(share s)
{
    return s.value * inv(fp61{static_cast<std::uint64_t>(s.party)});
}

/// @brief Add two shares of the same party.
/// @param a left share
/// @param b right share
/// @return the sum
/// @throws std::invalid_argument if the parties differ
HEDLEY_WARN_UNUSED_RESULT
inline share add(share a, share b)
{
    if (a.party != b.party)
        throw std::invalid_argument("shamir3: add different parties");
    return share{a.party, a.value + b.value};
}

/// @brief Typed share for runtime party `s.party` in `{1, 2, 3}`.
/// @throws std::invalid_argument if `s.party` is outside `1..3`
template <std::size_t Party>
HEDLEY_WARN_UNUSED_RESULT
inline shamir_share<fp61, Party> typed_share(share s)
{
    if (s.party != static_cast<int>(Party) + 1)
        throw std::invalid_argument("shamir3: typed party mismatch");
    return shamir_share<fp61, Party>::from_raw(s.value);
}

/// @brief Runtime share for a typed party `Party` (point `Party + 1`).
template <std::size_t Party>
HEDLEY_NO_THROW
HEDLEY_CONST
inline share runtime_share(const shamir_share<fp61, Party> & s) noexcept
{
    return share{static_cast<int>(Party) + 1, s.raw()};
}

}  // namespace shamir3
}  // namespace dpf

#endif  // LIBDPF_INCLUDE_DPF_SHAMIR3_HPP__