fss::Dmpf< in_bits, max_points, bucket_bits, Group, Prg, Prp, In, ch_lambda > Class Template Reference

2-party DMPF scheme. More...

Classes
struct	Key
	DMPF key for one party. More...

Public Types
using	Cw = typename InnerDpf::Cw
	Correction word of the inner DPF.
using	BucketKey = typename InnerDpf::Key
	One party's inner DPF key for a bucket.

Public Member Functions
	Dmpf (Prg prg, Prp prp)
	Construct a scheme with configured backends.
int	Gen (cuda::std::span< Cw > cws, int &m_rt, __uint128_t &b_size_rt, int4 sigma, cuda::std::span< const int4 > s0s, cuda::std::span< const In > as, cuda::std::span< const int4 > b_bufs, int t, int max_evictions=1000)
	Generate shared correction words with read-only seeds and one attempt.
void	BatchEval (bool b, int4 sigma, __uint128_t b_size_rt, cuda::std::span< const int4, kBucketCount > s0s, cuda::std::span< const Cw > cws, cuda::std::span< const In > xs, cuda::std::span< int4 > ys)
	Batch evaluation method.
void	EvalAll (bool b, int4 sigma, __uint128_t b_size_rt, cuda::std::span< const int4, kBucketCount > s0s, cuda::std::span< const Cw > cws, cuda::std::span< int4 > ys, int par_depth=0)
	Evaluate the DMPF on all input points.
template<int frontier_depth = 16, int threads_per_block = 256> requires (in_bits <= 38 && in_bits < sizeof(size_t) * 8 && bucket_bits < sizeof(size_t) * 8)
cudaError_t	EvalAllGpu (bool b, int4 sigma, __uint128_t b_size_rt, cuda::std::span< const int4 > s0s, cuda::std::span< const Cw > cws, cuda::std::span< int4 > ys, cudaStream_t stream=0) const
	Launch full-domain CUDA evaluation with internal temporary bucket outputs.

Static Public Attributes
static constexpr int	kBucketCount = cuckoo_hash::ChBucket(max_points, ch_lambda)
	Allocated bucket count.
static constexpr __uint128_t	kDomainSize = __uint128_t(1) << in_bits
	Input domain size.
static constexpr int	kMinPoints
	Smallest point count supported by this bucket_bits configuration.
static constexpr __uint128_t	kBucketSize
	Bucket domain size when the actual point count equals max_points: the smallest bucket domain size that keeps every located bucket below kBucketCount, as returned by cuckoo_hash::detail::MinBucketSize().

Detailed Description

template<int in_bits, int max_points, int bucket_bits, typename Group, typename Prg, typename Prp, typename In = uint, int ch_lambda = 80>
requires (ValidForInputBits<In, in_bits> && in_bits <= 126 && max_points >= 30 && ch_lambda >= 0 && 1 <= bucket_bits && bucket_bits <= 127 && cuckoo_hash::ChBucket(max_points, ch_lambda) > 0 && (((__uint128_t{3} << in_bits) + cuckoo_hash::ChBucket(max_points, ch_lambda) - 1) / cuckoo_hash::ChBucket(max_points, ch_lambda)) <= (__uint128_t{1} << bucket_bits) && Groupable<Group> && Prgable<Prg, 2> && Permutable<Prp>)
class fss::Dmpf< in_bits, max_points, bucket_bits, Group, Prg, Prp, In, ch_lambda >

2-party DMPF scheme.

Gen(), BatchEval(), and EvalAll() are host operations. Cuckoo hashing uses exactly three candidate buckets per input. The PRP permutes [0, 3*kDomainSize), where kDomainSize = 2^in_bits. kBucketCount is the allocated bucket count for max_points. Gen() returns the active bucket count m_rt and bucket-domain size b_size_rt for the actual point count. These runtime values, the PRP seed, and all per-bucket arrays must come from the same successful Gen() call. Evaluation derives its bucket bound from b_size_rt, so it needs b_size_rt but not m_rt; m_rt stays key metadata. The supported point-count interval is [kMinPoints, max_points]. Increasing bucket_bits can lower kMinPoints at the cost of more correction word storage.

Template Parameters

in_bits	Input domain bit size, in [1, 126].
max_points	Maximum number of point functions. Must be >= 30. Sizes arrays at compile time.
bucket_bits	Inner DPF domain width in [1, 127], with enough bucket capacity.
Group	Type for the output domain. See Groupable.
Prg	See Prgable.
Prp	See Permutable. Used for Cuckoo hashing.
In	Type for the input domain. From uint8_t to __uint128_t.
ch_lambda	Target Cuckoo-hashing failure exponent in bits, used by the bucket-count estimate.

