In Function Secret Sharing (FSS), a dealer with a given function f: {0,1}ⁿ → 𝔾 from n bits to a commutative group 𝔾 such that f is in a function class ℱ shares succinct keys with two properties. Evaluating each key separately on a common input x results in additive shares of f(x) and any subset of the keys does not provide information on f. Two-party FSS schemes which are reducible to One-way Functions (OWF) have applications in cryptography, complexity, and in practical data security systems. We establish a two-way transformation between a two-party FSS scheme for a function class ℱ, which is black-box reducible to an OWF, or even black-box reducible to a family of Pseudo-Random Functions (PRF) and a dynamic data structure that supports range queries on ℱ. A data structure of this type enables dynamically adding functions to a multiset of functions F ⊆ ℱ, and answering range queries on the output of F, i.e., returning ∑_{f ∈ F} f(x) for a query x. The data structures are defined in one of several models which abstract RAM. The correspondence together with known lower bounds on the update time and the query time in data structures leads to the first non-trivial lower bounds on FSS schemes which are black-box reducible to PRF. These lower bounds apply to FSS schemes with polynomial key size and include: - For ℱ^d_{box}, the class of all functions which assign a constant group element β ∈ 𝔾 to any input in a specified d-dimensional box and 0 to all other inputs: if the key sharing function, Gen, runs in time polynomial in n and the evaluation function is Eval then: - If d ≥ 2 and 𝔾 = ℤ₂ then Eval’s running time is Ω ((n^{3/2})/(log³ n)). - If d ≥ 2 and 𝔾 is cyclic such that log |𝔾| = (1 + ε) n then Eval’s running time is Ω ((n/(log n)) ²). - If d > 2 is a constant and further, Gen and Eval correspond to operations on data structures in the Oblivious Group Model (this includes all known FSS from OWF techniques), then the product of Eval’s time and the key size is Ω(n^{d-1}). - For ℱ_{mono}, the class of all monomials ax^b ∈ 𝔽_{2ⁿ}[X] such that b ≤ B, assuming n^{ω(1)} ≤ B ≤ 2^{n/4}: if Gen runs in polynomial time, then Eval’s running time is Ω ((n √{log B})/(log² n)).

We put forth a new paradigm for secure multi-party computation (MPC) in the preprocessing model, where a feasible one-time setup can enable a lifetime of efficient online secure computations. Our protocols match the security guarantees and low costs of the cheapest category of MPC solutions, namely 3-party protocols (3PC) secure against a single malicious party, with the qualitative advantages that one party communicates data sublinear in the circuit size, and can go offline after its initial messages. This “2+ 1“-party structure can alternatively be instantiated between 2 parties with the aid of an (untrusted) dealer. Within such existing protocols, we provide comparable online performance while improving the storage and offline dealer-to-party communication requirements by more than 3 orders of magnitude. At the technical level, we build on the Fully Linear Interactive Oracle Proof (FLIOP)-based protocol design of Boyle et al. (CRYPTO 2021). We provide an extensive assortment of algorithmic and implementation-level optimizations, design efficient distributed proofs of well-formedness of complex FLIOP correlations, and make them circuit-independent. We implement and benchmark our end-to-end system against the state of the art in the 2+1 regime, a dealer-aided variant of SPDZ for Boolean circuits. We additionally extend our techniques to the$(n+1)$party setting, where a dealer aids general dishonest-majority MPC, and provide a variant of the protocol which further achieves security with “identifiable abort.”

A Distributed Point Function (DPF) is a crypto-graphic primitive used for compressing additive secret shares of a secret unit vector across two parties. Many DPF applications require compressed shares of a sparse weight- t vector, namely a Distributed Multi-Point Function (DMPF). Despite the strong motivation and prior optimization efforts, in most use cases the best practical implementation of DMPF is still a simple brute-force combination of$t$independent DPFs. We present new constructions and optimized implementations of DMPFs in different parameter regimes, providing significant efficiency savings over existing approaches. We showcase our new constructions within applications of pseu-dorandom correlation generators (PCGs) and 2-server private set intersection (PSI). Incorporating our tools into the state-of-the-art PCG for “silent” generation of binary multiplication triples (FOLEAGE, Bombar et al, ePrint'24) yields a x2.68 improvement in throughput, with only x 1.4 blowup in the seed size. On a single core of our benchmark machine, our implementation silently generates up to 22.1 million triples per second, outperforming even the best “non-silent” protocol (Roy, CRYPTO'22), which generates 16 million triples per second.

