grotto_dcf.cuh File Reference

2-party distributed comparison function (DCF) over F2 from standard DPF. More...

#include <cuda_runtime.h>
#include <type_traits>
#include <cstddef>
#include <cassert>
#include <fss/dpf.cuh>
#include <fss/group/bytes.cuh>
#include <fss/prg.cuh>
#include <fss/util.cuh>
#include <fss/constraints.cuh>
#include <fss/compat.cuh>
#include <cuda/std/span>
#include <memory>
#include <utility>
#include <cstdint>
#include <limits>

Go to the source code of this file.

Classes
class	fss::GrottoDcf< in_bits, Prg, In >
	2-party DCF scheme over F2 from standard DPF (Grotto construction). More...
struct	fss::GrottoDcf< in_bits, Prg, In >::ParityTreeView
	Borrowed, read-only parity tree in level order. More...
class	fss::OwnedParityTree< Scheme >
	Own a host parity-tree allocation and expose a borrowed, read-only view. More...

Detailed Description

2-party distributed comparison function (DCF) over F2 from standard DPF.

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, Grotto: Screaming fast (2+1)-PC for Z{2^n} via (2,2)-DPFs_ (1: the published version).

Key generation is identical to standard BGI DPF. The comparison functionality emerges from prefix-parity of the DPF control bits: the two parties' control bits of a node XOR to the parity of the leaves below it (Theorem 4 of the paper).

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].

Evaluation

Eval(b, s0, cws, x) runs the paper's prefix-parity algorithm (Section 4) on x's root-to-leaf path: in_bits PRG calls per query and no preprocessing, the cost of a DPF point evaluation. Preprocess() instead expands the whole domain, about 2^in_bits PRG calls, into a parity segment tree that Eval(tree, x) then queries without PRG calls. It pays off once a key answers more than about 2^in_bits / in_bits queries. The two routes give different shares that reconstruct to the same value only in pairs, so both parties must use the same route.

References

1. Kyle Storrier, Adithya Vadapalli, Allan Lyons, Ryan Henry: Grotto: Screaming fast (2+1)-PC for Z_{2^n} via (2, 2)-DPFs. CCS 2023: 2143-2157. https://doi.org/10.1145/3576915.3623147. https://eprint.iacr.org/2023/108.