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

2-party VDMPF scheme. More...

Classes
struct	BucketKey
	Per-bucket VDPF key with shared correction words and one party's initial seed. More...
struct	Key
	VDMPF key for one party, containing the PRP seed and per-bucket keys. More...

Public Types
using	Cw = typename InnerVdpf::Cw
	Correction word of the inner VDPF.
using	EvalProof = cuda::std::array<cuda::std::array<int4, 4>, kCuckooChoices>
	Per-candidate corrected per-point hashes of one input, in candidate order.

Public Member Functions
	Vdmpf (Prg prg, XorHash xor_hash, Hash hash, Prp prp)
	Construct a scheme with configured backends.
int	Gen (cuda::std::span< Cw > cws, cuda::std::span< int4 > cs, 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 int4 > cs, cuda::std::span< const In > xs, cuda::std::span< int4 > ys, cuda::std::span< int4, 4 > pi)
	Batch verifiable evaluation method.
EvalProof	Eval (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 int4 > cs, In x, int4 &y)
	Evaluate one input and return the corrected per-point hashes for Prove() or ProveMerkle().
void	Prove (int4 sigma, __uint128_t b_size_rt, cuda::std::span< const int4 > cs, cuda::std::span< const In > xs, cuda::std::span< const EvalProof > proof_values, cuda::std::span< int4, 4 > pi)
	Proof accumulation method for the per-input evaluation.
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< const int4 > cs, cuda::std::span< int4 > ys, cuda::std::span< int4, 4 > pi)
	Evaluate the full domain on the host and produce a chain proof.
void	BatchEvalMerkle (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 int4 > cs, cuda::std::span< const In > xs, cuda::std::span< int4 > ys, cuda::std::span< int4, 4 > pi)
	Batch evaluation method with the Merkle-fold proof.
void	ProveMerkle (int4 sigma, __uint128_t b_size_rt, cuda::std::span< const int4 > cs, cuda::std::span< const In > xs, cuda::std::span< const EvalProof > proof_values, cuda::std::span< int4, 4 > pi)
	Proof accumulation method for the per-input evaluation with the Merkle-fold proof.
void	EvalAllMerkle (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 int4 > cs, cuda::std::span< int4 > ys, cuda::std::span< int4, 4 > pi)
	Evaluate the full domain on the host and produce a Merkle proof.
template<int threads_per_block = 256> requires (in_bits < sizeof(size_t) * 8)
cudaError_t	EvalAllMerkleGpu (bool b, int4 sigma, __uint128_t b_size_rt, cuda::std::span< const int4 > s0s, cuda::std::span< const Cw > cws, cuda::std::span< const int4 > cs, cuda::std::span< int4 > ys, cuda::std::span< int4, 4 > pi, cudaStream_t stream=0) const
	Launch full-domain Merkle evaluation with internal temporary storage.
template<int threads_per_block = 256> 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> && XorHashable<XorHash> && Hashable<Hash> && Permutable<Prp>)
cudaError_t	BatchEvalMerkleGpu (bool b, int4 sigma, __uint128_t b_size_rt, cuda::std::span< const int4 > s0s, cuda::std::span< const Cw > cws, cuda::std::span< const int4 > cs, cuda::std::span< const In > xs, cuda::std::span< int4 > ys, cuda::std::span< int4, 4 > pi, cudaStream_t stream=0) const
	Launch batch Merkle evaluation of an arbitrary ordered query sequence.

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	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 XorHash, typename Hash, 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> && XorHashable<XorHash> && Hashable<Hash> && Permutable<Prp>)
class fss::Vdmpf< in_bits, max_points, bucket_bits, Group, Prg, XorHash, Hash, Prp, In, ch_lambda >

2-party VDMPF scheme.

