libdpf/doc/pages/bibliography.md

Bibliography

Each paper is listed once. An ePrint number anywhere else in the manual links here. Used in points back at the pages that rely on that paper.

ePrint PDFs that IACR posts are cached next to these pages. Publisher PDFs from Springer, ACM, and USENIX are not.

[Point functions](@ref bib_sec_point) · [Generation and OT](@ref bib_sec_ot) · [Comparisons and proofs](@ref bib_sec_cmp) · [Three parties](@ref bib_sec_three) · [Grotto](@ref bib_sec_grotto) · [Protocols](@ref bib_sec_protocols)

Point functions and trees

Improvements and extensions

Elette Boyle, Niv Gilboa, and Yuval Ishai. Function Secret Sharing: Improvements and Extensions. ACM CCS 2016, pp. 1292–1303. Full version, 24 July 2018. ePrint 2018/707 · PDF

The point-function key make_dpf follows. Remark 3.4 is the early-stop packing: the last ν = log2(λ / log2|G|) levels are a lane inside the leaf, not correction words.

Used in [First program](@ref basics) · [Evaluation](@ref evaluation) · [Guided tour](@ref tour_eval)

Function Secret Sharing (2015)

Elette Boyle, Niv Gilboa, and Yuval Ishai. Function Secret Sharing. EUROCRYPT 2015, LNCS 9057, pp. 337–367. Publisher

The 4n(λ+1)-bit key named in the manual, as recorded in the bibliography of ePrint 2018/707. This library does not generate that key.

Used in [First program](@ref basics) · [Evaluation](@ref evaluation)

Half-Tree

Xiaojie Guo, Kang Yang, Xiao Wang, Wenhao Zhang, Xiang Xie, Jiang Zhang, and Zheli Liu. Half-Tree: Halving the Cost of Tree Expansion in COT and DPF. ePrint 2022/1431 · PDF

prg::aes128_ccr selects their dealer point-key expand. Section 5.2 is a different object: two-party key generation in the COT/OLE hybrid.

Used in [First program](@ref dpf_trees) · [Evaluation](@ref evaluation) · [Guided tour](@ref tour_trees)

Information-theoretic DPF

Elette Boyle, Niv Gilboa, Yuval Ishai, and Victor I. Kolobov. Information-Theoretic Distributed Point Functions. ePrint 2023/028 · PDF

A statistically private 3-server DPF. make_it_dpf3 is the additive interface on a uint8_t domain, not the 2-party PRG key.

Used in [Multiparty](@ref multiparty) · [Three-server PIR](@ref app_pir3) · [Evaluation](@ref it_dpf3)

Distributed point functions (2014)

Niv Gilboa and Yuval Ishai. Distributed Point Functions and Their Applications. EUROCRYPT 2014, LNCS 8441, pp. 640–658. Publisher

Two-server keyword PIR from a point function on the keyword.

Used in [Keyword PIR](@ref app_keyword)

Generation and oblivious transfer

Scaling ORAM

Jack Doerner and abhi shelat. Scaling ORAM for Secure Computation. ACM CCS 2017, pp. 523–535. ePrint 2017/827 · PDF

The per-level correction-word opening. geneval_* uses that opening on the public query and does not return their reusable key. Floram's secret read and write are the same opening.

Used in [Dealer-free keygen](@ref dealer_free) · [Guided tour](@ref tour_ds) · [Floram](@ref app_floram)

IKNP OT extension

Yuval Ishai, Joe Kilian, Kobbi Nissim, and Erez Petrank. Extending Oblivious Transfers Efficiently. CRYPTO 2003, LNCS 2729, pp. 145–161. Publisher

The semi-honest OT extension dpf::iknp::sample follows: κ base OTs, then a correlation-robust hash of the transposed matrix. IKNP is these four authors.

Used in [Dealer-free keygen](@ref dealer_free) · [Guided tour](@ref tour_iknp)

Simplest OT

Tung Chou and Claudio Orlandi. The Simplest Protocol for Oblivious Transfer. LATINCRYPT 2015. Full version: ePrint 2015/267 · PDF

The P-256 base OT under dpf::iknp (base_sender / base_receiver).

Used in [Guided tour](@ref tour_iknp)

AES S-box circuit

Joan Boyar and René Peralta. A depth-16 circuit for the AES S-box. ePrint 2011/332 · PDF

The 32-AND SubBytes used by party/oblivious_hash.hpp (aes_bp::and_count = 32).

Used in [Guided tour](@ref tour_iknp) · [Evaluation](@ref evaluation)