Constructor & Destructor Documentation

Dmpf()

template<int in_bits, int max_points, int bucket_bits, typename Group, typename Prg, typename Prp, typename In, int ch_lambda>
requires (ValidForInputBits<In, in_bits> && in_bits <= 126 && max_points >= 30 && ch_lambda >= 0 && 1 <= bucket_bits && bucket_bits <= 127 && cuckoo_hash::ChBucket(max_points, ch_lambda) > 0 && (((__uint128_t{3} << in_bits) + cuckoo_hash::ChBucket(max_points, ch_lambda) - 1) / cuckoo_hash::ChBucket(max_points, ch_lambda)) <= (__uint128_t{1} << bucket_bits) && Groupable<Group> && Prgable<Prg, 2> && Permutable<Prp>)

fss::Dmpf< in_bits, max_points, bucket_bits, Group, Prg, Prp, In, ch_lambda >::Dmpf ( Prg prg, Prp prp )

inlineexplicit

Construct a scheme with configured backends.

Parameters

prg	Configured Prg backend.
prp	Configured Prp backend.

Member Function Documentation

BatchEval()

template<int in_bits, int max_points, int bucket_bits, typename Group, typename Prg, typename Prp, typename In, int ch_lambda>
requires (ValidForInputBits<In, in_bits> && in_bits <= 126 && max_points >= 30 && ch_lambda >= 0 && 1 <= bucket_bits && bucket_bits <= 127 && cuckoo_hash::ChBucket(max_points, ch_lambda) > 0 && (((__uint128_t{3} << in_bits) + cuckoo_hash::ChBucket(max_points, ch_lambda) - 1) / cuckoo_hash::ChBucket(max_points, ch_lambda)) <= (__uint128_t{1} << bucket_bits) && Groupable<Group> && Prgable<Prg, 2> && Permutable<Prp>)

void fss::Dmpf< in_bits, max_points, bucket_bits, Group, Prg, Prp, In, ch_lambda >::BatchEval ( bool b, int4 sigma, __uint128_t b_size_rt, cuda::std::span< const int4, kBucketCount > s0s, cuda::std::span< const Cw > cws, cuda::std::span< const In > xs, cuda::std::span< int4 > ys )

inline

Batch evaluation method.

Evaluates a batch of input points using caller-owned shared correction words and party seeds.

Parameters

b	Party index. False for 0 and true for 1.
sigma	The effective PRP seed from Gen().
b_size_rt	Runtime bucket domain size returned by Gen().
s0s	This party's kBucketCount initial seeds in bucket order.
cws	At least kBucketCount*(bucket_bits+1) read-only correction words in bucket-major order.
xs	Input points to evaluate.
ys	Output shares (pre-allocated, size >= xs.size()). Will be zero-initialized.

Exceptions

std::invalid_argument

if b_size_rt is outside [kBucketSize, 2^bucket_bits], cws is shorter than kBucketCount*(bucket_bits+1), or ys is shorter than xs.

EvalAll()

template<int in_bits, int max_points, int bucket_bits, typename Group, typename Prg, typename Prp, typename In, int ch_lambda>
requires (in_bits < sizeof(size_t) * 8 && bucket_bits < sizeof(size_t) * 8)

void fss::Dmpf< in_bits, max_points, bucket_bits, Group, Prg, Prp, In, ch_lambda >::EvalAll ( bool b, int4 sigma, __uint128_t b_size_rt, cuda::std::span< const int4, kBucketCount > s0s, cuda::std::span< const Cw > cws, cuda::std::span< int4 > ys, int par_depth = 0 )

inline

Evaluate the DMPF on all input points.

Candidates are routed by the exclusive bucket bound derived from b_size_rt: ceil(3*kDomainSize/b_size_rt). Gen() sizes b_size_rt = ceil(3*kDomainSize/m_rt), so the bound is at most m_rt and is exactly one past the largest bucket index a candidate can reach.

Exceptions

std::invalid_argument

if b_size_rt is outside [kBucketSize, 2^bucket_bits], cws is shorter than kBucketCount*(bucket_bits+1), or ys does not hold 2^in_bits elements.

Precondition

The full output and each inner bucket output have element counts and byte sizes that fit size_t.

