Fully Homomorphic Encryption (FHE) is a promising solution to enable privacy-preserving inference and training of machine learning models over encrypted data. Among the machine learning methods used in practice, Extreme Gradient Boosting (XGBoost) is one technique that shines in many applications. While previous works have tackled the problem of training tree-based models over FHE, these works either rely on interaction with the client, which adds the extra burden of communication, or consume a typically unreasonable amount of time to train a large model. In this work, we present an efficient system for a non-interactive XGBoost training over FHE that achieves up to 360 imes speedup compared to the state of the art. The argmax operation is a basic building block invoked repeatedly during the XGBoost training as well as other machine learning algorithms, but computing it over FHE is time consuming. When utilizing the Single Instruction Multiple Data (SIMD) parallelism capability offered by most FHE schemes and using a configuration with s slots, the state of the art methods compute argmax on n <= s values using either O(log_2 n) SIMD-comparisons in tournament-style comparison or ceil{n^2 /s} SIMD-comparisons using all pairs comparison. As a second contribution of this work, we propose an efficient argmax algorithm that is based on a novel technique to maximize SIMD-utilization, and computes the argmax of n <= s values using only O(log_2(log_2(n)) SIMD-comparisons. The method extends to n > s with complexity O(n/s) + log_2(log_2(s)), compared to O(n/s) + log_2(s) for state of the art methods. We conduct empirical experiments to compare our method with other existing argmax methods, and show that when using the HEaaN FHE scheme with a configuration of s=2^15 to compute the argmax of n=s values, our implementation is about 1.6 times faster than the state of the art.

Abstract Homomorphic encryption () protects data in-use, but can be computationally expensive. To avoid the costly bootstrapping procedure that refreshes ciphertexts, some works have explored client-aided outsourcing protocols, where the client intermittently refreshes ciphertexts for a server that is performing homomorphic computations. But is this approach secure against malicious servers? We present a -secure encryption scheme that is completely insecure in this setting. We define a new notion of security, called , that we prove is sufficient. Additionally, we show: Homomorphic encryption schemes that have a certain type of circuit privacy—for example, schemes in which ciphertexts can be “sanitized"—are -secure. In particular, assuming certain existing schemes are -secure, they are also -secure. For certain encryption schemes, like Brakerski-Vaikuntanathan, that have a property that we call oblivious secret key extraction, -security implies circular security—i.e., that it is secure to provide an encryption of the secret key in a form usable for bootstrapping (to construct fully homomorphic encryption).

In common data analytic scenarios, data is produced by a multitude of _data producers_ (e.g., medical clinics), stored and maintained by some _data keeper_ (e.g., a centralized repository), and substantial benefit can be gained from making data accessible to a variety of _data consumers_ (e.g., researchers); however, making cleartext data accessible poses a privacy threat and may infringe on privacy regulation. Computing over data encrypted by fully homomorphic encryption (FHE) enables providing privacy guarantee together with data mining utility. To ensure that correct insights are extracted, it is essential to guarantee _data authenticity_. In this work we present an authenticity proof for encrypted data: As a central tool we show how to modify a classical MAC based on universal hashing to introduce _the first MAC with fast homomorphic verification over the reals_ (7.37 microseconds amortized runtime). We then utilize our MAC for guaranteeing data authenticity, for data provided by an untrusted data keeper in FHE encrypted form. We implemented our solution, demonstrating _substantial efficiency improvements_ over the prior art (Chatel et al. USENIX'21): improving the proof size and generation time by over 10^4X. To demonstrate the usefulness of our homomorphic verification in realistic systems we implemented it in AWS EC2 with S3 storage, demonstrating it achieves practical performance for fetching and authenticating FHE ciphertexts, as well as smooth integration with subsequent homomorphic evaluation of decision tree models.

Privacy-Preserving Machine Learning (PPML) provides protocols for learning and statistical analysis of data that may be distributed amongst multiple data owners (e.g., hospitals that own proprietary healthcare data), while preserving data privacy. The PPML literature includes protocols for various learning methods, including ridge regression. Ridge regression controls the L2 norm of the model, but does not aim to strictly reduce the number of non-zero coefficients, namely the L0 norm of the model. Reducing the number of non-zero coefficients (a form of feature selection) is important for avoiding overfitting, and for reducing the cost of using learnt models in practice. In this work, we develop a first privacy-preserving protocol for sparse linear regression under L0 constraints. The protocol addresses data contributed by several data owners (e.g., hospitals). Our protocol outsources the bulk of the computation to two non-colluding servers, using homomorphic encryption as a central tool. We provide a rigorous security proof for our protocol, where security is against semi-honest adversaries controlling any number of data owners and at most one server. We implemented our protocol, and evaluated performance with nearly a million samples and up to 40 features.

With the development of sequencing technologies, viral strain classification - which is critical for many applications, including disease monitoring and control - has become widely deployed. Typically, a lab (client) holds a viral sequence, and requests classification services from a centralized repository of labeled viral sequences (server). However, such “classification as a service” raises privacy concerns. In this paper we propose a privacy-preserving viral strain classification protocol that allows the client to obtain classification services from the server, while maintaining complete privacy of the client's viral strains. The privacy guarantee is against active servers, and the correctness guarantee is against passive ones. We implemented our protocol and performed extensive benchmarks, showing that it obtains almost perfect accuracy (99.8%-100%) and microAUC (0.999), and high efficiency (amortized per-sequence client and server runtimes of 4.95ms and 0.53ms, respectively, and 0.21MB communication). In addition, we present an extension of our protocol that guarantees server privacy against passive clients, and provide an empirical evaluation showing that this extension provides the same high accuracy and microAUC, with amortized per sequences overhead of only a few milliseconds in client and server runtime, and 0.3MB in communication complexity. Along the way, we develop an enhanced packing technique in which two reals are packed in a single complex number, with support for homomorphic inner products of vectors of ciphertexts. We note that while similar packing techniques were used before, they only supported additions and multiplication by constants.

A Hash Time Lock Contract (HTLC) is a protocol that is commonly used to exchange payments across different blockchains. Using HTLC as a building block for cross blockchain atomic swaps has its drawbacks: The notion of time is handled differently in each blockchain, be it private or public. Additionally, if the swap ends up aborted, the funds are locked in escrow until the safety timeout expires. In this work we formulate a new cryptographic primitive: Attribute Verifiable Timed Commitment which enables to prove that a timed commitment commits to a value which possesses certain attributes. Using our cryptographic primitive, we describe a new cross chain atomic swap protocol that operates without blockchain derived time and unlike the state of the art, all parties can instantly abort the swap without waiting for the safety timeouts to expire. In order to prove in zero knowledge that a secret committed to using a timed commitment has a claimed hash value, we employ the “MPC in the head” technique by Ishai et al. and implement our zero-knowledge proof protocol and evaluate its performance. As part of our techniques, we develop a novel and efficient procedure for integer Lower-Than validation in arithmetic circuits which may be of independent interest.

In the era of cloud computing and machine learning, data has become a highly valuable resource. Recent history has shown that the benefits brought forth by this data driven culture come at a cost of potential data leakage. Such breaches have a devastating impact on individuals and industry, and lead the community to seek privacy preserving solutions. A promising approach is to utilize Fully Homomorphic Encryption ( \( \mathsf {FHE } \) ) to enable machine learning over encrypted data, thus providing resiliency against information leakage. However, computing over encrypted data incurs a high computational overhead, thus requiring the redesign of algorithms, in an “ \( \mathsf {FHE } \) -friendly” manner, to maintain their practicality. In this work we focus on the ever-popular tree based methods, and propose a new privacy-preserving solution to training and prediction for trees over data encrypted with homomorphic encryption. Our solution employs a low-degree approximation for the step-function together with a lightweight interactive protocol, to replace components of the vanilla algorithm that are costly over encrypted data. Our protocols for decision trees achieve practical usability demonstrated on standard UCI datasets encrypted with fully homomorphic encryption. In addition, the communication complexity of our protocols is independent of the tree size and dataset size in prediction and training, respectively, which significantly improves on prior works. 1

Abstract We present a novel secure search protocol on data and queries encrypted with Fully Homomorphic Encryption (FHE). Our protocol enables organizations (client) to (1) securely upload an unsorted data array x = (x[1], . . . , x[n]) to an untrusted honest-but-curious sever, where data may be uploaded over time and from multiple data-sources; and (2) securely issue repeated search queries q for retrieving the first element (i*, x[i*]) satisfying an agreed matching criterion i* = min { i ∈ [n] | IsMatch(x[i], q) = 1 }, as well as fetching the next matching elements with further interaction. For security, the client encrypts the data and queries with FHE prior to uploading, and the server processes the ciphertexts to produce the result ciphertext for the client to decrypt. Our secure search protocol improves over the prior state-of-the-art for secure search on FHE encrypted data (Akavia, Feldman, Shaul (AFS), CCS’2018) in achieving: – Post-processing free protocol where the server produces a ciphertext for the correct search outcome with overwhelming success probability. This is in contrast to returning a list of candidates for the client to postprocess, or suffering from a noticeable error probability, in AFS. Our post-processing freeness enables the server to use secure search as a sub-component in a larger computation without interaction with the client. – Faster protocol: (a) Client time and communication bandwidth are improved by a log2 n/ log log n factor. (b) Server evaluates a polynomial of degree linear in log n (compare to cubic in AFS), and overall number of multiplications improved by up to log n factor. (c) Employing only GF(2) computations (compare to GF(p) for p ≫ in AFS) to gain both further speedup and compatibility to all current FHE candidates. – Order of magnitude speedup exhibited by extensive benchmarks we executed on identical hardware for implementations of ours versus AFS’s protocols. Additionally, like other FHE based solutions, our solution is setup-free: to outsource elements from the client to the server, no additional actions are performed on x except for encrypting it element by element (each element bit by bit) and uploading the resulted ciphertexts to the server.

We consider the secure search problem of retrieving from an unsorted data cost=(x_1,...,xm) an item (i,xi) matching a given lookup value l (for a generic matching criterion either hardcoded or given as part of the query), where both input and output are encrypted by a Fully Homomorphic Encryption (FHE). The secure search problem is central in applications of secure outsourcing to an untrusted party ("the cloud"). Prior secure search algorithms on FHE encrypted data are realized by polynomials of degree Ømega(m), evaluated in Ømega(log m) sequential homomorphic multiplication steps (ie., multiplicative depth) even using an unbounded number of parallel processors. This is too slow with current FHE implementations, especially as the size of the array grows. We present the first secure search algorithm that is realized by a polynomial of logarithmic degree, log3 m, evaluated in O(log log m) sequential homomorphic multiplication steps (ie., multiplicative depth) using m parallel processors. We implemented our algorithm in an open source library based on HElib and ran experiments on Amazon's EC2 cloud with up to 100 processors. Our experiments show that we can securely search in m= millions of entries in less than an hour on a standard EC2 64-cores machine. We achieve our result by: (1) Employing modern data summarization techniques known as sketching for returning as output (the encryption of) a short sketch C from which the matching item (i,xi) can be decoded in time polynomial in log m. (2) Designing for this purpose a novel sketch that returns the first strictly-positive entry in a (not necessarily sparse) array of non-negative integers; this sketch may be of independent interest. (3) Suggesting a multi-ring evaluation of FHE for degree reduction from linear to logarithmic.

Traffic patterns in the Internet are changing, with video and user generated content (UGC) taking an increasing share of the volume, and P2P traffic decreases. The widespread appearing of content providers and content peering has been shown to decrease profit for ISPs. To reduce expenses, the use of P2P caches for UGC has been suggested. In this work, we look at the problem of UGC content sharing between peering ISPs. We show a method for testing whether sharing is beneficial for the ISPs. We then give a method for total objects placement such that the optimal demand is maximized, under the following constraints: (1) The local demand is known at each ISP; (2) ISPs share only if they can satisfy at least the same demand as before the sharing. We further simulate our method with different workloads distributions that exhibit either UGC or P2P characteristics.

Pseudorandom functions (PRFs) play a fundamental role in symmetric-key cryptography. However, they are inherently complex and cannot be implemented in the class AC0 (MOD2). Weak pseudorandom functions (weak PRFs) do not suffer from this complexity limitation, yet they suffice for many cryptographic applications.

We present a deterministic algorithm for finding the significant Fourier frequencies of a given signal f ∈ CNand their approximate Fourier coefficients in running time and sample complexity polynomial in log N, L1(f̂)/||f̂||2, and 1/τ, where the significant frequencies are those occupying at least a τ-fraction of the energy of the signal, and L1(f̂) denotes the L1-norm of the Fourier transform of f. Furthermore, the algorithm is robust to additive random noise. This strictly extends the class of compressible/Fourier sparse signals efficiently handled by previous deterministic algorithms for signals in CN. As a central tool, we prove there is a deterministic algorithm that takes as input N, ε and an arithmetic progression P in ZN, runs in time polynomial in ln N and 1/ε, and returns a set APthat ε-approximates P in ZNin the sense that |Ex∈APe2πiω/N- Ex∈Pe2πiωx/N|Pof size polynomial in lnN and 1/ε that ε-approximate given arithmetic progressions P in ZN. This extends results on small-bias sets, which are sets approximating the entire domain, to sets approximating a given arithmetic progression; this result may be of independent interest.

In this work we study distributed public key schemes secure against continual memory leakage. The secret key will be shared among two computing devices communicating over a public channel, and the decryption operation will be computed by a simple 2-party protocol between the devices. Similarly, the secret key shares will be periodically refreshed by a simple 2-party protocol executed in discrete time periods throughout the lifetime of the system. The leakage adversary can choose pairs, one per device, of polynomial time computable length shrinking (or entropy shrinking) functions, and receive the value of the respective function on the internal state of the respective device (namely, on its secret share, internal randomness, and results of intermediate computations).

This is an errata for our STOC'06 paper, "On Basing One-Way Functions on NP-Hardness".

We consider the possibility of basing one-way functions on NP-Hardness; that is, we study possible reductions from a worst-case decision problem to the task of average-case inverting a polynomial-time computable function f. Our main findings are the following two negative results:

We introduce a unifying framework for proving that predicate P is hard-core for a one-way function f, and apply it to a broad family of functions and predicates, reproving old results in an entirely different way as well as showing new hard-core predicates for well known one-way function candidates. Our framework extends the list-coding method of Goldreich and Levin for showing hard-core predicates. Namely, a predicate will correspond to some error correcting code, predicting a predicate will correspond to access to a corrupted codeword, and the task of inverting one-way functions will correspond to the task of list decoding a corrupted codeword. A characteristic of the error correcting codes which emerge and are addressed by our framework is that codewords can be approximated by a small number of heavy coefficients in their Fourier representation. Moreover, as long as corrupted words are close enough to legal codewords, they will share a heavy Fourier coefficient. We list decodes, by devising a learning algorithm applied to corrupted codewords for learning heavy Fourier coefficients. For codes defined over {0, 1}/sup n/ domain, a learning algorithm by Kushilevitz and Mansour already exists. For codes defined over Z/sub N/, which are the codes which emerge for predicates based on number theoretic one-way functions such as the RSA and Exponentiation modulo primes, we develop a new learning algorithm. This latter algorithm may be of independent interest outside the realm of hard-core predicates.