myl7/fss 2.0.0
Function secret sharing (FSS) primitives including distributed point/comparison function (DPF/DCF)
Loading...
Searching...
No Matches
fss::Vdpf< in_bits, Group, Prg, XorHash, Hash, In > Class Template Reference

2-party VDPF scheme. More...

Classes

struct  Cw
 Correction word. More...

Public Types

using Input = In
 The caller-facing input-domain type.

Public Member Functions

 Vdpf (Prg prg, XorHash xor_hash, Hash hash)
 Construct a scheme with configured backends.
int Gen (cuda::std::span< int4 > cws, In &tr, cuda::std::span< int4, 4 > cs, cuda::std::span< const int4, 2 > s0s, In a, int4 b_buf, size_t stride=1)
 Generate correction words in a caller-strided layout and packed control bits.
cuda::std::array< int4, 4 > Eval (bool b, int4 s0, cuda::std::span< const int4 > cws, In tr, cuda::std::span< const int4, 4 > cs, In x, int4 &y, size_t stride=1)
 Evaluate one input from separate correction components.
void Prove (cuda::std::span< const cuda::std::array< int4, 4 > > pi_tildes, cuda::std::span< const int4, 4 > cs, cuda::std::span< int4, 4 > pi)
 Proof accumulation method.
void EvalAll (bool b, int4 s0, cuda::std::span< const int4 > cws, In tr, cuda::std::span< const int4, 4 > cs, cuda::std::span< int4 > ys, cuda::std::span< int4, 4 > pi, int par_depth=0, size_t stride=1)
 Evaluate the full domain and produce a chain proof from split correction words.
void EvalRange (bool b, In first, In last, int4 s0, cuda::std::span< const int4 > cws, In tr, cuda::std::span< const int4, 4 > cs, cuda::std::span< int4 > ys, cuda::std::span< int4, 4 > pi, int par_depth=0, size_t stride=1)
 Evaluate the inclusive range [first, last] and produce a chain proof from split correction words.
void ProveMerkle (cuda::std::span< const cuda::std::array< int4, 4 > > pi_tildes, cuda::std::span< const int4, 4 > cs, cuda::std::span< int4, 4 > pi, int par_depth=0)
 Proof accumulation method (Merkle fold).
void BatchEval (bool b, int4 s0, cuda::std::span< const int4 > cws, In tr, cuda::std::span< const int4, 4 > cs, cuda::std::span< const In > xs, cuda::std::span< int4 > ys, cuda::std::span< int4, 4 > pi, size_t stride=1)
 Evaluate an arbitrary ordered query sequence and produce a chain proof from split correction words.
void BatchEvalMerkle (bool b, int4 s0, cuda::std::span< const int4 > cws, In tr, cuda::std::span< const int4, 4 > cs, cuda::std::span< const In > xs, cuda::std::span< int4 > ys, cuda::std::span< int4, 4 > pi, size_t stride=1)
 Evaluate an arbitrary ordered query sequence and produce a Merkle proof from split correction words.
void EvalAllMerkle (bool b, int4 s0, cuda::std::span< const int4 > cws, In tr, cuda::std::span< const int4, 4 > cs, cuda::std::span< int4 > ys, cuda::std::span< int4, 4 > pi, int par_depth=0, size_t stride=1)
 Full-domain evaluation with the Merkle-fold proof from split correction words.
template<int frontier_depth = 16, int threads_per_block = 256>
requires (in_bits < sizeof(size_t) * 8)
cudaError_t EvalAllMerkleGpu (bool b, int4 s0, cuda::std::span< const int4 > cws, In tr, cuda::std::span< const int4, 4 > cs, cuda::std::span< int4 > ys, cuda::std::span< int4, 4 > pi, cudaStream_t stream=0, size_t stride=1) const
 Launch full-domain CUDA evaluation with the canonical Merkle-fold proof from split device arrays.
void EvalRangeMerkle (bool b, In first, In last, int4 s0, cuda::std::span< const int4 > cws, In tr, cuda::std::span< const int4, 4 > cs, cuda::std::span< int4 > ys, cuda::std::span< int4, 4 > pi, int par_depth=0, size_t stride=1)
 Evaluate [first, last] and apply ProveMerkle to its ordered corrected hashes, from split correction words.
template<int frontier_depth = 16, int threads_per_block = 256>
requires (ValidForInputBits<In, in_bits> && Groupable<Group> && Prgable<Prg, 2> && XorHashable<XorHash> && Hashable<Hash>)
cudaError_t EvalRangeMerkleGpu (bool b, In first, In last, int4 s0, cuda::std::span< const int4 > cws, In tr, cuda::std::span< const int4, 4 > cs, cuda::std::span< int4 > ys, cuda::std::span< int4, 4 > pi, cudaStream_t stream=0, size_t stride=1) const
 Launch range evaluation and the canonical ordered-sequence Merkle fold from split device arrays.