Parameters

b	Party index. False for 0 and true for 1.
sigma	The effective PRP seed from Gen().
b_size_rt	Runtime bucket domain size returned by Gen().
s0s	This party's kBucketCount initial seeds in bucket order.
cws	At least kBucketCount*(bucket_bits+1) read-only correction words in bucket-major order.
ys	Output shares (pre-allocated, size == kDomainSize). Will be zero-initialized.
par_depth	Nonnegative OpenMP split depth for this call. Zero runs sequentially. Positive depths require backends that support concurrent calls.

EvalAllGpu()

template<int in_bits, int max_points, int bucket_bits, typename Group, typename Prg, typename Prp, typename In, int ch_lambda>
requires (in_bits <= 38 && in_bits < sizeof(size_t) * 8 && bucket_bits < sizeof(size_t) * 8)

template<int frontier_depth, int threads_per_block>
requires (in_bits <= 38 && in_bits < sizeof(size_t) * 8 && bucket_bits < sizeof(size_t) * 8)

cudaError_t fss::Dmpf< in_bits, max_points, bucket_bits, Group, Prg, Prp, In, ch_lambda >::EvalAllGpu ( bool b, int4 sigma, __uint128_t b_size_rt, cuda::std::span< const int4 > s0s, cuda::std::span< const Cw > cws, cuda::std::span< int4 > ys, cudaStream_t stream = 0 ) const

inline

Launch full-domain CUDA evaluation with internal temporary bucket outputs.

The host instance supplies backend values as kernel arguments. Key/output buffers and backend device resources are prepared and retained by the caller. Temporary bucket outputs are allocated and released in the supplied stream. No backend upload, deep copy, or synchronization is performed. Prg, Prp, and Group must support the device execution and concurrency used. This is one multipoint key with ceil(3*kDomainSize/b_size_rt) inner DPF keys, not a batch of independent multipoint keys.

Template Parameters

frontier_depth	Inner DPF frontier depth, capped at bucket_bits. Defaults to 16.
threads_per_block	Inner DPF block size, capped at the frontier width. Defaults to 256. The requested block size is a power of two in [1,1024]. The inner DPF derives its block-root depth, permits at most eight tail levels, and uses signed-int block indices, exactly as Dpf::EvalAllGpuBatch().

Parameters

b	Party index, false for party 0 and true for party 1.
sigma	Shared PRP seed from successful Gen().
b_size_rt	Runtime bucket size from that Gen(). Every located bucket then stays below kBucketCount exactly when b_size_rt is at least ceil(3*kDomainSize/kBucketCount).
s0s	Device storage with this party's seed for each bucket below ceil(3*kDomainSize/b_size_rt).
cws	Device storage of at least ceil(3*kDomainSize/b_size_rt)*(bucket_bits+1) correction words, in bucket-major order.
ys	Device output storage of at least 2^in_bits int4 blocks, in input order.
stream	Stream on the device owning the referenced resources.

Precondition

this is accessible on the host. Buffers and backend resources remain valid until work completes.

Returns

The first immediate CUDA allocation, launch, or release failure, or cudaSuccess. Invalid metadata, buffer lengths, null used buffers, or byte sizes return cudaErrorInvalidValue. An unrepresentable merge grid returns cudaErrorInvalidConfiguration. Execution completion is asynchronous.

Gen()

template<int in_bits, int max_points, int bucket_bits, typename Group, typename Prg, typename Prp, typename In, int ch_lambda>
requires (ValidForInputBits<In, in_bits> && in_bits <= 126 && max_points >= 30 && ch_lambda >= 0 && 1 <= bucket_bits && bucket_bits <= 127 && cuckoo_hash::ChBucket(max_points, ch_lambda) > 0 && (((__uint128_t{3} << in_bits) + cuckoo_hash::ChBucket(max_points, ch_lambda) - 1) / cuckoo_hash::ChBucket(max_points, ch_lambda)) <= (__uint128_t{1} << bucket_bits) && Groupable<Group> && Prgable<Prg, 2> && Permutable<Prp>)

int fss::Dmpf< in_bits, max_points, bucket_bits, Group, Prg, Prp, In, ch_lambda >::Gen ( cuda::std::span< Cw > cws, int & m_rt, __uint128_t & b_size_rt, int4 sigma, cuda::std::span< const int4 > s0s, cuda::std::span< const In > as, cuda::std::span< const int4 > b_bufs, int t, int max_evictions = 1000 )

