Sadegh Riazi

With the rapid increase in cloud computing, concerns surrounding data privacy, security, and confidentiality also have been increased significantly. Not only cloud providers are susceptible to internal and external hacks, but also in some scenarios, data owners cannot outsource the computation due to privacy laws such as GDPR, HIPAA, or CCPA. Fully Homomorphic Encryption (FHE) is a groundbreaking invention in cryptography that, unlike traditional cryptosystems, enables computation on encrypted… Show more

With the rapid increase in cloud computing, concerns surrounding data privacy, security, and confidentiality also have been increased significantly. Not only cloud providers are susceptible to internal and external hacks, but also in some scenarios, data owners cannot outsource the computation due to privacy laws such as GDPR, HIPAA, or CCPA. Fully Homomorphic Encryption (FHE) is a groundbreaking invention in cryptography that, unlike traditional cryptosystems, enables computation on encrypted data without ever decrypting it. However, the most critical obstacle in deploying FHE at large-scale is the enormous computation overhead. In this paper, we present HEAX, a novel hardware architecture for FHE that achieves unprecedented performance improvements. HEAX leverages multiple levels of parallelism, ranging from ciphertext-level to fine-grained modular arithmetic level. Our first contribution is a new highly parallelizable architecture for number-theoretic transform (NTT) which can be of independent interest as NTT is frequently used in many lattice-based cryptography systems. Building on top of NTT engine, we design a novel architecture for computation on homomorphically encrypted data. Our implementation on reconfigurable hardware demonstrates 164–268× performance improvement for a wide range of FHE parameters. Show less

We present new secure protocols for approximate k-nearest neighbor search (k-NNS) over the Euclidean distance in the semi-honest model. Our implementation is able to handle massive datasets efficiently. On the algorithmic front, we show a new circuit for the approximate top-k selection from n numbers that is built from merely O(n + poly(k)) comparators. Using this circuit as a subroutine, we design new approximate k-NNS algorithms and two corresponding secure protocols: 1) optimized linear… Show more

We present new secure protocols for approximate k-nearest neighbor search (k-NNS) over the Euclidean distance in the semi-honest model. Our implementation is able to handle massive datasets efficiently. On the algorithmic front, we show a new circuit for the approximate top-k selection from n numbers that is built from merely O(n + poly(k)) comparators. Using this circuit as a subroutine, we design new approximate k-NNS algorithms and two corresponding secure protocols: 1) optimized linear scan; 2) clustering-based sublinear time algorithm. Our secure protocols utilize a combination of additively homomorphic encryption, garbled circuit and Oblivious RAM. Along the way, we introduce various optimizations to these primitives, which drastically improve concrete efficiency. We evaluate the new protocols empirically and show that they are able to handle datasets that are significantly larger than in the prior work. For instance, running on two standard Azure instances within the same availability zone, for a dataset of 96-dimensional descriptors of 10 000 000 images, we can find 10 nearest neighbors with average accuracy 0.9 in under 10 seconds improving upon prior work by at least two orders of magnitude. Show less

Authentication and identification methods based on human fingerprints are ubiquitous in several systems ranging from government organizations to consumer products. The performance and reliability of such systems directly rely on the volume of data on which they have been verified. Unfortunately, a large volume of fingerprint databases is not publicly available due to many privacy and security concerns. In this paper, we introduce a new approach to automatically generate high-fidelity synthetic… Show more

Authentication and identification methods based on human fingerprints are ubiquitous in several systems ranging from government organizations to consumer products. The performance and reliability of such systems directly rely on the volume of data on which they have been verified. Unfortunately, a large volume of fingerprint databases is not publicly available due to many privacy and security concerns. In this paper, we introduce a new approach to automatically generate high-fidelity synthetic fingerprints at scale. Our approach relies on (i) Generative Adversarial Networks to estimate the probability distribution of human fingerprints and (ii) SuperResolution methods to synthesize fine-grained textures. We rigorously test our system and show that our methodology is the first to generate fingerprints that are computationally indistinguishable from real ones, a task that prior art could not accomplish. Show less

