International Association
for Cryptologic Research

Correlated randomness lies at the core of efficient modern secure multi-party computation (MPC) protocols. Costs of generating such correlated randomness required for the MPC online phase protocol often constitute a bottleneck in the overall protocol. A recent paradigm of {\em pseudorandom correlation generator} (PCG) initiated by Boyle et al. (CCS'18, Crypto'19) offers an appealing solution to this issue. In sketch, each party is given a short PCG seed, which can be locally expanded into long correlated strings, satisfying the target correlation. Among various types of correlations, there is oblivious linear evaluation (OLE), a fundamental and useful primitive for typical MPC protocols on arithmetic circuits. Towards efficient generating a great amount of OLE, and applications to MPC protocols, we establish the following results: (i) We propose a novel {\em programmable} PCG construction for OLE over any field $\Fp$. For $kN$ OLE correlations, we require $O(k\log{N})$ communication and $O(k^2N\log{N})$ computation, where $k$ is an arbitrary integer $\geq 2$. Previous works either have quadratic computation (Boyle et al. Crypto'19), or can only support fields of size larger than $2$ (Bombar et al. Crypto'23). (ii) We extend the above OLE construction to provide various types of correlations for any finite field. One of the fascinating applications is an efficient PCG for two-party {\em authenticated Boolean multiplication triples}. For $kN$ authenticated triples, we offer PCGs with seed size of $O(k^2\log{N})$ bits. To our best knowledge, such correlation has not been efficiently realized with sublinear communication ever before. (iii) In addition, the {\em programmability} admits efficient PCGs for multi-party Boolean triples, and thus the first efficient MPC protocol for Boolean circuits with {\em silent} preprocessing. In particular, we show $kN$ $m$-party Boolean multiplication triples can be generated in $O(m^2k\log{N})$-bit communication, while the state-of-the-art FOLEAGE (Asiacrypt'24) requires a broadcast channel and takes $mkN+O(m^2\log{kN})$ bits communication. (iv) Finally, we present efficient PCGs for circuit-dependent preprocessing, matrix multiplications triples, and string OTs etc. Compared to previous works, each has its own right.

Function secret sharing (FSS) for a class $\cF$ 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 $\cF$ 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 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. \begin{itemize} \item \emph{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. \item \emph{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. For branching programs our FSS constructions show considerably improved run time 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. \item \emph{New feasibility.} 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. \item \emph{Applications.} We outline applications of our FSS constructions including pattern matching with wild cards, image matching, nearest neighbor search and regular expression matching. \end{itemize}

In this paper, we propose a new general construction to reduce the public key size of McEliece cryptosystems constructed from automorphism-induced Goppa codes. In particular, we generalize the ideas of automorphism-induced Goppa codes by considering nontrivial subsets of automorphism groups to construct Goppa codes with a nice block structure. By considering additive and multiplicative automorphism subgroups, we provide explicit constructions to demonstrate our technique. We show that our technique can be applied to automorphism-induced Goppa codes based cryptosystems to further reduce their key sizes.