2-party DCF scheme over F2 from standard DPF (Grotto construction). More...

Classes
struct	ParityTreeView
	Borrowed, read-only parity tree in level order. More...

Public Types
using	Cw = typename DpfType::Cw
	Correction-word type of the underlying DPF.
using	Input = In
	The caller-facing input-domain type.

Public Member Functions
	GrottoDcf (Prg prg)
	Configure the pseudorandom generator.
void	Gen (cuda::std::span< int4 > cws, In &tr, cuda::std::span< const int4, 2 > s0s, In a, size_t stride=1)
	Generate split DPF correction words with beta equal to zero.
bool	Eval (bool b, int4 s0, cuda::std::span< const int4 > cws, In tr, In x, size_t stride=1)
	Evaluate a comparison share along x's path from split correction words.
void	Preprocess (bool b, int4 s0, cuda::std::span< const int4 > cws, In tr, bool p[], int par_depth=0, size_t stride=1)
	Expand split leaf control bits and build a parity tree in caller-owned host storage.
OwnedParityTree< GrottoDcf >	PreprocessOwned (bool b, int4 s0, cuda::std::span< const int4 > cws, In tr, int par_depth=0, size_t stride=1)
	Allocate and populate a parity tree from split correction words in host storage.
void	EvalAll (bool b, int4 s0, cuda::std::span< const int4 > cws, In tr, bool ys[], int par_depth=0, size_t stride=1)
	Evaluate comparison shares for the full domain from split correction words.
template<int frontier_depth = 16, int threads_per_block = 256> requires (in_bits < sizeof(size_t) * 8)
cudaError_t	PreprocessGpu (bool b, int4 s0, cuda::std::span< const int4 > cws, In tr, cuda::std::span< bool > tree, cudaStream_t stream=0, size_t stride=1) const
	Build a parity tree on the GPU from split device correction words.
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< bool > ys, cudaStream_t stream=0, size_t stride=1) const
	Evaluate all comparison shares on the GPU from split device correction words.

Static Public Member Functions
static bool	Eval (ParityTreeView pt, In x)
	Query a preprocessed tree with O(in_bits) XOR operations and no PRG calls.
static void	EvalAll (ParityTreeView pt, bool ys[])
	Evaluate the full domain from a host parity tree without PRG calls.
static cudaError_t	EvalAllGpu (ParityTreeView pt, cuda::std::span< bool > ys, cudaStream_t stream=0)
	Evaluate all comparison shares from a device parity tree.

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 Prg, typename In = uint>
requires (ValidForInputBits<In, in_bits> && Prgable<Prg, 2>)
class fss::GrottoDcf< in_bits, Prg, In >

2-party DCF scheme over F2 from standard DPF (Grotto construction).

Template Parameters

in_bits	Input domain bit size.
Prg	See Prgable. Must satisfy Prgable<Prg, 2> (same as DPF).
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() is a host operation.

Constructor & Destructor Documentation

◆ GrottoDcf()

template<int in_bits, typename Prg, typename In>
requires (ValidForInputBits<In, in_bits> && Prgable<Prg, 2>)

fss::GrottoDcf< in_bits, Prg, In >::GrottoDcf ( Prg prg )

inlineexplicit

Configure the pseudorandom generator.

Parameters

prg	Backend used throughout generation and evaluation.

Member Function Documentation

◆ Eval() [1/2]

template<int in_bits, typename Prg, typename In>
requires (ValidForInputBits<In, in_bits> && Prgable<Prg, 2>)

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

inline

Evaluate a comparison share along x's path from split correction words.

Layer l is read from cws[l*stride] and the terminal from cws[in_bits*stride]. cws keeps the left-control correction in each layer's LSB and tr takes the right-control bits, bit l for layer l; bits of tr at or above in_bits are ignored.

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 right-control bits, bit l for layer l.
x	Query point.
stride	Positive stride between correction entries.

Returns: This party's XOR share of the predicate alpha <= x.

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.; 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 Prg, typename In>
requires (ValidForInputBits<In, in_bits> && Prgable<Prg, 2>)

bool fss::GrottoDcf< in_bits, Prg, In >::Eval	(	ParityTreeView	pt,
		In	x )

inlinestatic

Query a preprocessed tree with O(in_bits) XOR operations and no PRG calls.

Parameters

pt	View of a tree filled by Preprocess() or PreprocessGpu().
x	Query point in [0, 2^in_bits).

Returns: This party's XOR share of alpha <= x.

Precondition: The parity-tree element count and byte size fit size_t.; Storage is accessible in this execution space.

◆ EvalAll() [1/2]

template<int in_bits, typename Prg, typename In>
requires (ValidForInputBits<In, in_bits> && Prgable<Prg, 2>)

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

inline

Evaluate comparison shares for the full domain from split correction words.

Layer l is read from cws[l*stride] and the terminal from cws[in_bits*stride]. cws keeps the left-control correction in each layer's LSB and tr takes the right-control bits, bit l for layer l; bits of tr at or above in_bits are ignored. 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 seed from generation.
cws	Correction words, layer l at index l*stride.
tr	Packed right-control bits, bit l for layer l.
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 correction 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.; 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 XOR share of alpha <= x.

◆ EvalAll() [2/2]

template<int in_bits, typename Prg, typename In>
requires (ValidForInputBits<In, in_bits> && Prgable<Prg, 2>)

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