Gen() and CPU evaluation 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. kBucketCount is also the proof-fold range: the proof loops fold every allocated bucket, and the loops not involved in the fold use the bound derived from b_size_rt. No entry receives a bucket count. The supported point-count interval is [kMinPoints, max_points]. Increasing bucket_bits can lower kMinPoints at the cost of more correction word storage. BatchEval() uses chain accumulation and BatchEvalMerkle() uses a Merkle fold. Both parties must use the same accumulator, key configuration, and query sequence. XorHash receives (packed within-bucket index, clamped leaf seed), in that order. The index uses the full coordinate block; bit 0 of the seed's fourth word is reserved and passed as zero. The built-in backends use that seed bit for digest tags. Verification guarantees require the assumptions and accumulator-specific proof conditions in doc/vdpf_merkle_fold_security.md. EvalAll() and EvalAllMerkle() use the same accumulators for the full domain in increasing input order. Eval() evaluates one input per call and returns the proof material for Prove() (chain) or ProveMerkle() (Merkle). The per-input methods share the fused paths' bucket-level folds; with the same key and query sequence they produce the same proofs, and the same shares for the commutative Group backends in this repository.

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 VDPF domain width in [1, 127], with enough bucket capacity.
Group	Type for the output domain. See Groupable.
Prg	See Prgable.
XorHash	See XorHashable. Paper's \(H\): maps \((x, s)\) to \(4\lambda\) bits.
Hash	See Hashable. Paper's \(H'\): maps \(4\lambda\) bits to \(2\lambda\) bits.
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

Vdmpf()

template<int in_bits, int max_points, int bucket_bits, typename Group, typename Prg, typename XorHash, typename Hash, 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> && XorHashable<XorHash> && Hashable<Hash> && Permutable<Prp>)

fss::Vdmpf< in_bits, max_points, bucket_bits, Group, Prg, XorHash, Hash, Prp, In, ch_lambda >::Vdmpf ( Prg prg, XorHash xor_hash, Hash hash, Prp prp )

inlineexplicit

Construct a scheme with configured backends.

Parameters

prg	Configured Prg backend.
xor_hash	Configured XorHash backend.
hash	Configured Hash backend.
prp	Configured Prp backend.

Member Function Documentation

BatchEval()

template<int in_bits, int max_points, int bucket_bits, typename Group, typename Prg, typename XorHash, typename Hash, 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> && XorHashable<XorHash> && Hashable<Hash> && Permutable<Prp>)

void fss::Vdmpf< in_bits, max_points, bucket_bits, Group, Prg, XorHash, Hash, 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 int4 > cs, cuda::std::span< const In > xs, cuda::std::span< int4 > ys, cuda::std::span< int4, 4 > pi )

inline

Batch verifiable evaluation method.

Evaluates caller-owned correction words and party seeds on a batch of inputs, producing shares and a chain proof.

Inputs in xs must lie in [0, 2^in_bits). The sequence may be sparse, unsorted, or contain 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.

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, including each bucket's final output correction word.
cs	At least 4*kBucketCount read-only blocks of the inner VerDPF's correction seed, one seed per bucket, in bucket-major order.
xs	Input points to evaluate.
ys	Output shares (pre-allocated, size >= xs.size()). Will be zero-initialized.
pi	Borrowed output storage for four proof blocks.

Precondition

Every bucket's four cs blocks are not jointly all zero, for all kBucketCount buckets including inactive ones.

Exceptions

std::invalid_argument

if b_size_rt is outside [kBucketSize, 2^bucket_bits], cws or cs is too short, or ys is shorter than xs.

BatchEvalMerkle()

template<int in_bits, int max_points, int bucket_bits, typename Group, typename Prg, typename XorHash, typename Hash, 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> && XorHashable<XorHash> && Hashable<Hash> && Permutable<Prp>)

void fss::Vdmpf< in_bits, max_points, bucket_bits, Group, Prg, XorHash, Hash, Prp, In, ch_lambda >::BatchEvalMerkle ( 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 int4 > cs, cuda::std::span< const In > xs, cuda::std::span< int4 > ys, cuda::std::span< int4, 4 > pi )

inline

Batch evaluation method with the Merkle-fold proof.