inline

Generate shared correction words with read-only seeds and one attempt.

Makes one Cuckoo-hashing attempt, then generates each inner DPF. Caller-owned sigma and s0s are preserved.

Retrying a failed attempt

On return 1, draw a fresh uniformly random sigma block from a cryptographically secure random generator and rerun the whole Gen with the same points and payloads. Placement depends on sigma, not on the inner DPF seeds, so s0s need not change for this retry. Incrementing sigma is not resampling. The caller chooses the attempt limit and handles exhaustion. Reuse of the output buffers is allowed. Only a successful call's outputs and its sigma/s0s form a usable key.

Parameters

cws	At least kBucketCount*(bucket_bits+1) writable correction words in bucket-major order.
m_rt	Returned runtime bucket count.
b_size_rt	Returned runtime bucket domain size.
sigma	Uniformly random PRP seed from a cryptographically secure random generator.
s0s	At least 2*kBucketCount independent uniformly random initial seeds in party-major order: s0s[i] is party 0's seed for bucket i and s0s[kBucketCount+i] is party 1's seed. Sample independently of sigma with a cryptographically secure random generator.
as	Alpha values of t point functions.
b_bufs	Corresponding beta values, clamped before generation.
t	Actual number of points in [kMinPoints, max_points].
max_evictions	Eviction limit per inserted point. Exceeding it fails the attempt.

Precondition

as.size() >= t and b_bufs.size() >= t.

The first t alpha values are distinct and belong to [0, kDomainSize).

max_evictions is nonnegative.

ceil(3*kDomainSize/cuckoo_hash::ChBucket(t, ch_lambda)) <= 2^bucket_bits.

Exceptions

std::invalid_argument

if cws is shorter than kBucketCount*(bucket_bits+1), s0s is shorter than 2*kBucketCount, t is outside [kMinPoints, max_points], or the bucket size does not fit bucket_bits.

Postcondition

On success, cws, sigma, and s0s define both parties' keys. Correction-word outputs are unspecified on failure. m_rt and b_size_rt may already have been written when the attempt fails; metadata alone is not a key.

Returns

0 on success, or 1 if the Cuckoo-hashing attempt fails.

Member Data Documentation

kBucketSize

template<int in_bits, int max_points, int bucket_bits, typename Group, typename Prg, typename Prp, typename In = uint, int ch_lambda = 80>

__uint128_t fss::Dmpf< in_bits, max_points, bucket_bits, Group, Prg, Prp, In, ch_lambda >::kBucketSize

staticconstexpr

Initial value:

=
      cuckoo_hash::detail::MinBucketSize(kDomainSize, kCuckooChoices, kBucketCount)

Bucket domain size when the actual point count equals max_points: the smallest bucket domain size that keeps every located bucket below kBucketCount, as returned by cuckoo_hash::detail::MinBucketSize().

A smaller runtime point count can give a larger bucket domain. Use the b_size_rt returned by Gen() for the actual key's evaluation.

kMinPoints

template<int in_bits, int max_points, int bucket_bits, typename Group, typename Prg, typename Prp, typename In = uint, int ch_lambda = 80>

int fss::Dmpf< in_bits, max_points, bucket_bits, Group, Prg, Prp, In, ch_lambda >::kMinPoints

staticconstexpr

Initial value:

= [] {
    int lower = 30;
    int upper = max_points;
    while (lower < upper) {
      int middle = lower + (upper - lower) / 2;
      int buckets = cuckoo_hash::ChBucket(middle, ch_lambda);
      __uint128_t bucket_size = cuckoo_hash::detail::MinBucketSize(kDomainSize, kCuckooChoices, buckets);
      if (bucket_size <= (__uint128_t{1} << bucket_bits)) upper = middle;
      else lower = middle + 1;
    }
    return lower;
  }()

Smallest point count supported by this bucket_bits configuration.

Gen() accepts every t in [kMinPoints, max_points]. The lower bound is at least 30, where the Cuckoo bucket-count estimate applies. Fewer points use fewer buckets and can require a larger per-bucket domain. The capacity condition is ceil(3*kDomainSize/ChBucket(t, ch_lambda)) <= 2^bucket_bits. The shared buffer of correction words contains kBucketCount*(bucket_bits+1)*sizeof(Cw) bytes, so each extra bucket bit adds kBucketCount*sizeof(Cw) bytes without changing the bucket count.

---

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

• include/fss/dmpf.cuh