Comparisons, proofs, and products

Mixed-mode FSS

Elette Boyle, Nishanth Chandran, Niv Gilboa, Divya Gupta, Yuval Ishai, Nishant Kumar, and Mayank Rathee. Function Secret Sharing for Mixed-Mode and Fixed-Point Secure Computation. EUROCRYPT 2021, LNCS 12697, pp. 871–900. ePrint 2020/1392 · PDF

The distributed comparison function, and Figure 3's one-DCF public interval.

Used in [Comparisons](@ref comparisons) · [Evaluation](@ref evaluation) · [Guided tour](@ref tour_dcf)

Verifiable FSS

Leo de Castro and Antigoni Polychroniadou. Lightweight, Maliciously Secure Verifiable Function Secret Sharing. EUROCRYPT 2022, pp. 150–179. ePrint 2021/580 · PDF

The 4λ-bit correction seeds and 2λ-bit proof token, and §4's κ = 3 cuckoo packing. make_multipoint follows this GGM multi-point. S&P 2025 (Boyle, Gilboa, Hamilis, Ishai, and Tu) packs those bucket keys from a PCG seed. That packing is not a multipoint_params tweak and is not implemented here.

Used in [Verifiability](@ref verifiability) · [Multipoint](@ref multipoint_keys) · [Keyword PIR](@ref app_keyword) · [PSI](@ref app_psi)

ABY2.0

Arpita Patra, Thomas Schneider, Ajith Suresh, and Hossein Yalame. ABY2.0: Improved Mixed-Protocol Secure Two-Party Computation. USENIX Security 2021. Full version: ePrint 2020/1225 · PDF

One public reconstruction per newly opened wire.

Used in [Beaver triples](@ref beaver_triples) · [Arithmetic share runtime](@ref arith_runtime) · [Guided tour](@ref tour_beaver)

ABY

Daniel Demmler, Thomas Schneider, and Michael Zohner. ABY — A Framework for Efficient Mixed-Protocol Secure Two-Party Computation. NDSS 2015. ePrint 2014/386

Arithmetic / boolean / Yao sharing and conversions.

Used in [Arithmetic share runtime](@ref arith_runtime) · [A boolean function of a leaf](@ref yao_leaf)

Half-gates

Samee Zahur, Mike Rosulek, and David Evans. Two Halves Make a Whole: Reducing Data Transfer in Garbled Circuits using Half Gates. EUROCRYPT 2015. ePrint 2014/756

Free-XOR AND rows. yao::session sends two blocks per AND.

Used in [A boolean function of a leaf](@ref yao_leaf) · [Arithmetic share runtime](@ref arith_runtime)

Garbling gadgets

Marshall Ball, Tal Malkin, and Mike Rosulek. Garbling Gadgets for Boolean and Arithmetic Circuits. CCS 2016. ePrint 2016/969

Free addition and public scaling in (Z_m)^k, and a unary projection of m − 1 ciphertexts. A fan-in-b symmetric gate is a projection of the sum. arith_garble.hpp is this gadget. The session in beaver.hpp stays the interactive one-open product.

Used in [Beaver triples](@ref beaver_triples) · [Arithmetic share runtime](@ref arith_runtime)

Stacked garbling

David Heath and Vladimir Kolesnikov. Stacked Garbling: Garbled Circuit Proportional to Longest Execution Path. CRYPTO 2020. ePrint 2020/973

One XOR-stack of the branch materials. Inactive branches are rebuilt from seeds.

Used in [A boolean function of a leaf](@ref yao_leaf)

One-hot garbling

David Heath and Vladimir Kolesnikov. One Hot Garbling. CCS 2021.

The same stack over k branches. The demux carries the inactive seeds.

Used in [A boolean function of a leaf](@ref yao_leaf)

FLUTE

Andreas Brüggemann, Robin Hundt, Thomas Schneider, Ajith Suresh, and Hossein Yalame. FLUTE: Fast and Secure Lookup Table Evaluations. IEEE S&P 2023. ePrint 2023/499

A public LUT is a multi-fan-in inner product on ABY2.0 masked bits. Online cost is two bits per output bit.

Used in [Beaver triples](@ref beaver_triples) · [Arithmetic share runtime](@ref arith_runtime)

ABY3

Payman Mohassel and Peter Rindal. ABY3: A Mixed Protocol Framework for Machine Learning. CCS 2018. ePrint 2018/403

Honest-majority 3PC, RSS, probabilistic truncation, matrix triples.

