International Association for Cryptologic Research

International Association
for Cryptologic Research


Half-Tree: Halving the Cost of Tree Expansion in COT and DPF

Xiaojie Guo , State Key Laboratory of Cryptology, Nankai University
Kang Yang , State Key Laboratory of Cryptology
Xiao Wang , Northwestern University
Wenhao Zhang , Northwestern University
Xiang Xie , Shanghai Qi Zhi Institute, PADO Labs
Jiang Zhang , State Key Laboratory of Cryptology
Zheli Liu , Nankai University
DOI: 10.1007/978-3-031-30545-0_12 (login may be required)
Search ePrint
Search Google
Presentation: Slides
Conference: EUROCRYPT 2023
Abstract: GGM tree is widely used in designing correlated oblivious transfer (COT), subfield vector oblivious linear evaluation (sVOLE), distributed point function (DPF), and distributed comparison function (DCF). Often, the computation and communication cost associated with GGM tree is the major cost in these protocols. In this paper, we propose a suite of optimizations that can reduce this cost by half. - Halving the cost of COT and sVOLE. Our basic protocol introduces extra correlation in each level of a GGM tree used by the state-of-the-art COT protocol. As a result, it reduces the number of AES calls and the communication by half. Extending the idea to sVOLE, we are able to achieve similar improvement with either halved computation or halved communication. - Halving the cost of DPF and DCF. We propose improved two-party protocols for distributed generation of DPF/DCF keys. Our tree structures behind these protocols lead to more efficient full-domain evaluation and halve the communication and the round complexity of the state-of-the-art DPF/DCF protocols. All protocols are provably secure in the random-permutation model and can be accelerated based on fixed-key AES-NI. We also improve the state-of-the-art schemes of puncturable pseudorandom function (PPRF), DPF, and DCF, which are of independent interest in dealer-available scenarios.
  title={Half-Tree: Halving the Cost of Tree Expansion in COT and DPF},
  author={Xiaojie Guo and Kang Yang and Xiao Wang and Wenhao Zhang and Xiang Xie and Jiang Zhang and Zheli Liu},