Parallel-friendly alternative to BatchEval(): same output shares, and the proof replaces the paper's sequential chains with Merkle-style folds. Per bucket, the leaf nodes (hashes of the corrected per-point hashes, ordered by query position, then hash-function index) form one canonical Merkle tree. Adjacent nodes combine level by level, carrying an odd trailing node unchanged. The bucket node hashes the concatenation of its hashed cs and its tree root. An empty bucket contributes only its hashed cs. The kBucketCount bucket nodes fold the same way into the final proof, whose last two words stay zero. Execution block sizes and GPU work partitioning do not change this tree or the proof. Every combining step hashes 64B to 32B, so fold binding for a common ordered query sequence and tree shape reduces to the pairwise collision resistance of the fold hash. Share integrity also requires the remaining assumptions in doc/vdpf_merkle_fold_security.md.

The proof keeps the 64B shape, so Verify() is shared, but chain and fold accumulators produce different proofs: both parties must pick the same one. This host path is the sequential reference; the GPU path folds the same construction and matches it bit-exactly.

Inputs in xs must lie in [0, 2^in_bits). The sequence may be sparse, unsorted, or contain 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 candidate records and one leaf per record.

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, including each bucket's final output correction word.
cs	At least 4*kBucketCount read-only blocks of the inner VerDPF's correction seed, one seed per bucket, in bucket-major order.
xs	Input points to evaluate.
ys	Output shares (pre-allocated, size >= xs.size()). Will be zero-initialized.
pi	Borrowed output storage for four proof blocks.

Precondition

Every bucket's four cs blocks are not jointly all zero, for all kBucketCount buckets including inactive ones.

Exceptions

std::invalid_argument

if b_size_rt is outside [kBucketSize, 2^bucket_bits], cws or cs is too short, or ys is shorter than xs.

BatchEvalMerkleGpu()

template<int in_bits, int max_points, int bucket_bits, typename Group, typename Prg, typename XorHash, typename Hash, 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> && XorHashable<XorHash> && Hashable<Hash> && Permutable<Prp>)

template<int threads_per_block>
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> && XorHashable<XorHash> && Hashable<Hash> && Permutable<Prp>)

cudaError_t fss::Vdmpf< in_bits, max_points, bucket_bits, Group, Prg, XorHash, Hash, Prp, In, ch_lambda >::BatchEvalMerkleGpu ( bool b, int4 sigma, __uint128_t b_size_rt, cuda::std::span< const int4 > s0s, cuda::std::span< const Cw > cws, cuda::std::span< const int4 > cs, cuda::std::span< const In > xs, cuda::std::span< int4 > ys, cuda::std::span< int4, 4 > pi, cudaStream_t stream = 0 ) const

inline

Launch batch Merkle evaluation of an arbitrary ordered query sequence.

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(). Every input pays its own three located-bucket walks, one per Cuckoo candidate, as in the host batch path; no tree walk is shared across inputs.

Takes the raw key components sigma, b_size_rt, s0s, cws, and cs as Gen() returned them and prepares what the kernels need internally. The host instance passes backend values as kernel arguments. Referenced backend resources and device buffers are prepared and retained by the caller. Temporary work arrays and CUB sorting storage are allocated and released internally using CUDA stream-ordered allocation on stream. The CUB size query runs before allocation. No backend upload, deep copy, event management, or host/device synchronization is performed. The Prp backend must be device-callable: ChaChaFeistel qualifies; Aes128Feistel and Aes128FeistelRaw are host-only and fail to build with an unresolved-extern error when used on device.

Inputs in xs must lie in [0, 2^in_bits). The sequence may be sparse, unsorted, or contain 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 candidate records and one leaf per record.

Template Parameters

threads_per_block

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

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(), in [kBucketSize, 2^bucket_bits]. Every located bucket then stays below kBucketCount.
s0s	Device storage of kBucketCount party seeds, one per bucket.
cws	Device storage of kBucketCount*(bucket_bits+1) bucket-major correction words.
cs	Device storage of 4*kBucketCount bucket-major correction-seed blocks.
xs	Device storage of the ordered input sequence; it may be sparse, unsorted, and contain duplicates.
ys	Device output storage of at least xs.size() int4 blocks.
pi	Device output storage for four Merkle-proof blocks.
stream	Stream on the device owning the referenced resources.

