2-party DPF scheme using the Half-Tree construction. More...

Classes
struct	Cw
	Correction word. More...

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

Public Member Functions
	HalfTreeDpf (Hash hash, int4 instance_seed)
	Configure the CCR hash and public instance seed S.
void	Gen (cuda::std::span< int4 > cws, In &tr, cuda::std::span< const int4, 2 > s0s, In a, int4 b_buf, size_t stride=1)
	Generate split Cws from caller-owned initial seeds.
int4	Eval (bool b, int4 s0, cuda::std::span< const int4 > cws, In tr, In x, size_t stride=1)
	Evaluate one point from split Cws.
void	EvalAll (bool b, int4 s0, cuda::std::span< const int4 > cws, In tr, int4 ys[], int par_depth=0, size_t stride=1)
	Evaluate the full domain from split Cws.
void	EvalRange (bool b, In first, In last, int4 s0, cuda::std::span< const int4 > cws, In tr, cuda::std::span< int4 > ys, int par_depth=0, size_t stride=1)
	Evaluate the closed input interval [first, last] from split Cws.
template<int frontier_depth = 16, int threads_per_block = 256> requires (ValidForInputBits<In, in_bits> && Groupable<Group> && CcrHashable<Hash>)
cudaError_t	EvalRangeGpu (bool b, In first, In last, int4 s0, cuda::std::span< const int4 > cws, In tr, cuda::std::span< int4 > ys, cudaStream_t stream=0, size_t stride=1) const
	Evaluate the closed interval [first, last] on the given CUDA stream from split device arrays.
template<int frontier_depth = 16, int threads_per_block = 256> requires (in_bits < sizeof(size_t) * 8)
cudaError_t	EvalAllGpu (bool b, int4 s0, cuda::std::span< const int4 > cws, In tr, cuda::std::span< int4 > ys, cudaStream_t stream=0, size_t stride=1) const
	Launch full-domain CUDA evaluation from split device arrays.
template<int frontier_depth = 16, int threads_per_block = 256> requires (in_bits < sizeof(size_t) * 8)
cudaError_t	EvalAllGpuBatch (bool b, cuda::std::span< const int4 > s0s, cuda::std::span< const int4 > cws, cuda::std::span< const In > tr, cuda::std::span< int4 > ys, cudaStream_t stream=0, size_t stride=0) const
	Launch full-domain CUDA evaluation for s0s.size() keys from split device arrays.

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

Detailed Description

template<int in_bits, typename Group, typename Hash, typename In = uint>
requires (ValidForInputBits<In, in_bits> && Groupable<Group> && CcrHashable<Hash>)
class fss::HalfTreeDpf< in_bits, Group, Hash, In >

2-party DPF scheme using the Half-Tree construction.

Template Parameters

in_bits	Input domain bit size.
Group	Type for the output domain. See Groupable.
Hash	Unary CCR hash backend. See CcrHashable.
In	Type for the input domain. From uint8_t to __uint128_t.

Gen() and scalar Eval() are callable from host and device when the backend supports the execution space and all accessed storage is accessible there. EvalAll() and EvalRange() are host operations. EvalAllGpu() and EvalAllGpuBatch() are host launch methods compiled with a CUDA compiler; they do not run on the device.

Constructor & Destructor Documentation

◆ HalfTreeDpf()

template<int in_bits, typename Group, typename Hash, typename In>
requires (ValidForInputBits<In, in_bits> && Groupable<Group> && CcrHashable<Hash>)

fss::HalfTreeDpf< in_bits, Group, Hash, In >::HalfTreeDpf	(	Hash	hash,
		int4	instance_seed )

inlineexplicit

Configure the CCR hash and public instance seed S.

Parameters

hash	Unary CCR hash backend used throughout generation and evaluation.
instance_seed	Uniformly sampled public seed S, fixed for this instance.

Member Function Documentation

◆ Eval()

template<int in_bits, typename Group, typename Hash, typename In>
requires (ValidForInputBits<In, in_bits> && Groupable<Group> && CcrHashable<Hash>)