We revisit the problem of concretely efficient secure computation of sorting and selection (e.g., maximum, median, or top-k) on secret-shared data, focusing on the case of security against a single semi-honest party. Previous solutions either have a high communication overhead or many rounds of interaction, even when allowing input-independent preprocessing.

Finding eviction sets for a large fraction of the cache is an essential preprocessing step for Prime+Probe based cache side-channel attacks. Previous work on this problem reduces it to finding an eviction set for each cache set independently. In a w-way, set-associative cache with s cache sets this approach requires Ω(s2w) time.This work introduces the Prune+PlumTree algorithm, which finds eviction sets for any constant fraction of the cache in time O(sw log s), assuming the LRU cache replacement policy. We complement the asymptotic result with tests on current Intel processors, with 16k sets in the Last Level Cache (LLC) and 4 Kbyte memory pages, finding eviction sets for more than 98% of the LLC in 40–63 milliseconds, improving over previous work by two orders of magnitude. Simulating Prune+PlumTree on a standard, i.e. unskewed, randomized cache, mapping addresses to random cache sets, results in finding eviction sets for more than 98% of a 12-way cache with 214sets in less than 7.4 seconds.We further adapt Prune+PlumTree to caches with a random replacement policy based on a novel method to prune a large set of random memory lines to a union of minimal eviction sets in this setting. This variant of Prune+PlumTree runs in time O(sw2log s). As a final contribution, we show that Prune+PlumTree for the LRU replacement policy has asymptotically tight running time by proving that any algorithm that maps a constant fraction of the cache runs in time Ω(sw log s).

In covert channel attacks, an adversary seeks various means to influence a tangible characteristic of a system, and then makes the systems leak information by measuring this characteristic. Covert channels are, by nature, very elusive. This makes it very difficult to identify them and defend against attacks that use these channels to leak sensitive information . Thus, they are a serious threat to the security of many systems. In this paper, we present two network timing covert channel attacks, and a defense mechanism against them. The purpose of the proposed attacks is to leak sensitive information between two logically separated (or isolated) networks that are hosted by a single router – one that is connected to the Internet, and another that is isolated and contains sensitive information. The attacks build on the fact that the response time of the router for a specific type of packet sent from a device that is connected to it is usually predictable, given the network topology . By interacting with the single shared router in a specific manner, an attacker can increase the router’s packet response time. The interaction is determined based on the information to be leaked, so the receiver (a computer located on the Internet-connected network) can measure the delayed packet response times and decode the sender’s signals (which operates from the isolated network) to receive classified information. The two classes of attacks presented in this work differ in the way that the delay is caused. In the cross-router covert channel (CRCC) attack, the sender overloads the router with control-plane packets; in the Wi-Fi micro-jamming attack, the sender uses a pre-installed implant to transmit single-tone signals in the 2.4GHz frequency range, disturbing the router’s packet transmissions . We showed that both attacks can influence a wide range of router brands and Wi-Fi capable devices and evaluated the optimal settings for both attacks when using different types of packets, transmission power, and data transmission rates. Our proposed defense mechanism is based on semi-supervised machine learning and deep learning algorithms , which are both used for novelty detection in network traffic. By detecting unusual traffic, we can identify the disturbances needed to leak the information. The system can then respond by blocking the suspicious devices that are involved in the attack. We evaluated the attacks in noisy and noise-free environments, successfully detecting both attacks in both environments. All the data and code, which includes the implementation of the attacks and the defense mechanism, is published as a benefit to the research community.

A pseudorandom correlation generator (PCG) is a recent tool for securely generating useful sources of correlated randomness, such as random oblivious transfers (OT) and vector oblivious linear evaluations (VOLE), with low communication cost. We introduce a simple new design for PCGs based on so-called expand-accumulate codes, which first apply a sparse random expander graph to replicate each message entry, and then accumulate the entries by computing the sum of each prefix. Our design offers the following advantages compared to state-of-the-art PCG constructions: Competitive concrete efficiency backed by provable security against relevant classes of attacks; An offline-online mode that combines near-optimal cache-friendliness with simple parallelization; Concretely efficient extensions to pseudorandom correlation functions , which enable incremental generation of new correlation instances on demand, and to new kinds of correlated randomness that include circuit-dependent correlations. To further improve the concrete computational cost, we propose a method for speeding up a full-domain evaluation of a puncturable pseudorandom function (PPRF). This is independently motivated by other cryptographic applications of PPRFs.