template<int threads_per_block = 256>
requires (ValidForInputBits<In, in_bits> && Groupable<Group> && Prgable<Prg, 2> && XorHashable<XorHash> && Hashable<Hash>)
cudaError_t BatchEvalMerkleGpu (bool b, int4 s0, cuda::std::span< const int4 > cws, In tr, cuda::std::span< const int4, 4 > cs, cuda::std::span< const In > xs, cuda::std::span< int4 > ys, cuda::std::span< int4, 4 > pi, cudaStream_t stream=0, size_t stride=1) const
 Launch batch evaluation of an arbitrary ordered query sequence with the Merkle-fold proof, from split device arrays.

Static Public Member Functions

static bool Verify (cuda::std::span< const int4, 4 > pi0, cuda::std::span< const int4, 4 > pi1)
 Verification method.

Static Public Attributes

static constexpr int kCwCount = in_bits + 1
 Seed-component count Gen() writes at stride 1: in_bits layers plus the terminal.

Detailed Description

template<int in_bits, typename Group, typename Prg, typename XorHash, typename Hash, typename In = uint>
requires (ValidForInputBits<In, in_bits> && Groupable<Group> && Prgable<Prg, 2> && XorHashable<XorHash> && Hashable<Hash>)
class fss::Vdpf< in_bits, Group, Prg, XorHash, Hash, In >

2-party VDPF scheme.

Gen() and scalar Eval() support host and device calls when their backends do. CPU full-domain, range, and proof accumulation run on the host. The Gpu methods launch asynchronous device evaluation. Prove(), EvalAll(), and EvalRange() use chain accumulation. ProveMerkle(), EvalAllMerkle(), and EvalRangeMerkle() use a Merkle fold over a fixed ordered sequence. Both parties must use the same accumulator, key configuration, and ordered inputs. Chain and Merkle proofs have the same representation but different values. XorHash receives (packed coordinate, clamped leaf seed), in that order. Every coordinate bit is message data. Bit 0 of the seed's fourth word is reserved and passed as zero; the built-in backends use it for digest tags. Verification guarantees require the assumptions and accumulator-specific proof conditions in doc/vdpf_merkle_fold_security.md.

Template Parameters
in_bitsInput domain bit size.
GroupType for the output domain. See Groupable.
PrgSee Prgable.
XorHashSee XorHashable. Paper's \(H\): maps \((x, s)\) to \(4\lambda\) bits.
HashSee Hashable. Paper's \(H'\): maps \(4\lambda\) bits to \(2\lambda\) bits.
InType for the input domain. From uint8_t to __uint128_t.

Constructor & Destructor Documentation

◆ Vdpf()

template<int in_bits, typename Group, typename Prg, typename XorHash, typename Hash, typename In>
requires (ValidForInputBits<In, in_bits> && Groupable<Group> && Prgable<Prg, 2> && XorHashable<XorHash> && Hashable<Hash>)
fss::Vdpf< in_bits, Group, Prg, XorHash, Hash, In >::Vdpf ( Prg prg,
XorHash xor_hash,
Hash hash )
inlineexplicit

Construct a scheme with configured backends.

Parameters
prgConfigured Prg backend.
xor_hashConfigured XorHash backend.
hashConfigured Hash backend.

Member Function Documentation

◆ BatchEval()

template<int in_bits, typename Group, typename Prg, typename XorHash, typename Hash, typename In>
requires (ValidForInputBits<In, in_bits> && Groupable<Group> && Prgable<Prg, 2> && XorHashable<XorHash> && Hashable<Hash>)
void fss::Vdpf< in_bits, Group, Prg, XorHash, Hash, In >::BatchEval ( bool b,
int4 s0,
cuda::std::span< const int4 > cws,
In tr,
cuda::std::span< const int4, 4 > cs,
cuda::std::span< const In > xs,
cuda::std::span< int4 > ys,
cuda::std::span< int4, 4 > pi,
size_t stride = 1 )
inline

Evaluate an arbitrary ordered query sequence and produce a chain proof from split correction words.

One call over xs: Eval() for every input in the order given, then Prove() over the corrected per-point hashes in the same order. The result is bit-identical to calling Eval() per input and Prove() over the results on the same ordered xs. The order of xs is part of the contract: both parties must supply the same sequence, including duplicates.

The cost is not EvalAll()'s. A query sequence that is not a tree-structured set cannot prune, so every input pays its own root-to-leaf walk, exactly as Eval() does. This call does not inherit EvalAll()'s property of visiting each internal node once.

Internally buffers the corrected per-point hashes, 64 B per input.

xs may be any nonempty sequence of inputs in [0, 2^in_bits), including sparse, unsorted, or repeated inputs. Both parties must use the same sequence, including its order and length, and the same proof accumulator and hash configuration. Both servers must obtain the same xs by a path the client cannot split. Any verification guarantee is restricted to the evaluated input values and requires the scheme's security assumptions. See doc/vdpf_merkle_fold_security.md for assumptions and instantiation limits. Layer i is read from cws[i*stride] and the terminal from cws[in_bits*stride]. Packed bit i of tr is the right-control correction at layer i, and the left-control correction is the LSB of the layer's cws entry, exactly as the component form of Gen() writes them. Bits of tr at and above in_bits are ignored.