int4 fss::HalfTreeDpf< in_bits, Group, Hash, In >::Eval	(	bool	b,
		int4	s0,
		cuda::std::span< const int4 >	cws,
		In	tr,
		In	x,
		size_t	stride = 1 )

inline

Evaluate one point from split Cws.

Layer l is read from cws[l*stride] and the terminal from cws[in_bits*stride]. Levels 0..in_bits-2 read only their seed correction word. The final tree level (in_bits - 1) reads SetLsb(HCW, LCW_0) from its layer entry and LCW_1 from bit in_bits-1 of tr; every other bit of tr is ignored. The terminal cws[in_bits*stride] is the output correction word as Cw::s stores it.

Parameters

b	Party index, false for party 0 and true for party 1.
s0	This party's seed from generation.
cws	Correction words, layer l at index lstride and the terminal at index in_bitsstride.
tr	Packed control bits; only bit in_bits-1 is read.
x	Query point.
stride	Positive stride between Cw entries.

Returns: This party's output share.

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.; 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 Hash, typename In>
requires (ValidForInputBits<In, in_bits> && Groupable<Group> && CcrHashable<Hash>)

void fss::HalfTreeDpf< in_bits, Group, Hash, In >::EvalAll	(	bool	b,
		int4	s0,
		cuda::std::span< const int4 >	cws,
		In	tr,
		int4	ys[],
		int	par_depth = 0,
		size_t	stride = 1 )

inline

Evaluate the full domain from split Cws.

Layer l is read from cws[l*stride] and the terminal from cws[in_bits*stride]. Levels 0..in_bits-2 read only their seed correction word. The final tree level (in_bits - 1) reads SetLsb(HCW, LCW_0) from its layer entry and LCW_1 from bit in_bits-1 of tr; every other bit of tr is ignored. The terminal cws[in_bits*stride] is the output correction word as Cw::s stores it.

Parameters

b	Party index, false for party 0 and true for party 1.
s0	This party's seed from generation.
cws	Correction words, layer l at index lstride and the terminal at index in_bitsstride.
tr	Packed control bits; only bit in_bits-1 is read.
ys	Output array of at least 2^in_bits elements.
par_depth	Nonnegative OpenMP split depth for this call. Zero runs sequentially. Positive depths require backends that support concurrent calls.
stride	Positive stride between Cw entries.

Precondition: 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. A violation aborts with a diagnostic in Debug builds and is undefined behavior in Release builds.; The output element count and byte size fit size_t.

Exceptions

std::invalid_argument if stride is zero or too large or cws is shorter than in_bits*stride+1.

Postcondition: ys[x] contains this party's output share for x.

◆ EvalAllGpu()

template<int in_bits, typename Group, 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::HalfTreeDpf< in_bits, Group, Hash, In >::EvalAllGpu	(	bool	b,
		int4	s0,
		cuda::std::span< const int4 >	cws,
		In	tr,
		cuda::std::span< int4 >	ys,
		cudaStream_t	stream = 0,
		size_t	stride = 1 ) const

inline

Launch full-domain CUDA evaluation from split device arrays.

Layer l is read from cws[l*stride] and the terminal from cws[in_bits*stride]. Levels 0..in_bits-2 read only their seed correction word. The final tree level (in_bits - 1) reads SetLsb(HCW, LCW_0) from its layer entry and LCW_1 from bit in_bits-1 of tr; every other bit of tr is ignored. The terminal cws[in_bits*stride] is the output correction word as Cw::s stores it. Hash values, resource rules and tuning rules match EvalAllGpu().

Parameters

b	Party index, false for party 0 and true for party 1.
s0	This party's seed, passed by value as a kernel argument.
cws	Device correction words, layer l at index l*stride.
tr	Packed control bits; only bit in_bits-1 is read.
ys	Device storage containing at least 2^in_bits output blocks.
stream	Stream on the device owning the referenced resources.
stride	Positive stride between Cw entries.

Returns: Immediate CUDA launch status. Invalid buffer dimensions, strides, null used buffers, or unaddressable byte sizes return cudaErrorInvalidValue. Execution remains asynchronous; the caller observes completion errors through stream.

