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

##### Abstract

GGM tree is widely used in the design of correlated oblivious transfer (COT), subfield vector oblivious linear evaluation (sVOLE), distributed point function (DPF), and distributed comparison function (DCF). Often, the cost associated with GGM tree dominates the computation and communication of 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 COT protocol introduces extra correlation to each level of a GGM tree used by the state-of-the-art COT protocol. As a result, it reduces both the number of AES calls and the communication by half. Extending this 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 the 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.

Available format(s)
Category
Cryptographic protocols
Publication info
A major revision of an IACR publication in EUROCRYPT 2023
Keywords
Correlated Oblivious TransferSubfield Vector OLEDistributed Point FunctionDistributed Comparison Function
Contact author(s)
xiaojie guo @ mail nankai edu cn
yangk @ sklc org
wangxiao @ cs northwestern edu
wenhao zhang @ northwestern edu
xiexiangiscas @ gmail com
jiangzhang09 @ gmail com
liuzheli @ nankai edu cn
History
2023-03-07: last of 4 revisions
See all versions
Short URL
https://ia.cr/2022/1431

CC BY

BibTeX

@misc{cryptoeprint:2022/1431,
author = {Xiaojie Guo and Kang Yang and Xiao Wang and Wenhao Zhang and Xiang Xie and Jiang Zhang and Zheli Liu},
title = {Half-Tree: Halving the Cost of Tree Expansion in COT and DPF},
howpublished = {Cryptology ePrint Archive, Paper 2022/1431},
year = {2022},
note = {\url{https://eprint.iacr.org/2022/1431}},
url = {https://eprint.iacr.org/2022/1431}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.