Secure Function Evaluation (SFE) requires the underlying function to be compiled to a Boolean logic circuit. Designing custom SFE compilers has been an active research area. However, intelligent adaptation of the Integrated Circuits (IC) synthesis tools outperforms these compilers. It is time for the custom compilers to embrace this trend.

Emerging complex deep neural networks require a large amount of data to achieve a high precision. However, the high-volume of data is often collected from user’s logs and personal data which contains sensitive information about individuals. We provide a summary of recent cryptographic methodologies for provably privacy-preserving deep learning and inference.

Biometric authentication is increasingly being used for large scale human authentication and identification, creating the risk of leaking the biometric secrets of millions of users in the case of database compromise. Powerful “fuzzy” cryptographic techniques for biometric template protection, such as secure sketches, could help in principle, but go unused in practice. This is because they would require new biometric matching algorithms with potentially much diminished accuracy. We introduce a… Show more

Biometric authentication is increasingly being used for large scale human authentication and identification, creating the risk of leaking the biometric secrets of millions of users in the case of database compromise. Powerful “fuzzy” cryptographic techniques for biometric template protection, such as secure sketches, could help in principle, but go unused in practice. This is because they would require new biometric matching algorithms with potentially much diminished accuracy. We introduce a new primitive called a multisketch that generalizes secure sketches. Multisketches can work with existing biometric matching algorithms to generate strong cryptographic keys from biometric data reliably. A multisketch works on a biometric database containing multiple biometrics — e.g., multiple fingerprints — of a moderately large population of users (say, thousands). It conceals the correspondence between users and their biometric templates, preventing an attacker from learning the biometric data of a user in the advent of a breach, but enabling derivation of user-specific secret keys upon successful user authentication. We design a multisketch over tenprints — fingerprints of ten fingers — called TenSketch. We report on a prototype implementation of TenSketch, showing its feasibility in practice. We explore several possible attacks against TenSketch database and show, via simulations with real tenprint datasets, that an attacker must perform a large amount of computation to learn any meaningful information from a stolen TenSketch database.
Show less

Advancements in deep learning enable cloud servers to provide inference-as-a-service for clients. In this scenario, clients send their raw data to the server to run the deep learning model and send back the results. One standing challenge in this setting is to ensure the privacy of the clients’ sensitive data. Oblivious inference is the task of running the neural network on the client’s input without disclosing the input or the result to the server. This paper introduces XONN, a novel… Show more

Advancements in deep learning enable cloud servers to provide inference-as-a-service for clients. In this scenario, clients send their raw data to the server to run the deep learning model and send back the results. One standing challenge in this setting is to ensure the privacy of the clients’ sensitive data. Oblivious inference is the task of running the neural network on the client’s input without disclosing the input or the result to the server. This paper introduces XONN, a novel end-to-end framework based on Yao’s Garbled Circuits (GC) protocol, that provides a paradigm shift in the conceptual and practical realization of oblivious inference. In XONN, the costly matrix-multiplication operations of the deep learning model are replaced with XNOR operations that are essentially free in GC. We further provide a novel algorithm that customizes the neural network such that the runtime of the GC protocol is minimized without sacrificing the inference accuracy.

We design a user-friendly high-level API for XONN, allowing expression of the deep learning model architecture in an unprecedented level of abstraction. Extensive proof- of-concept evaluation on various neural network architectures demonstrates that XONN outperforms prior art such as Gazelle (USENIX Security’18) by up to 7×, MiniONN (ACM CCS’17) by 93×, and SecureML (IEEE S&P’17) by 37×. State-of-the-art frameworks require one round of interaction between the client and the server for each layer of the neural network, whereas, XONN requires a constant round of interactions for any number of layers in the model. XONN is first to perform oblivious inference on Fitnet architectures with up to 21 layers, suggesting a new level of scalability compared with state-of-the-art. Moreover, we evaluate XONN on four datasets to perform privacy-preserving medical diagnosis. The datasets include breast cancer, diabetes, liver disease, and Malaria. Show less

Secure Multi-party Computation (MPC) is one of the most influential achievements of modern cryptography: it allows evaluation of an arbitrary function on private inputs from multiple parties without revealing the inputs. A crucial step of utilizing MPC protocols is to describe the function as a Boolean circuit. While efficient solutions have been proposed for special case of two-party secure computation, the general case of more than two-party is not addressed. This paper proposes MPCircuits… Show more