Precondition: stride > 0 and cws holds at least in_bits*stride+1 elements.; All referenced storage remains alive until the stream work completes.

◆ EvalAllGpuBatch()

template<int in_bits, typename Group, 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::HalfTreeDpf< in_bits, Group, Hash, In >::EvalAllGpuBatch	(	bool	b,
		cuda::std::span< const int4 >	s0s,
		cuda::std::span< const int4 >	cws,
		cuda::std::span< const In >	tr,
		cuda::std::span< int4 >	ys,
		cudaStream_t	stream = 0,
		size_t	stride = 0 ) const

inline

Launch full-domain CUDA evaluation for s0s.size() keys from split device arrays.

The batch uses the level-major layout: key k layer l is read from cws[l*stride + k], key k's packed control is tr[k], and key k's terminal is cws[in_bits*stride + k]. Levels 0..in_bits-2 read only their seed correction word, the final tree level (in_bits - 1) reads SetLsb(HCW, LCW_0) from its layer entry and LCW_1 from bit in_bits-1 of tr[k], and every other bit of tr[k] is ignored. stride selects the layout. 0 selects the dense level-major layout, in which the stride is the key count of this call. Any other value is a positive stride of at least s0s.size(). Resource and tuning rules match EvalAllGpu(). The batch shares one party index and hash configuration. Every key produces the complete domain.

Parameters

b	Party index shared by the batch.
s0s	Device storage containing one seed per key.
cws	Device level-major correction words.
tr	Device packed control bits, one value per key.
ys	Device key-major rows of 2^in_bits output blocks per key.
stream	Stream on the device owning the referenced resources.
stride	0 for the dense level-major layout, where the stride is the key count of this call, or a positive element stride >= s0s.size().

Returns: Immediate CUDA status. Empty batches succeed without reading buffers. Invalid dimensions, null used buffers, strides, or unaddressable counts and bytes return cudaErrorInvalidValue. Oversized grids return cudaErrorInvalidConfiguration.

Precondition: stride is 0 or at least s0s.size().; cws holds at least in_bits*stride + s0s.size() elements, where a stride of 0 counts as s0s.size().; All referenced storage remains alive until the stream work completes.

◆ EvalRange()

template<int in_bits, typename Group, typename Hash, typename In>
requires (ValidForInputBits<In, in_bits> && Groupable<Group> && CcrHashable<Hash>)

void fss::HalfTreeDpf< in_bits, Group, Hash, In >::EvalRange	(	bool	b,
		In	first,
		In	last,
		int4	s0,
		cuda::std::span< const int4 >	cws,
		In	tr,
		cuda::std::span< int4 >	ys,
		int	par_depth = 0,
		size_t	stride = 1 )

inline

Evaluate the closed input interval [first, last] from split Cws.

Layer l is read from cws[l*stride] and the terminal from cws[in_bits*stride]. Levels 0..in_bits-2 read only their seed correction word. The final tree level (in_bits - 1) reads SetLsb(HCW, LCW_0) from its layer entry and LCW_1 from bit in_bits-1 of tr; every other bit of tr is ignored. The terminal cws[in_bits*stride] is the output correction word as Cw::s stores it.

Parameters

b	Party index, false for party 0 and true for party 1.
first	First input in the interval, inclusive.
last	Last input in the interval, inclusive.
s0	This party's initial seed.
cws	Correction words, layer l at index lstride and the terminal at index in_bitsstride.
tr	Packed control bits; only bit in_bits-1 is read.
ys	Output storage for at least last - first + 1 shares.
par_depth	Nonnegative OpenMP split depth. Zero runs sequentially. Positive depths require backends that support concurrent calls.
stride	Positive stride between Cw entries.

Precondition: first <= last and both endpoints belong to the input domain.; 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. A violation aborts with a diagnostic in Debug builds and is undefined behavior in Release builds.; The output count and byte size fit size_t, and used pointers are nonnull.

Exceptions

std::invalid_argument if stride is zero or too large, cws is shorter than in_bits*stride+1, ys is null, first > last, an endpoint is outside the input domain, or the interval does not fit size_t.