Used in [Arithmetic share runtime](@ref arith_runtime)

edaBits / CrypTFlow2

Daniel Escudero, Satrajit Ghosh, Marcel Keller, Rahul Rachuri, and Peter Scholl. Improved Primitives for MPC over Mixed Arithmetic-Binary Circuits. CRYPTO 2020. ePrint 2020/338

Used in [Arithmetic share runtime](@ref arith_runtime) · [A boolean function of a leaf](@ref yao_leaf)

EzPC

Nishanth Chandran, Divya Gupta, Aseem Rastogi, Rahul Sharma, and Shardul Tripathi. EzPC: Programmable and Efficient Secure Two-Party Computation for Machine Learning. EuroS&P 2019. ePrint 2017/1109

Used in [Arithmetic share runtime](@ref arith_runtime)

Gilboa multiplication

Niv Gilboa. Two Party RSA Key Generation. CRYPTO 1999, LNCS 1666, pp. 116–129.

Used in [Arithmetic share runtime](@ref arith_runtime)

Sharemind

Dan Bogdanov, Sven Laur, and Jan Willemson. Sharemind: A Framework for Fast Privacy-Preserving Computations. ESORICS 2008, LNCS 5283, pp. 192–206.

Used in [Arithmetic share runtime](@ref arith_runtime)

Beaver triples

Donald Beaver. Efficient Multiparty Protocols Using Circuit Randomization. CRYPTO 1991, LNCS 576, pp. 420–432. Publisher

The two-opening product triple, not the ABY2.0 session.

Used in [Beaver triples](@ref beaver_triples) · [Guided tour](@ref tour_beaver)

Bit commitment

Moni Naor. Bit Commitment Using Pseudorandomness. Journal of Cryptology 4(2), 1991, pp. 151–158. Publisher

dpf::ppvc binds each DPF root with this string commitment: G(r) XOR A*rho, under a public matrix A.

Used in [Programmable vectors](@ref ppvc_manual)

Three evaluators

Three-party DPF

Guy Zyskind, Avishay Yanai, and Alex "Sandy" Pentland. High-Throughput Three-Party DPFs with Applications to ORAM and Digital Currencies. ePrint 2024/1658 · PDF

Figure 3: each evaluator key is a pair of (2,2)-VDPF+ keys.

Used in [Multiparty](@ref multiparty) · [Guided tour](@ref tour_dpf3) · [Three-server PIR](@ref app_pir3) · [(2,3) ledger](@ref app_ledger23)

Grotto

Grotto

Kyle Storrier, Adithya Vadapalli, Allan Lyons, and Ryan Henry. Grotto: Screaming fast (2+1)-PC for Z_2ⁿ via (2,2)-DPFs. ePrint 2023/108 · PDF

Prefix parity along one key, and Appendix D's degree-0 exact tables. Offset Horner is not that piecewise-polynomial construction.

Used in [Grotto](@ref jet_and_ring) · [Guided tour](@ref tour_grotto)

Wave Hello

José Reis, Mehmet Ugurbil, Sameer Wagh, Ryan Henry, and Miguel de Vega. Wave Hello to Privacy: Efficient Mixed-Mode MPC using Wavelet Transforms. PoPETs 2025(2), pp. 697–718. Publisher · ePrint 2025/013 · PDF

Equations (7) and (8) are the cleartext Haar and bior(5,3) lookup. make_haar_dwt_lut and make_bior53_dwt_lut evaluate those tables. The online phase pairs Haar with a deterministic Pika truncation and bior(5,3) with segment parity.

Used in [Wavelet lookup tables](@ref dwt_luts) · [Guided tour](@ref tour_grotto)

Protocols

Duoram

Adithya Vadapalli, Ryan Henry, and Ian Goldberg. Duoram: A Bandwidth-Efficient Distributed ORAM for 2- and 3-Party Computation. USENIX Security 2023. USENIX

The 3-party read and update: unit DPFs at a random index, a cyclic shift by the opened offset, and a dot product with the memory.

Used in [3-party Duoram](@ref app_duoram)

BitMore

Syed Mahbub Hafiz and Ryan Henry. A Bit More Than a Bit Is More Than a Bit Better. PoPETs 2019(4), pp. 112–131. Publisher

Section 5.2 is the 2^L-server query: L independent 1-bit DPFs, one key per label bit.

Used in [BitMore](@ref app_bitmore)

Prio

Henry Corrigan-Gibbs and Dan Boneh. Prio: Private, Robust, and Scalable Computation of Aggregate Statistics. NSDI 2017, pp. 259–282. USENIX

