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.

Vehicular communication (V2X) technologies are expected to become common in the future, providing better efficiency and safety in transportation. This envisioned large-scale deployment, however, critically depends on addressing some issues. In special, to prevent abuse by drivers, messages exchanged among authorized vehicles must be authenticated. This implies the need of a Vehicular Public Key Infrastructure (VPKI). Unlike traditional PKIs, though, VPKIs are also expected to preserve the privacy of honest drivers, preventing their vehicles from being easily identified or tracked. One promising VPKI solution, which copes with such requirements and is among the main candidates for standardization in the United States, is the Security Credential Management System (SCMS). In this paper, aiming to enhance and address shortcomings identified in SCMS, we provide two main contributions. First, we describe and fix two birthday attacks against SCMS's certificate revocation process, thus improving the system's long-term privacy. Second, we propose a method that simplifies SCMS's architecture, removing the need for Linkage Authorities (LAs); this approach cuts down deployment costs while reducing the system's attack surface, in particular against some troublesome forms of replay attacks that are hereby unveiled.

This paper presents two efficient partially homomorphic encryption schemes built upon the approximate common divisor problem, believed to be resistant to quantum computer attacks. Both proposals, named FAHE1 and FAHE2, are additively homomorphic and have a symmetric nature, meaning that they are useful in scenarios where encryption and decryption are performed by the same entity. This is the case, for example, of encrypted databases stored in a public cloud. We also evaluate the performance of our proposals in comparison with two alternatives displaying additive homomorphism: the traditional Paillier asymmetric cryptosystem, which is not quantum-resistant; and the XPIR algorithm, which is both quantum-resistant and symmetric. Our experimental results show that both solutions provide considerable speed-ups when compared to Paillier. Namely, encryption and decryption with FAHE1 are, respectively, 120 and 25 times faster than Paillier's, while for FAHE2 both operations run more than 1000 times faster. In addition, when compared with a highly optimized XPIR code, our reference implementation remains quite competitive while producing smaller ciphertexts.

Vehicular communication (V2X) technologies allow vehicles to exchange information about the road conditions and their own status, and thereby enhance transportation safety and efficiency. For broader deployment, however, such technologies are expected to address security and privacy concerns, preventing abuse by users and by the system’s entities. In particular, the system is expected to enable the revocation of malicious vehicles, e.g., in case they send invalid information to their peers or to the roadside infrastructure; it should also prevent the system from being misused for tracking honest vehicles. Both features are enabled by Vehicular Public Key Infrastructure (VPKI) solutions such as Security Credential Management Systems (SCMS), one of the leading candidates for protecting V2X communication in the United States. Unfortunately, though, SCMS’s original revocation mechanism can lead to large Certification Revocation Lists (CRLs), which in turn impacts the bandwidth usage and processing overhead of the system. In this article, we propose a novel design called Activation Codes for Pseudonym Certificates (ACPC), which can be integrated into SCMS to address this issue. Our proposal is based on activation codes, short bit-strings without which certificates previously issued to a vehicle cannot be used by the latter, which are periodically distributed to non-revoked vehicles using an efficient broadcast mechanism. As a result, the identifiers of the corresponding certificates do no need to remain on the CRL for a long time, reducing the CRLs’ size and streamlining their distribution and verification of any vehicle’s revocation status. Besides describing ACPC in detail, we also compare it to similar-purpose solutions such as Issue First Activate Later (IFAL) and Binary Hash Tree based Certificate Access Management (BCAM). This analysis shows that our proposal not only improves privacy (e.g., in terms of resilience against colluding system authorities), but also leads to processing and bandwidth overheads that are orders of magnitude smaller than those observed in the state of the art.