2-party DCF scheme over F2 from the packed Half-Tree DPF (Grotto construction). More...

Classes
struct	ParityTreeView
	Borrowed, read-only packed leaves and their block-parity tree. More...

Public Types
using	Cw = typename DpfType::Cw
	Correction word type of the packed Half-Tree DPF.
using	Input = In
	Configure the CCR hash and public instance seed S.

Public Member Functions
void	Gen (cuda::std::span< int4 > cws, cuda::std::span< const int4, 2 > s0s, In a, size_t stride=1)
	Key generation method for split Cws.
bool	Eval (bool b, int4 s0, cuda::std::span< const int4 > cws, In x, size_t stride=1)
	Evaluation method for split Cws, see "Evaluation" in the file details.
void	Preprocess (bool b, int4 s0, cuda::std::span< const int4 > cws, int4 blocks[], bool p[], int par_depth=0, size_t stride=1)
	Build packed leaves and their parity tree from split Cws.
OwnedPackedParityTree< HalfTreeGrottoDcf >	PreprocessOwned (bool b, int4 s0, cuda::std::span< const int4 > cws, int par_depth=0, size_t stride=1)
	Allocate and populate packed leaves and their parity tree from split Cws.
void	EvalAll (bool b, int4 s0, cuda::std::span< const int4 > cws, bool ys[], int par_depth=0, size_t stride=1)
	Evaluate all comparison shares from split Cws on the host.
template<int frontier_depth = 16, int threads_per_block = 256> requires (kDepth < sizeof(size_t) * 8)
cudaError_t	PreprocessGpu (bool b, int4 s0, cuda::std::span< const int4 > cws, cuda::std::span< int4 > blocks, cuda::std::span< bool > tree, cudaStream_t stream=0, size_t stride=1) const
	Build packed leaves and their parity tree on the GPU from split Cws.
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, cuda::std::span< bool > ys, cudaStream_t stream=0, size_t stride=1) const
	Evaluate all comparison shares on the GPU from split Cws.

Static Public Member Functions
static bool	Eval (ParityTreeView pt, In x)
	Query a preprocessed tree without hash calls.
static void	EvalAll (ParityTreeView pt, bool ys[])
	Evaluate all comparison shares from preprocessed packed leaves on the host.
template<int threads_per_block = 256> requires (in_bits < sizeof(size_t) * 8)
static cudaError_t	EvalAllGpu (ParityTreeView pt, cuda::std::span< bool > ys, cudaStream_t stream=0)
	Evaluate all comparison shares from device packed leaves.

Static Public Attributes
static constexpr int	kLanes = DpfType::kLanes
	Number of one-bit output lanes in each packed leaf block.
static constexpr int	kDepth = DpfType::kDepth
	Tree depth that is actually expanded, see PackedHalfTreeDpf::kDepth.
static constexpr int	kCwCount = DpfType::kCwCount
	Seed-component count Gen() writes at stride 1: kDepth levels plus the packed-output terminal.

Detailed Description

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

2-party DCF scheme over F2 from the packed Half-Tree DPF (Grotto construction).

Template Parameters

in_bits	Input domain bit size. Must exceed 7, the levels a 1-bit output block covers.
Hash	Unary CCR hash backend. See CcrHashable and PackedHalfTreeDpf.
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. Preprocess() and both EvalAll() overloads are host operations. For N = 2^in_bits and B = N/128, preprocessing stores B packed leaf blocks and a parity tree of 2*B-1 bool entries over whole blocks. Tree queries use O(kDepth) XOR operations and no hash calls. Raw scalar Eval() and the leaf-prefix route can give different individual shares. Both parties must use the same route. Raw EvalAll() and preprocessed evaluation use the same leaf-prefix route and give identical shares.

Member Typedef Documentation

◆ Input

template<int in_bits, typename Hash, typename In = uint>

using fss::HalfTreeGrottoDcf< in_bits, Hash, In >::Input = In

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. The caller-facing input-domain type.

Member Function Documentation

◆ Eval() [1/2]

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

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

inline

Evaluation method for split Cws, see "Evaluation" in the file details.

Layer l is read from cws[l*stride] and the packed-output correction word from cws[kDepth*stride]. The construction carries no control bits, so there is no packed-control parameter.

Parameters

b	Party index. False for 0 and true for 1.
s0	This party's seed from generation.
cws	Correction words, layer l at index lstride and the packed-output correction word at index kDepthstride.
x	Query point in [0, 2^in_bits).
stride	Positive stride between Cw entries.

Returns: bool share such that share_0 XOR share_1 = 1[alpha <= x].

Precondition: stride > 0.; With M = numeric_limits<size_t>::max()/sizeof(int4), stride <= (M-1)/kDepth and cws has at least kDepth*stride+1 elements.; 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.

◆ Eval() [2/2]

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