This paper presents a new protocol for solving the private heavy-hitters problem. In this problem, there are many clients and a small set of data-collection servers. Each client holds a private bitstring. The servers want to recover the set of all popular strings, without learning anything else about any client’s string. A web-browser vendor, for instance, can use our protocol to figure out which homepages are popular, without learning any user’s homepage. We also consider the simpler private subset-histogram problem, in which the servers want to count how many clients hold strings in a particular set without revealing this set to the clients.Our protocols use two data-collection servers and, in a protocol run, each client send sends only a single message to the servers. Our protocols protect client privacy against arbitrary misbehavior by one of the servers and our approach requires no public-key cryptography (except for secure channels), nor general-purpose multiparty computation. Instead, we rely on incremental distributed point functions, a new cryptographic tool that allows a client to succinctly secret-share the labels on the nodes of an exponentially large binary tree, provided that the tree has a single non-zero path. Along the way, we develop new general tools for providing malicious security in applications of distributed point functions.A limitation of our heavy-hitters protocol is that it reveals to the servers slightly more information than the set of popular strings itself. We precisely define and quantify this leakage and explain how to ameliorate its effects. In an experimental evaluation with two servers on opposite sides of the U.S., the servers can find the 200 most popular strings among a set of 400,000 client-held 256-bit strings in 54 minutes. Our protocols are highly parallelizable. We estimate that with 20 physical machines per logical server, our protocols could compute heavy hitters over ten million clients in just over one hour of computation.

Correlated secret randomness is a useful resource for many cryptographic applications. We initiate the study of pseudorandom correlation functions (PCFs) that offer the ability to securely generate virtually unbounded sources of correlated randomness using only local computation. Concretely, a PCF is a keyed function Fk such that for a suitable joint key distribution ( k0, k1), the outputs (fk0(x), fk1(x)) are indistinguishable from instances of a given target correlation. An essential security requirement is that indistinguishability hold not only for outsiders, who observe the pairs of outputs, but also for insiders who know one of the two keys. We present efficient constructions of PCFs for a broad class of useful correlations, including oblivious transfer and multiplication triple correlations, from a variable-density variant of the Learning Parity with Noise assumption (VDLPN). We also present several cryptographic applications that motivate our efficient PCF constructions. The VDLPN assumption is independently motivated by two additional applications. First, different flavors of this assumption give rise to weak pseudorandom function candidates in depth-2 AC0[⊕] that can be conjectured to have subexponential security, matching the best known learning algorithms for this class. This is contrasted with the quasipolynomial security of previous (higher-depth) AC0[⊕] candidates. We support our conjectures by proving resilience to several classes of attacks. Second, VDLPN implies simple constructions of pseudorandom generators and weak pseudorandom functions with security against XOR related-key attacks.

We consider the problem of securely generating useful instances of two-party correlations, such as many independent copies of a random oblivious transfer (OT) correlation, using a small amount of communication. This problem is motivated by the goal of secure computation with silent preprocessing, where a low-communication input-independent setup, followed by local ("silent") computation, enables a lightweight "non-cryptographic" online phase once the inputs are known. Recent works of Boyle et al. (CCS 2018, Crypto 2019) achieve this goal with good concrete efficiency for useful kinds of two-party correlations, including OT correlations, under different variants of the Learning Parity with Noise (LPN) assumption, and using a small number of "base'' oblivious transfers. The protocols of Boyle et al. have several limitations. First, they require a large number of communication rounds. Second, they are only secure against semi-honest parties. Finally, their concrete efficiency estimates are not backed by an actual implementation. In this work we address these limitations, making three main contributions: Eliminating interaction. Under the same assumption, we obtain the first concretely efficient 2-round protocols for generating useful correlations, including OT correlations, in the semi-honest security model. This implies the first efficient 2-round OT extension protocol of any kind and, more generally, protocols for non-interactive secure computation (NISC) that are concretely efficient and have the silent preprocessing feature. Malicious security. We provide security against malicious parties without additional interaction and with only a modest overhead; prior to our work, no similar protocols were known with any number of rounds. Implementation. Finally, we implemented, optimized, and benchmarked our 2-round OT extension protocol, demonstrating that it offers a more attractive alternative to the OT extension protocol of Ishai et al. (Crypto 2003) in many realistic settings.

