What a lovely hat

Multiparty computation (MPC) is an important field of cryptography that deals with protecting the privacy of data, while allowing to do computation on that data. A key part of MPC is the parties involved having correlated randomness that they can use to make the computation or the communication between themselves more efficient, while still preserving the privacy of the data. Examples of these correlations include random oblivious transfer (OT) correlations, oblivious linear-function...

A prominent countermeasure against side channel attacks, the hiding countermeasure, typically involves shuffling operations using a permutation algorithm. Especially in the era of Post-Quantum Cryptography, the importance of the hiding coun- termeasure is emphasized due to computational characteristics like those of lattice and code-based cryptography. In this context, swiftly and securely generating permutations has a critical impact on an algorithm’s security and efficiency. The widely...

Servan-Schreiber et al. (S&P 2023) presented a new notion called private access control lists (PACL) for function secret sharing (FSS), where the FSS evaluators can ensure that the FSS dealer is authorized to share the given function. Their construction relies on costly non-interactive secret-shared proofs and is not secure in post-quantum setting. We give a construction of PACL from publicly verifiable secret sharing (PVSS) under short integer solution (SIS). Our construction adapts the...

We present a variant of Function Secret Sharing (FSS) schemes tailored for point, comparison, and interval functions, featuring compact key sizes at the expense of additional comparison. While existing FSS constructions are primarily geared towards $2$-party scenarios, exceptions such as the work by Boyle et al. (Eurocrypt 2015) and Riposte (S&P 2015) have introduced FSS schemes for $p$-party scenarios ($p \geq 3$). This paper aims to achieve the most compact $p$-party FSS key size to date....

Neural network inference as a service enables a cloud server to provide inference services to clients. To ensure the privacy of both the cloud server's model and the client's data, secure neural network inference is essential. Binarized neural networks (BNNs), which use binary weights and activations, are often employed to accelerate inference. However, achieving secure BNN inference with secure multi-party computation (MPC) is challenging because MPC protocols cannot directly operate on...

Structure-Aware Private Set Intersection (sa-PSI), recently introduced by Garimella et al. (Crypto'22), is a PSI variant where Alice's input set $S_A$ has a publicly known structure (for example, interval, ball or union of balls) and Bob's input $S_B$ is an unstructured set of elements. Prior work achieves sa-PSI where the communication cost only scales with the description size of $S_A$ instead of the set cardinality. However, the computation cost remains linear in the cardinality of $S_A$,...

A function secret sharing (FSS) scheme ($\mathsf{gen},\mathsf{eval}$) for a class of programs $\mathcal{F}$ allows a dealer to secret share any function $f \in \mathcal{F}$, such that each function share hides the function, and the shares can be used to non-interactively compute additive shares of $f(x)$ for any input $x$. All FSS related applications often requires the dealer to generate and share secret sharings for a batch of functions. We initiate the study of batched function secret...

A function secret sharing (FSS) (Boyle et al., Eurocrypt 2015) is a cryptographic primitive that enables additive secret sharing of functions from a given function family $\mathcal{F}$. FSS supports a wide range of cryptographic applications, including private information retrieval (PIR), anonymous messaging systems, private set intersection and more. Formally, given positive integers $r \geq 2$ and $t < r$, and a class $\mathcal{F}$ of functions $f: [n] \to \mathbb{G}$ for an Abelian group...

Multi-user (mu) security considers large-scale attackers that, given access to a number of cryptosystem instances, attempt to compromise at least one of them. We initiate the study of mu security of the so-called GGMtree that stems from the PRG-to-PRF transformation of Goldreich, Goldwasser, and Micali, with a goal to provide references for its recently popularized use in applied cryptography. We propose a generalized model for GGM trees and analyze its mu prefix-constrained PRF security in...

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

We design and implement GigaDORAM, a novel 3-server Distributed Oblivious Random Access Memory (DORAM) protocol. Oblivious RAM allows a client to read and write to memory on an untrusted server while ensuring the server itself learns nothing about the client's access pattern. Distributed Oblivious RAM (DORAM) allows a group of servers to efficiently access a secret-shared array at a secret-shared index. A recent generation of DORAM implementations (e.g. FLORAM, DuORAM) has focused on...

The Snowden's revelations kick-started a community-wide effort to develop cryptographic tools against mass surveillance. In this work, we propose to add another primitive to that toolbox: Fail-Stop Signatures (FSS) [EC'89]. FSS are digital signatures enhanced with a forgery-detection mechanism that can protect a PPT signer from more powerful attackers. Despite the fascinating concept, research in this area stalled after the '90s. However, the ongoing transition to post-quantum...

