In this paper, we present a new modular multiplier design that offers flexibility regarding the operand sizes it processes in parallel. The multiplier can efficiently compute different sizes using the same ASIC hardware, enabling parallel computations for smaller sizes, for example a 1024-bit instantiation of our multiplier can perform either one 1024-bit, sixteen 64-bit, or four 256-bit multiplications, etc. This capability is particularly valuable in accelerating a plethora of cryptosystems, such as RSA, ECC, or Fully Homomorphic Encryption, using the same ASIC hardware, since operand sizes can vary depending on the security parameters and the application requirements. The multiplier can be used in conjunction with software methods for parallelization. For instance, our multiplier enables users to employ both RNS and non-RNS versions of FHE using a single hardware accelerator. We implement our multiplier in hardware and demonstrate its efficiency compared to state-of-theart Montgomery designs, while offering the additional advantage of parallel processing flexibility

In this study, we introduce Coala, a novel framework designed to enhance the performance of finite field transformations for GPU environments. We have developed a GPU-optimized version of the Discrete Galois Transformation (DGT), a variant of the Number Theoretic Transform (NTT). We introduce a novel data access pattern scheme specifically engineered to enable coalesced accesses, significantly enhancing the efficiency of data transfers between global and shared memory. This enhancement not only boosts execution efficiency but also optimizes the interaction with the GPU's memory architecture. Additionally, Coala presents a comprehensive framework that optimizes the allocation of computational tasks across the GPU's architecture and execution kernels, thereby maximizing the use of GPU resources. Lastly, we provide a flexible method to adjust security levels and polynomial sizes through the incorporation of an in-kernel RNS method, and a flexible parameter generation approach. Comparative analysis against current state-of-the-art techniques reveals significant improvements. We observe performance gains of 2.82′ − 17.18′ against other DGT works on GPUs for different parameters, achieved concurrently with equal or lesser memory utilization.

Fully Homomorphic Encryption (FHE) is the pin-nacle of privacy-preserving outsourced computation as it enables meaningful computation to be performed in the encrypted domain without the need for decryption or back-and-forth communication between the client and service provider. Nevertheless, FHE is still orders of magnitude slower than unencrypted computation, which hinders its widespread adoption. In this work, we propose Furbo, a plug-and-play framework that can act as middleware between any FHE compiler and any FHE library. Our proposal employs smart ciphertext memory management and caching techniques to reduce data movement and computation, and can be applied to FHE applications without modifications to the underlying code. Experimental results using Microsoft SEAL as the base FHE library and focusing on privacy-preserving Machine Learning as a Service show up to 2x performance improvement in the fully-connected layers, and up to 24x improvement in the convolutional layers without any code change.

Shoup’s modular multiplication algorithm follows the idea of Barrett reduction algorithm. While Barrett reduction can be used to multiply two arbitrary numbers, Shoup’s multiplier requires a pre-computed value for one of the operands. At the same time, Shoup is more efficient as it requires less computation. In this work, we extend Shoup’s multiplier by adding functionality to operate on arbitrary operands in such a way that the multiplier can be used in both ways: using the original Shoup algorithm when one of the arguments can be pre-computed, or a general multiplier. The general multiplier reuses Shoup functionality in its core. We compare the performance of the multipliers in a software simulator and a hardware design.

Fully Homomorphic Encryption (FHE) enables computation directly on encrypted data. This property is desirable for outsourced computation of sensitive data as it relies solely on the underlying security of the cryptosystem and not in access control policies. Even though FHE is still significantly slower than unencrypted computation, practical times are possible for applications easily representable as low-order polynomials, since most FHE schemes support modular addition and multiplication over ciphertexts. If, however, an application cannot be expressed with low-order polynomials, then Boolean logic must be emulated. This bit-level arithmetic enables any computation to be performed homomorphically. Nevertheless, as it runs on top of the natively supported modular arithmetic, it has poor performance, which hinders its use in the majority of scenarios. In this work, we propose Bridging, a technique that allows conversion from bit-level to modular arithmetic and vice-versa. This enables the use of the comprehensive computation provided by bit-level arithmetic and the performance of modular arithmetic within the same application. Experimental results show that Bridging can lead to 1-2 orders of magnitude performance improvement for tested benchmarks and two real-world applications: URL denylisting and genotype imputation. Bridging performance comes from two factors: reduced number of operations and smaller multiplicative depth.

