Cryptology ePrint Archive
Not a member yet
24907 research outputs found
Sort by
SoK: Reassessing Side-Channel Vulnerabilities and Countermeasures in PQC Implementations
Get PDFPost-Quantum Cryptography (PQC) algorithms should remain secure even in the presence of quantum computers. Although the security of such schemes is guaranteed at the algorithmic level, real-world implementations often suffer from other vulnerabilities like Side-Channel Attacks (SCA). This Systematization of Knowledge (SoK) paper investigates side-channel attacks targeting implementations of PQC algorithms. This work categorizes attacks from an adversarial perspective to identify the most vulnerable components of the algorithms\u27 implementations and highlights unexplored parts in current implementations. In addition, it reviews and analyzes the efficiency and efficacy of existing countermeasures to SCA in current hardware implementations. This approach helps identify countermeasures that provide broader protection and highlights characteristics needed for future secure implementations. Our findings offer guidance in strengthening existing systems and developing more efficient defenses against side-channel attacks
Cymric: Short-tailed but Mighty
Get PDFAuthenticated encryption (AE) is a fundamental tool in today\u27s secure communication. Numerous designs have been proposed, including well-known standards such as GCM. While their performance for long inputs is excellent, that for short inputs is often problematic due to high overhead in computation, showing a gap between the real need for IoT-like protocols where packets are often very short. Existing dedicated short-input AEs are very scarce, the classical Encode-then-encipher (Bellare and Rogaway, Asiacrypt 2000) and Manx (Adomnic\u{a}i et al., CT-RSA 2023), using up to two block cipher calls. They have superior performance for (very) short inputs, however, security is up to bits, where is the block size of the underlying block cipher.
This paper proposes a new family of short-input AEs, dubbed Cymric, which ensures beyond-birthday-bound (BBB) security. It supports a wider range of input space than EtE and Manx with the help of one additional block cipher call (thus three calls). In terms of the number of block cipher calls, Cymric is the known minimum construction of BBB-secure AEs, and we also prove this is indeed minimal by presenting an impossibility result on BBB-secure AE with two calls. Finally, we show a comprehensive benchmark on microcontrollers to show performance advantage over existing schemes
A Generalized Approach to Root-based Attacks against PLWE
Get PDFIn the present work we address the robustness of the Polynomial Learning With Errors problem extending previous results in Blanco-Chacón et al. and in Elias et al. In particular, we produce two kinds of new distinguishing attacks: a) we generalize Blanco-Chacón et al. to the case where the defining polynomial has a root of degree up to 4, and b) we widen and refine the most general attack in Elias et al. to the non-split case and determine further dangerous instances previously not detected. Finally, we exploit our results in order to show vulnerabilities of some cryptographically relevant polynomials
Copy-Protection from UPO, Revisited
Get PDFQuantum copy-protection is a foundational notion in quantum cryptography that leverages the governing principles of quantum mechanics to tackle the problem of software anti-piracy. Despite progress in recent years, precisely characterizing the class of functionalities that can be copy-protected is still not well understood.
Two recent works, by [Coladangelo and Gunn, STOC 2024] and [Ananth and Behera, CRYPTO 2024, showed that puncturable functionalities can be copy-protected. Both works have significant caveats with regard to the underlying cryptographic assumptions and additionally restrict the output length of the functionalities to be copy-protected. In this work, we make progress towards simultaneously addressing both caveats. We show the following:
- Revisiting Unclonable Puncturable Obfuscation (UPO): We revisit the notion of UPO introduced by [Ananth and Behera, CRYPTO 2024]. We present a new approach to construct UPO and a variant of UPO, called independent-secure UPO. Unlike UPO, we show how to base the latter notion on well-studied assumptions.
- Copy-Protection from Independent-secure UPO: Assuming independent-secure UPO, we show that any m-bit, for m ≥ 2, puncturable functionality can be copy-protected.
- Copy-Protection from UPO: Assuming UPO, we show that any 1-bit puncturable functionality can be copy-protected. The security of copy-protection holds against identical challenge distributions
Limits on the Power of Private Constrained PRFs
Get PDFPrivate constrained PRFs are constrained PRFs where the constrained key hides information about the predicate circuit. Although there are many constructions and applications of PCPRF, its relationship to basic cryptographic primitives, such as one-way functions and public-key encryptions, has been unclear. For example, we don\u27t know whether one-way functions imply PCPRFs for general predicates, nor do we know whether 1-key secure PCPRF for all polynomial-sized predicates imply public-key primitives such as public-key encryption and secret-key agreement.
In this work, we prove the black-box separation between a 1-key secure PCPRF for any predicate and a secret-key agreement, which is the first black-box separation result about PCPRF. Specifically, we prove that there exists an oracle relative to which 1-key secure PCPRFs exist while secret-key agreement does not. Our proof is based on the simulation-based technique proposed by Impagliazzo and Rudich (STOC 89). The main technical challenge in generalizing the simulation-based technique to PCPRF is the issue of \textit{unfaithfulness} of Eve\u27s simulation to the real world because our oracle is more complicated than a random oracle. We introduce a new technique which we call the ``weighting technique and show how to leverage it to circumvent the issue of unfaithfulness in the proof framework of Impagliazzo and Rudich
Privacy-aware White and Black List Searching for Fraud Analysis
Get PDFIn many areas of cybersecurity, we require access to Personally Identifiable Information (PII), such as names, postal addresses and email addresses. Unfortunately, this can lead to data breaches, especially in relation to data compliance regulations such as GDPR. An Internet Protocol (IP) address is an identifier that is assigned to a networked device to enable it to communicate over networks that use IP. Thus, in applications which are privacy-aware, we may aim to hide the IP address while aiming to determine if the address comes from a blacklist. One solution to this is to use homomorphic encryption to match an encrypted version of an IP address to a blacklisted network list. This matching allows us to encrypt the IP address and match it to an encrypted version of a blacklist. In this paper, we use the OpenFHE library \cite{OpenFHE} to encrypt network addresses with the BFV homomorphic encryption scheme. In order to assess the performance overhead of BFV, we implement a matching method using the OpenFHE library and compare it against partial homomorphic schemes, including Paillier, Damgard-Jurik, Okamoto-Uchiyama, Naccache-Stern and Benaloh. The main findings are that the BFV method compares favourably against the partial homomorphic methods in most cases
OnionPIRv2: Efficient Single-Server PIR
Get PDFThis paper presents OnionPIRv2, an efficient implementation of OnionPIR incorporating standard orthogonal techniques and engineering improvements. OnionPIR is a single-server PIR scheme that improves response size and computation cost by utilizing recent advances in somewhat homomorphic encryption (SHE) and carefully composing two lattice-based SHE schemes to control the noise growth of SHE. OnionPIRv2 achieves x-x response overhead for databases with moderately large entries (around KB or above) and up to MB/s server computation throughput
Optimal Dimensionality Reduction using Conditional Variational AutoEncoder
Get PDFThe benefits of using Deep Learning techniques to enhance side-channel attacks performances have been demonstrated over recent years.
Most of the work carried out since then focuses on discriminative models.
However, one of their major limitations is the lack of theoretical results.
Indeed, this lack of theoretical results, especially concerning the choice of neural network architecture to consider or the loss to prioritize to build an optimal model, can be problematic for both attackers and evaluators.
Recently, Zaid et al. addressed this problem by proposing a generative model that bridges conventional profiled attacks and deep learning techniques, thus providing a model that is both explicable and interpretable.
Nevertheless the proposed model has several limitations.
Indeed, the architecture is too complex, higher-order attacks cannot be mounted and desynchronization is not handled by this model.
In this paper, we address the first limitation namely the architecture complexity, as without a simpler model, the other limitations cannot be treated properly.
To do so, we propose a new generative model that relies on solid theoretical results.
This model is based on conditional variational autoencoder and converges towards the optimal statistical model i.e. it performs an optimal attack.
By building on and extending the state-of-the-art theoretical works on dimensionality reduction, we integrate into this neural network an optimal dimensionality reduction i.e. a dimensionality reduction that is achieved without any loss of information.
This results in a gain of , with the dimension of traces, compared to Zaid et al. neural network in terms of architecture complexity, while at the same time enhancing the explainability and interpretability.
In addition, we propose a new attack strategy based on our neural network, which reduces the attack complexity of generative models from to , with the number of generated traces.
We validate all our theoretical results experimentally using extensive simulations and various publicly available datasets covering symmetric, asymmetric pre and post-quantum cryptography implementations
Homomorphic Field Trace Revisited : Breaking the Cubic Noise Barrier
Get PDFWe present a novel homomorphic trace evaluation algorithm , which mitigates the phase amplification problem that comes with the definition of the field trace. Our overcomes the phase amplification with only a negligible computational overhead, thereby improving the usability of the homomorphic field trace algorithm. Moreover, our tweak also improves the noise propagation of the and breaks the traditional variance bound in previous works into .
Our experimental results obtained by integrating into state-of-the-art homomorphic encryption algorithms further demonstrate the usefulness of our algorithm. Specifically, improves the noise accumulation of the (high precision) circuit bootstrapping, which also achieves maximal speedup by replacing the costly high precision trace evaluation. Also, based on our idea of , we present a low latency, high precision LWE-to-GLWE packing algorithm -. We also show that our - significantly reduces the packing error without severe degradation of performance
Treebeard: A Scalable and Fault Tolerant ORAM Datastore
Get PDFWe present Treebeard - the first scalable and fault tolerant Oblivious RAM (ORAM) based datastore designed to protect applications from access pattern attacks. Current ORAM systems face challenges in practical adoption due to their limited ability to handle concurrent workloads, scale effectively, and ensure fault tolerance. We address all three limitations in Treebeard by utilizing a multi-layer architecture that scales horizontally, handling thousands of requests in parallel, while replicating the data to prevent data loss upon failures. Experimental evaluation demonstrates Treebeard\u27s ability to scale linearly, achieving a throughput of 160K ops/sec with 16 machines; this behavior is similar to the enclave-based state-of-the-art, Snoopy. Being fault-tolerant, Treebeard recovers from failures with close to zero downtime and achieves 13.8x the throughput of QuORAM, the latest fault tolerant ORAM system, even without scaling