Recently, Servan-Schreiber et al. (S&P 2023) proposed a new notion called private access control lists (PACL) for function secret sharing (FSS), where the FSS evaluators can ensure that the FSS dealer is authorized to share the given function with privacy assurance. In particular, for the secret sharing of a point function $f_{\alpha, \beta}$, namely distributed point function (DPF), the authors showed how to efficiently restrict the choice of $\alpha$ via a specific PACL scheme from...

Decision tree evaluation is extensively used in machine learning to construct accurate classification models. Often in the cloud-assisted communication paradigm cloud servers execute remote evaluations of classification models using clients’ data. In this setting, the need for private decision tree evaluation (PDTE) has emerged to guarantee no leakage of information for the client’s input nor the service provider’s trained model i.e., decision tree. In this paper, we propose a private...

Secure 2-party computation (2PC) enables secure inference that offers protection for both proprietary machine learning (ML) models and sensitive inputs to them. However, the existing secure inference solutions suffer from high latency and communication overheads, particularly for transformers. Function secret sharing (FSS) is a recent paradigm for obtaining efficient 2PC protocols with a preprocessing phase. We provide SIGMA, the first end-to-end system for secure transformer inference...

Structure-Aware private set intersection (sa-PSI) is a variant of PSI where Alice's input set $A$ has some publicly known structure, Bob's input $B$ is an unstructured set of points, and Alice learns the intersection $A \cap B$. sa-PSI was recently introduced by Garimella et al. (Crypto 2022), who described a semi-honest protocol with communication that scales with the description size of Alice's set, instead of its cardinality. In this paper, we present the first sa-PSI protocol secure...

Secure Two-party Computation (2PC) allows two parties to compute any function on their private inputs without revealing their inputs to each other. In the offline/online model for 2PC, correlated randomness that is independent of all inputs to the computation, is generated in a preprocessing (offline) phase and this randomness is then utilized in the online phase once the inputs to the parties become available. Most 2PC works focus on optimizing the online time as this overhead lies on the...

Function Secret Sharing (FSS; Eurocrypt 2015) allows a dealer to share a function f with two or more evaluators. Given secret shares of a function f, the evaluators can locally compute secret shares of f(x) on an input x, without learning information about f. In this paper, we initiate the study of access control for FSS. Given the shares of f, the evaluators can ensure that the dealer is authorized to share the provided function. For a function family F and an access control list defined...

In two-party private set intersection (PSI), Alice holds a set $X$, Bob holds a set $Y$, and they learn (only) the contents of $X \cap Y$. We introduce structure-aware PSI protocols, which take advantage of situations where Alice's set $X$ is publicly known to have a certain structure. The goal of structure-aware PSI is to have communication that scales with the description size of Alice's set, rather its cardinality. We introduce a new generic paradigm for structure-aware...

Machine learning algorithms crucially depend on non-linear mathematical functions such as division (for normalization), exponentiation (for softmax and sigmoid), tanh (as an activation function), logarithm (for cross-entropy loss), and square root (for back-propagation of normalization layers). However, when machine learning is performed over secure computation, these protocols incur a large communication overhead and high round complexity. In this work, we propose new multi-party...

Recent advances in function secret sharing (FSS) have led to new possibilities in multi-party computation in the pre-processing model. Silent Pseudorandom Correlation Generators (Crypto '19, CCS '19, CCS '19, CCS '20) have demonstrated the ability to generate large quantities of pre-processing material such as oblivious transfers and Beaver triples through a non-interactive offline phase (with an initial set-up). However, there has been limited protocols for pre-processing material such as...

Secure machine learning (ML) inference can provide meaningful privacy guarantees to both the client (holding sensitive input) and the server (holding sensitive weights of the ML model) while realizing inference-as-a-service. Although many specialized protocols exist for this task, including those in the preprocessing model (where a majority of the overheads are moved to an input independent offline phase), they all still suffer from large online complexity. Specifically, the protocol phase...

In this work, we present a lightweight construction of verifiable two-party function secret sharing (FSS) for point functions and multi-point functions. Our verifiability method is lightweight in two ways. Firstly, it is concretely efficient, making use of only symmetric key operations and no public key or MPC techniques are involved. Our performance is comparable with the state-of-the-art non-verifiable DPF constructions, and we outperform all prior DPF verification techniques in both...

