Private Set Intersection (PSI) is a cryptographic technique that allows two parties to compute the intersection of their sets without revealing anything except intersection. We use fully homomorphic encryption construct fast PSI protocol with small communication overhead works particularly well when one much smaller than other, and secure against semi-honest adversaries.

Fully Homomorphic Encryption (FHE) refers to a set of encryption schemes that allow computations on encrypted data without requiring secret key. Recent cryptographic advances have pushed FHE into the realm practical applications. However, programming these applications remains huge challenge, as it requires domain expertise ensure correctness, security, and performance.

Homomorphic Encryption (HE) is a cryptosystem which supports computation on encrypted data. Ló pez-Alt et al. (STOC 2012) proposed generalized notion of HE, called Multi-Key (MKHE), capable performing arithmetic operations ciphertexts under different keys. In this paper, we present multi-key variants two HE schemes with packed ciphertexts. We new relinearization algorithms are simpler and faster than previous method by Chen (TCC 2017). then generalize the bootstrapping techniques for to...

Private information retrieval (PIR) is a key building block in many privacy-preserving systems. Unfortunately, existing constructions remain very expensive. This paper introduces two techniques that make the computational variant of PIR (CPIR) more efficient practice. The first technique targets recent class CPU-efficient CPIR protocols where query sent by client contains number ciphertexts proportional to size database. We show how compresses this query, achieving reductions up 274X. second...

Private Set Intersection (PSI) allows two parties, the sender and receiver, to compute intersection of their private sets without revealing extra information each other. We are interested in unbalanced PSI setting, where (1) receiver's set is significantly smaller than sender's, (2) receiver (with set) has a low-power device. Also, Labeled holds label per item its set, obtains labels from items intersection. build upon protocol Chen, Laine, Rindal (CCS~2017) several ways: we add efficient...

One of the tasks in 2017 iDASH secure genome analysis competition was to enable training logistic regression models over encrypted genomic data. More precisely, given a list approximately 1500 patient records, each with 18 binary features containing information on specific mutations, idea for data holder encrypt records using homomorphic encryption, and send them an untrusted cloud storage. The could then homomorphically apply algorithm obtain model, which can be sent decryption. In this...

This paper presents OnionPIR and stateful OnionPIR, two single-server PIR schemes that significantly improve the response size computation cost over state-of-the-art schemes. scheme utilizes recent advances in somewhat homomorphic encryption (SHE) carefully composes lattice-based SHE operations to control noise growth size. Stateful uses a technique based on evaluation of copy networks. achieves overhead just 4.2x insecure baseline, contrast 100x Our improves upon framework Patel et al....

Abstract Lattice-based cryptography is currently under consideration for standardization in the ongoing NIST PQC Post-Quantum Cryptography competition, and used as basis Homomorphic Encryption schemes world-wide. Both applications rely specifically on hardness of Learning With Errors (LWE) problem. Most deployments use small secrets an optimization, so it important to understand concrete security LWE when sampling secret from a non-uniform, distribution. Although there are numerous...

One of the tasks in iDASH Secure Genome Analysis Competition 2016 was to demonstrate feasibility privacy-preserving queries on homomorphically encrypted genomic data. More precisely, given a list up 100,000 mutations, task encrypt data using homomorphic encryption way that allows it be stored securely cloud, and enables owner query dataset for presence specific without revealing any information about or cloud. We devise novel string matching protocol enable Our combines state-of-the-art...

Decentralizing multi-authority attribute-based encryption (ABE) has been adopted for solving problems arising from sharing confidential corporate data in cloud computing. For decentralizing multiauthority ABE systems that do not rely on a central authority, collusion resistance can be achieved using global identifier. Therefore, identity needs to managed globally, which results the crucial of privacy and security. A scheme is developed does use authority manage users keys, only simple trust...

Oblivious RAM (ORAM) is a cryptographic primitive that allows client to hide access pattern its data encrypted and stored at remote server. Traditionally, ORAM algorithms assume the server acts purely as storage device. Under this assumption, has least log(N) bandwidth blowup for N entries. After three decades of improvements, have reached optimal logarithmic blowup. Nonetheless, in many practical use-cases constant overhead desirable. To purpose, Devadas et al. (TCC 2016) formalized...

The Ring Learning-with-Errors (RLWE) problem shows great promise for postquantum cryptography and homomorphic encryption. We describe a new attack on the nondual search RLWE with small error widths, using ring homomorphisms to finite fields chi-square statistical test. In particular, we identify "subfield vulnerability" give which finds this vulnerability by mapping field extension detecting nonuniformity respect number of elements in subfield. use examples vulnerable instances Galois...