inlinestatic

Evaluate the full domain from a host parity tree without PRG calls.

Scans the leaves with O(N) XOR operations, where N = 2^in_bits.

Parameters

pt	View of a preprocessed tree accessible on the host.
ys	Output array of at least N bool entries, disjoint from pt's storage.

Precondition: The parity-tree element count and byte size fit size_t.

Postcondition: ys[x] contains this party's XOR share of alpha <= x.

◆ EvalAllGpu() [1/2]

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

inline

Evaluate all comparison shares on the GPU from split device correction words.

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

Layer l is read from cws[l*stride] and tr carries the right-control bits, bit l for layer l, as in the Cw form. The host instance passes its PRG value to the expansion kernel. Temporary scan storage is queried, 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.
tr	Packed right-control bits, bit l for layer l.
ys	Device output of at least 2^in_bits bool entries, in input order.
stream	Stream used for expansion, scanning, and temporary storage.
stride	Positive stride between correction entries.

Precondition: stride > 0 and cws holds at least in_bits*stride+1 elements.; Buffers and referenced backend resources remain valid until 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 Prg, typename In>
requires (in_bits < sizeof(size_t) * 8)

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

inlinestatic

Evaluate all comparison shares from a device parity tree.

Scans the stored leaves without PRG calls. Temporary scan storage is queried, allocated, and released on stream, without implicit synchronization.

Parameters

pt	Borrowed tree produced by PreprocessGpu(), with 2^(in_bits+1)-1 entries.
ys	Device output of at least 2^in_bits bool entries, disjoint from pt.
stream	Stream used for the scan and temporary storage.

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

Returns: The first immediate CUDA failure. Invalid buffers/counts return cudaErrorInvalidValue. Completion remains asynchronous.

◆ Gen()

template<int in_bits, typename Prg, typename In>
requires (ValidForInputBits<In, in_bits> && Prgable<Prg, 2>)

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

inline

Generate split DPF correction words with beta equal to zero.

Layer l is stored at cws[l*stride] and the terminal at cws[in_bits*stride]. The key is the underlying DPF key, so cws keeps the left-control correction in each layer's LSB and tr takes the right-control bits, bit l for layer l, exactly as the Dpf split layout does.

Parameters

cws	Output seed components; its capacity includes in_bits*stride+1 elements.
tr	Output packed right-control bits, bit l for layer l.
s0s	Two initial seeds, retained by the caller.
a	The secret comparison threshold.
stride	Positive element stride between layer entries. The default stride of 1 stores the correction words 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.

Postcondition: cws, tr 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 Prg, typename In>
requires (ValidForInputBits<In, in_bits> && Prgable<Prg, 2>)

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

inline

Expand split leaf control bits and build a parity tree in caller-owned host storage.

Layer l is read from cws[l*stride] and the terminal from cws[in_bits*stride]. cws keeps the left-control correction in each layer's LSB and tr takes the right-control bits, bit l for layer l; bits of tr at or above in_bits are ignored. The produced tree matches the Cw form entry for entry.

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.
tr	Packed right-control bits, bit l for layer l.
p	Output buffer of at least 2^(in_bits+1)-1 writable 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 correction 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.; The parity-tree 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: ParityTreeView{p} can be queried through Eval() and EvalAll().

◆ PreprocessGpu()

template<int in_bits, typename Prg, 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::GrottoDcf< in_bits, Prg, In >::PreprocessGpu	(	bool	b,
		int4	s0,
		cuda::std::span< const int4 >	cws,
		In	tr,
		cuda::std::span< bool >	tree,
		cudaStream_t	stream = 0,
		size_t	stride = 1 ) const

inline

Build a parity tree on the GPU from split device correction words.

Layer l is read from cws[l*stride] and tr carries the right-control bits, bit l for layer l, as in the Cw form. The PRG value is passed to the kernel; any resources it references must already be device-accessible. 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.
tr	Packed right-control bits, bit l for layer l.
tree	Device output of at least 2^(in_bits+1)-1 bool entries.
stream	Stream on the device owning the referenced resources.
stride	Positive stride between correction entries.

Precondition: stride > 0 and cws holds at least in_bits*stride+1 elements.; Tree element 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 Prg, typename In>
requires (ValidForInputBits<In, in_bits> && Prgable<Prg, 2>)

OwnedParityTree< GrottoDcf< in_bits, Prg, In > > fss::GrottoDcf< in_bits, Prg, In >::PreprocessOwned	(	bool	b,
		int4	s0,
		cuda::std::span< const int4 >	cws,
		In	tr,
		int	par_depth = 0,
		size_t	stride = 1 )

inline

Allocate and populate a parity tree from split correction words in host storage.

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] and tr carries the right-control bits, bit l for layer l, 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.
tr	Packed right-control bits, bit l for layer l.
par_depth	Nonnegative CPU split depth for this call. Zero runs sequentially. Positive depths require backends that support concurrent calls.
stride	Positive stride between correction entries.

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

Precondition: stride > 0 and cws holds at least in_bits*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 in_bits*stride+1.

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

include/fss/dpf.cuh
include/fss/grotto_dcf.cuh

Classes

Public Types

Public Member Functions

Static Public Member Functions

Static Public Attributes

Detailed Description

Constructor & Destructor Documentation

◆ GrottoDcf()

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()