bool fss::HalfTreeGrottoDcf< in_bits, Hash, In >::Eval	(	ParityTreeView	pt,
		In	x )

inlinestatic

Query a preprocessed tree without hash calls.

Parameters

pt	Borrowed packed parity tree. Both buffers must remain alive and accessible in the execution space of this call.
x	Query point in [0, 2^in_bits).

Returns: This party's XOR share of alpha <= x, using the leaf-prefix route.

Precondition: Packed-block and parity-tree element counts and byte sizes fit size_t.

◆ EvalAll() [1/2]

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

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

inline

Evaluate all comparison shares from split Cws on the host.

Layer l is read from cws[l*stride] and the packed-output correction word from cws[kDepth*stride]. The construction carries no control bits, so there is no packed-control parameter. Outputs match the Cw form share for share.

Parameters

b	Party index, false for party 0 and true for party 1.
s0	This party's initial seed.
cws	Correction words, layer l at index l*stride.
ys	Output array of at least 2^in_bits bool entries.
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)/kDepth and cws has at least kDepth*stride+1 elements.; The output and packed-block element counts and byte sizes fit size_t.

Exceptions

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

Postcondition: ys[x] is this party's XOR share of alpha <= x, using the leaf-prefix route.

◆ EvalAll() [2/2]

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

void fss::HalfTreeGrottoDcf< in_bits, Hash, In >::EvalAll	(	ParityTreeView	pt,
		bool	ys[] )

inlinestatic

Evaluate all comparison shares from preprocessed packed leaves on the host.

Uses O(2^in_bits) XOR work, no hash calls, and no additional allocation.

Parameters

pt	Borrowed parity tree with storage accessible on the host.
ys	Output array of at least 2^in_bits bool entries, disjoint from pt's storage.

Precondition: The output and packed-block element counts and byte sizes fit size_t.

Postcondition: ys matches raw EvalAll() for the same party, configuration and key components.

◆ EvalAllGpu() [1/2]

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

inline

Evaluate all comparison shares on the GPU from split Cws.

Follows the leaf-prefix route, as in the Cw form. Per-party shares are not comparable across routes.

Expands packed blocks, unpacks their bits, and scans their prefix XOR. Layer l is read from cws[l*stride] and the packed-output correction word from cws[kDepth*stride]. The host instance passes its hash value and instance seed to the packed evaluator. Referenced backend resources must already be device-accessible. Packed-block and CUB scan scratch are allocated and released on stream. No backend upload, deep copy, synchronization, or event management occurs.

Parameters

b	Party index.
s0	This party's seed, passed by value.
cws	Device correction words, layer l at index l*stride.
ys	Device output of at least 2^in_bits bool entries, in input order.
stream	Stream used for evaluation, scanning, and temporary storage.
stride	Positive stride between Cw entries.

Precondition: stride > 0 and cws holds at least kDepth*stride+1 elements.; Buffers and backend resources remain valid until queued work completes.

Returns: The first immediate CUDA failure, including allocation or release. Invalid buffers/counts return cudaErrorInvalidValue. Work is asynchronous.

◆ EvalAllGpu() [2/2]

template<int in_bits, typename Hash, typename In>
requires (in_bits < sizeof(size_t) * 8)

template<int threads_per_block>
requires (in_bits < sizeof(size_t) * 8)

cudaError_t fss::HalfTreeGrottoDcf< in_bits, Hash, In >::EvalAllGpu	(	ParityTreeView	pt,
		cuda::std::span< bool >	ys,
		cudaStream_t	stream = 0 )

inlinestatic

Evaluate all comparison shares from device packed leaves.

Unpacks blocks and scans their prefix XOR without hash calls. The parity entries pt.p are not read. Scan scratch is allocated and released on stream.

Template Parameters

threads_per_block Power-of-two unpack block size in [1,1024], default 256.

Parameters

pt	Borrowed view with at least 2^kDepth device packed blocks.
ys	Device output of at least 2^in_bits bool entries, disjoint from pt.blocks.
stream	Stream used for unpacking, scanning, and temporary storage.

Precondition: Input and output buffers remain valid until queued work completes.

Returns: The first immediate CUDA failure, including allocation or release. Invalid buffers/counts return cudaErrorInvalidValue. Work is asynchronous.

◆ Gen()

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

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

inline

Key generation method for split Cws.

Delegates to PackedHalfTreeDpf::Gen() with beta = 1.

Layer l is stored at cws[l*stride] and the packed-output correction word at cws[kDepth*stride]. The construction carries no control bits, so there is no packed-control parameter.

Parameters

cws	Output storage; its capacity includes kDepth*stride+1 elements.
s0s	2 initial seeds. Users can randomly sample them.
a	The secret comparison threshold in [0, 2^in_bits).
stride	Positive element stride between layer entries. The default stride of 1 stores the components contiguously.