Secure Multi-party Computation (MPC) is one of the most influential achievements of modern cryptography: it allows evaluation of an arbitrary function on private inputs from multiple parties without revealing the inputs. A crucial step of utilizing MPC protocols is to describe the function as a Boolean circuit. While efficient solutions have been proposed for special case of two-party secure computation, the general case of more than two-party is not addressed. This paper proposes MPCircuits, the first automated solution to devise the optimized Boolean circuit representation for any MPC function using hardware synthesis tools with new customized libraries that are scalable to multiple parties. MPCircuits creates a new end-to-end toolchain to facilitate practical scalable MPC realization. To illustrate the practicality of MPCircuits, we design and implement a set of five circuits that represent real-world MPC problems. Our benchmarks inherently have different computational and communication complexities and are good candidates to evaluate MPC protocols. We also formalize the metrics by which a given protocol can be analyzed. We provide extensive experimental evaluations for these benchmarks; two of which are the first reported solutions in multi-party settings. As our experimental results indicate, MPCircuits reduces the computation time of MPC protocols by up to 4.2×. Show less

We present ARM2GC, a novel secure computation framework based on Yao's Garbled Circuit (GC) protocol and the ARM processor. It allows users to develop privacy-preserving applications using standard high-level programming languages (e.g., C) and compile them using off-the-shelf ARM compilers (e.g., gcc-arm). The main enabler of this framework is the introduction of SkipGate, an algorithm that dynamically omits the communication and encryption cost of the gates whose outputs are independent of… Show more

We present ARM2GC, a novel secure computation framework based on Yao's Garbled Circuit (GC) protocol and the ARM processor. It allows users to develop privacy-preserving applications using standard high-level programming languages (e.g., C) and compile them using off-the-shelf ARM compilers (e.g., gcc-arm). The main enabler of this framework is the introduction of SkipGate, an algorithm that dynamically omits the communication and encryption cost of the gates whose outputs are independent of the private data. SkipGate greatly enhances the performance of ARM2GC by omitting costs of the gates associated with the instructions of the compiled binary, which is known by both parties involved in the computation. Our evaluation on benchmark functions demonstrates that ARM2GC not only outperforms the current GC frameworks that support high-level languages, it also achieves efficiency comparable to the best prior solutions based on hardware description languages. Moreover, in contrast to previous high-level frameworks with domain-specific languages and customized compilers, ARM2GC relies on standard ARM compiler which is rigorously verified and supports programs written in the standard syntax. Show less

As the amount of data generated by the Internet of the Things (IoT) devices keeps increasing, many applications need to offload computation to the cloud. However, it often entails risks due to security and privacy issues. Encryption and decryption methods add to an already significant computational burden. In this paper, we propose a novel framework, called SecureHD, which provides a secure learning solution based on the idea of high-dimensional (HD) computing. We encode original data into… Show more

As the amount of data generated by the Internet of the Things (IoT) devices keeps increasing, many applications need to offload computation to the cloud. However, it often entails risks due to security and privacy issues. Encryption and decryption methods add to an already significant computational burden. In this paper, we propose a novel framework, called SecureHD, which provides a secure learning solution based on the idea of high-dimensional (HD) computing. We encode original data into secure, high-dimensional vectors. The training is performed with the encoded vectors. Thus, applications can send their data to the cloud with no security concerns, while the cloud can perform the offloaded tasks without additional decryption steps. In particular, we propose a novel HD-based classification algorithm which is suitable to handle a large amount of data that the cloud typically processes. In addition, we also show how SecureHD can recover the encoded data in a lossless manner. In our evaluation, we show that the proposed SecureHD framework can perform the encoding and decoding tasks 145.6× and 6.8× faster than a state-of-the-art encryption/decryption library running on the contemporary CPU. In addition, our learning method achieves high accuracy of 95% on average for diverse practical classification tasks including cloud-scale datasets. Show less