Precondition

xs is nonempty and xs[i] < 2^in_bits for every i. All key arrays and metadata come from the same successful Gen(). Buffers and referenced backend resources remain valid until queued work completes. CUDA stream-ordered allocation must be supported on the current device.

Every bucket's four cs blocks are not jointly all zero, for all kBucketCount buckets including inactive ones.

Returns

The first immediate CUDA allocation, launch, or release error. Invalid sizes, metadata, or pointers return cudaErrorInvalidValue. CUB's current int record count requires 3*xs.size() <= INT_MAX. Unrepresentable grids return cudaErrorInvalidConfiguration. Completion remains asynchronous.

Eval()

template<int in_bits, int max_points, int bucket_bits, typename Group, typename Prg, typename XorHash, typename Hash, 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> && XorHashable<XorHash> && Hashable<Hash> && Permutable<Prp>)

Vdmpf< in_bits, max_points, bucket_bits, Group, Prg, XorHash, Hash, Prp, In, ch_lambda >::EvalProof fss::Vdmpf< in_bits, max_points, bucket_bits, Group, Prg, XorHash, Hash, Prp, In, ch_lambda >::Eval ( 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 int4 > cs, In x, int4 & y )

inline

Evaluate one input and return the corrected per-point hashes for Prove() or ProveMerkle().

The per-input counterpart of the fused evaluation: with the same key and the same query sequence, Eval() per input followed by Prove() produces the same chain proof as one BatchEval() call, and by ProveMerkle() the same Merkle proof as one BatchEvalMerkle() call. The proofs do not depend on the group order. Shares match the fused paths for the commutative Group backends in this repository: Eval() adds one input's candidate shares in candidate order, while the fused paths add them in bucket order.

Routing covers every bucket below the bound ceil(3*kDomainSize/b_size_rt) derived from b_size_rt. Under a key from the same successful Gen(), b_size_rt = ceil(3*kDomainSize/m_rt) keeps every candidate below that bound, which is at most m_rt, so an inactive bucket cannot receive a candidate. Inactive buckets still take part in the accumulators through their correction seeds: Prove() folds each bucket's cs and ProveMerkle() folds each bucket's hashed cs.

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, including each bucket's final output correction word.
cs	At least 4*kBucketCount read-only blocks of the inner VerDPF's correction seed, one seed per bucket, in bucket-major order.
x	Input point to evaluate.
y	Output share for this input.

Returns

Corrected per-point hashes in candidate order, as described by EvalProof.

Precondition

All key arrays and metadata come from the same successful Gen().

Every bucket's four cs blocks are not jointly all zero, for all kBucketCount buckets including inactive ones.

b_size_rt is in [kBucketSize, 2^bucket_bits], cws has at least kBucketCount*(bucket_bits+1) elements, and cs has at least 4*kBucketCount elements. A violation of these three requirements 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, int max_points, int bucket_bits, typename Group, typename Prg, typename XorHash, typename Hash, 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> && XorHashable<XorHash> && Hashable<Hash> && Permutable<Prp>)

void fss::Vdmpf< in_bits, max_points, bucket_bits, Group, Prg, XorHash, Hash, 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< const int4 > cs, cuda::std::span< int4 > ys, cuda::std::span< int4, 4 > pi )

inline

Evaluate the full domain on the host and produce a chain proof.

Outputs and proof match BatchEval() with inputs 0 through kDomainSize - 1 in increasing order. No input array is required.

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 domain size returned by that 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.
cs	At least 4*kBucketCount read-only blocks of the inner VerDPF's correction seed, one seed per bucket, in bucket-major order.
ys	Caller-owned output storage with at least 2^in_bits int4 entries.
pi	Caller-owned output storage for four chain-proof blocks.

