Cryptology ePrint Archive
Not a member yet
24907 research outputs found
Sort by
Asymptotic improvements to provable algorithms for the code equivalence problem
Get PDFWe present several new provable algorithms for two variants of the code equivalence problem on linear error-correcting codes, the Linear Code Equivalence Problem (LCE) and the Permutation Code Equivalence Problem (PCE). Specifically, for arbitrary codes of block length and dimension over any finite field , we show:
1) A deterministic algorithm running in time for LCE.
2) A randomized algorithm running in time for LCE and PCE.
3) A quantum algorithm running in time for LCE and PCE.
The first algorithm complements the deterministic roughly -time algorithm of Babai (SODA 2011) for PCE.
The second two algorithms improve on recent work of Nowakowski (PQCrypto 2025), which gave algorithms with similar running times, but only for code equivalence on \emph{random} codes and only over fields of order
Breaking the Blindfold: Deep Learning-based Blind Side-channel Analysis
Get PDFPhysical side-channel analysis (SCA) operates on the foundational assumption of access to known plaintext or ciphertext. However, this assumption can be easily invalidated in various scenarios, ranging from common encryption modes like Cipher Block Chaining (CBC) to complex hardware implementations, where such data may be inaccessible. Blind SCA addresses this challenge by operating without the knowledge of plaintext or ciphertext. Unfortunately, prior such approaches have shown limited success in practical settings.
In this paper, we introduce the Deep Learning-based Blind Side-channel Analysis (DL-BSCA) framework, which leverages deep neural networks to recover secret keys in blind SCA settings. In addition, we propose a novel labeling method, Multi-point Cluster-based (MC) labeling, accounting for dependencies between leakage variables by exploiting multiple sample points for each variable, improving the accuracy of trace labeling.
We validate our approach across four datasets, including symmetric key algorithms (AES and Ascon) and a post-quantum cryptography algorithm, Kyber, with platforms ranging from high-leakage 8-bit AVR XMEGA to noisy 32-bit ARM STM32F4. Notably, previous methods failed to recover the key on the same datasets. Furthermore, we demonstrate the first successful blind SCA on a desynchronization countermeasure enabled by DL-BSCA and MC labeling. All experiments are validated with real-world SCA measurements, highlighting the practicality and effectiveness of our approach
Quantum function secret sharing
Get PDFWe propose a quantum function secret sharing scheme in which the communication is exclusively classical. In this primitive, a classical dealer distributes a secret quantum circuit by providing shares to quantum parties. The parties on an input state and a projection , compute values that they then classically communicate back to the dealer, who can then compute using only classical resources. Moreover, the shares do not leak much information about the secret circuit .
Our protocol for quantum secret sharing uses the Cayley path, a tool that has been extensively used to support quantum primacy claims. More concretely, the shares of correspond to randomized version of which are delegated to the quantum parties, and the reconstruction can be done by extrapolation. Our scheme has two limitations, which we prove to be inherent to our techniques: First, our scheme is only secure against single adversaries, and we show that if two parties collude, then they can break its security. Second, the evaluation done by the parties requires exponential time in the number of gates
b4M: Holistic Benchmarking for MPC
Get PDFSecure Multi-Party Computation (MPC) is becoming more and more usable in practice. The practicality origins primarily from well-established general-purpose MPC frameworks, such as MP-SPDZ. However, to evaluate the practicality of an MPC program in the envisioned environments, still many benchmarks need to be done. We identified three challenges in the context of performance evaluations within the MPC domain: first, the cumbersome process to holistically benchmark MPC programs; second, the difficulty to find the best-possible MPC setting for a given task and envisioned environment; and third, to have consistent evaluations of the same task or problem area across projects and papers. In this work, we address the gap of tedious and complex benchmarking of MPC. Related works so far mostly provide a comparison for certain programs with different engines.
To the best of our knowledge, for the first time the whole benchmarking pipeline is automated; provided by our open-sourced framework Holistic Benchmarking for MPC (b4M). b4M is easy to configure using TOML files, outputs ready-to-use graphs, and provides even the MPC engine itself as own benchmark dimension. Furthermore it takes three relatively easy steps to add further engines: first, integrate engine-specific commands into b4M’s runner class; second, output performance metrics in b4M’s format; third, provide a Docker container for the engine’s parties.
To showcase b4M, we provide an exemplary evaluation for the computation of the dot product and logistic regression using a real-world dataset. With this work, we move towards fully-automated evaluations of MPC programs, protocols, and engines, which smoothens the setup process and viewing various trade-offs. Hence, b4M advances MPC development by improving the benchmarking usability aspect of it
Zeus: Defending against Fee Stealing and Griefing Attacks in Multi-Hop Payments
Get PDFPayment Channel Networks (PCNs) are the most scalable and trust-minimized solution to Bitcoin\u27s scalability challenges. Within PCNs, connected payer and payee can make arbitrary off-chain transactions through multi-hop payments (MHPs), while intermediate relays charge relay fees by providing liquidity. However, current MHPs face critical security threats including fee-stealing attacks and griefing attacks. In this paper, we first identify new fee-stealing attacks targeting most existing MHP protocols. Then we demonstrate the impossibility of griefing resistance by reducing the griefing resistance MHP to a fair secret exchange problem. Finally, we introduce Zeus, the first Bitcoin-compatible MHP that is secure against fee-stealing attacks and offers bounded griefing protection against -cost-sensitive adversaries—those who only launch griefing attacks when the damage exceeds a fraction of their cost. These guarantees are established through rigorous proofs in the Global Universal Composability (GUC) framework. Our comprehensive evaluation demonstrates that Zeus reduces worst-case griefing damage to 28% and 75% compared to MHP schemes such as AMHL~(NDSS\u2719) and Blitz~(USENIX SEC\u2721), respectively. Our results further show that, even under the most adverse configurations in the Lightning Network, Zeus ensures attackers incur costs at least 10x higher than potential damage
Efficient Mixed-Mode Oblivious RAMs
Get PDFOblivious RAMs (ORAMs) allow data outsourcing to servers so that the access pattern to the outsourced data is kept private. It is also a crucial building block to enable private RAM access within secure multi-party computation (MPC). In recent years, schemes that match the ORAM lower bound have been proposed in both the outsourcing setting and the RAM-model MPC setting, seemingly putting an epilogue in the theory of ORAM. In this paper, we initiate a study of mixed-mode ORAMs, where accesses to the ORAM are a mix of both public and private accesses. Although existing ORAMs can support public access by treating them as private ones, achieving better efficiency is highly non-trivial.
- We present a mixed-mode ORAM algorithm, assuming the existence of private information retrieval (PIR). When the PIR scheme is communication-efficient, this ORAM achieves the best possible outcome: it has a bandwidth blowup of for private accesses and for public accesses. This construction can be easily extended for the MPC setting achieving circuit size for private accesses to -sized blocks and circuit size for public accesses to the same array.
- We instantiate the above protocol in the three-party computation (3PC) setting with more concrete optimizations, yielding a protocol that performs almost as efficiently as state-of-the-art RAM-3PC protocols for private accesses while being more efficient for public accesses in the LAN setting
Continuous Group-Key Agreement: Concurrent Updates without Pruning
Get PDFContinuous Group Key Agreement (CGKA) is the primitive underlying secure group messaging.
It allows a large group of users to maintain a shared secret key that is frequently rotated by the group members in order to achieve forward secrecy and post compromise security.
The group messaging scheme Messaging Layer Security (MLS) standardized by the IETF makes use of a CGKA called TreeKEM which arranges the group members in a binary tree.
Here, each node is associated with a public-key,
each user is assigned one of the leaves,
and a user knows the corresponding secret keys from their leaf to the root.
To update the key material known to them, a user must just replace keys at nodes, which requires them to create and upload ciphertexts. Such updates must be processed sequentially by all users, which for large groups is impractical.
To allow for concurrent updates, TreeKEM uses the ``propose and commit\u27\u27 paradigm, where multiple users can concurrently propose to update (by just sampling a fresh leaf key), and a single user can then commit to all proposals at once.
Unfortunately, this process destroys the binary tree structure as the tree gets pruned and some nodes must be ``blanked\u27\u27 at the cost of increasing the in-degree of others, which makes the commit operation, as well as, future commits more costly.
In the worst case, the update cost (in terms of uploaded ciphertexts) per user can grow from to .
In this work we provide two main contributions.
First, we show that MLS\u27 communication complexity is bad not only in the worst case but also if the proposers and committers are chosen at random:
even if there\u27s just one update proposal for every commit the expected cost is already over , and it approaches as this ratio changes towards more proposals.
Our second contribution is a new variant of propose and commit for TreeKEM which for moderate amounts of update proposals per commit provably achieves an update cost of assuming the proposers and committers are chosen at random
Fully-Fluctuating Participation in Sleepy Consensus
Get PDFProof-of-work allows Bitcoin to boast security amidst arbitrary fluctuations in participation of miners throughout time, so long as, at any point in time, a majority of hash power is honest. In recent years, however, the pendulum has shifted in favor of proof-of-stake-based consensus protocols. There, the sleepy model is the most prominent model for handling fluctuating participation of nodes. However, to date, no protocol in the sleepy model rivals Bitcoin in its robustness to drastic fluctuations in participation levels, with state-of-the-art protocols making various restrictive assumptions. In this work, we present a new adversary model, called external adversary. Intuitively, in our model, corrupt nodes do not divulge information about their secret keys. In this model, we show that protocols in the sleepy model can meaningfully claim to remain secure against fully fluctuating participation, without compromising efficiency or corruption resilience. Our adversary model is quite natural, and arguably naturally captures the process via which malicious behavior arises in protocols, as opposed to traditional worst-case modeling. On top of which, the model is also theoretically appealing, circumventing a barrier established in a recent work of Malkhi, Momose, and Ren
Not Easy to Prepare a Pesto: Cryptanalysis of a Multivariate Public-Key Scheme from CCZ Equivalence
Get PDFMultivariate cryptography is one of the challenging candidates for post-quantum cryptography. There exists a huge variety of proposals, most of them have been broken substantially. Multivariate schemes are usually constructed by applying two secret affine invertible transformations to a set of multivariate
polynomials (often quadratic). The secret polynomials
possess a trapdoor that allows the legitimate user to find a solution of the
corresponding system, while the public polynomials look like random polynomials. In [Calderini, M., Caminata, A., Villa, I. A New Multivariate Primitive from CCZ Equivalence. J. Cryptol. 38, 25 (2025)], the authors addressed the above challenge by presenting a promising new way of constructing a multivariate scheme by considering the CCZ equivalence, which has been introduced and studied in the context of vectorial Boolean functions. The resulting proposal is called Pesto with security parameters , where is the number of variables, and the size of the finite base field . In this paper we present an attack against Pesto by constructing an equivalent secret key from the public key. This attack has a precomputation phase with a complexity of
base field operations on average and an online complexity of base field operations to decipher a message or forge a signature, where .
Thus, our attack breaks Pesto for any practical choice of the security parameters and renders the concrete construction underlying Pesto insecure
Weak Keys in QC-MDPC-based cryptosystems via the Extended Euclidean Algorithm
Get PDFIn this work we analyze a problem strictly linked with the Rational Reconstruction, which forms the foundation of some post-quantum Quasi-Cyclic Moderate-Density Parity-Check and Quasi-Cyclic Low-Density Parity-Check code-based schemes such as LEDAkem and BIKE.
Given a polynomial in a cyclic ring as input, our aim is to recover two polynomials, with specific properties, whose ratio is the input one.
The starting point of this work is the paper of Bardet, Dragoi, Luque, and Otmani, which describes some approaches, based on the Extended Euclidean Algorithm, that solves this problem in some specific cases.
In comparison to previous work, we define an additional setting in which the problem can be solved. We also provide an alternative approach to estimate the probability of success, by taking into account a requirement that was not considered in the original paper, thus getting a more precise estimation. Finally, we present a key-recovery attack on BIKE, evaluate its computational cost, and compare it with that of the most efficient known attacks. Although this last step is performed specifically on BIKE, the methodology can be extended to other schemes as well