Postcondition: ys[j] is this party's scalar share at first + j. Extra output capacity is untouched.

◆ EvalRangeGpu()

template<int in_bits, typename Group, typename Hash, typename In>
requires (ValidForInputBits<In, in_bits> && Groupable<Group> && CcrHashable<Hash>)

template<int frontier_depth, int threads_per_block>
requires (ValidForInputBits<In, in_bits> && Groupable<Group> && CcrHashable<Hash>)

cudaError_t fss::HalfTreeDpf< in_bits, Group, Hash, In >::EvalRangeGpu	(	bool	b,
		In	first,
		In	last,
		int4	s0,
		cuda::std::span< const int4 >	cws,
		In	tr,
		cuda::std::span< int4 >	ys,
		cudaStream_t	stream = 0,
		size_t	stride = 1 ) const

inline

Evaluate the closed interval [first, last] on the given CUDA stream from split device arrays.

Output ys[j] corresponds to first+j.

Layer l is read from cws[l*stride] and the terminal from cws[in_bits*stride]. Levels 0..in_bits-2 read only their seed correction word. The final tree level (in_bits - 1) reads SetLsb(HCW, LCW_0) from its layer entry and LCW_1 from bit in_bits-1 of tr; every other bit of tr is ignored. The terminal cws[in_bits*stride] is the output correction word as Cw::s stores it. Resources and asynchronous error handling follow EvalAllGpu().

Parameters

b	Party index, false for party 0 and true for party 1.
first	First input in the interval, inclusive.
last	Last input in the interval, inclusive.
s0	This party's seed, passed by value as a kernel argument.
cws	Device correction words, layer l at index l*stride.
tr	Packed control bits; only bit in_bits-1 is read.
ys	Device output storage. Entry x - first receives this party's share at x.
stream	Stream on the device owning the referenced resources.
stride	Positive stride between Cw entries.

Returns: Immediate CUDA status. Invalid endpoints, buffers, strides, counts or byte sizes return cudaErrorInvalidValue. Grid limits return cudaErrorInvalidConfiguration.

Precondition: stride > 0 and cws holds at least in_bits*stride+1 elements.; All referenced storage remains alive until the stream work completes.

◆ Gen()

template<int in_bits, typename Group, typename Hash, typename In>
requires (ValidForInputBits<In, in_bits> && Groupable<Group> && CcrHashable<Hash>)

void fss::HalfTreeDpf< in_bits, Group, Hash, In >::Gen	(	cuda::std::span< int4 >	cws,
		In &	tr,
		cuda::std::span< const int4, 2 >	s0s,
		In	a,
		int4	b_buf,
		size_t	stride = 1 )

inline

Generate split Cws from caller-owned initial seeds.

Layer l is stored at cws[l*stride] and the terminal at cws[in_bits*stride]. Levels 0..in_bits-2 store a plain seed correction word. The final tree level (in_bits - 1) stores SetLsb(HCW, LCW_0) exactly as Cw::s does, and LCW_1 moves out of Cw::extra into bit in_bits-1 of tr. The control component exists only at that level, so every other bit of tr is zero on output. The terminal cws[in_bits*stride] holds the plain output correction word in Cw::s.

Parameters

cws	Output storage; its capacity includes in_bits*stride+1 elements.
tr	Output packed control bits; only bit in_bits-1 is written.
s0s	Two initial seeds, retained by the caller.
a	The secret point.
b_buf	Output value, clamped before conversion to Group.
stride	Positive element stride between layer entries. The default stride of 1 stores the components contiguously.

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.; 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: cws, tr and s0s[party] form the corresponding party's key.; Only the described prefix is written, and storage beyond it is untouched.

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

include/fss/half_tree_dpf.cuh

Classes

Public Types

Public Member Functions

Static Public Attributes

Detailed Description

Constructor & Destructor Documentation

◆ HalfTreeDpf()

Member Function Documentation

◆ Eval()

◆ EvalAll()

◆ EvalAllGpu()

◆ EvalAllGpuBatch()

◆ EvalRange()

◆ EvalRangeGpu()

◆ Gen()