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

Xiaojie Guo; Kang Yang; Xiao Wang; Wenhao Zhang; Xiang Xie; Jiang Zhang; Zheli Liu

doi:10.1007/978-3-031-30545-0_12

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

Xiaojie Guo, Kang Yang^*, Xiao Wang, Wenhao Zhang, Xiang Xie, Jiang Zhang, Zheli Liu

^*Corresponding author for this work

Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

9 Scopus citations

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.

Original language	English (US)
Title of host publication	Advances in Cryptology – EUROCRYPT 2023 - 42nd Annual International Conference on the Theory and Applications of Cryptographic Techniques, Proceedings
Editors	Carmit Hazay, Martijn Stam
Publisher	Springer Science and Business Media Deutschland GmbH
Pages	330-362
Number of pages	33
ISBN (Print)	9783031305443
DOIs	https://doi.org/10.1007/978-3-031-30545-0_12
State	Published - 2023
Event	42nd Annual International Conference on the Theory and Applications of Cryptographic Techniques, Eurocrypt 2023 - Lyon, France Duration: Apr 23 2023 → Apr 27 2023

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	14004 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	42nd Annual International Conference on the Theory and Applications of Cryptographic Techniques, Eurocrypt 2023
Country/Territory	France
City	Lyon
Period	4/23/23 → 4/27/23

Funding

Acknowledgements. Work of Kang Yang is supported by the National Key Research and Development Program of China (Grant No. 2022YFB2702000), and by the National Natural Science Foundation of China (Grant Nos. 62102037, 61932019). Work of Xiao Wang is supported by DARPA under Contract No. HR001120C0087, NSF award #2016240, #2236819, and research awards from Meta and Google. The views, opinions, and/or findings expressed are those of the author(s) and should not be interpreted as representing the official views or policies of the Department of Defense or the U.S. Government. Work of Jiang Zhang is supported by the National Key Research and Development Program of China (Grant No. 2022YFB2702000), and by the National Natural Science Foundation of China (Grant Nos. 62022018, 61932019). Work of Zheli Liu is supported by the National Natural Science Foundation of China (Grant No. 62032012).

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

Access to Document

10.1007/978-3-031-30545-0_12

Cite this

Guo, X., Yang, K., Wang, X., Zhang, W., Xie, X., Zhang, J., & Liu, Z. (2023). Half-Tree: Halving the Cost of Tree Expansion in COT and DPF. In C. Hazay, & M. Stam (Eds.), Advances in Cryptology – EUROCRYPT 2023 - 42nd Annual International Conference on the Theory and Applications of Cryptographic Techniques, Proceedings (pp. 330-362). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 14004 LNCS). Springer Science and Business Media Deutschland GmbH. https://doi.org/10.1007/978-3-031-30545-0_12

Guo, Xiaojie ; Yang, Kang ; Wang, Xiao et al. / Half-Tree : Halving the Cost of Tree Expansion in COT and DPF. Advances in Cryptology – EUROCRYPT 2023 - 42nd Annual International Conference on the Theory and Applications of Cryptographic Techniques, Proceedings. editor / Carmit Hazay ; Martijn Stam. Springer Science and Business Media Deutschland GmbH, 2023. pp. 330-362 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{6a35c5aa97cb49218a88452f82b59688,

title = "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.",

author = "Xiaojie Guo and Kang Yang and Xiao Wang and Wenhao Zhang and Xiang Xie and Jiang Zhang and Zheli Liu",

note = "Publisher Copyright: {\textcopyright} 2023, International Association for Cryptologic Research.; 42nd Annual International Conference on the Theory and Applications of Cryptographic Techniques, Eurocrypt 2023 ; Conference date: 23-04-2023 Through 27-04-2023",

year = "2023",

doi = "10.1007/978-3-031-30545-0_12",

language = "English (US)",

isbn = "9783031305443",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Science and Business Media Deutschland GmbH",

pages = "330--362",

editor = "Carmit Hazay and Martijn Stam",

booktitle = "Advances in Cryptology – EUROCRYPT 2023 - 42nd Annual International Conference on the Theory and Applications of Cryptographic Techniques, Proceedings",

address = "Germany",

}

Guo, X, Yang, K, Wang, X, Zhang, W, Xie, X, Zhang, J & Liu, Z 2023, Half-Tree: Halving the Cost of Tree Expansion in COT and DPF. in C Hazay & M Stam (eds), Advances in Cryptology – EUROCRYPT 2023 - 42nd Annual International Conference on the Theory and Applications of Cryptographic Techniques, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 14004 LNCS, Springer Science and Business Media Deutschland GmbH, pp. 330-362, 42nd Annual International Conference on the Theory and Applications of Cryptographic Techniques, Eurocrypt 2023, Lyon, France, 4/23/23. https://doi.org/10.1007/978-3-031-30545-0_12

Half-Tree: Halving the Cost of Tree Expansion in COT and DPF. / Guo, Xiaojie; Yang, Kang; Wang, Xiao et al.
Advances in Cryptology – EUROCRYPT 2023 - 42nd Annual International Conference on the Theory and Applications of Cryptographic Techniques, Proceedings. ed. / Carmit Hazay; Martijn Stam. Springer Science and Business Media Deutschland GmbH, 2023. p. 330-362 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 14004 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - Half-Tree

T2 - 42nd Annual International Conference on the Theory and Applications of Cryptographic Techniques, Eurocrypt 2023

AU - Guo, Xiaojie

AU - Yang, Kang

AU - Wang, Xiao

AU - Zhang, Wenhao

AU - Xie, Xiang

AU - Zhang, Jiang

AU - Liu, Zheli

PY - 2023

Y1 - 2023

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

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

UR - http://www.scopus.com/inward/record.url?scp=85161434154&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85161434154&partnerID=8YFLogxK

U2 - 10.1007/978-3-031-30545-0_12

DO - 10.1007/978-3-031-30545-0_12

M3 - Conference contribution

AN - SCOPUS:85161434154

SN - 9783031305443

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 330

EP - 362

BT - Advances in Cryptology – EUROCRYPT 2023 - 42nd Annual International Conference on the Theory and Applications of Cryptographic Techniques, Proceedings

A2 - Hazay, Carmit

A2 - Stam, Martijn

PB - Springer Science and Business Media Deutschland GmbH

Y2 - 23 April 2023 through 27 April 2023

ER -

Guo X, Yang K, Wang X, Zhang W, Xie X, Zhang J et al. Half-Tree: Halving the Cost of Tree Expansion in COT and DPF. In Hazay C, Stam M, editors, Advances in Cryptology – EUROCRYPT 2023 - 42nd Annual International Conference on the Theory and Applications of Cryptographic Techniques, Proceedings. Springer Science and Business Media Deutschland GmbH. 2023. p. 330-362. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-031-30545-0_12