Secure multiparty computation enables a set of parties to securely carry out a joint computation on their private inputs without revealing anything but the output. A particularly motivated setting is that of three parties with a single corruption (hereafter denoted 3PC). This 3PC setting is particularly appealing for two main reasons: (1) it admits more efficient MPC protocols than in other standard settings; (2) it allows in principle to achieve full security (and fairness). Highly efficient protocols exist within this setting with security against a semi-honest</> adversary; however, a significant gap remains between these and protocols with stronger security against a malicious</> adversary. In this paper, we narrow this gap within concretely efficient protocols. More explicitly, we have the following contributions: Concretely Efficient Malicious 3PC. We present an optimized 3PC protocol for arithmetic circuits over rings with (amortized) communication of 1 ring element per multiplication gate per party, matching the best semi-honest protocols. The protocol applies also to Boolean circuits, significantly improving over previous protocols even for small circuits. Our protocol builds on recent techniques of Boneh et al. (Crypto 2019) for sublinear zero-knowledge proofs on distributed data, together with an efficient semi-honest protocol based on replicated secret sharing (Araki et al., CCS 2016). We present a concrete analysis of communication and computation costs, including several optimizations. For example, for 40-bit statistical security, and Boolean circuit with a million (nonlinear) gates, the overhead on top of the semi-honest protocol can involve less than 0.5KB of communication for the entire circuit,</> while the computational overhead is dominated by roughly 30 multiplications per gate in the field F247. In addition, we implemented and benchmarked the protocol for varied circuit sizes. Full Security. We augment the 3PC protocol to further provide full security</> (with guaranteed output delivery) while maintaining amortized 1 ring element communication per party per multiplication gate, and with hardly any impact on concrete efficiency. This is contrasted with the best previous 3PC protocols from the literature, which allow a corrupt party to mount a denial-of-service attack without being detected.

Oblivious linear-function evaluation (OLE) is a secure two-party protocol allowing a receiver to learn any 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 any linear combination of two vectors held by the sender. In several applications of OLE, one can replace a large number of instances of OLE by a smaller number of instances of VOLE. This motivates the goal of amortizing the cost of generating long instances of VOLE. We suggest a new approach for fast generation of pseudo-random instances of VOLE via a deterministic local expansion of a pair of short correlated seeds and no interaction. This provides the first example of compressing a non-trivial and cryptographically useful correlation with good concrete efficiency. Our VOLE generators can be used to enhance the efficiency of a host of cryptographic applications. These include secure arithmetic computation and non-interactive zero-knowledge proofs with reusable preprocessing. Our VOLE generators are based on a novel combination of function secret sharing (FSS) for multi-point functions and linear codes in which decoding is intractable. Their security can be based on variants of the learning parity with noise (LPN) assumption over large fields that resist known attacks. We provide several constructions that offer tradeoffs between different efficiency measures and the underlying intractability assumptions.

Homomorphic secret sharing (HSS) is the secret sharing analogue of homomorphic encryption. An HSS scheme supports a local evaluation of functions on shares of one or more secret inputs, such that the resulting shares of the output are short. Some applications require the stronger notion of additive HSS, where the shares of the output add up to the output over some finite Abelian group. While some strong positive results for HSS are known under specific cryptographic assumptions, many natural questions remain open. We initiate a systematic study of HSS, making the following contributions. - A definitional framework. We present a general framework for defining HSS schemes that unifies and extends several previous notions from the literature, and cast known results within this framework. - Limitations. We establish limitations on information-theoretic multi-input HSS with short output shares via a relation with communication complexity. We also show that additive HSS for non-trivial functions, even the AND of two input bits, implies non-interactive key exchange, and is therefore unlikely to be implied by public-key encryption or even oblivious transfer. - Applications. We present two types of applications of HSS. First, we construct 2-round protocols for secure multiparty computation from a simple constant-size instance of HSS. As a corollary, we obtain 2-round protocols with attractive asymptotic efficiency features under the Decision Diffie Hellman (DDH) assumption. Second, we use HSS to obtain nearly optimal worst-case to average-case reductions in P. This in turn has applications to fine-grained average-case hardness and verifiable computation.