Precondition

All key arrays and metadata come from the same successful Gen().

Every bucket's four cs blocks are not jointly all zero, for all kBucketCount buckets including inactive ones.

The full output and each temporary array's count and byte size fit size_t.

Exceptions

std::invalid_argument

if b_size_rt is outside [kBucketSize, 2^bucket_bits], cws or cs is too short, or ys is shorter than 2^in_bits.

EvalAllMerkle()

template<int in_bits, int max_points, int bucket_bits, typename Group, typename Prg, typename XorHash, typename Hash, 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> && XorHashable<XorHash> && Hashable<Hash> && Permutable<Prp>)

void fss::Vdmpf< in_bits, max_points, bucket_bits, Group, Prg, XorHash, Hash, Prp, In, ch_lambda >::EvalAllMerkle ( 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 int4 > cs, cuda::std::span< int4 > ys, cuda::std::span< int4, 4 > pi )

inline

Evaluate the full domain on the host and produce a Merkle proof.

Outputs and proof match BatchEvalMerkle() with inputs 0 through kDomainSize - 1 in increasing order. No input array is required.

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 domain size returned by that 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.
cs	At least 4*kBucketCount read-only blocks of the inner VerDPF's correction seed, one seed per bucket, in bucket-major order.
ys	Caller-owned output storage with at least 2^in_bits int4 entries.
pi	Caller-owned output storage for four Merkle-proof blocks.

Precondition

All key arrays and metadata come from the same successful Gen().

Every bucket's four cs blocks are not jointly all zero, for all kBucketCount buckets including inactive ones.

The full output and each temporary array's count and byte size fit size_t.

Exceptions

std::invalid_argument

if b_size_rt is outside [kBucketSize, 2^bucket_bits], cws or cs is too short, or ys is shorter than 2^in_bits.

EvalAllMerkleGpu()

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

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

cudaError_t fss::Vdmpf< in_bits, max_points, bucket_bits, Group, Prg, XorHash, Hash, Prp, In, ch_lambda >::EvalAllMerkleGpu ( bool b, int4 sigma, __uint128_t b_size_rt, cuda::std::span< const int4 > s0s, cuda::std::span< const Cw > cws, cuda::std::span< const int4 > cs, cuda::std::span< int4 > ys, cuda::std::span< int4, 4 > pi, cudaStream_t stream = 0 ) const

inline

Launch full-domain Merkle evaluation with internal temporary storage.

The outputs and proof match BatchEvalMerkle() on inputs 0 through 2^in_bits-1 in that order. No input-index array is required. The host instance passes backend values as kernel arguments. Referenced backend resources and device buffers are prepared and retained by the caller. Temporary work arrays and CUB sorting storage are allocated and released internally using CUDA stream-ordered allocation on stream. The CUB size query runs before allocation. No backend upload, deep copy, event management, or host/device synchronization is performed.

Template Parameters

threads_per_block

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

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(), in [kBucketSize, 2^bucket_bits]. Every located bucket then stays below kBucketCount.
s0s	Device storage of kBucketCount party seeds, one per bucket.
cws	Device storage of kBucketCount*(bucket_bits+1) bucket-major correction words.
cs	Device storage of 4*kBucketCount bucket-major blocks of the inner VerDPF's correction seed, one seed per bucket.
ys	Device output storage of at least 2^in_bits int4 blocks.
pi	Device output storage for four Merkle-proof blocks.
stream	Stream on the device owning the referenced resources.

Precondition

this is host accessible. Buffers and referenced backend resources remain valid until queued work completes. CUDA stream-ordered allocation must be supported on the current device.

Every bucket's four cs blocks are not jointly all zero, for all kBucketCount buckets including inactive ones.

Returns

The first immediate CUDA allocation, launch, or release error. Invalid sizes, metadata, or pointers return cudaErrorInvalidValue. CUB's current int record count requires 3*2^in_bits <= INT_MAX. Unrepresentable grids return cudaErrorInvalidConfiguration. Completion remains asynchronous. Chain evaluation has no GPU counterpart.