Precondition
xs is nonempty and xs[i] < 2^in_bits for every i.
The four cs blocks are not jointly all zero.
Parameters
bParty index, false for party 0 and true for party 1.
s0This party's initial seed.
cwsCorrection words, layer i at index i*stride and the terminal at index in_bits*stride.
trPacked right-control bits, bit i for layer i.
csShared correction seed returned by Gen().
xsOrdered input sequence; it may be sparse, unsorted, and contain duplicates.
ysOutput shares in xs order, with at least xs.size() entries.
piBorrowed output storage for four chain-proof blocks.
stridePositive element stride between correction-word entries.
Exceptions
std::invalid_argumentif stride is zero or too large, cws is shorter than in_bits*stride+1, xs is empty, or ys is too short.

◆ BatchEvalMerkle()

template<int in_bits, typename Group, typename Prg, typename XorHash, typename Hash, typename In>
requires (ValidForInputBits<In, in_bits> && Groupable<Group> && Prgable<Prg, 2> && XorHashable<XorHash> && Hashable<Hash>)
void fss::Vdpf< in_bits, Group, Prg, XorHash, Hash, In >::BatchEvalMerkle ( bool b,
int4 s0,
cuda::std::span< const int4 > cws,
In tr,
cuda::std::span< const int4, 4 > cs,
cuda::std::span< const In > xs,
cuda::std::span< int4 > ys,
cuda::std::span< int4, 4 > pi,
size_t stride = 1 )
inline

Evaluate an arbitrary ordered query sequence and produce a Merkle proof from split correction words.

Same evaluation and ordering contract as BatchEval(), with the proof coming from ProveMerkle() over the corrected per-point hashes in xs order: bit-identical to calling Eval() per input and ProveMerkle() over the results on the same ordered xs. Both parties must supply the same sequence and agree on the Merkle accumulator.

The cost is not EvalAll()'s. Every input pays its own root-to-leaf walk, as Eval() does; the fold over the sequence adds no tree-structured savings. This call does not inherit EvalAll()'s property of visiting each internal node once.

Internally buffers the corrected per-point hashes, 64 B per input.

xs may be any nonempty sequence of inputs in [0, 2^in_bits), including sparse, unsorted, or repeated inputs. Both parties must use the same sequence, including its order and length, and the same proof accumulator and hash configuration. Both servers must obtain the same xs by a path the client cannot split. Any verification guarantee is restricted to the evaluated input values and requires the scheme's security assumptions. See doc/vdpf_merkle_fold_security.md for assumptions and instantiation limits. Each occurrence of a repeated input contributes its own leaf. Layer i is read from cws[i*stride] and the terminal from cws[in_bits*stride]. Packed bit i of tr is the right-control correction at layer i, and the left-control correction is the LSB of the layer's cws entry, exactly as the component form of Gen() writes them. Bits of tr at and above in_bits are ignored.

Precondition
xs is nonempty and xs[i] < 2^in_bits for every i.
The four cs blocks are not jointly all zero.
Parameters
bParty index, false for party 0 and true for party 1.
s0This party's initial seed.
cwsCorrection words, layer i at index i*stride and the terminal at index in_bits*stride.
trPacked right-control bits, bit i for layer i.
csShared correction seed returned by Gen().
xsOrdered input sequence; it may be sparse, unsorted, and contain duplicates.
ysOutput shares in xs order, with at least xs.size() entries.
piBorrowed output storage for four Merkle-proof blocks.
stridePositive element stride between correction-word entries.
Exceptions
std::invalid_argumentif stride is zero or too large, cws is shorter than in_bits*stride+1, xs is empty, or ys is too short.

◆ BatchEvalMerkleGpu()

template<int in_bits, typename Group, typename Prg, typename XorHash, typename Hash, typename In>
requires (ValidForInputBits<In, in_bits> && Groupable<Group> && Prgable<Prg, 2> && XorHashable<XorHash> && Hashable<Hash>)
template<int threads_per_block>
requires (ValidForInputBits<In, in_bits> && Groupable<Group> && Prgable<Prg, 2> && XorHashable<XorHash> && Hashable<Hash>)
cudaError_t fss::Vdpf< in_bits, Group, Prg, XorHash, Hash, In >::BatchEvalMerkleGpu ( bool b,
int4 s0,
cuda::std::span< const int4 > cws,
In tr,
cuda::std::span< const int4, 4 > cs,
cuda::std::span< const In > xs,
cuda::std::span< int4 > ys,
cuda::std::span< int4, 4 > pi,
cudaStream_t stream = 0,
size_t stride = 1 ) const
inline

Launch batch evaluation of an arbitrary ordered query sequence with the Merkle-fold proof, from split device arrays.

The outputs and proof match host BatchEvalMerkle() bit for bit on the same ordered xs, for any query sequence: sparse, unsorted, or duplicated. The order of xs is part of the contract; both parties must pass the same sequence and agree on the Merkle accumulator. Chain accumulation over a query sequence stays on the host, in BatchEval().