We continue the study of Homomorphic Secret Sharing (HSS), recently introduced by Boyle et al. (Crypto 2016, Eurocrypt 2017). A (2-party) HSS scheme splits an input x into shares (x0,x1) such that (1) each share computationally hides x, and (2) there exists an efficient homomorphic evaluation algorithm $\Eval$ such that for any function (or "program") from a given class it holds that Eval(x0,P)+Eval(x1,P)=P(x). Boyle et al. show how to construct an HSS scheme for branching programs, with an inverse polynomial error, using discrete-log type assumptions such as DDH.

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 F. More concretely, an m-party FSS scheme splits a function f : {0, 1}n -> G, for some abelian group G, into functions f1,...,fm, described by keys k1,...,km, such that f = f1 + ... + fm and every strict subset of the keys hides f. A Distributed Point Function (DPF) is a special case where F is the family of point functions, namely functions f_{a,b} that evaluate to b on the input a and to 0 on all other inputs. FSS schemes are useful for applications that involve privately reading from or writing to distributed databases while minimizing the amount of communication. These include different flavors of private information retrieval (PIR), as well as a recent application of DPF for large-scale anonymous messaging.

We propose efficient schemes for information-theoretically secure key exchange in the Bounded Storage Model (BSM), where the adversary is assumed to have limited storage. Our schemes generate a secret One Time Pad (OTP) shared by the sender and the receiver,from a large number of public random bits produced by the sender or by an external source. Our schemes initially generate a small number of shared secret bits, using known techniques. We introduce a new method to expand a small number of shared bits to a much longer, shared key.

Many anonymous peer-to-peer (P2P) file sharing systems have been proposed in recent years. One problem that remains open is how to protect the anonymity of all participating users, namely, reader, server and publisher. In this work we propose a novel solution for a P2P file sharing system. Our solution provides overall anonymity to all participating users.

We present information-theoretically secure schemes for sharing and modifying secrets among a dynamic swarm of computing devices. The schemes support an unlimited number of changes to the swarm including players joining and leaving the swarm, while swarms may be merged, cloned or split. The schemes securely and distributively maintain a global state for the swarm, and support an unlimited number of changes to the state according to received input. Our schemes are based on a novel construction of a strongly oblivious universal Turing Machine and on a distributed evaluation of this TM that reveals nothing to an adversary beyond a bound on the space complexity of the TM.

The flourishing of Peer-to-Peer (P2P) applications has encouraged extensive research on end-to-end anonymity. In particular, interactive services such as VoIP and instant messaging are becoming extremely popular and require low latency. Preserving the anonymity of users in such services is becoming a major challenge. While existing schemes provide anonymity for the communicating parties; they incur high latency and are not suitable for interactive services. Even designs that attempt to reduce the latency, employ an encryption scheme that involves a comparatively high computation overhead and delay. In this paper, we describe a novel low-latency P2P scheme that provides anonymity for both senders and receivers while adhering to low bounds of delay, communication and bandwidth overheads. The design offers resistance against various attacks including a coalition of malicious peers. It has inherited scalability and fault tolerance and is applicable for various interactive P2P services.

Recently, there has been a growing interest in performing flow inspection within devices in the core network. Frequently, a session passing through the core network is routed through several paths either due to network architecture or due to malicious intent.

Gilboat show that the computational approach leads to substantial savings.For every ~> 0, we present a two database computational PIR scheme whose communication complexity is O(n').This improved efficiency is achieved by a combination of a novel balancing technique, together with careful application of pseudo random generators.Our schemes preserve some desired properties of previous solutions.In particular, all our schemes use only one round of communication, they are fairly simple, they are memoryless, and the database contents is stored in its plain form, without any encoding.is possible to protect the user's privacy.The solutions to this private information retrieval (PIR) problem enable the user to retrieve a desired data item, while giving each individual database no partial information on the query.The quality of a solution is measured primarily ' Details on related models and techniques can also be found in [3].random generators [2, 10].(This is equivalent to the existence of one way functions [6, 5]. ) Under this assumption, we develop a family of computational PIR schemes.All these schemes