Gen()

template<int in_bits, int max_points, int bucket_bits, typename Group, typename Prg, typename XorHash, typename Hash, 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> && XorHashable<XorHash> && Hashable<Hash> && Permutable<Prp>)

int fss::Vdmpf< in_bits, max_points, bucket_bits, Group, Prg, XorHash, Hash, Prp, In, ch_lambda >::Gen ( cuda::std::span< Cw > cws, cuda::std::span< int4 > cs, 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 and one attempt for each inner VDPF. 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. Keep s0s unchanged because placement does not depend on the inner VDPF seeds. On return 2, keep sigma and draw fresh independent uniformly random seed pairs for all kBucketCount buckets from a cryptographically secure random generator. The bucket containing the failed inner VDPF is not reported. Both inner VDPF failure conditions use this same resampling procedure. In either case, rerun the whole Gen with the same points and payloads. 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 and cs from the failed attempt, including completed buckets. Only outputs and input seeds from a successful call form a usable key.

Parameters

cws	At least kBucketCount*(bucket_bits+1) writable correction words in bucket-major order, including each bucket's final output correction word.
cs	At least 4*kBucketCount writable blocks of the inner VerDPF's correction seed, one seed per bucket, 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, including empty and inactive buckets.
as	Alpha values of t point functions.
b_bufs	Corresponding beta values. Will be clamped.

Precondition

kMinPoints <= t <= max_points, as.size() >= t, and b_bufs.size() >= t.

The first t alpha values are distinct, belong to [0, kDomainSize), and the runtime bucket size fits bucket_bits.

max_evictions is nonnegative.

Parameters

t	Actual number of points in [kMinPoints, max_points].

Precondition

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

Parameters

max_evictions

Eviction limit per inserted point. Exceeding it fails the attempt.

Postcondition

On success, cws, cs, 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.

Exceptions

std::invalid_argument

if cws, cs, or s0s is too short, t is outside [kMinPoints, max_points], or the bucket size does not fit bucket_bits.

Returns

0 on success, 1 if Cuckoo placement fails, or 2 if an inner VDPF Gen fails.

Prove()

template<int in_bits, int max_points, int bucket_bits, typename Group, typename Prg, typename XorHash, typename Hash, 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> && XorHashable<XorHash> && Hashable<Hash> && Permutable<Prp>)

void fss::Vdmpf< in_bits, max_points, bucket_bits, Group, Prg, XorHash, Hash, Prp, In, ch_lambda >::Prove ( int4 sigma, __uint128_t b_size_rt, cuda::std::span< const int4 > cs, cuda::std::span< const In > xs, cuda::std::span< const EvalProof > proof_values, cuda::std::span< int4, 4 > pi )

inline

Proof accumulation method for the per-input evaluation.

The per-input counterpart of BatchEval(): accumulates the corrected per-point hashes of Eval() into the chain proof with the same per-bucket and cross-bucket folds as the fused path. With the same key and the same query sequence, Eval() per input followed by Prove() gives the same proof as one BatchEval() call, and the same shares for commutative group addition.

Bucket ids and candidate indices are re-located from sigma, b_size_rt, and xs, so proof_values stores corrected hashes only. Both parties must supply the same xs order and the same accumulator. Chain and Merkle accumulators must not be mixed: Prove() and ProveMerkle() produce different proofs from the same values.

Inputs in xs must lie in [0, 2^in_bits). The sequence may be sparse, unsorted, or contain 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.

Parameters

sigma	The effective PRP seed from Gen().
b_size_rt	Runtime bucket domain size returned by Gen().
cs	At least 4*kBucketCount read-only blocks of the inner VerDPF's correction seed, one seed per bucket, in bucket-major order.
xs	Input points evaluated by Eval() with this party's key, in the order of proof_values.
proof_values	proof_values[i] is the EvalProof returned by Eval() for xs[i]. Entries for candidates outside the allocated buckets are not read.
pi	Borrowed output storage for four proof blocks.