The cost is not EvalAll()'s: a sparse query set cannot prune the tree, so every input pays its own root-to-leaf walk and no frontier is shared. That is why this entry takes no frontier_depth. Group, Prg, XorHash, and Hash must support device execution.

Takes the raw key components s0, cws, tr, and cs as Gen() returned them. Layer i is read from cws[i*stride] and the terminal from cws[in_bits*stride]. Packed bit i of tr is the right-control correction at layer i, and the left-control correction is the LSB of the layer's cws entry, exactly as the component form of Gen() writes them. Bits of tr at and above in_bits are ignored. Uses caller-owned device arrays and backend resources. Temporary node buffers with 32*(M + ceil(M/2)) scratch bytes for M inputs are allocated and released on stream. No upload, deep copy, or synchronization occurs. Backend resources must support concurrent device calls and remain valid until the stream completes. The host instance supplies backend values.

xs may be any nonempty sequence of inputs in [0, 2^in_bits), including sparse, unsorted, or repeated inputs. Both parties must use the same sequence, including its order and length, and the same proof accumulator and hash configuration. Both servers must obtain the same xs by a path the client cannot split. Any verification guarantee is restricted to the evaluated input values and requires the scheme's security assumptions. See doc/vdpf_merkle_fold_security.md for assumptions and instantiation limits. Each occurrence of a repeated input contributes its own leaf.

Template Parameters
threads_per_blockPower-of-two block size in [1, 1024]. Defaults to 256.
Parameters
bParty index, false for party 0 and true for party 1.
s0This party's initial seed, passed by value to the kernel.
cwsDevice correction words, layer i at index i*stride and the terminal at index in_bits*stride.
trPacked right-control bits, bit i for layer i.
csDevice storage containing the four shared correction-seed blocks.
xsDevice storage of the ordered input sequence; it may be sparse, unsorted, and contain duplicates.
ysDevice output storage with at least xs.size() int4 blocks.
piDevice output storage for the four-block Merkle proof.
streamStream on the device owning the referenced resources.
stridePositive element stride between correction-word entries.
Precondition
xs is nonempty and xs[i] < 2^in_bits for every i.
stride > 0 and cws holds at least in_bits*stride+1 elements.
The four cs blocks are not jointly all zero.
Returns
First immediate CUDA error. Invalid buffers, strides, or empty xs return cudaErrorInvalidValue. An oversized grid returns cudaErrorInvalidConfiguration. Execution errors are observed by the caller when synchronizing stream.

◆ Eval()

template<int in_bits, typename Group, typename Prg, typename XorHash, typename Hash, typename In>
requires (ValidForInputBits<In, in_bits> && Groupable<Group> && Prgable<Prg, 2> && XorHashable<XorHash> && Hashable<Hash>)
cuda::std::array< int4, 4 > fss::Vdpf< in_bits, Group, Prg, XorHash, Hash, In >::Eval ( bool b,
int4 s0,
cuda::std::span< const int4 > cws,
In tr,
cuda::std::span< const int4, 4 > cs,
In x,
int4 & y,
size_t stride = 1 )
inline

Evaluate one input from separate correction components.

Root-order packed bit i is the right-control correction at layer i. The correction s LSB is the left-control correction. Layer i is read from cws[i*stride] and the terminal from cws[in_bits*stride], which Gen() writes as a plain int4 with its LSB zero. Packed bits at and above in_bits are ignored.

Parameters
bParty index, false for party 0 and true for party 1.
s0This party's initial seed.
cwsCorrection words, layer i at index i*stride and the terminal at index in_bits*stride.
trPacked right-control bits, bit i for layer i.
csShared correction seed returned by Gen().
xInput in the scheme's domain.
yOutput share for this input.
stridePositive stride between correction entries.
Returns
Corrected per-point hash for Prove() or ProveMerkle().
Precondition
x is in [0, 2^in_bits).
stride > 0.
With M = numeric_limits<size_t>::max()/sizeof(int4), stride <= (M-1)/in_bits and cws has at least in_bits*stride+1 elements.
cws[in_bits*stride].w & 1 == 0.
The four cs blocks are not jointly all zero.
All accessed storage is accessible from the calling execution space.
A stride, capacity, or terminal violation aborts with a diagnostic in Debug builds on both the host and the device, and is undefined behavior in Release builds.

◆ EvalAll()

template<int in_bits, typename Group, typename Prg, typename XorHash, typename Hash, typename In>
requires (ValidForInputBits<In, in_bits> && Groupable<Group> && Prgable<Prg, 2> && XorHashable<XorHash> && Hashable<Hash>)
void fss::Vdpf< in_bits, Group, Prg, XorHash, Hash, In >::EvalAll ( bool b,
int4 s0,
cuda::std::span< const int4 > cws,
In tr,
cuda::std::span< const int4, 4 > cs,
cuda::std::span< int4 > ys,
cuda::std::span< int4, 4 > pi,
int par_depth = 0,
size_t stride = 1 )
inline

