Multivariate basic function secret sharing from oblivious transfer

Abstract

Function secret sharing (FSS) is a secret sharing technique for functions in a specific function class, mainly including distributed point function (DPF) and distributed comparison function (DCF). As an important basis for function secret sharing, DPF and DCF are the foundation for the extension of this technique to other more general and complex function classes. However, the function classes corresponding to the current DPF and DCF schemes are almost all unary function classes, and there is no efficient construction for multivariate function classes. The applications of FSS can be extended with the development of a multivariate scheme, e.g., a multi-keyword private information retrieval scheme can be constructed.

To solve this problem, this paper presents a binary DCF scheme based on the “two-layer binary tree” structure. In a binary tree structure, each node computes the seed of its child nodes based on its own seed. The key technique is to realize the transition transfer of seeds by using oblivious transfer, to connect two unary structures. Theoretical analysis and experimental results show that our binary scheme changes from single-round communication in the original definition to multi-round communication, and has great advantages in communication cost and computation efficiency. For the security parameter \lambda and input length n, the key size is reduced from O(\lambda n^2) to O(\lambda n).

In addition, we explore the extensions and applications of the above method. In the batch computation, this paper uses oblivious transfer (OT) extension to realize the one-time transmission of multiple pairs of seeds and optimize its communication efficiency. By extending the structure from “two-layer” to “multi-layer”, a secret sharing scheme of multivariate mixed basic function is proposed based on the serial thought. Furthermore, by employing the parallel thought, a general 2-layer FSS structure from OT for multivariate mixed basic functions is explored to enhance the efficiency, where the first layer is composed of d parallel binary trees with d representing the input dimension, and the second layer is one binary tree of depth d. And the applications of our schemes in multi-keyword private information retrieval are presented.

Graphical abstract

Keywords

function secret sharing / binary distributed comparison function / oblivious transfer / multivariate basic function / private information retrieval

References

[1] Boyle E, Gilboa N, Ishai Y. Function secret sharing. In: Proceedings of the 34th Annual International Conference on the Theory and Applications of Cryptographic Techniques. 2015, 337−367

[2] Gilboa N, Ishai Y. Distributed point functions and their applications. In: Proceedings of the 33rd Annual International Conference on the Theory and Applications of Cryptographic Techniques. 2014, 640−658

[3] Boyle E, Gilboa N, Ishai Y. Function secret sharing: improvements and extensions. In: Proceedings of 2016 ACM SIGSAC Conference on Computer and Communications Security. 2016, 1292−1303

[4] Demmler D, Rindal P, Rosulek M, Trieu N . PIR-PSI: scaling private contact discovery. Proceedings on Privacy Enhancing Technologies, 2018, 2018( 4): 159–178

[5] Doerner J, Shelat A. Scaling ORAM for secure computation. In: Proceedings of 2017 ACM SIGSAC Conference on Computer and Communications Security. 2017, 523−535

[6] Boyle E, Chandran N, Gilboa N, Gupta D, Ishai Y, Kumar N, Rathee M. Function secret sharing for mixed-mode and fixed-point secure computation. In: Proceedings of the 40th Annual International Conference on the Theory and Applications of Cryptographic Techniques. 2021, 871−900

[7] Boyle E, Gilboa N, Ishai Y. Secure computation with preprocessing via function secret sharing. In: Proceedings of the Theory of Cryptography: 17th International Conference. 2019, 341−371

[8] Chor B, Goldreich O, Kushilevitz E, Sudan M. Private information retrieval. In: Proceedings of the 36th IEEE Annual Foundations of Computer Science. 1995, 41−50

[9] Chor B, Kushilevitz E, Goldreich O, Sudan M . Private information retrieval. Journal of the ACM (JACM), 1998, 45( 6): 965–981

[10] Bunn P, Katz J, Kushilevitz E, Ostrovsky R. Efficient 3-party distributed ORAM. In: Proceedings of the Security and Cryptography for Networks: 12th International Conference. 2020, 215−232

[11] de Castro L, Polychroniadou A. Lightweight, maliciously secure verifiable function secret sharing. In: Proceedings of the 41st Annual International Conference on the Theory and Applications of Cryptographic Techniques, Trondheim. 2022, 150−179

[12] Xing P, Li H, Hao M, Chen H, Zeng S. TriFSS: secure trigonometric function evaluation via function secret sharing. In: Proceedings of the IEEE International Conference on Communications. 2023, 1585−1590

[13] Agarwal A, Boyle E, Chandran N, Gilboa N, Gupta D, Ishai Y, Kelkar M, Ma Y. Secure sorting and selection via function secret sharing. In: Proceedings of 2024 on ACM SIGSAC Conference on Computer and Communications Security. 2024, 3023−3037

[14] Beaver D. Efficient multiparty protocols using circuit randomization. In: Feigenbaum J, ed. Advances in Cryptology–CRYPTO. Berlin, Heidelberg: Springer, 1992, 420−432

[15] Canetti R, Lindell Y, Ostrovsky R, Sahai A. Universally composable two-party and multi-party secure computation. In: Proceedings of the 34th Annual ACM Symposium on Theory of Computing. 2002, 494−503

[16] Ishai Y, Prabhakaran M, Sahai A. Founding cryptography on oblivious transfer–efficiently. In: Proceedings of the 28th Annual International Cryptology Conference. 2008, 572−591

[17] Ishai Y, Prabhakaran M, Sahai A. Secure arithmetic computation with no honest majority. In: Proceedings of the 6th Theory of Cryptography Conference on Theory of Cryptography. 2009, 294−314

[18] Naor M, Pinkas B . Oblivious polynomial evaluation. SIAM Journal on Computing, 2006, 35( 5): 1254–1281

[19] Damgård I, Nielsen J B, Nielsen M, Ranellucci S. The TinyTable protocol for 2-party secure computation, or: gate-scrambling revisited. In: Proceedings of the 37th Annual International Cryptology Conference. 2017, 167−187

[20] Ishai Y, Kushilevitz E, Meldgaard S, Orlandi C, Paskin-Cherniavsky A. On the power of correlated randomness in secure computation. In: Proceedings of the 10th Theory of Cryptography Conference on Theory of Cryptography. 2013, 600−620

[21] Fu J, Cheng K, Chang Z, Shen Y . PPA-DBSCAN: privacy-preserving ρ-approximate density-based clustering. IEEE Transactions on Dependable and Secure Computing, 2024, 21( 6): 5324–5340

[22] Rabin M O. How to exchange secrets by oblivious transfer. Number Technical Report TR-81. Harvard University: Aiken Computation Laboratory, 1981

[23] Even S, Goldreich O, Lempel A. A randomized protocol for signing contracts. In: Chaum D, Rivest R L, Sherman A T, eds. Advances in Cryptology: Proceedings of Crypto 82. Boston: Springer, 1983, 205−210

[24] Naor M, Pinkas B. Efficient oblivious transfer protocols. In: Proceedings of the 12th Annual ACM-SIAM Symposium on Discrete Algorithms. 2001, 448−457

[25] Beaver D. Correlated pseudorandomness and the complexity of private computations. In: Proceedings of the 28th Annual ACM Symposium on Theory of Computing. 1996, 479−488

[26] Ishai Y, Kilian J, Nissim K, Petrank E. Extending oblivious transfers efficiently. In: Proceedings of the 23rd Annual International Cryptology Conference. 2003, 145−161

RIGHTS & PERMISSIONS

Higher Education Press