Precondition

All key arrays and metadata come from the same successful Gen().

Every bucket's four cs blocks are not jointly all zero, for all kBucketCount buckets including inactive ones.

xs is nonempty and proof_values.size() >= xs.size().

Exceptions

std::invalid_argument

if b_size_rt is outside [kBucketSize, 2^bucket_bits], cs is shorter than 4*kBucketCount, or proof_values is shorter than xs.

ProveMerkle()

template<int in_bits, int max_points, int bucket_bits, typename Group, typename Prg, typename XorHash, typename Hash, 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> && XorHashable<XorHash> && Hashable<Hash> && Permutable<Prp>)

void fss::Vdmpf< in_bits, max_points, bucket_bits, Group, Prg, XorHash, Hash, Prp, In, ch_lambda >::ProveMerkle ( int4 sigma, __uint128_t b_size_rt, cuda::std::span< const int4 > cs, cuda::std::span< const In > xs, cuda::std::span< const EvalProof > proof_values, cuda::std::span< int4, 4 > pi )

inline

Proof accumulation method for the per-input evaluation with the Merkle-fold proof.

The per-input counterpart of BatchEvalMerkle(): folds the corrected per-point hashes of Eval() with the same per-bucket and cross-bucket Merkle folds as the fused path, in the order of the query sequence. With the same key and the same query sequence, Eval() per input followed by ProveMerkle() gives the same proof as one BatchEvalMerkle() call, and the same shares for commutative group addition.

Bucket ids and candidate indices are re-located from sigma, b_size_rt, and xs, so proof_values stores corrected hashes only. Both parties must supply the same xs order and the same accumulator. Chain and Merkle accumulators must not be mixed: Prove() and ProveMerkle() produce different proofs from the same values.

Inputs in xs must lie in [0, 2^in_bits). The sequence may be sparse, unsorted, or contain 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 candidate records and one leaf per record.

Parameters

sigma	The effective PRP seed from Gen().
b_size_rt	Runtime bucket domain size returned by Gen().
cs	At least 4*kBucketCount read-only blocks of the inner VerDPF's correction seed, one seed per bucket, in bucket-major order.
xs	Input points evaluated by Eval() with this party's key, in the order of proof_values.
proof_values	proof_values[i] is the EvalProof returned by Eval() for xs[i]. Entries for candidates outside the allocated buckets are not read.
pi	Borrowed output storage for four proof blocks.

Precondition

All key arrays and metadata come from the same successful Gen().

Every bucket's four cs blocks are not jointly all zero, for all kBucketCount buckets including inactive ones.

xs is nonempty and proof_values.size() >= xs.size().

Exceptions

std::invalid_argument

if b_size_rt is outside [kBucketSize, 2^bucket_bits], cs is shorter than 4*kBucketCount, or proof_values is shorter than xs.

Verify()

template<int in_bits, int max_points, int bucket_bits, typename Group, typename Prg, typename XorHash, typename Hash, 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> && XorHashable<XorHash> && Hashable<Hash> && Permutable<Prp>)

bool fss::Vdmpf< in_bits, max_points, bucket_bits, Group, Prg, XorHash, Hash, Prp, In, ch_lambda >::Verify ( cuda::std::span< const int4, 4 > pi0, cuda::std::span< const int4, 4 > pi1 )

inlinestatic

Verification method.

Parameters

pi0	Party 0 proof.
pi1	Party 1 proof using the same accumulator and queries.

Returns

True if proofs match (Accept), false otherwise (Reject).

Member Data Documentation

kBucketSize

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

__uint128_t fss::Vdmpf< in_bits, max_points, bucket_bits, Group, Prg, XorHash, Hash, 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 XorHash, typename Hash, typename Prp, typename In = uint, int ch_lambda = 80>

int fss::Vdmpf< in_bits, max_points, bucket_bits, Group, Prg, XorHash, Hash, 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/vdmpf.cuh