Evaluate the full domain and produce a chain proof from split correction words.

Layer i is read from cws[i*stride] and the terminal from cws[in_bits*stride]. Packed bit i of tr is the right-control correction at layer i, and the left-control correction is the LSB of the layer's cws entry, exactly as the component form of Gen() writes them. Bits of tr at and above in_bits are ignored.

Parameters
bParty index, false for party 0 and true for party 1.
s0This party's initial seed.
cwsCorrection words, layer i at index i*stride and the terminal at index in_bits*stride.
trPacked right-control bits, bit i for layer i.
csShared correction seed returned by Gen().
ysOutput shares in input order, with at least 2^in_bits entries.
piBorrowed output storage for four chain-proof blocks.
par_depthNonnegative OpenMP split depth for this call. Zero runs sequentially. Positive depths require backends that support concurrent calls.
stridePositive element stride between correction-word entries.
Precondition
The full-domain output count and byte size fit size_t.
The four cs blocks are not jointly all zero.
cws[in_bits*stride].w & 1 == 0. A violation aborts with a diagnostic in Debug builds before any traversal and is undefined behavior in Release builds.
Exceptions
std::invalid_argumentif stride is zero or too large, cws is shorter than in_bits*stride+1, or ys is too short.

◆ EvalAllMerkle()

template<int in_bits, typename Group, typename Prg, typename XorHash, typename Hash, typename In>
requires (ValidForInputBits<In, in_bits> && Groupable<Group> && Prgable<Prg, 2> && XorHashable<XorHash> && Hashable<Hash>)
void fss::Vdpf< in_bits, Group, Prg, XorHash, Hash, In >::EvalAllMerkle ( bool b,
int4 s0,
cuda::std::span< const int4 > cws,
In tr,
cuda::std::span< const int4, 4 > cs,
cuda::std::span< int4 > ys,
cuda::std::span< int4, 4 > pi,
int par_depth = 0,
size_t stride = 1 )
inline

Full-domain evaluation with the Merkle-fold proof from split correction words.

Same output shares as EvalAll(); the proof comes from ProveMerkle() over the corrected per-point hashes. The conversion phase and every fold level are OpenMP parallel honoring par_depth, unlike EvalAll()'s sequential phase 2. See doc/vdpf_merkle_fold_security.md. Layer i is read from cws[i*stride] and the terminal from cws[in_bits*stride]. Packed bit i of tr is the right-control correction at layer i, and the left-control correction is the LSB of the layer's cws entry, exactly as the component form of Gen() writes them. Bits of tr at and above in_bits are ignored.

Parameters
bParty index. False for 0 and true for 1. \(i\).
s0This party's initial seed.
cwsCorrection words, layer i at index i*stride and the terminal at index in_bits*stride.
trPacked right-control bits, bit i for layer i.
csShared correction seed returned by Gen().
ysPre-allocated output array. Its size must be at least 2 ** in_bits.
piBorrowed output storage for four proof blocks.
par_depthNonnegative OpenMP split depth for this call. Zero runs sequentially. Positive depths require backends that support concurrent calls.
stridePositive element stride between correction-word entries.
Precondition
The full-domain output count, output bytes, and per-point proof scratch bytes fit size_t.
The four cs blocks are not jointly all zero.
cws[in_bits*stride].w & 1 == 0. A violation aborts with a diagnostic in Debug builds before any traversal and is undefined behavior in Release builds.
Exceptions
std::invalid_argumentif stride is zero or too large, cws is shorter than in_bits*stride+1, ys is too short, or the proof scratch does not fit size_t.

◆ EvalAllMerkleGpu()

template<int in_bits, typename Group, typename Prg, typename XorHash, typename Hash, typename In>
requires (in_bits < sizeof(size_t) * 8)
template<int frontier_depth, int threads_per_block>
requires (in_bits < sizeof(size_t) * 8)
cudaError_t fss::Vdpf< in_bits, Group, Prg, XorHash, Hash, In >::EvalAllMerkleGpu ( bool b,
int4 s0,
cuda::std::span< const int4 > cws,
In tr,
cuda::std::span< const int4, 4 > cs,
cuda::std::span< int4 > ys,
cuda::std::span< int4, 4 > pi,
cudaStream_t stream = 0,
size_t stride = 1 ) const
inline

Launch full-domain CUDA evaluation with the canonical Merkle-fold proof from split device arrays.

Uses this host instance's backend values as kernel arguments. The caller prepares device-accessible key/output buffers and every resource referenced by the backends. Temporary block roots are allocated and released in the supplied stream. No backend upload, deep copy, or synchronization is performed. Group, Prg, XorHash, and Hash must support device execution. Layer i is read from cws[i*stride] and the terminal from cws[in_bits*stride]. Packed bit i of tr is the right-control correction at layer i, and the left-control correction is the LSB of the layer's cws entry, exactly as the component form of Gen() writes them. Bits of tr at and above in_bits are ignored.