Precondition: stride > 0.; With M = numeric_limits<size_t>::max()/sizeof(int4), stride <= (M-1)/kDepth and cws has at least kDepth*stride+1 elements.; Inputs and outputs do not overlap.; All accessed storage is accessible from the calling execution space.

Postcondition: cws and s0s[party] form the corresponding party's key.; Only the described prefix is written, and storage beyond it is untouched.

◆ Preprocess()

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

void fss::HalfTreeGrottoDcf< in_bits, Hash, In >::Preprocess	(	bool	b,
		int4	s0,
		cuda::std::span< const int4 >	cws,
		int4	blocks[],
		bool	p[],
		int	par_depth = 0,
		size_t	stride = 1 )

inline

Build packed leaves and their parity tree from split Cws.

Layer l is read from cws[l*stride] and the packed-output correction word from cws[kDepth*stride]. The construction carries no control bits, so there is no packed-control parameter. The produced arrays match the Cw form entry for entry.

Parameters

b	Party index, false for party 0 and true for party 1.
s0	This party's initial seed.
cws	Correction words, layer l at index l*stride.
blocks	Writable output array of at least 2^kDepth int4 entries.
p	Writable output array of at least 2^(kDepth+1)-1 bool entries.
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)/kDepth and cws has at least kDepth*stride+1 elements.; Packed-block and parity-tree element counts and byte sizes fit size_t.

Exceptions

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

Postcondition: ParityTreeView{blocks, p} can be passed to Eval() and EvalAll().

◆ PreprocessGpu()

template<int in_bits, typename Hash, typename In>
requires (kDepth < sizeof(size_t) * 8)

template<int frontier_depth, int threads_per_block>
requires (kDepth < sizeof(size_t) * 8)

cudaError_t fss::HalfTreeGrottoDcf< in_bits, Hash, In >::PreprocessGpu	(	bool	b,
		int4	s0,
		cuda::std::span< const int4 >	cws,
		cuda::std::span< int4 >	blocks,
		cuda::std::span< bool >	tree,
		cudaStream_t	stream = 0,
		size_t	stride = 1 ) const

inline

Build packed leaves and their parity tree on the GPU from split Cws.

Reuses PackedHalfTreeDpf::EvalAllGpu(). Layer l is read from cws[l*stride] and the packed-output correction word from cws[kDepth*stride]. The hash value and instance seed are passed as kernel arguments; resources referenced by the hash must already be device-accessible and allow concurrent use. No allocation, upload, deep copy, or synchronization is performed.

Parameters

b	Party index.
s0	This party's initial seed, passed by value to the kernel.
cws	Device correction words, layer l at index l*stride.
blocks	Device output of at least 2^kDepth packed int4 blocks.
tree	Device output of at least 2^(kDepth+1)-1 bool parity entries.
stream	Stream on the device owning the referenced resources.
stride	Positive stride between Cw entries.

Precondition: stride > 0 and cws holds at least kDepth*stride+1 elements.; Packed-block and parity-tree counts and byte counts fit size_t.; Buffers and backend resources remain valid until queued work completes.

Returns: Immediate CUDA status. Invalid buffers or unaddressable counts return cudaErrorInvalidValue; oversized grids return cudaErrorInvalidConfiguration. Work remains asynchronous, and execution errors are observed on the stream.

◆ PreprocessOwned()

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

OwnedPackedParityTree< HalfTreeGrottoDcf< in_bits, Hash, In > > fss::HalfTreeGrottoDcf< in_bits, Hash, In >::PreprocessOwned	(	bool	b,
		int4	s0,
		cuda::std::span< const int4 >	cws,
		int	par_depth = 0,
		size_t	stride = 1 )

inline

Allocate and populate packed leaves and their parity tree from split Cws.

The returned owner holds independent storage; this instance keeps no key or preprocessed tree. Its View() is accepted by Eval() and EvalAll(). Layer l is read from cws[l*stride], as in the Cw form.

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 l*stride.
par_depth	Nonnegative CPU split depth for this call. Zero runs sequentially. Positive depths require backends that support concurrent calls.
stride	Positive stride between Cw entries.

Returns: Move-only owner of the populated host storage.

Precondition: stride > 0 and cws holds at least kDepth*stride+1 elements.; All allocated element counts and byte sizes fit size_t.

Exceptions

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

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

include/fss/half_tree_grotto_dcf.cuh

Classes

Public Types

Public Member Functions

Static Public Member Functions

Static Public Attributes

Detailed Description

Member Typedef Documentation

◆ Input

Member Function Documentation

◆ Eval() [1/2]

◆ Eval() [2/2]

◆ EvalAll() [1/2]

◆ EvalAll() [2/2]

◆ EvalAllGpu() [1/2]

◆ EvalAllGpu() [2/2]

◆ Gen()

◆ Preprocess()

◆ PreprocessGpu()

◆ PreprocessOwned()