Paper 2024/192

Direct FSS Constructions for Branching Programs and More from PRGs with Encoded-Output Homomorphism

Elette Boyle, Reichman University, NTT Research
Lisa Kohl, Centrum Wiskunde & Informatica
Zhe Li, Centrum Wiskunde & Informatica
Peter Scholl, Aarhus University

Function secret sharing (FSS) for a class $\cal{F}$ allows to split a secret function $f \in \cal{F}$ into (succinct) secret shares $f_0,f_1$, such that for all $x\in \{0,1\}^n$ it holds $f_0(x)-f_1(x)=f(x)$. FSS has numerous applications, including private database queries, nearest neighbour search, private heavy hitters and secure computation in the preprocessing model, where the supported class $\cal{F}$ translates to richness in the application. Unfortunately, concretely efficient FSS constructions are only known for very limited function classes. In this work we introduce the notion of pseudorandom generators with encoded-output homomorphism (EOH-PRGs), and give direct FSS constructions for bit-fixing predicates, branching programs and more based on this primitive. Further, we give constructions of FSS for deterministic finite automatas (DFAs) from a KDM secure variant of EOH-PRGs. - New abstractions. Following the work of Alamati et al.(EUROCRYPT '19), who classify minicrypt primitives with algebraic structure and their applications, we capture the essence of our FSS constructions in the notion of EOH-PRG, paving the road towards future efficiency improvements via new instantiations of this primitive. The abstraction of EOH-PRG and its instantiations may be of independent interest, as it is an approximate substitution of an ideal homomorphic PRG. - Better efficiency. We show that EOH-PRGs can be instantiated from LWE and a small-exponent variant of the DCR assumption. A theoretical analysis of our instantiations suggest efficiency improvements over the state of the art both in terms of key size and evaluation time: We show that our FSS instantiations lead to smaller key sizes, improving over previous constructions by a factor of $3.5$ and more. While for bit-fixing predicates our FSS constructions show comparable or mildly improved run time (depending on the instantiation), we achieve considerable improvements for branching programs by avoiding the expensive generic transformation via universal circuits, shaving off a factor of $w$ and more in the number of abstract operations, where $w$ corresponds to an upper bound on the width of the underlying class of branching programs. - New constructions. We show that our instantiations of EOH-PRGs additionally support a form of KDM-security, without requiring an additional circular-security assumption. Based on this, we give the first FSS construction for DFAs which supports the evaluation of inputs of a-priori unbounded length without relying on FHE. - Applications. We outline applications of our FSS constructions including pattern matching with wild cards, image matching, nearest neighbor search and regular expression matching.

Available format(s)
Cryptographic protocols
Publication info
FSSFunction Secret SharingBranching ProgramsDFABit-fixing Predicates
Contact author(s)
eboyle @ alum mit edu
Lisa Kohl @ cwi nl
lizh0048 @ e ntu edu sg
Peter Scholl @ cs au dk
2024-02-09: approved
2024-02-08: received
See all versions
Short URL
Creative Commons Attribution


      author = {Elette Boyle and Lisa Kohl and Zhe Li and Peter Scholl},
      title = {Direct {FSS} Constructions for Branching Programs and More from {PRGs} with Encoded-Output Homomorphism},
      howpublished = {Cryptology ePrint Archive, Paper 2024/192},
      year = {2024},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.