Template Parameters
frontier_depthFrontier depth, capped at in_bits. Defaults to 16.
threads_per_blockPower-of-two block size in [1, 1024], capped at the frontier width. Defaults to 256. The remaining tail has at most eight levels. The block-root depth is derived from these two values, and the number of block roots must not exceed the resolved threads per block.
Parameters
bParty index, false for party 0 and true for party 1.
s0This party's initial seed, passed by value to the kernel.
cwsDevice correction words, layer i at index i*stride and the terminal at index in_bits*stride.
trPacked right-control bits, bit i for layer i.
csDevice storage containing the four shared correction-seed blocks.
ysDevice output storage with at least 2^in_bits int4 blocks.
piDevice output storage for the four-block Merkle proof.
streamStream on the device owning the referenced resources.
stridePositive element stride between correction-word entries.
Precondition
stride > 0 and cws holds at least in_bits*stride+1 elements.
this is host-accessible. Buffers and backend resources remain valid until work completes and permit the kernel's concurrent backend calls.
The four cs blocks are not jointly all zero.
Returns
The first immediate CUDA allocation, launch, or release status. Invalid buffers, strides, or unaddressable output storage return cudaErrorInvalidValue. Execution is asynchronous; the caller observes execution errors when synchronizing.

◆ EvalRange()

template<int in_bits, typename Group, typename Prg, typename XorHash, typename Hash, typename In>
requires (ValidForInputBits<In, in_bits> && Groupable<Group> && Prgable<Prg, 2> && XorHashable<XorHash> && Hashable<Hash>)
void fss::Vdpf< in_bits, Group, Prg, XorHash, Hash, In >::EvalRange ( bool b,
In first,
In last,
int4 s0,
cuda::std::span< const int4 > cws,
In tr,
cuda::std::span< const int4, 4 > cs,
cuda::std::span< int4 > ys,
cuda::std::span< int4, 4 > pi,
int par_depth = 0,
size_t stride = 1 )
inline

Evaluate the inclusive range [first, last] and produce a chain proof from split correction words.

Under the VDPF security assumptions, successful verification guarantees at most one nonzero reconstructed output within this range, except with negligible probability. It makes no guarantee outside the range. Layer i is read from cws[i*stride] and the terminal from cws[in_bits*stride]. Packed bit i of tr is the right-control correction at layer i, and the left-control correction is the LSB of the layer's cws entry, exactly as the component form of Gen() writes them. Bits of tr at and above in_bits are ignored.

Parameters
bParty index, false for party 0 and true for party 1.
firstFirst input, included in evaluation.
lastLast input, included in evaluation.
s0This party's initial seed.
cwsCorrection words, layer i at index i*stride and the terminal at index in_bits*stride.
trPacked right-control bits, bit i for layer i.
csShared correction seed returned by Gen().
ysOutput shares in input order, with at least last - first + 1 entries.
piBorrowed output storage for four chain-proof blocks for this range.
par_depthNonnegative OpenMP split depth for this call. Zero runs sequentially. Positive depths require backends that support concurrent calls.
stridePositive element stride between correction-word entries.
Precondition
first <= last < 2^in_bits. The range output count and byte size fit size_t. A small range is supported even when the full input domain cannot be materialized in addressable storage.
The four cs blocks are not jointly all zero.
cws[in_bits*stride].w & 1 == 0. A violation aborts with a diagnostic in Debug builds before any traversal and is undefined behavior in Release builds.
Exceptions
std::invalid_argumentif first > last, last is outside the input domain, the interval does not fit size_t, stride is zero or too large, cws is shorter than in_bits*stride+1, or ys is too short.

◆ EvalRangeMerkle()

template<int in_bits, typename Group, typename Prg, typename XorHash, typename Hash, typename In>
requires (ValidForInputBits<In, in_bits> && Groupable<Group> && Prgable<Prg, 2> && XorHashable<XorHash> && Hashable<Hash>)
void fss::Vdpf< in_bits, Group, Prg, XorHash, Hash, In >::EvalRangeMerkle ( bool b,
In first,
In last,
int4 s0,
cuda::std::span< const int4 > cws,
In tr,
cuda::std::span< const int4, 4 > cs,
cuda::std::span< int4 > ys,
cuda::std::span< int4, 4 > pi,
int par_depth = 0,
size_t stride = 1 )
inline

Evaluate [first, last] and apply ProveMerkle to its ordered corrected hashes, from split correction words.

ys[j] is the share for first + j. Extra output capacity is unchanged. The proof tree covers this sequence, with odd nodes carried unchanged. Both parties must agree on the range, order, and accumulator externally. For M = last - first + 1, proof scratch payload is at most 96*M + 32*ceil(M/2) bytes, plus 16*M output bytes and allocator overhead. Layer i is read from cws[i*stride] and the terminal from cws[in_bits*stride]. Packed bit i of tr is the right-control correction at layer i, and the left-control correction is the LSB of the layer's cws entry, exactly as the component form of Gen() writes them. Bits of tr at and above in_bits are ignored.

