Cryptology ePrint Archive
Not a member yet
24907 research outputs found
Sort by
On the Pitfalls of Modeling Individual Knowledge
Get PDFThe concept of knowledge has been central in cryptography, especially within cryptographic proof systems. Traditionally, research in this area considers an abstract \emph{prover} defending a claim that it knows a message . Recently, a stronger concept—termed ``individual\u27\u27 (Dziembowski et al., CRYPTO\u2723) or ``complete\u27\u27 (Kelkar et al., CCS\u2724) knowledge—has emerged. This notion ensures the prover physically stores on a machine that it controls. As we argue in the paper, this concept also appears in earlier work on ``non-outsourceable puzzles\u27\u27 (Miller et al., CCS\u2715), which implicitly assumes that performing quickly complex computation on a string implies storing it on a single machine.
In this line of work, the authors typically rely on the algorithms whose computation requires a massive number of queries to a hash function . This paper highlights a subtle issue in the modeling used in some of these papers, more concretely, the assumption that H can be modeled as an atomic random oracle on long messages. Unfortunately, this does not correspond well to how the hash functions are constructed in practice. For example, the real-world hash functions (e.g., Merkle-Damgard or sponge-based) allow partial evaluation on long inputs, violating this assumption. Another example is the hashing used in Bitcoin mining, which permits similar precomputation. This undermines some protocols relying on individual knowledge. We demonstrate practical attacks against Miller et al.\u27s and Kelkar et al.\u27s schemes based on this observation, and discuss secure alternatives. Our alternative constructions, which are modifications of the original ones, avoid reliance on the random oracle behavior of hash functions on long messages. In the full version of this paper, we will provide their formal security analysis in the individual cryptography model of Dziembowski et al. (CRYPTO\u2723)
How to Compare Bandwidth Constrained Two-Party Secure Messaging Protocols: A Quest for A More Efficient and Secure Post-Quantum Protocol
Get PDFTransitioning existing classical two-party secure messaging protocols to post-quantum protocols has been an active movement in practice in recent years: Apple’s PQ3 protocol and the recent Triple Ratchet protocol being investigated by the Signal team with academics (Dodis et al. Eurocrypt’25). However, due to the large communication overhead of post-quantum primitives, numerous design choices non-existent in the classical setting are being explored, rendering comparison of secure messaging protocols difficult, if not impossible.
In this work, we thus propose a new pragmatic metric to measure how secure a messaging protocol is given a particular communication pattern, enabling a concrete methodology to compare secure messaging protocols. We uncover that there can be no “optimal” protocol, as different protocols are often incomparable with the respect to worst-case (adversarial) messaging behaviors, especially when faced with real-world
bandwidth constraints. We develop a comprehensive framework to experimentally compare various messaging protocols under given bandwidth limits and messaging behaviors. Finally, we apply our framework to compare several new and old messaging protocols. Independently, we also uncover untapped optimizations which we call opportunistic sending, leading to better post-quantum messaging protocols. To capture these optimizations, we further propose sparse continuous key agreement as a fundamental building block for secure messaging protocols, which could be of independent interest
Breaking UOV Encryption: Key Recovery Attack On Olivier
Get PDFThe Oil and Vinegar (OV) trapdoor is widely used in signature schemes such as UOV and MAYO. Recently, Esposito et al. proposed OliVier, an encryption scheme based on this trapdoor. However, the OV trapdoor was originally designed for signatures, and adapting it to encryption introduces inherent challenges.
We identify two such challenges and analyze how OliVier addresses the first, while showing that the unresolved second challenge enables a practical key-recovery attack. We conclude that any scheme using the OV trapdoor for encryption must also solve this second problem, for which no efficient solution is currently known
Learning from Leakage: Database Reconstruction from Just a Few Multidimensional Range Queries
Get PDFSearchable Encryption (SE) has shown a lot of promise towards enabling secure and efficient queries over encrypted data. In order to achieve this efficiency, SE inevitably leaks some information, and a big open question is how dangerous this leakage is. While prior reconstruction attacks have demonstrated effectiveness in one-dimensional settings, extending them to high-dimensional datasets remains challenging. Existing methods either demand excessive query information (e.g. an attacker that has observed all possible responses) or produce low-quality reconstructions in sparse databases. In this work, we present REMIN, a new leakage-abuse attack against SE schemes in multi-dimensional settings, based on access and search pattern leakage from range queries. Our approach leverages unsupervised representation learning to transform query co-occurrence frequencies into geometric signals, allowing the attacker to infer relative spatial relationships between records. This enables accurate and scalable reconstruction of high-dimensional datasets under minimal leakage. We begin with a passive adversary that persistently observes all encrypted queries and responses, and later extend our analysis to an more active attacker capable of poisoning the dataset. Furthermore, we introduce REMIN-P, a practical variant of the attack that incorporates a poisoning strategy. By injecting a small number of auxiliary anchor points REMIN-P significantly improves reconstruction quality, particularly in sparse or boundary regions. We evaluate our attacks extensively on both synthetic and real-world structured datasets. Compared to state-of-the-art reconstruction attacks, our reconstruction attack achieves up to 50% reduction in mean squared error (MSE), all while maintaining fast and scalable runtime. Our poisoning attack can further reduce MSE by an additional 50% on average, depending on the poisoning strategy
Swarm in EM Hay: Particle Swarm-guided Probe Placement for EM SCA
Get PDFDespite decades of research in electromagnetic (EM) side-channel analysis (SCA), practical attacks still require manual effort and domain expertise to identify informative probe locations on target devices.
Existing approaches rely heavily on exhaustive grid scanning or handcrafted alignment, limiting attack scalability and realism.
In this work, we present the first automated and adaptive EM SCA framework that uses particle swarm optimization (PSO) to navigate the probe.
Particles are guided by mutual information (MI) leakage maps, enabling efficient recovery of secret-dependent emissions.
We introduce a novel application of the Nyström approximation to accelerate MI estimation across EM trace windows, allowing real-time swarm guidance without full kernel computations.
Unlike prior work, our method requires no leakage templates, manual tuning, or alignment assistance, enabling automated attacks with minimal assumptions.
We validate our framework on both microcontroller and FPGA platforms running AES-128.
PSO-guided scanning identifies high-leakage points faster than grid search and reduces the number of traces required for successful CPA-based key recovery by up to a factor of 16, i.e., saving tens of thousands of traces
Beyond Ethernet: Reusing MACsec for CANsec
Get PDFIn the past, Secure Onboard Communication (SecOC) has been defined to serve as the foundational mechanism for securing in-vehicle networks. For over a decade, it has been used in hundreds of millions of automotive systems. Its application-layer design and AUTOSAR-based specification have enabled broad adoption across diverse platforms. However, this design also introduces challenges: software-centric dependencies complicate full hardware integration and can limit scalability in resource-constrained electronic control units, particularly as bandwidth demands continue to grow.
To address these constraints, CANsec has been proposed to address the security objectives of CAN XL. As a Layer 2 security protocol, CANsec aims to overcome SecOC’s shortcomings and offer modern guarantees comparable to MACsec. However, the CANsec specification remains under active development even after several years of work, leaving a gap between conceptual goals and practical deployment.
This paper proposes a pragmatic and standards-aligned solution: it re-uses existing MACsec specifications and implementations as the security engine for CAN XL.
MACsec, standardized for over two decades and widely scrutinized in both academic and industrial contexts, offers robust and well-understood security functions. Our approach introduces a lightweight wrapper that maps CAN XL frames to virtual Ethernet frames, enabling MACsec to provide confidentiality, integrity, authenticity, and freshness. We formally define the wrapping process, frame formats, and protocol data units, while preserving MACsec’s security properties, adapting them to the constraints and requirements of automotive networks. This enables a practical and secure path forward for CAN XL deployment, leveraging mature cryptographic algorithms and protocols without compromising performance or assurance.
To support standardization and practical adoption, we have submitted this approach to the CAN in Automation (CiA) CANsec specification task force, CiA\u27s IG 04 SIG 01 TF 03 CAN XL security, contributing to the ongoing effort to define an efficient, standardized and interoperable security solution for CAN XL
A New Practical Cube Attack via Recovering Numerous Superpolys
Get PDFCube attack is one of the most powerful approaches for recovering keys of stream ciphers. Practical cube attacks generate several superpolys first and solve the system constructed by these superpolys afterward. Unlike previous practical attacks, we propose a new cube attack that transfers the difficulty of generating easy-solving superpolys to solving the system built by numerous nonlinear ones. In the offline phase, we recovered lots of nonlinear superpolys by improving the approach proposed by Delaune et al. at SAC 2022 in theory. In the online phase, taking advantage of the sparsity and asymmetry of these numerous superpolys, we present a new testing method to solve the constructed system efficiently. As applications, the latest attack could practically recover the keys for 820- and 832-round Trivium with the time complexity no more extensive than and , while the previous highest number of rounds of Trivium that can be attacked practically is 830. We believe the proposed approach can be used to attack more rounds of Trivium and other stream ciphers
Hybrid Subsupport Guessing: A New Hybrid Technique for the Rank Decoding Problem
Get PDFThe Rank Decoding Problem (R-DP) has gained a lot of attention due to the competitive KEM proposals ROLLO and RQC, as well as the more recent signature scheme RYDE, the latter being a second-round candidate in the ongoing NIST post-quantum standardization process. While previous attacks on the R-DP are based on combinatorial methods, the seminal work of [Bardet et al., 2020] has shown the potential of attacks that use algebraic modelings, breaking the proposed parameters of ROLLO and RQC. These algebraic attacks model the R-DP as a large system of equations. For most parameter ranges, this system is underdetermined; hence, the algebraic attack first needs to perform several guessing steps to obtain a reduced instance for which the system of equations is overdetermined. These steps, in essence, guess a supersupport of the unknown error support, making this attack a hybrid approach between combinatorial and algebraic solvers.
In this paper, we present a novel type of guessing step based on searching a subsupport of the error support. While supersupport guessing only reduces the length and dimension of the code, subsupport guessing instead reduces the length and the rank weight of the sought-after error vector. This introduces an additional method for instance reduction compatible with supersupport guessing. Both types of guessing step can be performed sequentially in hybrid attacks, and their numbers can be optimized to outperform current hybrid attacks. We provide experimentally supported comparisons of the attack complexities with and without the novel guessing technique. We measure the impact of our new hybrid attack on the RYDE parameters; for the NIST security category 5 parameters, we decrease the hybrid MaxMinors attack complexity from 301 bits to 272 bits, outperforming all other known rank decoders and tightening the margin above the 256 threshold.
For the other security levels, we decrease the complexities to be on par with the best performing combinatorial decoders
1-Adaptive Weak Pseudorandom Functions
Get PDFA message authentication code (MAC) ensures authenticity and integrity in symmetric-key settings. The Carter–Wegman–Shoup (CWS) paradigm establishes that MACs for arbitrary-length messages can be built in a black-box way using a single call to a pseudorandom function (PRF) on a random input. More than a decade ago, Dodis, Kiltz, Pietrzak, and Wichs left open whether weak pseudorandom functions (wPRFs) would suffice in this construction.
This work establishes tight upper and lower bounds that precisely characterize the minimal computational assumptions needed for the security of the CWS paradigm.
On the negative side, we prove that weak PRFs are insufficient to instantiate the CWS paradigm. On the positive side, we introduce a new primitive, the 1-adaptive weak pseudorandom function (1-awPRF), which guarantees pseudorandomness for polynomially many non-adaptive queries followed by one adaptive query. We show that 1-awPRFs are sufficient to secure CWS in a black-box manner.
Finally, we construct 1-adaptive weak pseudorandom functions in a black-box way from standard cryptographic assumptions, using a new randomized design paradigm that treats randomization as a fundamental structural element. Instantiating our generic construction under the Decisional Diffie Hellman and Learning with Errors assumptions yields concrete and efficient realizations. These lead to more efficient MAC schemes and illustrate how weak and abstract building blocks can be transformed into stronger and practically useful cryptographic constructions
The Coding Limits of Robust Watermarking for Generative Models
Get PDFWe ask a basic question about cryptographic watermarking for generative models: to what extent can a watermark remain reliable when an adversary is allowed to corrupt the encoded signal? To study this question, we introduce a minimal coding abstraction that we call a zero-bit tamper-detection code. This is a secret-key procedure that samples a pseudorandom codeword and, given a candidate word, decides whether it should be treated as unmarked content or as the result of tampering with a valid codeword. It captures the two core requirements of robust watermarking: soundness and tamper detection.
Within this abstraction we prove a sharp unconditional limit on robustness to independent symbol corruption. For an alphabet of size , there is a critical corruption rate of such that no scheme with soundness, even relaxed to allow a fixed constant false positive probability on random content, can reliably detect tampering once an adversary can change more than this fraction of symbols. In particular, in the binary case no cryptographic watermark can remain robust if more than half of the encoded bits are modified. We also show that this threshold is tight by giving simple information-theoretic constructions that achieve soundness and tamper detection for all strictly smaller corruption rates.
We then test experimentally whether this limit appears in practice by looking at the recent watermarking for images of Gunn, Zhao, and Song (ICLR 2025). We show that a simple crop and resize operation reliably flipped about half of the latent signs and consistently prevented belief-propagation decoding from recovering the codeword, erasing the watermark while leaving the image visually intact