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, a research team led by Yanqing YAO published their new research on 15 October 2025 in Frontiers of Computer Science co-published by Higher Education Press and Springer Nature.
In the research, they implement the binary DPF simply by concatenating two input strings to a long input and then calling the unary DPF scheme. More importantly, in terms of DCF, they presents a new “two-layer binary tree” structure for constructing binary DCF. In this structure, the OT protocol acts as a “bridge” to connect the layers. According to the output of the binary tree in the first layer, the corresponding initial seed is passed to the next layer. Then the parties use the new initial seed to generate a new binary tree in the second layer and get the final output. Theoretical analysis and experimental results show that their 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 λ and input length n, the key size is reduced from O(λn²) to O(λn).
In addition, they explore the extensions and applications of the above method. In the batch computation, they uses 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 “multilayer”, a secret sharing scheme of multivariate mixed basic function is proposed based on the serial thought. Furthermore, by employing the parallel thought, they explore a general 2-layer FSS structure from OT for multivariate mixed basic functions to enhance the efficiency, where the first layer is composed of d parallel binary trees by employing the parallel method and the second layer is composed of one binary tree of depth d. Similarly, the OT protocol is used to transfer the new initial seeds between the first layer and the second layer.
They give the applications of their schemes in 2-server multi-keyword private information retrieval, including private multiple keywords search based on multivariate DPF as well as generalized multiple keywords search based on multivariate mixed basic function secret sharing (e.g., counting the number of multi-keywords that lie in multi-range).
Future work can focus on constructing more efficient binary/multivariate basic FSS with a simple one-round communication (or no interactive communication rounds), improving the definition and concrete construction of binary distributed comparison function by deleting the OT protocol tool, and increasing the range of function classes for secure complex computation.
DOI: 10.1007/s11704-025-40919-y