Parameters
bParty index, false for party 0 and true for party 1.
firstFirst input, included in evaluation.
lastLast input, included in evaluation.
s0This party's initial seed.
cwsCorrection words, layer i at index i*stride and the terminal at index in_bits*stride.
trPacked right-control bits, bit i for layer i.
csShared correction seed returned by Gen().
ysOutput shares in input order, with at least last - first + 1 entries.
piBorrowed output storage for four Merkle-proof blocks for this range.
Precondition
first <= last < 2^in_bits. Output and proof scratch bytes fit size_t.
The four cs blocks are not jointly all zero.
cws[in_bits*stride].w & 1 == 0. A violation aborts with a diagnostic in Debug builds before any traversal and is undefined behavior in Release builds.
Parameters
par_depthNonnegative OpenMP split depth. Zero runs sequentially. Positive depths require backends that support concurrent calls.
stridePositive element stride between correction-word entries.
Exceptions
std::invalid_argumentif first > last, last is outside the input domain, the output or proof scratch does not fit size_t, stride is zero or too large, cws is shorter than in_bits*stride+1, or ys is too short.

◆ EvalRangeMerkleGpu()

template<int in_bits, typename Group, typename Prg, typename XorHash, typename Hash, typename In>
requires (ValidForInputBits<In, in_bits> && Groupable<Group> && Prgable<Prg, 2> && XorHashable<XorHash> && Hashable<Hash>)
template<int frontier_depth, int threads_per_block>
requires (ValidForInputBits<In, in_bits> && Groupable<Group> && Prgable<Prg, 2> && XorHashable<XorHash> && Hashable<Hash>)
cudaError_t fss::Vdpf< in_bits, Group, Prg, XorHash, Hash, In >::EvalRangeMerkleGpu ( bool b,
In first,
In last,
int4 s0,
cuda::std::span< const int4 > cws,
In tr,
cuda::std::span< const int4, 4 > cs,
cuda::std::span< int4 > ys,
cuda::std::span< int4, 4 > pi,
cudaStream_t stream = 0,
size_t stride = 1 ) const
inline

Launch range evaluation and the canonical ordered-sequence Merkle fold from split device arrays.

Uses caller-owned device arrays and backend resources. Internal scratch is allocated and released on stream. No upload or synchronization occurs. Backend resources must support concurrent device calls and remain valid until the stream completes. The host instance supplies backend values. frontier_depth is relative to each aligned evaluation subtree, capped at its depth. Deep subtrees are split privately to leave at most eight tail levels and a block-root depth of at most 30. threads_per_block is a power of two in [1, 1024], capped at each subtree frontier width. Evaluation fuses share conversion and corrected leaf hashing. The ordered fold uses two buffers with 32*(M + ceil(M/2)) scratch bytes for M inputs, plus 16*M output bytes. These payload sizes exclude allocator overhead. The leaf kernel keeps a bounded depth-first pending-sibling stack of at most eight int4 states per thread and threads_per_block int4 shared frontier states per block. Layer i is read from cws[i*stride] and the terminal from cws[in_bits*stride]. Packed bit i of tr is the right-control correction at layer i, and the left-control correction is the LSB of the layer's cws entry, exactly as the component form of Gen() writes them. Bits of tr at and above in_bits are ignored. The proof uses actual inputs in increasing order and carries odd nodes. Both parties must agree on the range, order, and Merkle mode externally.

Parameters
bParty index, false for party 0 and true for party 1.
firstFirst input in the interval.
lastLast input in the interval, included in the output.
s0This party's initial seed, passed by value to the kernel.
cwsDevice correction words, layer i at index i*stride and the terminal at index in_bits*stride.
trPacked right-control bits, bit i for layer i.
csDevice storage containing the four shared correction-seed blocks.
ysDevice output storage. Entry x-first receives this party's share at x.
piDevice output storage for the four-block Merkle proof.
streamStream on the device owning the referenced resources.
stridePositive element stride between correction-word entries.
Precondition
stride > 0 and cws holds at least in_bits*stride+1 elements.
The four cs blocks are not jointly all zero.
Returns
First immediate CUDA error. Invalid endpoints, buffers, strides, or byte counts return cudaErrorInvalidValue. An oversized grid returns cudaErrorInvalidConfiguration. Execution errors are observed by the caller when synchronizing stream.

◆ Gen()

template<int in_bits, typename Group, typename Prg, typename XorHash, typename Hash, typename In>
requires (ValidForInputBits<In, in_bits> && Groupable<Group> && Prgable<Prg, 2> && XorHashable<XorHash> && Hashable<Hash>)
int fss::Vdpf< in_bits, Group, Prg, XorHash, Hash, In >::Gen ( cuda::std::span< int4 > cws,
In & tr,
cuda::std::span< int4, 4 > cs,
cuda::std::span< const int4, 2 > s0s,
In a,
int4 b_buf,
size_t stride = 1 )
inline

Generate correction words in a caller-strided layout and packed control bits.

Layer i is stored at cws[i*stride] and the terminal at cws[in_bits*stride]. tr receives root-order packed right-control bits: bit 0 is the root layer, bit i belongs to layer i, and bits at or above in_bits are zero. The layer LSB keeps the left-control correction. The terminal is stored unchanged as a plain int4. The default stride of 1 stores the correction words contiguously.

