Lattices are the basis of most NIST-recommended post-quantum cryptography (PQC) schemes, required to thwart the threat posed by the eventual construction of large-scale quantum computers. At the same time, lattices enable more advanced cryptographic constructions, such as fully homomorphic encryption (FHE), which is increasingly used for privacy-preserving applications like machine learning. This work delves into the efficiency and trade-off assessment of polynomial multiplication algorithms and their applications to PQC, FHE, and other schemes. Such algorithms are at the core of lattice-based cryptography and may become a critical bottleneck when deploying PQC-and FHE-based solutions on resource-constrained devices. We propose a formal analysis of so-called incompleteness in the Number Theoretic Transform (NTT). Although this concept is not new, our systematization shows how to optimize polynomial multiplication in quotient rings, considering factors such as the degree of incompleteness, the associated prime moduli, constraints of the target platform, and target security level. Besides efficiency, we formally show that the systematized family of incomplete NTT variants supports a larger set of prime moduli. This property enables new trade-offs for algorithms like the FIPS-approved module-lattice-based key encapsulation mechanism (ML-KEM) and faster amortized bootstrapping in FHE schemes. Our results include shorter ciphertexts in ML-KEM with only a modest hit in performance and a 6 – 42% performance boost in the NTT computation of a state-of-the-art FHE solution.

Fully Homomorphic Encryption (FHE) enables secure computation on encrypted data without decryption, allowing a great opportunity for privacy-preserving computation. Many companies maintain extensive, high-quality databases to deliver services, making preserving data privacy during the database pattern searches crucial. With FHE, the server can take encrypted queries from clients and search through the reference database on the server without decryption, thus guaranteeing data security for all parties. While FHE provides a promising solution to data privacy, it has severe drawbacks of explosive memory requirements and excessive latency, which amplify the computational and memory inefficiencies for database search applications.To address these, we propose PATHE that exploits FHE and hyperdimensional computing (HDC), which provides high parallelism, excellent robustness to errors, for high-performance privacy-preserving database search. On the software side, we propose an FHE-friendly PATHE algorithm that leverages efficient FHE-HDC search and a scheme-switching-based argmax to support database search and maintain comparable accuracy to the state-of-the-art. On the hardware side, PATHE proposes an efficient and scalable FHE accelerator system using Compute Express Link (CXL) for large-scale FHE database search, along with a novel, storage-aware dataflow designed to optimize memory and storage transfers for large database workloads. We evaluate PATHE on the large-scale encrypted database of protein mass spectra, PATHE achieves 2.1× speedup and 1.7× better energy efficiency compared to the baseline system.

This work addresses the synthesis of efficient torus fully homomorphic encryption (TFHE) circuits for private Boolean function evaluation through encoding strategy management. Modern TFHE implementations support multiple plaintext encoding spaces, each offering distinct trade-offs between computational cost and the expressiveness enabled by larger plaintext domains. Smartly switching between encoding strategies to maximize evaluation efficiency remains challenging due to the lack of algorithmic support for determining when and where such transitions should occur. To address this, we propose a synthesis framework that enables encoding-switch-aware TFHE circuit generation. Our approach leverages the structural properties of the exclusive-or sum of products (ESOP) representation to partition Boolean functions into encoding-aligned regions, enabling cost-effective evaluation while minimizing switch overhead. Experimental results demonstrate that our encoding-aware synthesis technique significantly accelerates homomorphic Boolean function evaluation – achieving up to 53.46% and 23.34% average evaluation time reduction on general-purpose Boolean benchmarks – compared to advanced synthesis baselines lacking explicit encoding-switch management. This work lays the groundwork for systematic encoding strategy management in TFHE circuits and highlights the role of logic-level design automation in advancing efficient homomorphic evaluation.

Fully Homomorphic Encryption (FHE) enables arbitrary computations on encrypted data without decryption, thus protecting data in cloud computing scenarios. However, FHE adoption has been slow due to the significant computation and memory overhead it introduces. This becomes particularly challenging for end-to-end processes, including training and inference, for conventional neural networks on FHE-encrypted data. Additionally, machine learning tasks require a high throughput system due to data-level parallelism. However, existing FHE accelerators only utilize a single SoC, disregarding the importance of scalability. In this work, we address these challenges through two key innovations. First, at an algorithmic level, we combine hyperdimensional Computing (HDC) with FHE. The machine learning formulation based on HDC, a brain-inspired model, provides lightweight operations that are inherently well-suited for FHE computation. Consequently, FHE-HD has significantly lower complexity while maintaining comparable accuracy to the state-of-the-art. Second, we propose an efficient and scalable FHE system for FHE-based machine learning. The proposed system adopts a novel interconnect network between multiple FHE accelerators, along with an automated scheduling and data allocation framework to optimize throughput and hardware utilization. We evaluate the value of the proposed FHE-HD system on the MNIST dataset and demonstrate that the expected training time is 4.7 times faster compared to state-of-the-art MLP training. Furthermore, our system framework exhibits up to 38.2 times speedup and 13.8 times energy efficiency improvement over the baseline scalable FHE systems that use the conventional data-parallel processing flow.

The Tower variant of the Number Field Sieve (TNFS) is known to be asymptotically the most efficient algorithm to solve the discrete logarithm problem in finite fields of medium characteristics, when the extension degree is composite. A major obstacle to an efficient implementation of TNFS is the collection of algebraic relations, as it happens in dimension greater than 2. This requires the construction of new sieving algorithms which remain efficient as the dimension grows. In this article, we overcome this difficulty by considering a lattice enumeration algorithm which we adapt to this specific context. We also consider a new sieving area, a high-dimensional sphere, whereas previous sieving algorithms for the classical NFS considered an orthotope. Our new sieving technique leads to a much smaller running time, despite the larger dimension of the search space, and even when considering a larger target, as demonstrated by a record computation we performed in a 521-bit finite field \({\mathbb F}_{p^6}\). The target finite field is of the same form than finite fields used in recent zero-knowledge proofs in some blockchains. This is the first reported implementation of TNFS.