cuckoo_hash.cuh File Reference

Cuckoo-hashing utility for DMPF and VDMPF. More...

#include <cuda_runtime.h>
#include <cmath>
#include <limits>
#include <span>
#include <utility>
#include <random>
#include <fss/prp.cuh>
#include <stdexcept>

Go to the source code of this file.

Functions
constexpr int	fss::cuckoo_hash::ChBucket (int t, int lambda)
	Estimate the number of buckets for three-choice Cuckoo hashing.
constexpr __uint128_t	fss::cuckoo_hash::detail::CeilDiv (__uint128_t num, __uint128_t den)
	Ceiling division of two positive integers, in the wrap-free form.
constexpr __uint128_t	fss::cuckoo_hash::detail::BucketIndexBound (__uint128_t n, int choices, __uint128_t bucket_size)
	Exclusive upper bound on the bucket index of a located candidate.
constexpr __uint128_t	fss::cuckoo_hash::detail::MinBucketSize (__uint128_t n, int choices, __uint128_t bucket_count)
	Smallest bucket domain size that keeps every located bucket in range.
constexpr bool	fss::cuckoo_hash::detail::ValidBucketSize (__uint128_t b_size_rt, __uint128_t bucket_size_min, int bucket_bits)
	Test a key's runtime bucket domain size against a configuration.

Variables
constexpr int	fss::cuckoo_hash::detail::kRejectedBucket = std::numeric_limits<int>::max()
	Bucket identifier of a rejected candidate.

Detailed Description

Cuckoo-hashing utility for DMPF and VDMPF.

Copyright

Apache License, Version 2.0. Copyright (C) 2026 Yulong Ming i@myl.nosp@m.7.or.nosp@m.g.

Author

Yulong Ming i@myl.nosp@m.7.or.nosp@m.g

The scheme is from the paper, Lightweight, Maliciously Secure Verifiable Function Secret Sharing (1: the published version), Section 4.1 and Algorithm 4.

References

1. Leo de Castro, Antigoni Polychroniadou: Lightweight, Maliciously Secure Verifiable Function Secret Sharing. EUROCRYPT 2022: 150-179. https://doi.org/10.1007/978-3-031-06944-4_6.

Function Documentation

BucketIndexBound()

__uint128_t fss::cuckoo_hash::detail::BucketIndexBound ( __uint128_t n, int choices, __uint128_t bucket_size )

constexpr

Exclusive upper bound on the bucket index of a located candidate.

PrpHash::Locate() maps every candidate with a positive bucket domain size and an int-representable bucket index into [0, choices * n / bucket_size), so the largest such bucket is ceil(choices * n / bucket_size) - 1, and this is the smallest bucket count that covers every located bucket. A candidate outside that interval locates kRejectedBucket instead.

Parameters

n	Original input domain size, at least 1.
choices	Candidate count per input, at least 1.
bucket_size	Positive bucket domain size carried by a key.

Returns

ceil(choices * n / bucket_size).

CeilDiv()

__uint128_t fss::cuckoo_hash::detail::CeilDiv ( __uint128_t num, __uint128_t den )

constexpr

Ceiling division of two positive integers, in the wrap-free form.

(num - 1) / den + 1 equals ceil(num / den) for every num at least 1 and den at least 1. The direct form (num + den - 1) / den gives the same value for every in-range input, but wraps in __uint128_t once den exceeds 2^126 with num = 3 * 2^126.

Parameters

num	Positive dividend.
den	Positive divisor.

Returns

ceil(num / den).

MinBucketSize()

__uint128_t fss::cuckoo_hash::detail::MinBucketSize ( __uint128_t n, int choices, __uint128_t bucket_count )

constexpr

Smallest bucket domain size that keeps every located bucket in range.

A candidate locates at bucket index ceil(choices * n / bucket_size) - 1 at most, so the smallest bucket domain size whose candidates all stay below bucket_count is ceil(choices * n / bucket_count). This is the inverse direction of BucketIndexBound(): it takes the bucket count a caller can allocate and returns the bucket domain size to require of a key.

Parameters

n	Original input domain size, at least 1.
choices	Candidate count per input, at least 1.
bucket_count	Positive number of allocated buckets.

Returns

ceil(choices * n / bucket_count).

ValidBucketSize()

bool fss::cuckoo_hash::detail::ValidBucketSize ( __uint128_t b_size_rt, __uint128_t bucket_size_min, int bucket_bits )

constexpr

Test a key's runtime bucket domain size against a configuration.

b_size_rt is exact-transport key metadata, like the correction-word arrays: no entry trusts the caller to pre-validate it, and the entries that do check it deduplicate the bound through this function. A candidate locates at bucket index ceil(choices*n/b_size_rt) - 1 at most, so every located bucket stays below the allocated bucket count exactly when b_size_rt is at least MinBucketSize(n, choices, bucket_count), and a within-bucket input is an index into a bucket of bucket_bits width, so b_size_rt must also fit bucket_bits.

Parameters

b_size_rt	Bucket domain size carried by a key.
bucket_size_min	Smallest usable bucket domain size, e.g. a scheme's kBucketSize.
bucket_bits	Bucket domain bit width.

Returns

True when b_size_rt is at least bucket_size_min and is at most 2^bucket_bits.

Variable Documentation

kRejectedBucket

int fss::cuckoo_hash::detail::kRejectedBucket = std::numeric_limits<int>::max()

constexpr

Bucket identifier of a rejected candidate.

PrpHash::Locate() returns it when the exact bucket index does not fit int, or when the bucket domain size is zero. It equals INT_MAX, so every caller filter of the form bucket >= bound, whose bound is an int, rejects the candidate.