cuckoo_hash.cuh File Reference

Cuckoo-hashing utility for VDMPF. More...

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

Go to the source code of this file.

Classes
struct	fss::cuckoo_hash::PrpHash< Prp, In, kappa >
	PRP-based hash for Cuckoo hashing. More...
struct	fss::cuckoo_hash::Compact< Prp, In, kappa >
	Compact Cuckoo hashing (Algorithm 4 from the paper). More...

Functions
constexpr double	fss::cuckoo_hash::detail::Log2 (double x)
constexpr double	fss::cuckoo_hash::detail::Ceil (double x)
constexpr int	fss::cuckoo_hash::ChBucket (int t, int lambda)
	Compute the number of Cuckoo-hash buckets from Lemma 5 of the paper, simplified per Remark 1.

Detailed Description

Cuckoo-hashing utility for 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

ChBucket()

constexpr int fss::cuckoo_hash::ChBucket ( int  t, int  lambda  )

constexpr

Compute the number of Cuckoo-hash buckets from Lemma 5 of the paper, simplified per Remark 1.

This formula assumes kappa = 3 hash functions.

For sufficiently large t (>= 30), the Normal CDF factors in Lemma 5 become effectively 1, giving the simplified formula: lambda = 123.5 * e - 130 - log2(t) e = (lambda + 130 + log2(t)) / 123.5 m = ceil(e * t)

This formula is monotonic in t, so ChBucket(max_t) >= ChBucket(t) for all t <= max_t.

Parameters

t	Number of elements. Must be >= 30.
lambda	Cuckoo-hashing security parameter in bits.

Returns

Number of buckets m.