- Generated by
1.15.0
|
myl7/fss 2.0.0
Function secret sharing (FSS) primitives including distributed point/comparison function (DPF/DCF)
|
2-party distributed point function (DPF) with packed sub-128-bit outputs, based on Half-Tree expansion. More...
#include <cuda_runtime.h>#include <type_traits>#include <cstddef>#include <cassert>#include <vector>#include <fss/hash.cuh>#include <fss/util.cuh>#include <fss/constraints.cuh>#include <fss/compat.cuh>#include <cuda/std/span>#include <limits>#include <fss/half_tree_dpf.cuh>#include <stdexcept>Go to the source code of this file.
Classes | |
| class | fss::PackedHalfTreeDpf< in_bits, out_bits, Hash, In > |
| 2-party DPF scheme with packed sub-128-bit outputs, using the Half-Tree construction. More... | |
| struct | fss::PackedHalfTreeDpf< in_bits, out_bits, Hash, In >::Cw |
| Correction word for a tree level or the final packed-output correction word. More... | |
2-party distributed point function (DPF) with packed sub-128-bit outputs, based on Half-Tree expansion.
For the output width out_bits < 128, full-domain evaluation can return one 16B block per 128 / out_bits consecutive inputs instead of one element per input: the expansion stops at tree depth in_bits - log2(kLanes), and the bits of each level node cover the kLanes outputs of the inputs under it. This removes the last log2(kLanes) levels of hash calls and shrinks both the key and the output array by that factor, mirroring what LibDPF does for 1-bit outputs.
A block is read as a little-endian 128-bit integer with x the low word and w the high word, matching fss::detail::Pack(). Lane j occupies bits [j * out_bits, (j + 1) * out_bits). The output share for input x is lane x & (kLanes - 1) of block x >> log2(kLanes); see Extract().
The output group is XOR only: the two parties' blocks XOR-reconstruct to beta at alpha's lane and to the zero block everywhere else. Additive groups cannot be packed into shared lanes. HalfTreeGrottoDcf evaluates a 1-bit key with beta = 1 as a comparison function.
The tree levels follow Half-Tree: one CCR hash call per expanded node yields both children (right = left XOR node), and the control bit rides in the node LSB. On the alpha path the two parties' nodes differ by a constant delta equal to the XOR of the two root seeds, and exactly one party has t = 1; off the path the nodes are identical.
The leaf conversion is a hash: y = H(S XOR node) XOR (t ? fcw : 0), with fcw = packed_beta XOR leaf_0 XOR leaf_1. The hash is required for privacy. Without it the output blocks would be the raw level nodes, and fcw = packed_beta XOR node_0 XOR node_1 would expose the constant path difference — the XOR of the two root seeds — to any key holder whenever beta is known (LibDPF accepts the milder one-bit version of this leak by returning raw blocks; we do not). Its inputs are the level kDepth nodes, which are never expanded, so expansion and conversion read disjoint hash input sets, as in HalfTreeDpf.
EvalAll() runs in level order: a scalar top widens the root to an 8-node frontier, then every level advances 8 frontier nodes per batched expansion through detail::HashBatch(). The correction words apply through branchless masks, and the leaf conversion is fused into the final expansion so each output block is written once. The level-order node index equals the in-order leaf index the DFS walk produces, so the ys layout is identical. Domains with kDepth <= kBatchTopDepth never fill a frontier and evaluate one point per block.
Gen makes 2 * (kDepth + 1) hash calls, Eval kDepth + 1, and EvalAll under 2^(kDepth + 1). A key contains kDepth + 1 correction words and s0, i.e. 16 * (kDepth + 2) bytes.
1.15.0