Cryptology ePrint Archive
Not a member yet
24907 research outputs found
Sort by
A High Throughput Kyber NTT
Get PDFNIST recently selected Kyber as a standard for key encapsulation and decapsulation. As such, servers will soon need dedicated hardware for these encapsulation protocols. The computationally critical operation of Kyber is its Number Theoretic Transform, which is commonly accelerated by dedicated hardware such as FPGAs.
This work presents an extremely high-throughput design for the Kyber NTT. By utilizing the LUT-based modular multiplication technique used by us in CHES 2025, its area delay product is generally between one and two orders of magnitude better than similar designs in literature. For instance, where Yaman et al. with 16 Processing Elements requires 9500 LUTs and 16 DSPs to perform an NTT in 69 clock cycles, our design requires 67210 LUTs and no DSPs to perform an NTT every clock cycle
Large-Plaintext Functional Bootstrapping in FHE with Small Bootstrapping Keys
Get PDFFunctional bootstrapping is a core technique in Fully Homomorphic Encryption(FHE). For large plaintext, to evaluate a general function homomorphically over a ciphertext, in the FHEW/TFHE approach, since the function in look-up table form is encoded in the coefficients of a test polynomial, the degree of the polynomial must be high enough to hold the entire table.
This increases the bootstrapping time complexity and memory cost, as the size of bootstrapping keys and keyswitching keys need to be large accordingly.
In this paper, we propose to encode the look-up table of any function in a polynomial vector, whose coefficients can hold more data. The corresponding representation of the additive group used in the RGSW-based bootstrapping is the group of monic monomial permutation matrices, which integrates the permutation matrix representation used by Alperin-Sheriff and Peikert in 2014, and the monic monomial representation used in the FHEW/TFHE scheme. We make comprehensive investigation of the new representation, and propose a new bootstrapping algorithm based on it.
The new algorithm supports functional bootstrapping of large-plaintexts, and achieves polynomial reduction in key sizes and a constant-factor improvement in run-time cost
Verifiable PIR with Small Client Storage
Get PDFEfficient Verifiable Private Information Retrieval (vPIR) protocols, and more generally Verifiable Linearly Homomorphic Encryption (vLHE), suffer from high client storage. VeriSimplePIR (USENIX Security 2024), the state-of-the-art vPIR protocol, requires clients to persistently maintain over 1 GiB of local storage to privately access an 8 GiB remote database. We present a new vPIR protocol that reduces the client state by orders of magnitude while preserving online latency. In our protocol, clients only need to store 512 KiB for an 8 GiB database, achieving a 2000× improvement. Our vPIR protocol is built over our new vLHE scheme. Unlike VeriSimplePIR, our scheme doesn’t use random oracles and relies only on standard lattice assumptions - (R)LWE and SIS. These improvements come at a 2.5× cost in server throughput over VeriSimplePIR. Despite this throughput overhead, we achieve a comparable online latency to VeriSimplePIR by implementing several optimizations including query-level preprocessing. We also introduce the notion of covert vPIR (cvPIR), where stateful clients enjoy full vPIR security, while even stateless clients benefit from covert security against a malicious server
Accelerating FHEW-like Bootstrapping via New Configurations of the Underlying Cryptosystems
Get PDFThis work introduces a new configuration of the GSW fully homomorphic encryption (FHE) (Gentry, Sahai, Waters~Crypto 2013), with a squared gadget ,batching and scale-based homomorphic operation.
This configuration offers improved efficiency compared to existing approaches. By utilizing our proposed method as the underlying building block, we can accelerate
FHEW-like bootstrapping implementations, including the libraries of FHEW and TFHE. We conduct comprehensive experiments to evaluate the concrete performance of our method, demonstrating improvements of more than 2 times faster. For example, the current ring GSW under OpenFHE takes 84 ms and TFHE takes 11.4 ms, while our approach achieves 26.2 ms and 4.8 ms, respectively. These improvements have significant implications for the practical aspects of FHE, enhancing real-world usability
Updatable Signature from Lattices
Get PDFUpdatable Signature (US) schemes allow updating signatures so that they can be verified using a new key. This updating feature is useful for key rotation in practice. Cini et al. (PKC\u2721) first formalised this primitive. However, their post-quantum-secure US scheme does not satisfy their security definition, i.e., without unlinkability and only bounded unforgeability. This paper aims to solve this problem by providing a new fully secure construction. First, we simplify the definition of unlinkability by a hybrid argument, and reduce the update oracle of the unforgeability experiment by assuming unlinkability. Then, we construct our US scheme from verifiable encryption and the SIS assumption. This scheme is fully unlinkable and unforgeable, but also a unique signature scheme in each epoch, allowing only one signature for each message during one epoch and rendering a stateful signer/proxy. This is sufficient for many applications
Lattice Reduction via Dense Sublattices: A Cryptanalytic No-Go
Get PDFMost concrete analyses of lattice reduction focus on the BKZ algorithm or its variants relying on Shortest Vector Problem (SVP) oracles. However, a variant by Li and Nguyen (Cambridge U. Press 2014) exploits more powerful oracles, namely for the Densest rank- Sublattice Problem () for .
We first observe that, for random lattices, --and possibly even -- seems heuristically not much more expensive than solving SVP with the current best algorithm. We indeed argue that a densest sublattice can be found among pairs or triples of vectors produced by lattice sieving, at a negligible additional cost. This gives hope that this approach could be competitive.
We therefore proceed to a heuristic and average-case analysis of the slope of -BKZ output, inspired by a theorem of Kim (Journal of Number Theory 2022) which suggests a prediction for the volume of the densest rank- sublattice of a random lattice.
Under this heuristic, the slope for or appears tenuously better than that of BKZ, making this approach less effective than regular BKZ using the Dimensions for Free\u27\u27 of Ducas (EUROCRYPT 2018). Furthermore, our experiments show that this heuristic is overly optimistic.
Despite the hope raised by our first observation, we therefore conclude that this approach appears to be a No-Go for cryptanalysis of generic lattice problems
FHEMaLe: Framework for Homomorphic Encrypted Machine Learning
Get PDFMachine learning (ML) has revolutionized various industries by leveraging predictive models and data-driven insights, often relying on cloud
computing for large-scale data processing. However, this dependence introduces challenges such as bandwidth constraints and network latency. Edge
computing mitigates these issues by enabling localized processing, reducing reliance on continuous cloud connectivity, and optimizing resource
allocation for dynamic workloads. Given the limited computational capacity of sensory nodes in ML systems, edge devices provide an effective
solution by offloading processing tasks. However, a critical challenge in this paradigm is to ensure user privacy while handling sensitive data
both in the cloud and in edge processing. To address this, we propose a Fully Homomorphic Encryption (FHE) enabled framework that enables
ML computations directly on encrypted data, eliminating need for decryption. The main challenge to design such framework is that ML complex
implementation steps need to be revisited with suitable optimizations to match FHE processing requirements. There are different standard libraries to
support basic computation blocks on which encrypted ML processing is to be developed. These libraries vary in supported computation operators,
computational complexity and memory demands. Those in-turn introduces latency and throughput challenges, especially on resource-constrained
edge nodes. For example, in general HE library CKKS(Cheon-Kim-Kim-Song) with packing and approximate homomorphic operation support is
known to be the best choice for privacy preserving AI algorithm implementation. However, analysis shows leveled CKKS is limited in implementing
complex operators and hence not suitable for few specific ML algorithms like KNN, Logistic Regression or general activations in NN etc without any
approximation. To avoid accuracy drops associated with approximations, Torus based FHE library (TFHE) can be a better choice to make certain
ML implementations feasible. Moreover, our study shows compared to TFHE, CKKS with huge memory requirement is not suitable for resource
constrained edge. Thus, underlying library choice to design such framework is crucial considering the trade-off between latency and accuracy. In
this work, we propose an integrated framework FHEMaLe for encrypted ML processing which takes model architecture, desired accuracy, and
platform preference as inputs and based on that appropriate execution environment is selected: a cloud platform leveraging the CKKS homomorphic
encryption library or an edge platform using the TFHE library. Further, analysis shows the limitation of performing FHE ML on a single edge device
and hence our framework partitions encrypted data, transmits it via a fabric API, and performs distributed encrypted ML computations across the
edge cluster. We implement distributed ML inference for algorithms such as -Nearest Neighbors (KNN) (Cloud CKKS=248 sec, Edge TFHE=37
min), Support Vector Machine (SVM) (Cloud CKKS=18 sec, Edge TFHE=4.15 min), and Logistic Regression (LR) ( Cloud CKKS=17 sec, Edge
TFHE=7.82 min) on a cluster of 11 edge nodes. This work explains why KNN suffers from a major performance bottleneck in encrypted domain and
may not be a great choice for encrypted ML processing without application specific optimizations. Furthermore, our encrypted operators are capable of supporting encrypted NN processing
(Cloud CKKS= 57 sec), but we explain why CKKS is a preferred choice in this case. The distributed nature of our implementation shows a promise
of further improvement and scalability with the support of larger cluster
Experience from UNITA Elections: Reconciling Revote, E2E Verifiability and Low Coercion
Get PDFThis paper presents an experience of designing, building and deploying an online voting system for the Student Assembly elections in the UNITA Alliance with the following requirements. First, the system should allow voters to vote as many times as they wish before the election’s closing time with only the last vote being counted (known as revote). Second, the system should allow end-to-end (E2E) verifiability. Third, the system should allow voters to cast votes under the minimum influence from external forces or coercion. Developing an online voting system to meet these requirements poses a unique challenge. In this pa- per, we present an online voting system for UNITA elections, based on a variant of the DRE-ip protocol to provide E2E verifiability with support for revote. The system adopts a two-server architecture and implements a separation of control between the two servers to protect the voter’s anonymity. The first UNITA elections were successfully concluded in March 2025, providing a case study for reconciling revote, E2E verifiability and low coercion in a real-world setting. The use of verifiable online voting to empower students from different European universities to elect the Student Assembly also serves as a model for more inclusive democratic governance of a university alliance
Post-Quantum Cryptography in Practice: A Literature Review of Protocol-Level Transitions and Readiness
Get PDFThis paper presents a structured literature review of ongoing global efforts to integrate post-quantum cryptography (PQC) into widely deployed communication and identity protocols. We analyze current readiness, standardization initiatives, hybrid cryptographic approaches, and deployment challenges across multiple layers of the protocol stack, including TLS, SSH, VPNs, certificate infrastructure, and messaging protocols.
The report also discusses hybrid cryptographic strategies, current deployment efforts, and the technical challenges facing real-world implementation, including performance, interoperability, and resistance to side-channel attacks. With insights from recent research, industry trials, and open source tools, the report aims to provide a clear and accessible overview of the growing role of PQC in securing the future of digital communication.
We aim to guide researchers, developers, and policymakers in understanding the state of PQC integration and encourage broader involvement in the testing, implementation, and evaluation of next-generation cryptographic solutions
WISCH: Efficient data signing via correlated signatures
Get PDFWe present WISCH, a commit-reveal protocol that combines compact aggregate signatures with hash-based commitments to enable selective disclosure of correlated data in multiparty computation. The protocol separates an on-chain verification core from off chain preparation, so that verification cost depends only on the number of openings, not on the size of the underlying message space. This yields asymptotic efficiency: on-chain cost grows linearly in the number of revealed items and is independent of the ambient domain, while the per-byte overhead decreases with the message granularity. Security is established via a simulation-based proof in a UC framework with an ideal ledger functionality, in the algebraic group and global random-oracle models, under standard assumptions for discrete-log-based signatures and hash-based commitments. Thus WISCH provides selectively verifiable revelation with succinct on-chain checks and provable security guarantees