Retrying a failed attempt
On return 1, draw two fresh independent uniformly random seed blocks from a cryptographically secure random generator, replace both s0s entries, and call Gen again with the same a and b_buf. Incrementing seed words is not resampling. The caller chooses the attempt limit and handles exhaustion. Reuse of the output buffers is allowed, but discard all cws, tr, and cs values from a failed attempt. Only outputs from a successful call form a key.
Parameters
cwsOutput storage; its capacity includes in_bits*stride+1 elements.
trOutput packed right-control bits, with unused bits zero.
csCorrection seed output ( \(4\lambda\) bits).
s0sTwo independent uniformly random initial seed blocks from a cryptographically secure random generator. Gen clears their control bits internally without modifying this input storage.
aSecret point in [0, 2^in_bits).
b_bufPayload, clamped and converted to the group element.
stridePositive element stride between correction-word entries.
Returns
0 on success, 1 if cs is all zeros or \(t_0 = t_1\) at the end (caller should resample seeds and retry).
Precondition
a is in [0, 2^in_bits).
stride > 0.
With M = numeric_limits<size_t>::max()/sizeof(int4), stride <= (M-1)/in_bits and cws has at least in_bits*stride+1 elements.
The input seeds are unchanged.
Inputs and outputs do not overlap.
All accessed storage is accessible from the calling execution space.
A stride or capacity violation aborts with a diagnostic in Debug builds on both the host and the device, and is undefined behavior in Release builds.
Postcondition
Only the described prefix is written, and storage beyond it is untouched.
On success, the terminal at index in_bits*stride has its LSB zero. Correction-word, control-bit, and cs outputs are unspecified on failure.

◆ Prove()

template<int in_bits, typename Group, typename Prg, typename XorHash, typename Hash, typename In>
requires (ValidForInputBits<In, in_bits> && Groupable<Group> && Prgable<Prg, 2> && XorHashable<XorHash> && Hashable<Hash>)
void fss::Vdpf< in_bits, Group, Prg, XorHash, Hash, In >::Prove ( cuda::std::span< const cuda::std::array< int4, 4 > > pi_tildes,
cuda::std::span< const int4, 4 > cs,
cuda::std::span< int4, 4 > pi )
inline

Proof accumulation method.

Accumulates corrected per-point hashes (from Eval()) into a chain proof. Both parties must supply the same ordered input sequence.

Precondition
pi_tildes is nonempty.
The four cs blocks are not jointly all zero.
Parameters
pi_tildesCorrected per-point hashes returned by Eval().
csReturned by Gen().
piBorrowed output storage for four proof blocks.

◆ ProveMerkle()

template<int in_bits, typename Group, typename Prg, typename XorHash, typename Hash, typename In>
requires (ValidForInputBits<In, in_bits> && Groupable<Group> && Prgable<Prg, 2> && XorHashable<XorHash> && Hashable<Hash>)
void fss::Vdpf< in_bits, Group, Prg, XorHash, Hash, In >::ProveMerkle ( cuda::std::span< const cuda::std::array< int4, 4 > > pi_tildes,
cuda::std::span< const int4, 4 > cs,
cuda::std::span< int4, 4 > pi,
int par_depth = 0 )
inline

Proof accumulation method (Merkle fold).

Parallel alternative to Prove() over a fixed ordered sequence: hashes corrected per-point hashes into the leaves of a binary Merkle tree over the given sequence and folds adjacent nodes with the same hash level by level (an odd trailing node carries to the next level unchanged). The proof is {root, cs[2], cs[3]}, the same 64B shape as the chain's, so Verify() is shared. Every level is an OpenMP parallel batch honoring par_depth, so a par_depth of 0 makes the fold sequential. See doc/vdpf_merkle_fold_security.md.

Precondition
pi_tildes is nonempty.
The four cs blocks are not jointly all zero.
Parameters
pi_tildesCorrected per-point hashes returned by Eval().
csReturned by Gen().
piBorrowed output storage for four proof blocks.
par_depthNonnegative OpenMP split depth for this call. Zero runs sequentially. Positive depths require backends that support concurrent calls.
Exceptions
std::invalid_argumentif pi_tildes is empty.

◆ Verify()

template<int in_bits, typename Group, typename Prg, typename XorHash, typename Hash, typename In>
requires (ValidForInputBits<In, in_bits> && Groupable<Group> && Prgable<Prg, 2> && XorHashable<XorHash> && Hashable<Hash>)
bool fss::Vdpf< in_bits, Group, Prg, XorHash, Hash, In >::Verify ( cuda::std::span< const int4, 4 > pi0,
cuda::std::span< const int4, 4 > pi1 )
inlinestatic

Verification method.

Parameters
pi0Party 0 proof.
pi1Party 1 proof from the same accumulator and ordered inputs.
Returns
True if proofs match (Accept), false otherwise (Reject).

The documentation for this class was generated from the following file: