- 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 comparison function (DCF) over F2 from the packed Half-Tree DPF. More...
#include <cuda_runtime.h>#include <cuda/std/bit>#include <fss/grotto_dcf.cuh>#include <fss/packed_half_tree_dpf.cuh>#include <fss/util.cuh>#include <memory>#include <cuda/std/span>#include <utility>#include <stdexcept>Classes | |
| class | fss::HalfTreeGrottoDcf< in_bits, Hash, In > |
| 2-party DCF scheme over F2 from the packed Half-Tree DPF (Grotto construction). More... | |
| struct | fss::HalfTreeGrottoDcf< in_bits, Hash, In >::ParityTreeView |
| Borrowed, read-only packed leaves and their block-parity tree. More... | |
| class | fss::OwnedPackedParityTree< Scheme > |
| Own packed host leaves and their block-parity tree. More... | |
2-party distributed comparison function (DCF) over F2 from the packed Half-Tree DPF.
The comparison is the prefix-parity algorithm of Grotto (1), which GrottoDcf runs on the BGI DPF, applied to a PackedHalfTreeDpf key with out_bits = 1 and beta = 1. SIGMA (2) runs the same algorithm on the BGI DPF with early termination. A key is the DPF key itself, so PackedHalfTreeDpf::Eval() on the same key still gives the shares of 1[x == alpha].
Output shares are in F2 (XOR sharing). Each party holds a single bool per query. For inputs x: share_0 XOR share_1 = 1[alpha <= x], as in GrottoDcf.
The two parties' control bits of a node XOR to 1 exactly when the node is on alpha's path, i.e., to the parity of the 1-bit outputs below it. Eval() walks x's path and XORs the control bit of every node at which x's bit differs from the previous bit, taking the bit before the first as 0. These are the nodes where the path turns. If x leaves alpha's path at tree level d, the XORed bits reconstruct to x's bit at level d, and x's output block reconstructs to zero. If x stays on the path, they reconstruct to x's last tree bit r, and the block holds a single 1 at alpha's lane. Eval() then XORs the block lanes up to and including x's lane when r = 0, or the lanes above it when r = 1, which gives 1[alpha <= x] in both cases.
Gen makes 2 * (kDepth + 1) hash calls and Eval kDepth + 1, the costs of PackedHalfTreeDpf. A key is 16 * (kDepth + 2) bytes with kDepth = in_bits - 7.
1.15.0