Publications

Privacy guarantees are still insufficient for outsourced data processing in the cloud. While employing encryption is feasible for data at rest or in transit, it is not for computation without remarkable performance slowdown. Thus, handling data in plaintext during processing is still required, which creates vulnerabilities that can be exploited by malicious entities. Homomorphic encryption (HE) schemes are natural candidates for computation in the cloud since they enable processing of ciphertexts without any knowledge about the related plaintexts or the decryption key. This work focuses on the challenge of developing an efficient implementation of the BFV HE scheme on CUDA. This is done by combining and adapting different approaches from the literature, namely the double-CRT representation and the Discrete Galois Transform. Moreover, we propose and implement an improved formulation of the DGT inspired by classical algorithms, which computes the transform up to 2.6 times faster than the state-of-the-art. By using these approaches, we obtain up to 3.6 times faster homomorphic multiplication.

Recent works challenged the number-theoretic transform (NTT) as the most efficient method for polynomial multiplication in GPU implementations of fully homomorphic encryption schemes such as CKKS and BFV. In particular, these works argue that the discrete galois transform (DGT) is a better candidate for this particular case. However, these claims were never rigorously validated, and only intuition was used to argue in favor of each transform. This work brings some light on the discussion by developing similar CUDA implementations of the CKKS cryptosystem, differing only in the underlying transform and related data structure. We ran several experiments and collected performance metrics in different contexts, ranging from the basic direct comparison between the transforms to measuring the impact of each one on the inference phase of the logistic regression algorithm. Our observations suggest that, despite some specific polynomial ring configurations, the DGT in a standalone implementation does not offer the same performances of the NTT. However, when we consider the entire cryptosystem, we noticed that the effects of the higher arithmetic density of the DGT on other parts of the implementation are substantial, implying a considerable performance improvement of up to 15% on the homomorphic multiplication. Furthermore, this speedup is consistent when we consider a more complex application, indicating that the DGT suits better the target architecture.

Cloud computing is a ubiquitous paradigm responsible for a fundamental change in the way distributed computingis performed. The possibility to outsource the installation, maintenance and scalability of servers, added to competitive prices, makes this platform highly attractive to the computing industry. Despite this, privacy guarantees are still insufficient for data processed in the cloud, since the data owner has no real control over the processing hardware. This work proposes a framework for database encryption that preserves data secrecy on an untrusted environment and retains searching and updating capabilities. It employs order-revealing encryption to perform selection with time complexity in Θ(log n), and homomorphic encryption to enable computation over ciphertexts. When compared to the current state of the art, our approach provides higher security and flexibility. A proof-of-concept implementation on top of the MongoDB system is offered and applied in the implementation of some of the main predicates required by the winning solution to Netflix Grand Prize.

Privacy guarantees are still insufficient for outsourced data processing in the cloud. While employing encryption is feasible for data at rest or in transit, it is not for computation without remarkable performance slowdown. Thus, handling data in plaintext during processing is still required, which creates vulnerabilities that can be exploited by malicious entities. Homomorphic encryption schemes enable computation over ciphertexts without knowing the related plaintexts or the decryption key. This work focuses on the challenge of developing an efficient implementation of the BFV scheme on CUDA. This is done by combining and adapting different literature approaches, as the double-CRT representation and the Discrete Galois Transform. Moreover, we propose and implement an improved formulation of the DGT inspired by classical algorithms, which computes the transform up to 2.6 times faster than the state-of-the-art. By using these approaches, we obtain up to 3.6 times faster homomorphic multiplication.

Cloud computing is a ubiquitous paradigm. It has been responsible for a fundamental change in the way distributed computing is performed. The possibility to outsource the installation, maintenance and scalability of servers, added to competitive prices, makes this platform highly attractive to the industry. Despite this, privacy guarantees are still insufficient for data processed in the cloud, since the data owner has no real control over the processing hardware. This work proposes a framework for database encryption that preserves data secrecy on an untrusted environment and retains searching and updating capabilities. It employs order-revealing encryption to provide selection with time complexity in Θ(log n),and homomorphic encryption to enable computation over ciphertexts. When compared to the current state of the art, our approach provides higher security and flexibility. A proof-of-concept implementation on top of MongoDB is offered and presents an 11-factor overhead for a selection query over an encrypted database.