Function Secret Sharing (FSS), introduced by Boyle, Gilboa and Ishai [BGI15], extends the classical notion of secret-sharing a *value* to secret sharing a *function*. Namely, for a secret function f (from a class $F$), FSS provides a sharing of f whereby *succinct shares (``keys'') are distributed to a set of parties, so that later the parties can non-interactively compute an additive sharing of f(x), for any input x in the domain of f. Previous work on FSS concentrated mostly on the...

In this work we describe a token-based solution to Contact Tracing via Distributed Point Functions (DPF) and, more generally, Function Secret Sharing (FSS). The key idea behind the solution is that FSS natively supports secure keyword search on raw sets of keywords without a need for processing the keyword sets via a data structure for set membership. Furthermore, the FSS functionality enables adding up numerical payloads associated with multiple matches without additional interaction. These...

Boyle et al. (TCC 2019) proposed a new approach for secure computation in the preprocessing model building on function secret sharing (FSS), where a gate $g$ is evaluated using an FSS scheme for the related offset family $g_r(x)=g(x+r)$. They further presented efficient FSS schemes based on any pseudorandom generator (PRG) for the offset families of several useful gates $g$ that arise in "mixed-mode'' secure computation. These include gates for zero test, integer comparison, ReLU, and spline...

Machinelearning(ML)istodaycommonlyemployedintheFinancialServicesSector(FSS) to create various models to predict a variety of conditions ranging from financial transactions fraud to outcomes of investments and also targeted marketing campaigns. The common ML technique used for the modeling is supervised learning using regression algorithms and usually involves large amounts of data that needs to be shared and prepared before the actual learning phase. Compliance with privacy laws and...

We propose a simple and powerful new approach for secure computation with input-independent preprocessing, building on the general tool of function secret sharing (FSS) and its efficient instantiations. Using this approach, we can make efficient use of correlated randomness to compute any type of gate, as long as a function class naturally corresponding to this gate admits an efficient FSS scheme. Our approach can be viewed as a generalization of the "TinyTable" protocol of Damgard et al....

We investigate concretely efficient protocols for distributed oblivious linear evaluation over vectors (Vector-OLE). Boyle et al. (CCS 2018) proposed a protocol for secure distributed pseudorandom Vector-OLE generation using sublinear communication, but they did not provide an implementation. Their construction is based on a variant of the LPN assumption and assumes a distributed key generation protocol for single-point Function Secret Sharing (FSS), as well as an efficient batching scheme...

Oblivious linear-function evaluation (OLE) is a secure two-party protocol allowing a receiver to learn a secret linear combination of a pair of field elements held by a sender. OLE serves as a common building block for secure computation of arithmetic circuits, analogously to the role of oblivious transfer (OT) for boolean circuits. A useful extension of OLE is vector OLE (VOLE), allowing the receiver to learn a linear combination of two vectors held by the sender. In several applications of...

Function Secret Sharing (FSS), introduced by Boyle et al. (Eurocrypt 2015), provides a way for additively secret-sharing a function from a given function family $\mathcal F$. More concretely, an $m$-party FSS scheme splits a function $f:\{0,1\}^n\to \mathbb G$, for some abelian group $\mathbb G$, into functions $f_1,\ldots,f_m$, described by keys $k_1,\ldots,k_m$, such that $f=f_1+\ldots+f_m$ and every strict subset of the keys hides $f$. A Distributed Point Function (DPF) is a special case...

Many online services let users query public datasets such as maps, flight prices, or restaurant reviews. Unfortunately, the queries to these services reveal highly sensitive information that can compromise users’ privacy. This paper presents Splinter, a system that protects users’ queries on public data and scales to realistic applications. A user splits her query into multiple parts and sends each part to a different provider that holds a copy of the data. As long as any one of the...

Consider a setting where inputs $x_1,\ldots,x_n$ are encrypted under independent public keys. Given the ciphertexts $\{c_i = Enc(pk_i,x_i)\}_i$, Alice outputs ciphertexts $c'_1,\ldots,c'_n$ that decrypt to $y_1,\ldots,y_n$ respectively. What relationships between the $x_i$'s and $y_i$'s can Alice induce? Motivated by applications to delegating computations, Dwork, Langberg, Naor, Nissim and Reingold (unpublished manuscript, 2004) showed that a semantically secure scheme disallows signaling...

Function secret sharing(FSS) was introduced by Boyle et al. in Eurocrypt 2015, which allowed a dealer to split a secret function f into n separate pieces such that each piece enables the server who owns it to generate a secret share of the evaluation of f(x). However, when just only one collusive server returns a wrong result, reconstructing the secret will fail. Therefore, we are required to find an applicable approach to check the correctness of result returned by the untrusted server. To...