We present a new secure protocol for approximate nearest neighbor search over the Euclidean distance tailored for massive datasets in the semi-honest model. At a high level, our protocol combines additively homomorphic encryption (for distance computation) and garbled circuits (for top-k selection). To achieve good performance, we utilize several algorithmic and implementational improvements. In particular, we show the existence of a linear-sized circuit for approximate top-k selection. As an… Show more

We present a new secure protocol for approximate nearest neighbor search over the Euclidean distance tailored for massive datasets in the semi-honest model. At a high level, our protocol combines additively homomorphic encryption (for distance computation) and garbled circuits (for top-k selection). To achieve good performance, we utilize several algorithmic and implementational improvements. In particular, we show the existence of a linear-sized circuit for approximate top-k selection. As an example, for the SIFT dataset of image descriptors (1M data points, 128 dimensions), our algorithm when run on two standard Azure instances can retrieve IDs of the 10 nearest neighbors with accuracy 92% in less than 4 seconds. This improves by more than an order of magnitude when compared to the alternative approaches. Show less

We provide a systemization of knowledge of the recent progress made in addressing the crucial problem of deep learning on encrypted data. The problem is important due to the prevalence of deep learning models across various applications, and privacy concerns over the exposure of deep learning IP and user's data. Our focus is on provably secure methodologies that rely on cryptographic primitives and not trusted third parties/platforms. Computational intensity of the learning models, together… Show more

We provide a systemization of knowledge of the recent progress made in addressing the crucial problem of deep learning on encrypted data. The problem is important due to the prevalence of deep learning models across various applications, and privacy concerns over the exposure of deep learning IP and user's data. Our focus is on provably secure methodologies that rely on cryptographic primitives and not trusted third parties/platforms. Computational intensity of the learning models, together with the complexity of realization of the cryptography algorithms hinder the practical implementation a challenge. We provide a summary of the state-of-the-art, comparison of the existing solutions, as well as future challenges and opportunities. Show less

In this article, we present SHAIP, a secure Hamming distance–based mutual authentication protocol. It allows an unlimited number of authentications by employing an intrinsic Physical Unclonable Function (PUF). PUFs are being increasingly employed for remote authentication of devices. Most of these devices have limited resources. Therefore, the intrinsic PUFs are most suitable for this task as they can be built with little or no modification to the underlying hardware platform. One major… Show more

In this article, we present SHAIP, a secure Hamming distance–based mutual authentication protocol. It allows an unlimited number of authentications by employing an intrinsic Physical Unclonable Function (PUF). PUFs are being increasingly employed for remote authentication of devices. Most of these devices have limited resources. Therefore, the intrinsic PUFs are most suitable for this task as they can be built with little or no modification to the underlying hardware platform. One major drawback of the current authentication schemes is that they expose the PUF response. This makes the intrinsic PUFs, which have a limited number of challenge-response pairs, unusable after a certain number of authentication sessions. Moreover, these schemes are one way in the sense that they only allow one party, the prover, to authenticate herself to the verifier. We propose a symmetric mutual authentication scheme based on secure (privacy-preserving) computation of the Hamming distance between the PUF response from the remote device and reference response stored at the verifier end. This allows both parties to authenticate each other without revealing their respective sets of inputs. We show that our scheme is effective with all state-of-the-art intrinsic PUFs. The proposed scheme is lightweight and does not require any modification to the underlying hardware. Show less

We present Chameleon, a novel hybrid (mixed-protocol) framework for secure function evaluation (SFE) which enables two parties to jointly compute a function without disclosing their private inputs. Chameleon combines the best aspects of generic SFE protocols with the ones that are based upon additive secret sharing. In particular, the framework performs linear operations in the ring Z 2 l using additively secret shared values and nonlinear operations using Yao's Garbled Circuits or the… Show more