The frequency count is a one-hot encoding. dpf::field64 is this paper's Field64, via libprio.

Used in [Prio](@ref app_prio)

Poplar

Dan Boneh, Elette Boyle, Henry Corrigan-Gibbs, Niv Gilboa, and Yuval Ishai. Lightweight Techniques for Private Heavy Hitters. ePrint 2021/017

The incremental DPF on prefixes of one secret string. EvaluateUntil is eval_until. Mastic is this prefix walk with a weight payload.

Used in [Prio](@ref app_prio) · [I-DPF max and k-th](@ref app_idpf_agg) · [Mastic](@ref app_mastic) · [Guided tour](@ref tour_eval)

Incremental aggregation

Nan Cheng, Aikaterini Mitrokotsa, Feng Zhang, and Frank Hartmann. Efficient Two-Party Secure Aggregation via Incremental Distributed Point Function. ePrint 2024/1190

Communication tracks the bit length of the domain. The max and k-th walks are idpf_agg_max and idpf_agg_kth.

Used in [I-DPF max and k-th](@ref app_idpf_agg)

LLAMA

Kanav Gupta, Deepak Kumaraswamy, Nishanth Chandran, and Divya Gupta. LLAMA: A Low Latency Math Library for Secure Inference. ePrint 2022/793

Offset comparison and spline gates.

Used in [LLAMA](@ref app_llama)

Pika

Sameer Wagh. Pika: Secure Computation using Function Secret Sharing over Rings. PoPETs 2022(4), pp. 351–377. Publisher

Figure 1 is the unit-DPF table lookup.

Used in [Pika](@ref app_pika)

Express

Saba Eskandarian, Henry Corrigan-Gibbs, Matei Zaharia, and Dan Boneh. Express: Lowering the Cost of Metadata-hiding Communication with Cryptographic Privacy. USENIX Security 2021, pp. 1775–1792. USENIX

Section 3.1 is the DPF mailbox write.

Used in [Express](@ref app_express) · [Sabre](@ref app_sabre)

PRAC

Sajin Sasy, Adithya Vadapalli, and Ian Goldberg. PRAC: Round-Efficient 3-Party MPC for Dynamic Data Structures. ePrint 2023/1897

One incremental DPF replaces the lg n point keys of a binary search. A wide leaf updates a heap node and both children.

Used in [PRAC](@ref app_prac)

Splinter

Frank Wang, Catherine Yun, Shafi Goldwasser, Vinod Vaikuntanathan, and Matei Zaharia. Splinter: Practical Private Queries on Public Data. NSDI 2017. USENIX

A unit DPF selects one public group. The server dots that selector with a pre-aggregated column.

Used in [Splinter](@ref app_splinter)

Waldo

Emma Dauterman, Mayank Rathee, Raluca Ada Popa, and Ion Stoica. Waldo: A Private Time-Series Database from Function Secret Sharing. IEEE S&P 2022. ePrint 2021/1661

Append-only unit DPFs, and a comparison inner product for a secret threshold.

Used in [Waldo](@ref app_waldo)

Sabre

Adithya Vadapalli, Kyle Storrier, and Ryan Henry. Sabre: Sender-Anonymous Messaging with Fast Audits. IEEE S&P 2022.

The write is Express's full-domain add. The audit is a verifiable DPF proof instead of Express's fp61 sketch.

Used in [Sabre](@ref app_sabre)

Batched OPRF / PSI

Vladimir Kolesnikov, Ranjit Kumaresan, Mike Rosulek, and Ni Trieu. Efficient Batched Oblivious PRF with Applications to Private Set Intersection. ACM CCS 2016. ePrint 2016/799

Membership as an oblivious PRF. On this domain the PRF table is public and each receiver element is a unit DPF.

Used in [Private set intersection](@ref app_psi)

Private SUBLEQ

Jiang and Henry. MSc thesis, University of Calgary. A subtract-and-branch instruction for private function evaluation. The DPF work is a prepaid wildcard unit vector, rotated once the address is opened.

Used in [MPC SUBLEQ](@ref app_subleq)

\htmlonly

TL;DR. The point key is ePrint 2018/707, not the longer EUROCRYPT 2015 key. Proofs and cuckoo multipoint are 2021/580. Comparisons are 2020/1392. The dealer-free opening is 2017/827, and the pads are IKNP plus the 2015/267 base OT. Three-party spines are 2024/1658. The information-theoretic table is 2023/028. Grotto is 2023/108.

\endhtmlonly