Under the dominant cloud computing paradigm, employing encryption for data storage and transport may not be enough. Security guarantees should also be extended to data processing. Homomorphic encryption schemes are natural candidates for computation over encrypted data since they are able to satisfy the requirements imposed by the cloud environment. This work presents CUYASHE as a GPGPU implementation of the leveled fully homomorphic scheme YASHE. It employs CUDA, the Chinese Remainder Theorem and the Fast Fourier Transform to obtain significant performance improvements. In particular, there was a speedup between 6 and 35 times for homomorphic multiplication.

Under the dominant cloud computing paradigm, employing encryption fordata storage and transport may not be enough. Security guarantees should also be extended to data processing, to preserve the privacy of data owners and contractors. Homomorphic encryption schemes are a natural candidate for computing over encrypted data, satisfying these new security requirements. In this work, CUYASHE is presented as a GPGPU implementation of the leveled fully homomorphic scheme YASHE. The implementation employs the CUDA platform, the Chinese Remainder Theorem and the Fast Fourier Transform to obtain significant performance improvements. When compared with the state-of-the-art implementation in CPUs, speedups of 20% for homomorphic addition and 58% for multiplication were observed. These operations are performance-critical for evaluating any function over encrypted data, demonstrating that GPUs are an appropriate technology for bootstraping privacy-preserving cloud computing environments.

Neste trabalho falamos sobre a utilização da arquitetura CUDA, criada pela NVIDIA, na simulação de traçamento de raios. Essa arquitetura permite a execução de programas através do processador da placa gráfica, com o intuito de aproveitar a grande capacidade de poder de processamento paralelo que essa possui. Mostramos que, dessa forma o ganho de performance pode chegar a 82% em relação ao algoritmo sequencial.

Under the dominant cloud computing paradigm, employing encryption for data storage and transport may not be enough for assurance of secrecy, because the data owner has no real control over the processing hardware. This way,security guarantees should also be extended to data processing. Homomorphic encryption schemes are natural candidates for computation over encrypted data in the cloud, since they are able to satisfy all security requirements imposed by that environment. This work investigates strategies to efficiently implement the leveled fully homomorphic scheme YASHE on GPGPUs. As result of this research, the CUYASHE library was developed and made available to the community. In particular, it presents a speedup between 6 and 35 times for homomorphic multiplication. This operation is performance-critical for evaluating any function over encrypted data, demonstrating that GPGPUs are an appropriate technology for bootstrapping privacy-preserving cloud computing environments.

Data is the gold of the modern era, and the capability of collecting it is as crucial as securely storing and handling it. This is a compilation thesis composed of published or under revision papers that explore different aspects of privacy-preserving computing, such as the efficient implementation of primitives, protocols, and applications. Our work offers a framework for an always-encrypted database, which can store ciphertexts and answer encrypted queries without decryption. In the same direction, we also study the case of large-scale data collection from smart meters. In this case, an entity, such as the electricity provider, collects user data that can be used in statistical methods, such as machine learning, and splits the computation through a network without revealing user information. On the other hand, we also present papers that explore the efficient implementation of the arithmetic used by modern fully homomorphic encryption schemes, such as BFV and the CKKS. We experiment with different methods targeting the CUDA architecture and show how the cryptosystems can be accelerated through the proper choice for the data structure, locality, and algorithm used on the polynomial multiplication. Four papers are presented on these topics, as well as a discussion that connects our work during the years of research.

Security in cloud computing is a relevant topic for research. Multiple branches of industry are embracing this paradigm to reduce operational costs, improve scalability and availability. Surprisingly, several techniques are still missing to properly preserve privacy on the cloud. Employing encryption for data storage and transport is not enough once the data owner has no real control over the processing hardware. This way, security requirements must also be extended to data processing tasks. Homomorphic encryption schemes are natural candidates for computation over encrypted data, since they are able to satisfy the requirements imposed by the cloud environment. This work investigates strategies to efficiently implement the leveled fully homomorphic scheme YASHE. It employs the CUDA platform to provide parallel processing capabilities and the chinese remainder theorem to replace expensive big integer arithmetic by simpler instructions natively supported in hardware. Moreover, this work offers a comparison between the Fast Fourier transform and the Number-Theoretic transform for reducing the complexity of polynomial multiplication. The former is provided by the cuFFT library, while the latter is implemented through the Stockham formulation. As result of this research, the cuYASHE library was developed and made available to the community. When compared with the state-of-the-art implementation in CPU, GPU and FPGA, it shows speed-ups for all operations. In particular, there was an improvement between 6 and 35 times for polynomial multiplication. This operation is performance-critical for evaluating any function over encrypted data, demonstrating that GPUs are an appropriate technology for bootstrapping privacy-preserving cloud computing environments.