We present Chameleon, a novel hybrid (mixed-protocol) framework for secure function evaluation (SFE) which enables two parties to jointly compute a function without disclosing their private inputs. Chameleon combines the best aspects of generic SFE protocols with the ones that are based upon additive secret sharing. In particular, the framework performs linear operations in the ring Z 2 l using additively secret shared values and nonlinear operations using Yao's Garbled Circuits or the Goldreich-Micali-Wigderson protocol. Chameleon departs from the common assumption of additive or linear secret sharing models where three or more parties need to communicate in the online phase: the framework allows two parties with private inputs to communicate in the online phase under the assumption of a third node generating correlated randomness in an offline phase. Almost all of the heavy cryptographic operations are precomputed in an offline phase which substantially reduces the communication overhead. Chameleon is both scalable and significantly more efficient than the ABY framework (NDSS'15) it is based on. Our framework supports signed fixed-point numbers. In particular , Chameleon's vector dot product of signed fixed-point numbers improves the efficiency of mining and classification of encrypted data for algorithms based upon heavy matrix multiplications. Our evaluation of Chameleon on a 5 layer convolutional deep neural network shows 110x and 3.5x faster executions than Microsoft CryptoNets (ICML'16) and MiniONN (CCS'17), respectively. Show less

This paper proposes DeepSecure, a novel framework that enables scalable execution of the state-of-the-art Deep Learning (DL) models in a privacy-preserving setting. DeepSecure targets scenarios in which neither of the involved parties including the cloud servers that hold the DL model parameters or the delegating clients who own the data is willing to reveal their information. Our framework is the first to empower accurate and scalable DL analysis of data generated by distributed clients… Show more

This paper proposes DeepSecure, a novel framework that enables scalable execution of the state-of-the-art Deep Learning (DL) models in a privacy-preserving setting. DeepSecure targets scenarios in which neither of the involved parties including the cloud servers that hold the DL model parameters or the delegating clients who own the data is willing to reveal their information. Our framework is the first to empower accurate and scalable DL analysis of data generated by distributed clients without sacrificing the security to maintain efficiency. The secure DL computation in DeepSecure is performed using Yao’s Garbled Circuit (GC) protocol. We devise GC-optimized realization of various components used in DL. Our optimized implementation achieves more than 58-fold higher throughput per sample compared with the best prior solution. In addition to our optimized GC realization, we introduce a set of novel low-overhead pre-processing techniques which further reduce the GC overall runtime in the context of deep learning. Extensive evaluations of various DL applications demonstrate up to two orders-of-magnitude additional runtime improvement achieved as a result of our pre-processing methodology. We also provide mechanisms to securely delegate GC computations to a third party in constrained embedded settings. Show less

We introduce CAMsure, the first realization of secure Content Addressable Memory (CAM) in the context of approximate search using near-neighbor algorithms. CAMsure provides a lightweight solution for practical secure (approximate) search with a minimal drop in the accuracy of the search results. CAM has traditionally been used as a hardware search engine that explores the entire memory in a single clock cycle. However, there has been little attention to the security of the data stored in CAM… Show more

We introduce CAMsure, the first realization of secure Content Addressable Memory (CAM) in the context of approximate search using near-neighbor algorithms. CAMsure provides a lightweight solution for practical secure (approximate) search with a minimal drop in the accuracy of the search results. CAM has traditionally been used as a hardware search engine that explores the entire memory in a single clock cycle. However, there has been little attention to the security of the data stored in CAM. Our approach stores distance-preserving hash embeddings within CAM to ensure data privacy. The hashing method provides data confidentiality while preserving similarity in the sense that a high resemblance in the data domain is translated to a small Hamming distance in the hash domain. Consequently, the objective of near-neighbor search is converted to approximate lookup table search which is compatible with the realizations of emerging content addressable memories. Our methodology delivers on average two orders of magnitude faster response time compared to RAM-based solutions that preserve the privacy of data owners. Show less

PriSearch allows two parties, Alice holding a query string and Bob holding a text, to perform string search, while keeping both the query and the text private without relying on any third party. Such privacy-preserving string search avoids any data leakage when handling sensitive information, e.g., genomic data. PriSearch provides an efficient solution where two parties only need to interact for a constant number of rounds independent of query and text size. Our work is based on provably secure… Show more

PriSearch allows two parties, Alice holding a query string and Bob holding a text, to perform string search, while keeping both the query and the text private without relying on any third party. Such privacy-preserving string search avoids any data leakage when handling sensitive information, e.g., genomic data. PriSearch provides an efficient solution where two parties only need to interact for a constant number of rounds independent of query and text size. Our work is based on provably secure Yao’s Garbled Circuit (GC) protocol that requires the string search algorithm to be described as a Boolean circuit. We leverage logic synthesis tools to generate optimized Boolean circuit for PriSearch such that it incurs the minimum communication/computation cost. We achieve almost 2× improvement in execution time compared to the state-of-the-art solution.
Show less

The Stable Matching (SM) algorithm has been deployed in many real-world scenarios including the National Residency Matching Program (NRMP) and financial applications such as matching of suppliers and consumers in capital markets. Since these applications typically involve highly sensitive information such as the underlying preference lists, their current implementations rely on trusted third parties. This paper introduces the first provably secure and scalable implementation of SM based on… Show more

The Stable Matching (SM) algorithm has been deployed in many real-world scenarios including the National Residency Matching Program (NRMP) and financial applications such as matching of suppliers and consumers in capital markets. Since these applications typically involve highly sensitive information such as the underlying preference lists, their current implementations rely on trusted third parties. This paper introduces the first provably secure and scalable implementation of SM based on Yao’s garbled circuit protocol and Oblivious RAM (ORAM). Our scheme can securely compute a stable match for 8k pairs four orders of magnitude faster than the previously best known method. We achieve this by introducing a compact and efficient sub-linear size circuit. We even further decrease the computation cost by three orders of magnitude by proposing a novel technique to avoid unnecessary iterations in the SM algorithm. We evaluate our implementation for several problem sizes and plan to publish it as open-source. Show less

In Near-Neighbor Search (NNS), a new client wants to query a database (held by a server) for the most similar data (near-neighbors) with a certain similarity metric. The Privacy-Preserving variant (PP-NNS) requires that neither server nor the client shall learn anything about the other party’s data except what can be inferred from the outcome of NNS. The overwhelming growth in the size of current datasets and the lack of a truly secure server in the online world render the existing solutions… Show more

In Near-Neighbor Search (NNS), a new client wants to query a database (held by a server) for the most similar data (near-neighbors) with a certain similarity metric. The Privacy-Preserving variant (PP-NNS) requires that neither server nor the client shall learn anything about the other party’s data except what can be inferred from the outcome of NNS. The overwhelming growth in the size of current datasets and the lack of a truly secure server in the online world render the existing solutions impractical either due to their high computational requirements or non-realistic assumptions which potentially compromise privacy. PP-NNS having query time sub-linear in the size of the database has been proposed as an open research direction. In this paper, we provide the first such algorithm which has a sub-linear query time and the ability to handle Honest-but-Curious (HbC) parties. At the heart of our proposal lies a secure probabilistic embedding scheme generated from a novel probabilistic transformation over Locality Sensitive Hashing (LSH) family. We provide in- formation theoretic bound for the privacy gauntness and support our theoretical claims using substantial empirical evidence on real-world datasets.
Show less

We introduce GenMatch, a novel set of techniques based on hardware synthesis, for achieving efficient and scalable privacy-preserving genetic testing. Processing and handling sensitive genome data require methodologies to thwart possible attacks and data theft scenarios. The GenMatch secure genome testing method utilizes Yao’s Garbled Circuit (GC) protocol and creates a formulation of the matching problem in a sequential GC format. Our formulation involves private matching of genome data by the… Show more

We introduce GenMatch, a novel set of techniques based on hardware synthesis, for achieving efficient and scalable privacy-preserving genetic testing. Processing and handling sensitive genome data require methodologies to thwart possible attacks and data theft scenarios. The GenMatch secure genome testing method utilizes Yao’s Garbled Circuit (GC) protocol and creates a formulation of the matching problem in a sequential GC format. Our formulation involves private matching of genome data by the GC protocol. Our method reduces the memory footprint of the secure computation such that it can be done in a resource-constrained devices like embedded platforms, rendering the method scalable and time-efficient. Proof-of-concept evaluations are performed on the application of matching Human Leukocyte Antigen (HLA) data for organ and tissue transplant compatibility between recipient and donors. This type of testing also has applications in ancestry testing and genetic matchmaking. HLA data of the recipient is matched with a database of possible donor HLA data while keeping the data from both parties private. Experimental results on real genome data demonstrate the practicability of GenMatch in terms of timing and communication complexity for HLA database in the order of million user profiles. Show less