The dramatic increase of data breaches in modern computing platforms has emphasized that access control is not sufficient to protect sensitive user data. Recent advances in cryptography allow end-to-end processing of encrypted data without the need for decryption using Fully Homomorphic Encryption (FHE). Such computation however, is still orders of magnitude slower than direct (unencrypted) computation. Depending on the underlying cryptographic scheme, FHE schemes can work natively either at bit-level using Boolean circuits, or over integers using modular arithmetic. Operations on integers are limited to addition/subtraction and multiplication. On the other hand, bit-level arithmetic is much more comprehensive allowing more operations, such as comparison and division. While modular arithmetic can emulate bit-level computation, there is a significant cost in performance. In this work, we propose a novel method, dubbed bridging, that blends faster and restricted modular computation with slower and comprehensive bit-level computation, making them both usable within the same application and with the same cryptographic scheme instantiation. We introduce and open source C++ types representing the two distinct arithmetic modes, offering the possibility to convert from one to the other. Experimental results show that bridging modular and bit-level arithmetic computation can lead to 1--2 orders of magnitude performance improvement for tested synthetic benchmarks, as well as one real-world FHE application: a genotype imputation case study.

Improving fully homomorphic encryption computation by designing specialized hardware is an active topic of research. The most prominent encryption schemes operate on long polynomials requiring many concurrent modular multiplications of very big numbers. Thus, it is crucial to use many small and efficient multipliers. Interleaved and Montgomery iterative multipliers are the best candidates for the task. Interleaved designs, however, suffer from longer latency as they require a number comparison within each iteration; Montgomery designs, on the other hand, need extra conversion of the operands or the result. In this work, we propose a novel hardware design that combines the best of both worlds: Exhibiting the carry save addition of Montgomery designs without the need for any domain conversions. Experimental results demonstrate improved latency-area product efficiency by up to 47% when compared to the standard Interleaved multiplier for large arithmetic word sizes.

The rapid increase of recent privacy attacks has significantly decreased trust on behalf of the users. A root cause to these problems is that modern computer architectures have always been designed for performance, while security protections are traditionally addressed reactively. Practical security protections, such as Intel SGX, rely on processing unencrypted data in the architectural state, which leaves them exposed to software attacks (e.g., SGXpectre). This work revisits the traditional computation stack and introduces a novel computation paradigm, where data is never decrypted in the architectural state. Through our architecture, data are protected with symmetric or asymmetric encryption and the programmer manipulates them directly in the encrypted domain. To increase performance, we exploit data locality by introducing decryption caches in the microarchitectural state. Our proposal addresses all abstraction levels in the computation stack: from microarchitecture to library support for high-level programming. The proposed architecture is instantiated through new assembly instructions, registers and functional units operating on large integers. In our evaluation, we extend the OpenRISC 1000 architecture and develop open-source libraries for C++. As a case study, we employ data-oblivious benchmarks and observe that for benchmarks with high temporal locality, our architecture can achieve comparable performance to processing unencrypted data.

Encrypted computation enables processing sensitive data directly in the encrypted domain, which allows outsourcing to third parties without compromising privacy. Recent solutions that leverage partial homomorphic encryption, however, require excessive lookup tables or obfuscated software oracles to implement branching over encrypted control values. To address these limitations and make encrypted computations more practical on memory-constrained systems, we present a novel approach for limiting the amount of randomness in probabilistic ciphertexts, using number theory primitives and hash tables. This allows de-randomizing probabilistic ciphertexts and define a new encrypted abstract machine that is memory-friendly to the target system. Compared to obfuscated oracles in previous work, our method performs control flow decisions over ciphertexts twice as fast, while requiring selectively small lookup tables.

The rapid expansion and increased popularity of cloud computing comes with no shortage of privacy concerns about outsourcing computation to semi-trusted parties. Leveraging the power of encryption, in this paper, we introduce Cryptoleq: an abstract machine based on the concept of one instruction set computer, capable of performing general-purpose computation on encrypted programs. The program operands are protected using the Paillier partially homomorphic cryptosystem, which supports addition on the encrypted domain. Full homomorphism over addition and multiplication, which is necessary for enabling general-purpose computation, is achieved by inventing a heuristically obfuscated software re-encryption module written using Cryptoleq instructions and blended into the executing program. Cryptoleq is heterogeneous, allowing mixing encrypted and unencrypted instruction operands in the same program memory space. Programming with Cryptoleq is facilitated using an enhanced assembly language that allows the development of any advanced algorithm on encrypted data sets. In our evaluation, we compare Cryptoleq's performance against a popular fully homomorphic encryption library, and demonstrate correctness using a typical private information retrieval problem.