In this work, we study the proposal for a linkable ring signature (LRS) in [KTS+24]. It is instantiated from the group action based framework described in [BKP20], using the Lattice Isomorphism Group Action (LIGA), meaning that the security of the signature rests on the famous Lattice Isomorphism Problem (LIP). We will show that this signature does not in fact fit the requirements to be a linkable ring signature, despite the guarantees of the [BKP20] framework, due to it straying from that framework by using a non-commutative group for the group actions. More specifically, we will show that the signature from [KTS+24] satisfies neither the property of correctness nor linkability, which are required of a LRS. This further damages the signature, as it was already shown in [BCF25] that the linkable anonymity property of [KTS24+] isn't satisfied. The group used in LIGA is the group of invertible integer matrices: $\mathrm{GL}_n(\mathbb{Z})$. As the main obstacle in successfully applying the framework mentioned above to construct a LRS based on LIP is the fact that this group is non-commutative, we try fixing the signature by restricting the secret key space to a commutative subgroup of $\mathrm{GL}_n(\mathbb{Z})$. However, we will see that finding a commutative subgroup of $\mathrm{GL}_n(\mathbb{Z})$ that maintains the hardness of the underlying LIP, and that at the same time is realistic to use is not as easy as it may seem.

Hax is a verification pipeline that translates a subset of Rust into F*, enabling machine-checked proofs of panic freedom and functional correctness for cryptographic implementations being developed in partnership with Google and tested in Signal's post-quantum protocol. We study whether hax's translation preserves the security properties it claims to verify. Through a structural analysis of its 35-phase transformation engine, F* proof libraries, and specification API, we identify three classes of semantic gap between the Rust source and the F* verification target: translation infidelity, where pipeline transformations distort security-relevant semantics; unverifiable trust boundaries, where operations are axiomatized without postconditions; and specification gaming, where escape hatches inject unproven facts into the verification context. We demonstrate each class through five proof-of-concept exploits against ML-DSA (FIPS 204), ML-KEM (FIPS 203), Ed25519 (FIPS 186-5), and ChaCha20 (RFC 8439). Every exploit meets a strict criterion: the Rust code compiles, passes functional tests, and extracts to F* without warnings, while harboring a security gap invisible to testing. We distinguish three gradations: facade gaps where the F* model actively diverges from Rust semantics, a conditional gap dependent on the compilation mode, and a scope gap where the model is faithful but cannot cover a critical property. We call the resulting phenomenon a verification facade: verification that is performed but covers less than it appears to cover.

Payment channel networks (PCNs) are a leading method to deal with the scalability limitations of blockchain networks. PCNs allow users to execute transactions without committing them to the blockchain by relying on predefined payment channels. Transactions between pairs of users without a connecting channel are also supported through a path of multiple channels. Serving such transactions involves fees paid to intermediate users. In this paper, we uncover the potential existence of the Braess paradox in payment networks: Sometimes, establishing a new payment channel can increase the fees paid for serving some fixed transactions. We study conditions for the paradox to appear under two different models of fees: Liquidity-based fees as a function of the transaction value jointly with the channel liquidity values and proportional fees which are based only on the transaction value. We also provide indications for the appearance of the paradox based on real data from Lightning, a popular payment channel network of Bitcoin. Last, we discuss methods to mitigate the paradox upon establishing a new payment channel.

We consider the worst-case hardness of the gap version of the classic time-bounded Kolmogorov complexity problem—$Gap_pMK^tP[s_1,s_2]$—where the goal is to determine whether for a given string x, $K^t(x) ≤s_1(n)$ or $K^{p(t)}(x) > s_2(n)$, where $K^t(x)$ denotes the t-bounded Kolmogorov complexity of x. As shown by Hirahara (STOC’18), if $Gap_pMK^tP[s_1,s_2] \notin prBPP$ for every polynomial p, then (under appropriate derandomization assumption) $Gap_pMK^tP$ is errorless average-case hard with respect to BPP heuristics. The notion of errorless average-case hardness, however, is seemingly insufficient for cryptographic applications where one needs to consider average-case hardness against attacks that simply may err with some probability (i.e., two-sided error hardness). In this work, we present several new consequences of the assumption that $Gap_pMK^tP[s_1,s_2]\notin P/poly$ for all polynomials p, for appropriate choices of $s_1$,$s_2$, and under appropriate (worst-case) derandomization assumptions. In particular, we show that this assumption implies: - The existence of an (inefficient-prover) zero-knowledge proof system for NP with a non-uniform simulator w.r.t. adversaries with a-priori bounded-length auxiliary-input. - The existence of a hard disjoint NP pair, defined as a promise problem $(Y,N)$ where both $Y,N\in NP$; this provides a barrier towards showing that $Gap_pMK^tP$ is NP-complete. The above results are proven via first showing that the above assumption implies the existence of a so-called conditional PRG—roughly speaking, a cryptographic PRG where indistinguishability only needs to hold for some (potentially not efficiently sampleable) distribution over the seed to the PRG. (In fact, this notion of a PRG also almost directly implies average-case hardness of $Gap_pMK^tP$, and as such, this provides a modular explanation to Hirahara’s results.) Finally, we show that for the results on conditional PRGs and Zero-knowledge Proofs, unconditional results can be obtained (that is, without making any derandomization assumptions), if considering an appropriate version of $Gap_pMK^tP$ concerning randomized $K^t$.

In recent years, the shuffle model has emerged as a prevalent paradigm in privacy-preserving data analysis, centered on the principle of \textit{privacy amplification via shuffling}: an individual user's report is obscured by the ``background noise'' of other users' messages, a phenomenon intuitively known as the \textit{privacy blanket}. This paper initiates a foundational and systematic study of this mechanism from an information-theoretic perspective. We investigate the following optimal noise-design problem: given that a target user's message $Y_1$ follows a distribution $P$, what is the optimal blanket noise distribution $Q$ that maximizes privacy? Specifically, when $Y_1 \sim P$ and the remaining messages $Y_2, \dots, Y_n \stackrel{\text{i.i.d.}}{\sim} Q$ are shuffled to produce an output $\boldsymbol{Z} = (Y_{\sigma(i)})_{i=1}^n$, we seek the $Q$ that affords the strongest protection for $Y_1$ under various metrics, including mutual information $I(Y_1; \mathbf{Z})$, total-variation-information $I_{\mathrm{TV}}(Y_1; \mathbf{Z})$, message recovery advantage, and expected posterior variance. Our analysis reveals a series of non-intuitive results that challenge the conventional heuristic of setting $Q=P$. First, we prove that the optimal noise distribution $Q$ generally \textit{deviates} from the target distribution $P$. For binary alphabets, we show that the (near-)uniform distribution is optimal in a strong sense. For general finite alphabets, we derive an explicit analytical form $Q \propto \sqrt{P(1-P)}$ that achieves asymptotic optimality for mutual information. Furthermore, we demonstrate that our analytical framework transcends the shuffle model, yielding new security insights into broader cryptographic primitives such as the \textit{ideal cipher model} and \textit{honey encryption}. Finally, we extend our results to the shuffle-DP paradigm, where messages $Y_i = \mathcal{R}(X_i)$ are outputs of $\varepsilon_0$-locally differentially private mechanisms. We establish a new, tight information-theoretic upper bound $I(X_1; \mathbf{Z} \mid (X_i)_{i=2}^n) \le \frac{(e^{\varepsilon_0/2}-1)^2}{2n} + \mathcal{O}(n^{-3/2})$. This result provides a sharp characterization that matches the optimal privacy-amplification parameters known in the literature, while offering a novel interpretation of the shuffling gain.

Post-quantum migration in TLS 1.3 couples signature-algorithm choice with certificate-hierarchy structure, chain exposure during the handshake, and role-dependent cryptographic cost. In certificate-based authentication, the practical effect of a signature family depends on where it appears in the certification hierarchy, how much of that hierarchy is exposed during the handshake, and how the resulting cryptographic cost is distributed across client and server roles. Post-quantum TLS migration must therefore be evaluated as cryptographic design within authenticated key establishment, with algorithm selection assessed in its deployment context. This paper presents a local experimental study of TLS 1.3 authentication strategies implemented with OpenSSL~3 and oqsprovider. Using a reproducible laboratory setting, it compares ML-DSA and SLH-DSA across multiple certificate placements, hierarchy depths, and key-exchange modes, including classical, hybrid, and pure post-quantum configurations. The analysis is organized into four complementary campaigns: a leaf-only comparison, a full hierarchy strategy matrix, a depth comparison, and a key-exchange exploration. Across the experimental matrix, the main discontinuity appears when SLH-DSA is placed in the server leaf certificate. In that configuration, handshake latency and server-side compute cost increase by orders of magnitude, whereas strategies that confine SLH-DSA to upper trust layers and preserve ML-DSA in the interactive leaf remain within a more plausible operational range. The results also show that transport size alone does not explain the heavy regime: outside leaf-SLH scenarios, transferred bytes and observed chain size track latency closely, but once SLH-DSA reaches the leaf, server-side cryptographic cost becomes dominant. The paper evaluates post-quantum TLS migration as a problem of certificate-hierarchy design, chain exposure, and cryptographic cost concentration during live authentication. In practical terms, signature placement matters at least as much as signature-family choice.

We introduce metric-aware code-based cryptography by moving beyond the Hamming metric to the Niederreiter-Rosenbloom-Tsfasman (NRT) and sum-rank metrics and by exploiting their linear isometry groups via Bruhat-Chevalley-Renner decompositions. On the structural side, we give isometry-invariant distance tests: a parity-check prefix-rank test for single-chain NRT, its multi-prefix extension for block-NRT, and a block rank-profile test for sum-rank. We also analyze orbit structure under the relevant isometry subgroups and prove NP-hardness of a block-NRT canonicalization problem via a reduction from Exact-3-Cover, pinning down the difficulty of public ``structure recovery.'' On the design side, we propose an inner-outer Niederreiter cryptosystem that couples a short rowwise single-chain NRT inner code with $k_V$ outer binary Goppa codes across columns. For the resulting matrix code we prove a distance guarantee $d_{\mathrm{NRT}}\!\ge\!\delta_V\cdot \min_t d^{(t)}$ and give a simple two-stage decoder (outer Goppa per coordinate, then inner per column). Public keys are dense, obfuscated parity-checks $M=S H_{\mathrm{sys}} (PD)$ drawn from a metric-preserving subgroup, preserving decodability while hiding structure. Finally, we reduce NRT and sum-rank syndrome decoding to classical Hamming/Rank decoding, yielding one-wayness of the public syndrome map at standard regimes.

In the noisy $k$-XOR problem, one is given $y \in \mathbb F_2^M$ and must distinguish between the case where $y$ is uniform and the case where $y = Ax + e$, where $A$ is the adjacency matrix of a $k$-left-regular bipartite graph with $N$ variables and $M$ constraints, $x \in \mathbb F_2^N$ is random, and $e$ is noise with rate $\eta$. Lower bounds in restricted computational models such as Sum-of-Squares and low-degree polynomials are closely tied to the expansion of the underlying constraint graph, leading to conjectures that expansion implies hardness. We show that such conjectures are false by constructing an explicit family of graphs with near-optimal expansion for which noisy $k$-XOR is solvable in polynomial time. Our construction combines two powerful directions of work in pseudorandomness and coding theory that have not been previously put together. Specifically, our graphs are based on the lossless expanders of Guruswami, Umans and Vadhan (JACM 2009). Our key insight is that by an appropriate interpretation of the vertices of their graphs, the noisy XOR problem turns into the problem of decoding Reed-Muller codes from random errors. Then we build on a powerful body of work from the 2010s correcting from large amounts of random errors. Putting these together yields our construction. Concretely, we obtain explicit families for which noisy $k$-XOR is solvable in polynomial time at constant noise rate $\eta = 1/3$, with graphs satisfying $M = 2^{O(\log^2 N)}$, $k = (\log N)^{O(1)}$, and $(N^{1-\alpha}, 1-o(1))$-expansion. Under standard conjectures on Reed--Muller codes over the binary erasure channel, this extends to families with $M = N^{O(1)}$, $k = (\log N)^{O(1)}$, $(N^{1-\alpha}, 1-o(1))$-expansion, and polynomial-time algorithms at noise rate $\eta = N^{-c}$.

ECDSA is a widely deployed digital signature scheme used in securing communications and distributed systems but its structure prevents efficient batch verification. This limitation is impactful in high-throughput applications such as blockchain transaction validation. In this paper, we consider two modified versions of standard ECDSA, namely ECDSA_rec and ECDSA_ast, which embed additional bits in the signature, that enable efficient batch verification. We contribute the first publicly available C implementations of ECDSA_ast on secp256k1 and of both ECDSA_ast and ECDSA_rec on secp256r1, built on top of Bitcoin and OpenSSL codebases, respectively. We evaluate both variants on the two curves and demonstrate batch verification using the two established randomization techniques, NMVR-rand and HSS-rand. The results of our software implementation indicate that batch verification of modified ECDSA signatures usingHSS-rand generally outperforms individual verification of standard ECDSA. Furthermore, the HSS-rand technique provides more efficient batch verification than NMVR-rand in the majority of cases. For a batch of 32 ECDSA_ast (ECDSA_rec resp.) signatures on secp256k1, HSS-rand batch verification improves individual verification by approximately 30.9% (17.2% for ECDSA_rec) and outperforms NMVR_rand batch verification, which achieves improvements of 10.6% (9.8% for ECDSA_rec). The improvements achieved by HSS-rand on secp256r1 are even more pronounced, reaching 53.9% for ECDSA_ast and 40.5% for ECDSA_rec over individual verification of standard ECDSA signatures. In comparison, HSS-rand yields improvements of 27.6% for ECDSA_ast and 22.9% for ECDSA_rec over NMVR-rand, respectively.

Succinct non-interactive arguments (SNARGs) for P are a powerful tool for verifiably outsourcing a computation to a single entity. In this work, we study verifiable outsourcing in a distributed divide-and-conquer setting: a party tasked with solving a large computational problem divides it into smaller subproblems, delegates each subproblem to a different party, and then combines their solutions. Moreover, each party may recursively apply the same strategy, further delegating its computation. Verifying such recursive outsourcing requires SNARGs that are \emph{mergeable}, so that proofs for subproblems can be efficiently combined into a single proof for the original problem. While mergeable proofs have been known for nearly two decades (either based on heuristic assumptions such at SNARKs or, more recently, on standard hardness assumptions), in all existing approaches security degrades exponentially with the number of recursive merges. In this work, we overcome this barrier. Assuming the Learning with Errors (LWE) assumption, we construct a mergeable SNARG for P that supports an unbounded polynomial number of recursive merges. The proof size grows only linearly with the depth of the merge tree, and is independent of its total size.

This paper systematically analyzes the security of the two-branch Unified Feistel Lai Massey (UFLM) structure with independent random round functions under chosen plaintext and chosen ciphertext attacks, focusing on its indistinguishability from a random permutation. UFLM uses an invertible linear layer represented as a $2 \times 2$ block matrix $\varphi$ with blocks $A_{11}, A_{12}, A_{21}, A_{22}$. Previously, Dai et al. proved that when $A_{12}$ is invertible, $4$-round UFLM achieves CCA security and resists up to $\mathcal{O}(2^{n/2})$ queries, where the UFLM input is $2n$ bits. Our work imposes no restriction on $A_{12}$. We determine the minimal number of rounds for UFLM to achieve CPA and CCA security, fully determined by the parameters $T(A_{12}^{\top}, A_{11}^{\top})$ and $T(A_{12}, A_{22})$. For UFLM with enough rounds to be secure, the query bound is primarily determined by the rank of $A_{12}$. For all UFLM with too few rounds to be secure, we present successful distinguishing attacks that require at most four queries. Our results rigorously show, for the first time, that when $A_{12}$ has full rank, UFLM requires the fewest rounds to achieve CPA and CCA security and attains the highest query bound. Nevertheless, when $A_{12}$ is not full rank, CPA and CCA security can still be achieved by increasing the number of rounds unless $T(A_{12}^{\top}, A_{11}^{\top}) = \infty$ or $T(A_{12}, A_{22}) = \infty$. At last, for involutory $\varphi$, we find UFLM achieves CPA and CCA security if and only if $A_{12}$ has full rank.

The advancement of quantum computing poses a serious threat to widely-used public-key cryptographic systems, leaving organizations with the challenge of identifying quantum-vulnerable (QV) executables within their systems and migrating to post-quantum cryptography (PQC). The prior work QED achieves high detection precision through angr-based static call graph analysis (P3), but its processing time of a few to over ten minutes per dataset and RAM consumption of up to 5 GB pose practical limitations on exhaustive screening in largescale environments. In this paper, we propose QED-Lite, a lightweight approximation tool that lightens the analysis stages that incur high computational overhead relative to their detection precision, replacing them with version-based PQC support determination of cryptographic libraries. QED-Lite introduces a newly built PQC risk classification database for 11 major cryptographic libraries and is implemented with a single dependency on pyelftools. Experimental results on the Network dataset show that QED-Lite achieves an execution time up to 855× faster (0.84 seconds) and reduces memory usage by 228× (22.9 MB) compared to QED, while maintaining a TPR of 100%. QED-Lite delivers practical value relative to its cost as a first-pass screening tool that is operationally viable in large-scale organizational environments.

In this note, we review the formulation of SNOVA in three different languages: the ring-equation form, the whipping form, and the tensor form. Based on this, we propose a reformulation of SNOVA and discuss the security analysis of the resulting reformulated scheme. As a conclusion, we find that this new framework allows for greater flexibility in parameter selection and enables us to obtain parameter sets that remain competitive. In particular, as shown in the appendix, parameter sets over odd characteristic $\mathbb{F}_{q}$ lead to smaller key sizes and may offer improved resistance against certain attacks. This makes parameter sets over odd characteristic $\mathbb{F}_{q}$ especially interesting from a practical perspective. We propose a number of parameter sets that have certificate sizes below one kilobyte.

In incentivized outsourced computation,an outsourcer hands a computation to multiple contractors, and in return expects the same computation output from each. The state-of-the-art proposals succeed in incentivizing all contractors for honest computation by setting this behavior as the unique Nash equilibrium of the system. Yet, they are either limited to the two-contractor case or the multi-contractor case without security proof against fully collaborating coalitions. Further, employing a smart contract for managing submissions from the contractors has been a non-trivial task due to the copy attack. In this work, we target this issue and propose a smart contract based multi-contractor incentivized outsourced computation protocol Delegate, which is provably secure against coalitions. We further mitigate the copy attack by a universally composable response submission protocol based on commitments, in contrast to previous solutions which only disincentivize it.

The study of coin-tossing protocols lies at the intersection of cryptography and game theory, where parties with potentially conflicting interests aim to jointly generate an unbiased random bit. Classical cryptographic results establish that strong fairness is achievable with an honest majority in the statistical setting, but impossible with a dishonest majority. In parallel, game-theoretic approaches [TCC 2018, Eurocrypt 2022 \& CRYPTO 2024] have demonstrated that weaker equilibrium-based fairness guarantees can sometimes circumvent cryptographic lower bounds, raising the question of whether such techniques can overcome impossibility in the statistical regime. In this work, we answer this question negatively. - We show that for $n$ parties and $t \geq n/2$ corruptions, there exists no statistically secure, game-theoretic coin-tossing protocol, even assuming broadcast and bounded round complexity—with the sole exception of the case $n=4$ where all but one party share the same preference. This complements known feasibility results for $t < n/2$, thereby completing the statistical feasibility landscape. - We further consider the setting without broadcast. Here we prove that no computationally secure game-theoretic coin-tossing protocol exists for $t \geq n/3$ and polynomial-round complexity, except for the corner case $n=6$ where all but one party share the same preference. To establish these results, we refine existing frameworks for game-theoretic fairness to capture both broadcast and point-to-point communication models. Together, our results establish the boundaries of game-theoretic fairness in multi-party coin tossing: while it extends feasibility in the computational setting, it offers no advantage in the statistical setting once an honest majority is lost.

The Hamming Quasi-Cyclic (HQC) cryptosystem, recently selected by NIST for standardization, uses a concatenation of Reed-Muller (RM) and Reed-Solomon (RS) codes to ensure correct decryption. This work optimizes the underlying code and decoder with the goal of reducing ciphertext and public-key sizes. First, we propose a two-level generalized concatenated code (GCC), exploiting the observation that the inner RM code contains a repetition subcode. The repetition layer incurs a smaller inner failure probability and, therefore, admits a higher code rate than the RS code. Second, we develop a reliability-based decoding framework for the outer code. The inner decoder provides a reliability measure whose distribution, jointly with the decoding outcome, is bounded analytically. These bounds allow deriving conservative DFR guarantees for two erasure-assignment strategies (threshold-based and partition-based). Combining both contributions, we observe that public-key and ciphertext sizes can be reduced by up to 4.34%.

Secure multiparty computation (MPC) enables mutually distrustful parties to jointly compute over private data without revealing their inputs. While protocols in both synchronous and asynchronous settings have achieved impressive efficiency in either communication or round complexity, combining the two has remained challenging. Only recently, Abraham, Asharov, Patil, and Patra (Eurocrypt’23, Eurocrypt’24) achieved protocols that combine low communication complexity ($O((Cn + Dn^2 + n^4)\log n)$) with fast execution ($O(D)$ rounds) in both synchronous and asynchronous models, for circuits of size $C$ and depth $D$, in the perfect setting with optimal resilience. However, both protocols crucially assume advanced knowledge of the network type and are fragile under mismatched or varying network conditions. The fragility of protocols under mismatched network assumptions highlights the need for network-agnostic MPC, where security and correctness are preserved in both synchronous and asynchronous settings. Yet, all known perfect network-agnostic protocols incur $\Omega(D+n)$ rounds and communication complexity in the order of $n^3$ or higher, far worse than their network-specific counterparts. In this work, we present the first network-agnostic MPC protocol in the perfect security setting, achieving expected round complexity $O(D)$. Our protocol has expected communication complexity $O((Cn^2 + Dn^2 + n^4)\log n)$, improving on the state of the art by a factor of $n^3$ for small circuits and $n^2$ for large circuits in communication, in addition to an additive $O(n)$ improvement in round complexity. Our design departs from the structure of prior network-agnostic protocols and introduces several new technical ideas that enable both round and communication efficiency.

The Inner Product Extractor (IPE) of Impagliazzo, Levin, and Luby (STOC'89) takes a seed $h\in\mathbb{F}^\gamma$ and a source $x\in\{0,1\}^\gamma$ for some $\gamma\in\mathbb{N}$ and produces $\langle h,x\rangle$ with error $\varepsilon=\mathsf{SD}((\langle\mathcal{H},\mathcal{X}\rangle,\mathcal{H}),(\mathcal{Y},\mathcal{H}))$ such that $$ \varepsilon\le\frac{1}{2}\sqrt{|\mathbb{F}|^{\gamma}/2^{H_\infty(\mathcal{H})}}\,\,\sqrt{|\mathbb{F}|/2^{H_\infty(\mathcal{X})}} $$ where $\mathcal{Y}$ is the uniform distribution over $\mathbb{F}$, and $\mathcal{H}$ and $\mathcal{X}$ are the independent but possibly non-uniform distributions from which $h$ and $x$ are drawn, respectively. In other words, the IPE's error grows with the square root of seed bias, at most. This square root arises because prior works bound the squared error using the 2-universality of the IPE. The analysis requires an even power of the error, and the IPE is not $4$-universal. Motivated by applications to multiparty computation, we revisit the problem of the IPE with biased seeds and prove far tighter bounds on the influence of seed bias by bypassing universal hashing. We first prove an Elevated General Leftover Hash Lemma, which yields an $n^{\text{th}}$ root bound for functions that are almost $n$-universal. Bounding number of inputs on which the IPE is not 4-universal yields $\varepsilon=\mathsf{SD}((\langle\mathcal{H},\mathcal{W}\rangle,\mathcal{H}),(\mathcal{Y},\mathcal{H}))$ where $$ \varepsilon\lesssim\frac{2.1}{2}\left(|\mathcal{F}|^\gamma/2^{H_\infty(\mathcal{H})}\right)^{\frac14} \sqrt{|\mathbb{F}|/2^{H_\infty(\mathcal{W})}} $$ for any oblivious bit-fixing source $\mathcal{W}$ with $2^{0.585 H_\infty(\mathcal{W})} \le |\mathbb{F}| \le 2^{H_\infty(\mathcal{W})}$. Next, we use matroid theory to directly analyze the $n$-way multicollision probability of the IPE, yielding an asymptotic bound for any even $n$. For $n\ge4$, $0 < \epsilon \le 0.83/(n - 2)$, and $|\mathbb{F}| \le 2^{(1 - \epsilon)\cdot H_\infty(\mathcal{W})}$, as $|\mathbb{F}|\to\infty$, $$ \varepsilon \le\frac{(n - 1)}{2}\left({|\mathcal{F}|}^\gamma/2^{H_\infty(\mathcal{H})}\right)^{\frac1n} \sqrt{\vphantom{/}2^{-\epsilon\cdot H_\infty(\mathcal{W})}}\,\, (1 + o(1)). $$ Computing a \emph{concrete} version of this bound requires time exponential in $n$. We compute concrete $\{4,6,8\}^{\text{th}}$-root bounds and demonstrate that no one choice of $n$ is optimal. Finally, we introduce a new class of seed-adaptive oblivious bit-fixing sources, extend our results to such sources, and use this extension to fix a bug that we identify in the proof of the oblivious linear evaluation protocol of Doerner et al. (SP'24).

Secret Sharing schemes allow a dealer to distribute $n$ shares $s_1,\ldots, s_n$ of a secret $s$ so that any $t$ shares suffice to reconstruct the secret, while any $t-1$ shares reveal no information about $s$. In fact, schemes such as Shamir Secret Sharing satisfy a stronger guarantee called $(t\!-\!1)$-perfect privacy, meaning that for any subset $S \subseteq [n]$ with $|S| \le t-1$, the joint distribution $(s_i)_{i \in S}$ is uniformly distributed over its domain. This strong guarantee is essential for applications such as fuzzy password-authenticated key exchange (fPAKE) and conditional encryption --- a recent cryptographic primitive introduced to enable secure personalized password typo correction. Unfortunately, Shamir secret sharing is not robust: corrupted shares can prevent correct reconstruction or cause reconstruction of an incorrect secret. Existing robust secret sharing schemes address this issue but necessarily sacrifice perfect privacy. We introduce and construct Random Robust Secret Sharing with Perfect Privacy (RRSS), a new notion that preserves $(t\!-\!1)$-perfect privacy while providing robustness against random share corruptions. In our schemes, the secret is recovered with high probability even if an arbitrary subset of up to $n-t$ shares is independently corrupted at random. We demonstrate the utility of RRSS through two applications. First, we present the first practically efficient fPAKE construction that tolerates Hamming errors. Second, we obtain the first efficient conditional encryption scheme for arbitrary Hamming distances, improving upon prior work that achieved efficiency only for constant distances. We implement both constructions and empirically demonstrate their practicality.

A recent paper by Calderini et al. investigates the use of a CCZ transformation to mask the quadratic central map in a multivariate scheme, providing an instance leading to a system of degree four. A following paper by Caminata et al. presents two methods to reduce the masked system back to a quadratic system. In this work we further study the method based on the quadratic relations between input and output of the masked function, generalizing it and applying to any CCZ transformation (of any quadratic map). Moreover, we study how the existence of these quadratic relations can be used to study whether a function can be CCZ equivalent to a quadratic map and, more generally, to study whether two functions can be CCZ equivalent. In fact, this analysis gives us necessary conditions that can be checked also in relatively large dimensions. Particularly, we completely analyse the cases of vectorial Boolean functions with 1 and 2 output bits.

The BBS+ signature scheme is a widely used foundation for anonymous credential systems. It is favored for its support of selective disclosure and its efficiency in proving credential possession. However, in traditional settings, credentials are typically issued by a single authority, creating a single point of failure and potential security risk. This limitation can be mitigated by adopting a distributed variant, known as the threshold BBS+ scheme. In this work, we present \textit{Robot}, the first two-round threshold BBS+ signature scheme. Robot is round-minimal and achieves robustness, ensuring that every signing execution successfully completes as long as there exist $t+1$ parties behaving honestly. To achieve this, we employ a threshold verifiable random function (TVRF) to robustly generate the public nonces within a single round. Specifically, we utilize an efficient DDH-based TVRF construction, which not only provides our scheme with a round advantage but also enhances its overall performance. Then, by carefully invoking the threshold Castagnos-Laguillaumie and threshold ElGamal homomorphic encryptions, we complete all remaining non-linear operations within the second round. Asymptotically, Robot achieves a constant per-party upload communication and linear computation overhead with respect to the number of signers. Compared with the four-round robust scheme of Wong et al. (NDSS'24, WMC24), which has the same asymptotic complexity, Robot achieves a smaller constant communication cost (2.02 KB vs. 3.23 KB) and nearly halves the runtime. Compared with the three-round robust scheme of Tang and Xue (S\&P'25, TX25), which has linear communication overhead, Robot exhibits better communication and computational efficiency when the number of signers is five or more.

In 2021, Bruna, Regev, Song and Tang introduced the continuous analogue of LWE, CLWE. Shortly after, Gupte, Vafa, and Vaikuntanathan showed a classical reduction from LWE to CLWE and from discrete-CLWE (secret from a discrete set) to LWE. In this paper, we show two results. The first result is a search-to-decision reduction for CLWE. The search-to-decision reduction works similarly to the standard reduction for LWE. The main difference between the reductions is the continuous nature of the CLWE secret. As a consequence, our reduction can find the secret up to a polynomial error $n^{-k}$ for some constant $k$. The second and our main result is the reduction from CLWE to discrete-CLWE. The reduction is an identity reduction, i.e. samples are passed as-is to the distinguisher. To prove the distinguisher can accept the samples we employ tools from analytic number theory. These tools allow us to show that the set $\frac{1}{r} \cdot \mathbb{Z}^n$ with fixed $\ell_2$ norm $r$, i.e. integer vectors projected onto the unit sphere, can mimic the unit sphere $S^{n-1}$ for some $r > r'$. By completing this missing link, we can show that LWE is equivalent to CLWE i.e. $\text{LWE} \equiv \text{CLWE}$ and existing or new results on each problem apply to the other.

Modern blockchains increasingly rely on parallel execution to improve throughput. We show several industry and academic transaction fee mechanisms (TFMs) struggle to simultaneously account for execution parallelism while remaining performant and fair. First, if parallelism affects fees, adversarial protocol manipulations that offset possible benefits to throughput by introducing fake transactions become rational: users can insert functionally useless parallel transactions solely to reduce fees, and schedulers can create useless sequential transactions to increase revenue. Execution contingency, a core feature of expressive programming languages, both exacerbates the aforementioned threats and introduces new ones: (1) users may overpay for unused resources, and (2) scheduler revenue is harmed when reserved scheduling slots go unused due to contingency. We introduce a framework for this challenging setting, and prove an impossibility, highlighting an inherent tension: both parallelism and contingency involve a trade-off between minimizing risks for users and schedulers, as favoring one comes at the expense of the other. To complete the picture, we introduce a fee mechanisms and prove that they achieve the boundaries of this trade-off. Our results provide rigorous foundations for evaluating designs advanced by notable blockchains, such as Sui and Monad.

Fault injection attacks pose a significant threat to the security of embedded devices. While their effects are commonly modeled as instruction skips or data corruption, characterizing these faults requires programs that expose software-visible faulty behavior. However, many fault effects originate from microarchitectural elements, making them difficult to identify using existing approaches. On one hand, Register Transfer Level (RTL) analyses provide fine-grained insights but rely on abstract models that may not fully reflect the physical circuit. On the other hand, empirical characterization captures real faults but requires extensive experimentation and often reveals multiple fault models simultaneously, complicating precise identification. To address this gap, we propose an automated methodology that synthesizes characterization programs specifically designed to expose targeted microarchitectural fault models using a model-checking algorithm. Our methodology also assesses additional fault models revealed by these programs. Applied to two RISC-V processor cores, CV32E40P and Ibex, our methodology synthesizes programs that expose bit-flip faults for approximately 70 % of microarchitectural signals, using two days of computation on 10 parallel cores. For 25 % of the control signals in CV32E40P, we synthesize programs enabling the precise attribution of a bit-flip to a targeted signal. Such programs could facilitate the use of fault injection to deduce the placement of microarchitectural elements and help design more effective countermeasures. To the best of our knowledge, this work represents the first systematic methodology for building fault characterization pro- grams, marking a significant step beyond empirical approaches.

SSLE-DAG Proof-of-Stake (PoS) blockchains with publicly visible leader schedules expose future proposers to targeted Denial-of-Service (DoS) attacks. Single Secret Leader Election (SSLE) techniques address this problem by hiding the leader's identity until block publication. However, existing SSLE techniques are difficult to integrate with high-throughput Directed Acyclic Graph (DAG)-based Proof-of-Stake consensus protocols. We introduce SSLE-DAG, a PoS consensus protocol that combines a zk-SNARK-based SSLE commitment scheme with the adaptive DAG-based consensus protocol that splits or merges parallel chains (and thus regulates throughput) upon transaction demand. The commitment scheme uses EdDSA signatures, MiMC hashing, and Merkle proofs to guarantee uniqueness, fairness, and unpredictability while keeping leader identities private. We implement SSLE-DAG in Go (gnark) and evaluate it in a geo-distributed simulation using real-world latency traces. In a 60-node network, we achieve about 990 TPS, and in a 40-node network with shorter rounds, we reach about 1,600 TPS with low variance in block rewards.

Low-entropy keys such as passwords and biometrics are pervasive, yet classical information-theoretic guarantees, such as perfect secrecy and entropic security, cannot generally be achieved in this regime. Honey encryption (HE) and homophonic ciphers (HC) tailor encryption to the message distribution to provide meaningful security, but their analyses do not establish optimal guarantees for arbitrary distributions. We ask: for messages and keys drawn independently from arbitrary distributions $(p_{\mathrm m},p_{\mathrm k})$, what is the optimal information-theoretic security achievable by any symmetric encryption scheme, and which conditions characterize its attainment? For key confidentiality (KC), the optimal guarantee is that the ciphertext $C$ reveals only negligible information about the key $K$, i.e., $I(K;C)=\operatorname{negl}(\ell)$. For uniform schemes, this is achieved if and only if decrypting under every fixed key yields a distribution statistically close to $p_{\mathrm m}$. HC and HE achieve this guarantee. For message-recovery security (MRS), the optimal guarantee is that no adversary guesses the message with probability above $p_{\max}+\operatorname{negl}(\ell)$, while a trivial adversary achieves at least $p_{\max}$ by guessing the most likely message or decrypting under the most likely key. We construct MRS-OE, a uniform scheme tailored to $(p_{\mathrm m},p_{\mathrm k})$ that attains $p_{\max}+O(2^{-\ell})$, and prove that $p_{\mathrm k}$-agnostic schemes, including HC and HE, cannot achieve optimal MRS in general. We also show that optimal KC and optimal MRS generally cannot be achieved simultaneously. Technically, we establish the KC characterization through flow and cut analysis on a weighted directed acyclic graph. We also introduce a continuous-ciphertext framework that separates structural constraints from discretization error.

In a dictatorial setting where the receiver’s secret key may be exposed to an adversary, anamorphic encryption enables secure communication. Since its introduction in 2022, anamorphic cryptography has attracted considerable attention in the cryptographic literature. Anamorphic extension (AE) strengthens this paradigm by providing deniability: although the receiver can participate in covert communication, it can plausibly deny the existence of such communication to the dictator. The security of an AE of a public key encryption (PKE) is captured by the indistinguishability between its normal and anamorphic modes of operation, formalized by the IND-NA notion. In this paper, we have introduced two concrete constructions of AE from the number-theoretic assumptions-based indistinguishability against chosen plaintext attack (IND-CPA)-secure Goldwasser-Micali PKE and Benaloh PKE. We have proved the IND-NA security of our proposed AEs assuming the existence of secure pseudo-random function (PRF). To the best of our knowledge, our proposed Goldwasser-Micali based construction is the first AE that achieves natural robustness, attains bandwidth rate 1 and has small key-sizes where bandwidth rate is determined by the ratio of the covert and normal plaintext. The bandwidth rate of the Benaloh PKE-based construction is >> 1. Our proposed AEs are efficient due to small key size, low computation costs mostly involving computations of PRF and modular operations, high bandwidth rate, low anamorphic ciphertext expansion rate (ratio of the ciphertext size and the covert plaintext size) and deniability.

Ordered multi-signatures allow multiple signers to sign a common message sequentially, and anyone to verify the signing order of signers with a public-key list. Recently, Baum et al. (PKC 2025) proposed an ordered multi-signature scheme over a pairing-free group by modifying the multi-signature scheme MuSig2 by Nick et al. (CRYPTO 2021). The security of their ordered multi-signature scheme was proven under the algebraic one-more discrete logarithm (AOMDL) assumption in the random oracle model (ROM). The AOMDL assumption is stronger than the discrete logarithm (DL) assumption. To strengthen the assurance of security, it is desirable either to prove their scheme under the DL assumption or give a construction whose security is proven under the DL assumption. In this paper, we give an ordered multi-signature scheme from linear hash function families. Our scheme is obtained by generalizing Baum et al.’s scheme via linear hash function families. The security of our scheme is proven under the algebraic one-more preimage resistance (AOMPR) property of a linear hash function in the ROM. There is a linear hash function whose AOMPR property can be proven under the DL assumption. Thus, by using this linear hash function, we obtain the first DL- based ordered multi-signature scheme.

In federated learning (FL), secure aggregation (SA) allows a server to compute aggregate model updates (gradients) without accessing individual client gradients. SA is intended to protect clients’ local dataset from being inferred through individual gradients. However, recent NDSS 2025 work shows that even state-of-the-art SA protocols can be vulnerable, as a malicious server may reconstruct clients’ datasets from aggregated gradients. This demonstrates that protecting dataset privacy requires not only gradient confidentiality but also aggregation hiding. Moreover, a malicious server may deviate from the protocol and return manipulated results, making authenticity an additional critical security goal. Supporting one-shot clients, which send a single message per iteration to reduce synchronization overhead, further increases design complexity. To address these challenges, we propose FOVA, a fast one-shot verifiable aggregation protocol that simultaneously achieves aggregation hiding and authenticity against an actively malicious server. Notably, authenticity, defined under full participation, must be relaxed for dropout robustness due to the indistinguishability between adversarial omissions and legitimate dropout. FOVA is built upon the verifiable linearly homomorphic encryption scheme, for which we give a new construction based solely on the Paillier cryptosystem. This design enables high efficiency and allows FOVA to be integrated into existing Paillier-based FL frameworks with minimal modifications. We implement FOVA on top of an industrial FL framework. Experimental results show that, compared to the most relevant prior protocols, FOVA achieves up to three orders-of-magnitude speedup while providing stronger security guarantees.

As digital transformation accelerates, securing communication through hierarchical Public Key Infrastructures (PKIs) is increasingly critical. Yet, this centralized trust architecture remains inherently vulnerable. As a Systematization of Knowledge (SoK), this paper maps the threat landscape of hierarchical PKIs, demonstrating how a compromise at any single node from a Root CA breach to an operational revocation failure can trigger a cascading loss of global trust. Grounded in the Weakest-Link Principle, our analysis reveals that a PKI ecosystem is only as resilient as its least protected vector. Traditional revocation mechanisms, particularly CRLs and OCSP, exhibit significant operational and privacy flaws, and are often rendered ineffective by client-side "soft-fail" policies. To address these vulnerabilities, we advocate for a shift: replacing unconditional trust in individual entities with decentralized,verifiable protocols. We evaluate Certificate Transparency (CT) as a core mitigation strategy, illustrating how append-only Merkle trees make misissuance publicly visible and cryptographically auditable. Finally, we synthesize essential operational hardening measures such as strict key cryptoperiods and procedural policies to ensure long-term ecosystem resilience.

We present $\mathsf{HyperVerITAS}$, a new zero-knowledge proof (ZKP) system for image provenance that enables scalable, efficient, and privacy-preserving verification of image transformations. $\mathsf{HyperVerITAS}$ builds upon the same minimal trust model as $\mathsf{VerITAS}$ (IEEE S&P '25), requiring trust only in the image source device, while treating the editing software as untrusted. Unlike $\mathsf{VerITAS}$, which relies on FFT-intensive SNARKs and suffers from high memory overhead (up to 120 GB), $\mathsf{HyperVerITAS}$ leverages multilinear polynomial encodings over the Boolean hypercube to dramatically reduce both proving time and memory usage. Our design cleanly separates signature verification from image transformation, supports modular integration of multiple polynomial commitment schemes (including post-quantum constructions) and naturally extends to a wide range of affine image transformations. We implement $\mathsf{HyperVerITAS}$ with two distinct commitment schemes (Brakedown and multilinear KZG) and evaluate it on full-system pipelines involving cropping and grayscaling. On commodity hardware (Apple M3, 36 GB RAM), $\mathsf{HyperVerITAS}$ generates proofs for 33 MP images using only 27 GB of RAM and 6.6 minutes of proving time, whereas $\mathsf{VerITAS}$ fails to scale beyond 4 MP. These results establish $\mathsf{HyperVerITAS}$ as a practical and scalable ZKP system for secure and efficient image provenance.

We give a down to earth and elementary introduction to the isogeny based cryptography protocol MIKE.

Synchronous Byzantine fault tolerant (BFT) protocols offer stronger security guarantees, increasing resilience from one third to one half. However, existing constructions suffer from three drawbacks that are critical in blockchain settings. First, blockchain systems require rotating leaders, but the existing constructions are not optimized for low latency under leader rotation. Second, blockchain systems require provable commitments that can be forwarded to clients or offchain entities. Third, modern blockchains optimize for low latency in the good case, and often further optimize for a fast path under even milder adversarial conditions. In this work, we formalize and study fast paths in the context of provable synchronous BFT. Our first result is that for $n \le 2t + 2p + c -1$, it is impossible to obtain a provable synchronous BFT protocol that tolerates $t$ Byzantine and $c$ crash faults while also achieving a two round fast path resilient to $p$ Byzantine faults. Guided by this bound, we then present four provable synchronous protocols tailored to two deployment paradigms: optimistic responsivness and fixed view schedules. For optimistic responsiveness, we present $\Delta$-Sync Simplex and $2\Delta$-Sync Simplex, which for $n = 2t + 2p + c + 1$, produce provable commit certificates in time $2\delta$ under a correct leader when the number of faulty parties $f$ satisfies $f \le p$. $2\Delta$-Sync Simplex also achieves $3\delta$ commit latency when the total number of faulty parties is $f \le \lfloor (p + t)/2 \rfloor$ with Byzantine faults $f_b \le t$ and crash faults $f_c \le c$. Outside these optimistic regimes, the protocols remain safe and live for $t$ Byzantine and $c$ crash faults, and output provable commitments within $2\Delta + 2\delta$ and $1\Delta + 3\delta$, respectively. Under faulty leaders, the protocols guarantee a worst case view length of $6\Delta + \delta$ and $5\Delta + \delta$ respectively. For fixed view schedules, we present two additional protocols, TenderSync and SyncMint, that trade off commit latency and view duration. They achieve either $3\Delta$ provable commit with $4\Delta$ views, or $4\Delta$ provable commit with $3\Delta$ views. Both protocols obtain a provable commit in $2\delta$ under a correct leader when $f \le p$.

We describe THED, a threshold version of the Dilithium signature scheme (ML-DSA), whose issued signatures are valid for the genuine Dilithium verification algorithm. The signing protocol has two rounds of communication, one of which that lends itself to preprocessing. The scheme supports arbitrary number of users and threshold parameter. The construction consists in running Dilithium's signing algorithm under Threshold Fully Homomorphic Encryption (ThFHE), except for the computation of the signing challenge that happens in clear. For signing-mask generation, SHAKE is replaced by a ring variant of the Darkmatter PRF under an additional pseudorandomness assumption. Due to the type of operations performed, we rely on the CKKS scheme for homomorphic computations. However, a number of challenges remain, for which we develop new tools. In particular, we describe a CKKS-BFV continuum that helps for modular operations in the context of other non-arithmetic operations, a hybrid-format homomorphic comparison when the input is the sum of a bit-decomposed integer and a small integer, and a modulus-thrifty homomorphic comparison of larger non-bit-decomposed integers. Furthermore, to ensure the protocol is communication efficient, we developed a new threshold decryption method for CKKS providing more compact decryption shares. Our proof-of-concept implementation of the FHE components of the signing protocol runs in under 1.3s on an RTX-5090 GPU, with 23.6KB of communication per party for the NIST level-2 Dilithium variant. In the randomized signing mode, most of the computation can be run in an offline phase without the message to be signed; the online cost then shrinks to under 0.25s. Apart from the two decryption steps, this computation is entirely public and can be delegated to a server with more powerful hardware.

Retrieval-Augmented Generation (RAG) is widely used to enhance Large Language Models (LLMs), yet the "hallucination" characteristic allows malicious providers to bypass retrieval or claim non-existent data quality. To address these challenges, we present VeriRAG, a framework that leverages Zero-Knowledge Proofs (ZKP) to provide efficient integrity guarantees for RAG systems without compromising dataset privacy. Leveraging the robustness of AI inference, our framework supports Approximate Nearest Neighbor Search (ANNS)-based retrieval to avoid exhaustive searches. For the verification of top-$k$ sorting, we propose an innovative protocol that bypasses the intricate verification of sorting processes. To further enhance performance, we introduce a joint optimization leveraging vector lookup and chunk-merging strategies, which collectively drive down verification overhead while maintaining high generation accuracy. Experimental results demonstrate that VeriRAG scales efficiently to a 37GB dataset, achieving a prover time of 96s and a verifier time of 3s.

Feedback shift registers, such as Linear Feedback Shift Registers (LFSRs), Multi-Recursive Matrix Methods (MRMMs), and Lagged Fibonacci Generators (LFGs), are fundamental components in stream cipher-based cryptographic systems. In this paper, we investigate systems composed of LFSRs under two distinct configurations. First, we study the cascade connection of LFSRs and demonstrate that it represents a special case of the first configuration. Under specific conditions, we derive the exact period of these cascaded systems. Second, we analyze a system comprising two LFSRs in the second configuration, where carry bits are introduced into the feedback computation of the second LFSR. We examine the periodicity of both the carry bits and the overall system. Furthermore, we generalize this construction to word size $m$, and show that an additive LFG can be represented by an equivalent system of LFSRs. This approach enables efficient LFG implementation in resource-constrained environments by using multiple LFSRs and a simple adder, thus eliminating the need for large word sizes.

We present a low-stack implementation of the module-lattice signature scheme \(\mathrm{HAETAE}\), targeting microcontrollers with \(8\,\mathrm{kB}\)–\(16\,\mathrm{kB}\) of available SRAM. On such devices, peak stack usage is often the binding constraint, and \(\mathrm{HAETAE}\)'s hyperball-based sampler, large transient polynomial vectors, and variable-length signature payloads (hint and high-bits arrays) pose a particular challenge. To address this, we introduce (i) rejection-aware pass decomposition, which isolates encoding to the post-acceptance path; (ii) component-level early rejection, which short-circuits the response computation when a partial norm already exceeds the bound; and (iii) reverse-order streaming entropy coding using range Asymmetric Numeral Systems (rANS), which eliminates full hint and high-bits staging buffers. Combined with streamed matrix generation, a two-pass hyperball sampler with streaming Gaussian backend, and row-streamed verification, these techniques bring signing stack usage from \(71\,\mathrm{kB}\)–\(141\,\mathrm{kB}\) in the reference implementation down to \(5.8\,\mathrm{kB}\)–\(6.0\,\mathrm{kB}\), key generation to \(4.7\,\mathrm{kB}\)–\(5.7\,\mathrm{kB}\), and verification to \(4.7\,\mathrm{kB}\)–\(4.8\,\mathrm{kB}\) across all three security levels. Our pure C implementation covers all three security levels (\(\mathrm{HAETAE}\)-2/3/5), whose optimization paths differ due to the public-key domain (\(d > 0\) vs. \(d = 0\)) and rejection structure. We implement our optimization on a Nucleo-L4R5ZI and compare it to the reference `pqm4` implementation (for \(\mathrm{HAETAE}\)-2 and -3) and to a recently published memory-optimized implementation (targeting \(\mathrm{HAETAE}\)-5 only). We reduce \(\mathrm{HAETAE}\)-2, -3, and -5 stack usage by respectively \(75\%\), \(86\%\), and \(8\%\) for key generation, \(92\%\), \(95\%\), and \(24\%\) for signature generation, and \(85\%\), \(91\%\), and \(22\%\) for verification. Depending on the parameter set, this impacts performance by at most a factor of \(1.8\) and \(3.4\) for key generation and signature generation, respectively, while even offering a performance improvement of up to \(18\%\) for verification. Verification at all security levels fits within \(8\,\mathrm{kB}\) of RAM (signature buffer + stack) and is \(2.34\)–\(3.34\times\) faster than ML-DSA m4fstack at each comparable security level. We additionally validate portability under RIOT-OS on ARM Cortex-M4 and RISC-V targets.

In this technical note, we discuss a new direction in the design of privacy-preserving and scalable Layer-2 (L2) protocols by presenting a concrete construction, PlasmaBlind. To minimize the L2 users’ overhead for achieving privacy while enabling efficient creation of compact blocks, PlasmaBlind is built upon a novel architecture that leverages folding schemes’ powerful and flexible properties. On the user side, we utilize their blinding property to shield and prove transaction data without expensive succinct zero-knowledge proofs. On the aggregator side, their low accumulation cost allows efficient aggregation of user instances into a constant size proof of block validity. We further improve our proof aggregation performance by proposing an optimization technique that efficiently links two different verification tasks with shared input while eliminating the need for cumbersome proof composition of non-uniform circuits, which could be of independent interest. The practicality of PlasmaBlind is validated by our preliminary benchmarks, which demonstrate that, with consumer hardware, PlasmaBlind achieves sub-100ms proving time on the client side and sub-300ms per-transaction time on the aggregator side.

Information set decoding (ISD) algorithm is the main tool to estimate the concrete bit security of code-based cryptographic schemes including Classic McEliece, HQC and BIKE. Inspired by sieving methods in lattice-based cryptoanalysis, a new type of ISD algorithm (called sieving-ISD) based on locality sensitive filter (LSF) was recently proposed by Guo, Johansson, and Nguyen [GJN24, TIT], which has been shown to achieve comparable complexity with the BJMM/MMT algorithm when attacking Classic McEliece. At EUROCRYPT 2024, Ducas, Esser, Etinski and Kirshanova extended [GJN24, TIT]'s deterministic LSF to probabilistic LSFs and provided an asymptotic worst-case complexity analysis for sieving-ISD with different LSFs in the full-distance setting, which indicates that the sieving-ISD with probabilistic LSFs can achieve better time complexity than the ones with [GJN24, TIT]'s deterministic LSF. In this paper, we first propose a generalized sieving-ISD framework (called progressive sieving-ISD), which allows for more freedom in parameter configuration. In particular, we present a concrete complexity analysis for both our progressive sieving-ISD and its ``decoding one out of many'' (DOOM) variant under a binary sieve heuristic, whose validity can be verified via experiments. Then, by searching the optimal parameter configuration, we show that our progressive sieving-ISD can achieve attack time complexity improvements over the previous non-progressive version by 5-12 bits. In particular, for all the three categories of HQC to be standardized by NIST, we show that the state-of-the-art complexity results can be reduced by 7-9 bits using our progressive sieving-ISD, making their security levels 5.1/2.1/5.7 bits below the NIST requirements (143/207/272 bits). Interestingly, our results show that when considering the concrete security of Classic McEliece/HQC/BIKE, the progressive sieving-ISD with [GJN24, TIT]'s deterministic LSF can achieve a better performance than the ones with probabilistic LSFs in [DEEK24, EC]. Finally, we show the connection between progressive sieving-ISD and BJMM, and hence explain why progressive sieving-ISD can achieve a better time complexity than BJMM.

The SPHINCS+ framework, recently standardized by NIST as SLH-DSA (FIPS 205), is a leading stateless hash-based signature scheme for the post-quantum era. Concrete-security evaluation of SPHINCS+ faces a trade-off: tight bounds require a conjectural multi-target decisional second-preimage resistance (SM-DSPR), while fully proven bounds incur substantial looseness. In this paper, we refine the concrete security analysis of SPHINCS+ by eliminating this heuristic reliance. In our approach, we analyze the SM-openPRE and SM-PRE properties instead of relying on SM-DSPR. By utilizing a precise probabilistic simulation technique, we restrict the multi-target tightness degradation exclusively to the maximum number of practically revealed targets rather than the total theoretical targets. When applied to the SLH-DSA parameter sets, our conjecture-free approach bridges the theoretical gap, recovering up to 18 bits of classical security and 9 bits of quantum security compared to the NIST loose evaluation. Our results establish a provable bound for the practical security of SLH-DSA without relying on optimistic multi-target assumptions.

Among the schemes in the second round of NIST's additional call for Post-Quantum signatures, PERK builds its security on the intractability of the Permuted Kernel Problem (PKP). In its original formulation, this problem asks, on input three matrices $\mathbf H,\mathbf X,\mathbf Y$, to find a permutation matrix $\mathbf P$ such that $\mathbf H \mathbf P \mathbf X = \mathbf Y$. To achieve better performance and smaller signatures, in its first proposal, the PERK signature modified the security assumption in the following way: given a PKP instance, the matrix $\mathbf P$ does not have to verify the exact previous equation but a relaxed one, taking care of a non-null vector $\mathbf v$ such that $(\mathbf H \mathbf P \mathbf X)\mathbf v = \mathbf Y \mathbf v$. In this work, we rephrase the relaxed problem so that it no longer depends on the PKP instance nor the vector $\mathbf v$. We show that it suffices to find $\mathbf P$ such that $\mathbf H\mathbf P \mathbf X - \mathbf Y$ has rank deficiency. This generalized formulation is easier to model and allows us to design an algebraic attack inspired by those of MinRank and Rank Syndrome Decoding, writing a polynomial system in the entries of $\mathbf P$. Moreover, we can consider it as linear in the minors of $\mathbf P$ and provide some results on them, which may be of independent interest.

We present an asymptotic analysis of the ternary variant of Sparse Learning with Errors (spLWE), a structured LWE variant proposed by Jain--Lin--Saha (CRYPTO'24) in which each equation involves only $k \ll n$ of the $n$ secret coordinates, enabling significantly more efficient computation than dense LWE. Unlike standard LWE, the small-secret regime of spLWE is not automatically reducible to its large-secret counterpart, leaving asymptotic hardness unclear, particularly when $k$ is very small. We develop a two-pronged attack framework that depends explicitly on the sparsity parameter $k$. In the geometric regime $q > 3^k$, each sparse row reduces to a short-vector problem in a $k$-dimensional lattice, yielding complexity $2^{0.292k}$ via a sieving algorithm. In the statistical regime $q \leq 3^k$, we propose a greedy coordinate-recovery attack with running time $O(m \cdot k \cdot 3^k)$, where $m$ is the number of samples. Heuristically, under mild assumptions, full recovery holds with high probability once the sample size is large enough; the resulting complexity is exponential only in $k$ and otherwise mild (up to polylogarithmic factors), i.e., polynomial in $n$, which makes very small $k$ vulnerable even at large dimensions. Experiments on toy instances confirm the predicted sharp transition. Complexity comparisons with prior works indicate lower complexity on a few of their parameter sets, while identifying regimes where our method is not applicable.

Recent MPC-in-the-Head (MPCitH) signatures increasingly rely on aggressive GGM-tree optimizations to reduce signature size and cost, culminating in secret-key-root correlated GGM trees as used in SBC (Huth and Joux, CRYPTO 2024), MQOM (NIST PQC Standardization for Additional Signature Round-2, 2024), and rBN++ (Kim, Lee, and Son, EUROCRYPT 2025). While this technique yields substantial compression, it introduces a dependency loop in the proof (Kosuge and Xagawa, ePrint 2025/1999). We analyze MQOM and resolve this circularity by providing EUF-CMA security proofs for a slightly modified variant. The modifications consist of incorporating a salt into the input of a hash function and modifying the evaluation domain to ensure that all evaluation points are nonzero. For the resulting variant of MQOM, we prove EUF-CMA security for the GF(2) parameter sets in the random-oracle plus ideal-cipher model, assuming EUF-NMA security, standard one-wayness, and a heuristic conjecture on matrices. Our proof combines the H-coefficient technique with one-wayness, which may be of independent interest. We also prove EUF-CMA security in the (quantum) random-oracle model, where block-cipher-based hash functions are modeled as random oracles. The proof relies on EUF-NMA security and partial-guessing one-wayness (Feneuil and Rivain, ASIACRYPT 2026), which can be reduced classically to partial-domain one-wayness and, in the quantum setting, to a new notion introduced in this work called domain-extension one-wayness.

Registration-based Encryption ($\mathsf{RBE}$) is an emerging paradigm to remove the key escrow problem in identity-based encryption (IBE) systems. $\mathsf{RBE}$ represents a promising alternative to a public-key infrastructure, attaining the best of both worlds between IBE and traditional public-key encryption. Despite a lot of recent progress, existing constructions of $\mathsf{RBE}$ are not yet on-par with other approaches in terms of practical efficiency. To make things worse, all known concretely efficient constructions are based on bilinear pairings and are broken by quantum algorithms. In this work, we make progress on this problem. We construct a lattice-based, and therefore with plausible post-quantum security, $\mathsf{RBE}$ scheme with compact ciphertexts and fast encryption/decryption algorithms. Compared to the state-of-the-art lattice-based $\mathsf{RBE}$, our scheme reduces ciphertext size to $0.148$\,MB, down from $9$\,MB, for $1000$ users, and improves the encryption/decryption runtime by an order of magnitude. To the best of our knowledge, this is the first lattice-based $\mathsf{RBE}$ construction with ciphertexts well below one megabyte and competitive end-to-end performance, representing a significant step toward the practical adoption of $\mathsf{RBE}$.

Recent work by Houben (Asiacrypt'25) introduced a new formulation for class group actions on supersingular elliptic curves oriented by an imaginary quadratic order for an arbitrarily large discriminant. The algorithm is not only constant-time but also fully deterministic, dummy-free, and branch-free. As a result, it gives the fastest isogeny-based non-interactive key exchange (NIKE) in theory, referred to as OSIDH-LD in this paper. However, the current proof-of-concept SageMath implementation remains substantially slower than mainstream post-quantum key-exchange candidates. In this paper, we develop an efficient implementation of OSIDH-LD with several approaches. First, we provide algorithmic-level optimizations: (i) we develop the ``tail pruning'' approach such that key agreement avoids redundant orientation updates. This optimization maintains the fully deterministic and dummy-free feature of OSIDH-LD; (ii) we adapt a faster codomain isomorphism identification adapted from the technique used in the SQIsign implementations; and (iii) we present effective isogeny-computation strategies tailored to the cost profile of OSIDH-LD. Second, we adapt the parallelism technique. We apply the fork-join parallel execution model to optimize the class group action performance, and achieve near-perfect parallelism in key generation, as well as improved performance in key agreement. We provide two kinds of implementations to show the impacts of our improvements. The first one is in C with assembly language for field arithmetic, which verifies the correctness of our optimization techniques targeting OSIDH-LD. The experimental results show that our techniques lead to an overall $1.56\times$ and $1.87\times$ acceleration for key generation and key agreement, respectively. On an Intel Core i7 CPU, the resulting costs are 12.8~Gcycs (KeyGen) and 10.57~Gcycs (KeyAgree) at a conjectured CSIDH-4096 security strength. Second, we provide parallel implementations that exploit multi-threading and AVX-512 vector extensions, respectively, by batching independent subroutines in the class group action. In particular, the AVX-512 vectorized implementation is $4.97\times$ faster than the improved C+assembly implementation in key generation, which is close to the theoretical optimum.

Lightweight cryptographic primitives are widely deployed in resource-constrained environments, particularly in Internet of Things (IoT) devices. Due to their public accessibility, these devices are vulnerable to physical attacks, especially fault attacks. Recently, deep learning–based cryptanalytic techniques have demonstrated promising results; however, their application to fault attacks remains limited, particularly for stream ciphers. In this work, we investigate the feasibility of deep learning assisted differential fault attacks on three lightweight stream ciphers, namely ACORNv3, MORUSv2, and ATOM, under a relaxed fault model in which a single-bit bit-flipping fault is injected at an unknown location. We develop and train multilayer perceptron (MLP) models to identify the fault locations. Experimental results show that the trained models achieve high identification accuracies of 0.999880, 0.999231, and 0.823568 for ACORNv3, MORUSv2 and ATOM, respectively, and outperform traditional signature-based methods. For the secret recovery process, we introduce a threshold-based method to optimize the number of fault injections required to recover the secret information. The results show that the initial state of ACORN can be recovered with 21 to 34 faults, while MORUS requires 213 to 248 faults, with at most 6 bits of guessing. Both attacks reduce the attack complexity compared to existing works. For ATOM, the results show that it possesses a higher security margin, as the majority of state bits in the Nonlinear Feedback Shift Register (NFSR) can only be recovered under a precise control model. To the best of our knowledge, this work provides the first experimental results of differential fault attacks on ATOM.

The expected emergence of cryptographically relevant quantum computers (CRQCs) will represent a singular discontinuity in the history of digital security, with wide ranging impacts. This whitepaper seeks to elucidate specific implications that the capabilities of developing quantum architectures have on blockchain vulnerabilities and potential mitigation strategies. First, we provide new resource estimates for breaking the 256-bit Elliptic Curve Discrete Logarithm Problem over the secp256k1 curve, the core of modern blockchain cryptography. We demonstrate that Shor's algorithm for this problem can execute with either $\leq 1200$ logical qubits and $\leq 90$ million Toffoli gates or $\leq 1450$ logical qubits and $\leq 70$ million Toffoli gates. In the interest of responsible disclosure, we use a zero-knowledge proof to validate these results without disclosing attack vectors. On superconducting architectures with $10^{-3}$ physical error rates and planar connectivity, those circuits can execute in minutes using fewer than half a million physical qubits. We introduce a critical distinction between "fast-clock" (such as superconducting and photonic) and "slow-clock" (such as neutral atom and ion trap) architectures. Our analysis reveals that the first fast-clock CRQCs would enable "on-spend" attacks on public mempool transactions of some cryptocurrencies. We survey major cryptocurrency vulnerabilities through this lens, identifying systemic risks associated with advanced features in some blockchains such as smart contracts, Proof-of-Stake consensus, and Data Availability Sampling mechanism, as well as the enduring concern of "abandoned" assets. We argue that technical solutions would benefit from accompanying public policy and discuss various frameworks of "digital salvage" to regulate the recovery or destruction of dormant assets while preventing adversarial seizure. We also discuss implications for other digital assets and tokenization as well as challenges and successful examples of the ongoing transition to Post-Quantum Cryptography (PQC). Finally, we urge all vulnerable cryptocurrency communities to join the migration to PQC without delay.

This note describes a weak-key attack on the tweakable block cipher Blink, which was recently introduced at FSE 2026. Specifically, it is shown that two rounds of Blink admit several nonlinear invariants. To illustrate that these invariants indeed lead to attacks, we describe a partial key-recovery attack on Blink-64 with data and time complexity $2^{23}$, for a fraction of $2^{-96}$ weak keys or tweaks. There is a trade-off between the fraction of weak keys and the data complexity, e.g., with $2^{56}$ data the fraction of weak keys increases to $2^{-63}$. The attack is based on the same strategy as our attack on Midori-64 from Asiacrypt 2018.

Design-hiding (DH) schemes, such as logic locking, aim to protect circuit-design intellectual property (IP) in the integrated-circuit (IC) supply chain. While many practical DH schemes have been proposed over the past 15 years, nearly all have been broken by efficient attacks. Security and efficiency claims for these schemes have been based primarily on evaluations using benchmark circuits from legacy test-suites such as ISCAS’85 and MCNC. Recent work suggests that some circuits are fundamentally unhideable, as their functionality can be approximately learned using classical blackbox (BB) learning-theoretic (LT) algorithms. In this work, we ask: How prevalent are unhideable circuits in standard DH benchmarks? To answer this, we identify properties—such as sparse Fourier spectra—that make circuits unhideable. However, since BB Fourier-analytic algorithms are often slow and inaccurate for large-domain circuits, we shift to a whitebox (WB) setting. We develop new, efficient WB variants of Fourier-analytic algorithms that leverage WB access to a circuit and advances in model counting to efficiently evaluate whether the circuit has properties that make it unhideable. Upon applying these algorithms to standard DH benchmarks, we find that most circuits in the ISCAS'85 and MCNC test-suites are fundamentally unhideable, whereas newer benchmarks exhibit stronger resistance to Fourier-analytic algorithms and merit broader use in DH evaluation.

We consider (almost) $k$-wise independent hash functions, whose evaluations on any $k$ inputs are (almost) uniformly random, for very large values of $k$. Such hash functions need to have a large key that grows linearly with $k$. However, it may be possible to evaluate them in sub-linear time by only reading a small subset of $t \ll k$ locations during each evaluation; we call such hash functions $t$-local. Local hash functions were previously studied in several works starting with Siegel (FOCS'89, SICOMP'04). For a hash function with $n$-bit input and output size, we get the following new results: * There exist (non-constructively) perfectly $k$-wise independent $t$-local hash functions with key size $O(kn)$ and locality of $t = O(n)$ bits. An analogous prior result of Larsen et al. (ICALP '24) had a locality of $t=O(n)$ words consisting of $w= O(n)$ bits each, and hence a suboptimal $O(n^2)$ bits total. Furthermore, we show that such hash functions could be made explicit if we had explicit optimal constructions of unbalanced bipartite lossless expanders. Plugging in currently best known suboptimal explicit expanders yields correspondingly suboptimal hash functions. * Perfectly $k$-wise independent local hash functions generically yield expanders with corresponding parameters. This is true even if the locations accessed by the hash function can be chosen adaptively and shows that progress on explicit hash functions inherently requires progress on explicit expanders. * We initiate the study of $\epsilon$-almost $k$-wise independent hash functions, where any $k$ adaptive queries to the hash function are $\epsilon$-statistically indistinguishable from $k$ queries to a random function. We construct an explicit family of such hash functions with optimal key size $O(kn)$ bits, optimal locality $t = O(n)$ bits, and $\epsilon= 2^{-n}$, significantly improving over the best known parameters for explicit perfectly independent hashing. * More generally, if we consider a word model with larger word size $w$, then we get an explicit, efficient construction of $\epsilon$-almost $k$-wise independent hash functions with key size $O(kn/w)$ words, locality $t = O(n/\sqrt{w})$ words, and statistical distance $\epsilon= 2^{-n}$, which we show to be nearly optimal. Such parameters go beyond what is possible for perfect independence. We discuss applications to nearly optimal bounded-use information-theoretic cryptography.

We present a Number Theoretic Transform (NTT) hardware architecture based on the Prouhet-Thue-Morse (PTM) code, enabling NTT implementations relying only on single-port RAMs (SPRAMs), rather than using dual-port RAMs (DPRAMs) as usually done in the literature. We show that the PTM code supports a conflict-free, transactional, and streamlined pipeline across all NTT computation stages, as well as scalable parallelism through multiple butterfly units. Using this approach, we design single- and dual-butterfly NTT modules for ML-DSA that are compliant with reference software and can be packaged as a standalone AXI-Stream peripheral, allowing the forward and inverse NTT operations to be offloaded from software via DMA transfers. Experimental results show that the proposed PTM-based NTT designs achieve near one-cycle-per-butterfly and half-cycle-per-butterfly performance for the single- and dual-butterfly configurations, respectively. At the same time, it maintains FPGA resource utilization comparable to state-of-the-art compact NTT implementations relying on mixed SPRAM/DPRAM architectures or SPRAM-only designs requiring coefficient reordering.

We present AHAB, a suite of protocols for threshold Schnorr signatures in the asynchronous communication setting with guaranteed output delivery (robustness). We build on the AVSS and GoAVSS protocols of Shoup–Smart and Groth–Shoup, which allow t < n/3 static corruptions. First, we provide protocol enhancements and a full security proof in the adaptive corruption model with erasures. Second, we introduce a signature production pipeline with a player elimination framework that bounds the damage from actively misbehaving parties: if t* corrupt parties disrupt a presignature batch, the total communication overhead is at most O(t*) times the happy-path cost, and all t* parties are identified and eliminated, after which the system runs at the happy-path rate until further active misbehavior occurs. Third, we present a simplified protocol variant for t < n/4 adaptive corruptions that achieves worst-case linear communication complexity by eliminating the complaint mechanism entirely and using star-finding at the pipeline level to agree on which dealers and receivers to use. Fourth, we present a hiding variant of GoAVSS that yields an unbiased distributed key generation protocol, preventing an adaptive adversary from biasing the signing key. We also give new and more efficient star-finding algorithms, including an ILP-based optimization that should improve the yield of presignatures per batch in practice. For the main protocol (t < n/3), with t=16 and n=49, on a 1 Gbps network with commodity hardware, we estimate a throughput of 100K signatures per second; for the simplified protocol (t < n/4), with t=16 and n=65, the estimate is 160–250K signatures per second.

This paper presents fault‑injection attacks on six candidates of the Round‑2 NIST post‑quantum digital signatures call: code-based schemes CROSS and LESS, multivariate schemes MAYO, and MPC-in-the-Head schemes Mirath, RYDE, and PERK. These schemes rely on SHA‑3‑based hash functions to securely embed secret-dependent values in the signature construction. We show that a single instruction skip fault targeting the Keccak-f permutation during the sponge squeezing phase can reveal these secret values and enable full key recovery. The attacks break the one‑way property of the affected SHA‑3 implementation, as the fault allows recovering the function's input from its output. We experimentally validate the attacks on the optimised pqm4 ARM Cortex-M4 CROSS implementation via instruction-skipping using voltage glitching, and present practical countermeasures.

The advent of quantum computing poses a fundamental threat to classical cryptographic assumptions. While algorithms such as RSA and Elliptic-Curve Cryptography are secure against classical adversaries, they would be efficiently broken by a sufficiently powerful quantum adversary. Yet, despite rapid industrial and academic progress, the timeline for achieving a Cryptographically Relevant Quantum Computer (CRQC) remains uncertain and opaque. In this work, we propose a mechanism to monitor quantum capabilities through economic incentives. We introduce QCAP, a trustless distributed protocol for deploying a quantum canary address alert. QCAP enables the creation of publicly auditable cryptographic challenges whose solutions would reveal the existence of quantum computers capable of breaking the Elliptic Curve Discrete Logarithm problem. The protocol is decentralized, secure, efficient, and verifiable, featuring adjustable difficulty and native Bitcoin compatibility. A proof-of-concept implementation demonstrates the feasibility of QCAP as a Bitcoin-based early-warning system for the emergence of quantum computational power.

In this work we analyse the qualitative memory and bandwidth efficiency properties of the currently standardised post-quantum signatures as such and of their protocol integrations mainly in the X.509 context. The term “qualitative” in this respect refers to how memory and bandwidth requirements scale with the size of the signed message. Specifically, we address the question in how far the algorithms support online-computations, a.k.a streaming, with respect to the signed message in the signing and verification operations. Further, we review the possibilities for the pre-computation of a short message representative outside the cryptographic module responsible for the signing or verification operation of the different signature schemes. We also give a preview on the corresponding cryptographic API of the PKCS#11 standard which introduces numerous PQC signature algorithms in the upcoming version 3.2. We demonstrate that for specific realistic use cases, the qualitative memory and bandwidth efficiency of the PQC signature schemes in protocol use is widely varied and by tendency substantially degraded compared to the traditional signature schemes based on RSA and elliptic curves, which always allow for the pre-computation of a short message representative in the form of a hash value. Our results are relevant to PQC migrations of existing applications using traditional RSA or elliptic curve schemes.

Arithmetic correlation is a critical performance measure for pseudorandom sequences generated by feedback with carry shift registers (FCSRs), extending classical correlation by accounting for carry propagation. Chen et al. proved that for binary sequences with coprime periods, the arithmetic crosscorrelation is constant, and established bounds for Legendre sequences and $m$-sequences. In this paper, we further investigate the arithmetic crosscorrelation of sequences with coprime periods. We derive upper bounds for sequences constructed from the Legendre symbol, which generalize classical Legendre sequences, and for sequences generated by trace functions. In addition, we show that the constant property of arithmetic crosscorrelation extends to non-binary sequences with coprime periods.

Recent MPC-in-the-Head techniques enable the construction of signature schemes with compact signature sizes from various hardness assumptions. These techniques rely on commitments based on GGM trees, which have been optimized to further reduce the signature size with the so-called one-tree or correlated tree optimizations. While the one-tree technique has no incidence on the security of the scheme, this is not obvious for the correlated tree technique, and a formal security analysis of this technique has been missing in the literature. In this work, we fill this gap and provide the first formal security analysis of MPC-in-the-Head signature schemes based on correlated trees. We first exhibit a potential security flaw of this technique which rules out any hope for a security reduction to the underlying hardness assumption. In particular, we show that recovering the first $\lambda$ bits of the secret witness is sufficient to achieve a full key recovery (where $\lambda$ is the security level). The underlying assumption should hence be such that recovering these $\lambda$ bits is as hard as recovering the full witness. Some state-of-the-art schemes do not satisfy this condition, which prevents a direct application of the correlated tree technique. We then provide a formal security proof for signature schemes based on the correlated tree technique under this degraded hardness assumption. Our proof comes in several variants, in the random oracle mode or in the ideal cipher model, depending on the specific correlated tree construction. We also introduce a tweak for the instantiation of the leaf seed expansion in the ideal cipher model, which allows us to achieve a tighter security reduction. Our result shows that MPC-in-the-Head signatures based on correlated trees can achieve strong security guarantees and provides the first formal security proof for the MQOM v2 signature scheme, the on-going candidate in the NIST post-quantum standardization process with the shortest signature size in the MPC-in-the-Head family.

Given a set of $k$-sparse linear equations over a ring $R$, we give algorithms to determine whether the right-hand sides are random or have a secret assignment planted with noise. For a parameter $k/2\leq l\leq n$, we give a spectral method to solve this problem in $\widetilde{O}\left(\binom{n}{l}\lvert{R}\rvert^l\right)$ time except with probability at most $n^{-\Omega(l)}$, provided the number of samples is roughly at least $\left(\frac{\lvert{R}\rvert n}{l}\right)^{k/2}$. This attack generalizes the Kikuchi method described by Wein et. al. (Journal of the ACM 2019) for $\mathbb{Z}_2$ to (commutative) rings of any finite size. We also give a simpler algorithm with better runtime than the spectral method and better sample complexity when $\lvert{R}\rvert =\omega(n/l)$. As a consequence, we obtain new sample-time tradeoffs for the decision problem of sparse LWE, sparse LPN over higher modulus $q$, and in general the distinguishing random vs planted $\mathbb{Z}_q$-linear equations for a large class of noise distributions. Our results imply a tightness of the hardness claims of Jain, Lin, Saha (Annual International Cryptology Conference, 2024) for sparse LWE.

Verifiable election systems allow voters to verify that their secret ballots were accurately recorded and counted, while enabling anyone to verify the announced tallies. However, two practical obstacles stand between this guarantee and actual verification. First, public election records can be prohibitively large: for an election with one million ballots, deployed systems may publish more than 100GB of cryp- tographic data. Second, most existing systems protect ballot privacy through encryption, introducing key management—usually one of the most cumbersome and error-prone components of election administration. We present Haechi, a keyless verifiable election scheme for in-person voting, based on cryptographic vector commitments rather than encryption. At the core of Haechi is a new zero-knowledge proof of ballot well-formedness based on Compressed Σ-protocol theory. Our proof scheme proves the validity of an entire ballot using only a logarithmic number of group elements in the number of the ballot options. This allows all of a voter’s selections to be encoded into a single vector commitment. With this approach, Haechi reduces the data required for public verification by more than an order of magnitude compared to prior in-person verifiable election systems. Haechi thereby makes verifications for large-scale election considerably more practical. We also give a post-quantum instantiation of Haechi based on lattice commitments, which preserves the same keyless workflow at the cost of larger election records.

The Learning with Errors (LWE) problem is a hard math problem in lattice-based cryptography. In the simplest case of binary secrets, it is the subset sum problem, with error. Effective ML attacks on LWE were demonstrated in the case of binary, ternary, and small secrets, succeeding on fairly sparse secrets. The ML attacks recover secrets with up to 3 active bits in the "cruel region" (Nolte et al. 2024) on samples pre-processed with BKZ. We show that using larger training sets and repeated examples enables recovery of denser secrets. Empirically, we observe a power-law relationship between model-based attempts to recover the secrets, dataset size, and repeated examples. We introduce a stepwise regression technique to recover the "cool bits" of the secret.

DATA [22] and Microwalk [23] are two advanced dynamic binary instrumentation (DBI) tools for detecting constant-time (CT) violations in software implementations. This paper presents a comparative evaluation of these tools' findings using a common test setup and several cryptographic implementations that are included in the libraries LibTomCrypt, OpenSSL, and liboqs. Our experiments yield reliable results for symmetric ciphers. For asymmetric cryptographic schemes, however, internal random numbers cause a high number of reported findings that also differ among the tools. In order to make the tools' results more comparable our test setup is adapted to externally inject random numbers that are otherwise generated internally by the cryptographic libraries. We discuss the differences of the tools' design and their impact on practical results of cryptographic implementations as well as their resource consumption in terms of memory and runtime.

By construction, Fully Homomorphic Encryption schemes have probabilistic correctness due to their underlying cryptographic assumptions. The family of Learning With Errors (LWE) problems assumes that a random error term is added during encryption. Statistically, this error grows as homomorphic computation proceeds. While predicting the noise evolution was initially only a correctness issue, recent works have shown a direct link with the security of FHE schemes in the IND-CPA-D model. Here, we present a framework that provides practical guarantees that the probabilities extrapolated from theoretical models satisfy bounds as small as $2^{-128}$. We show how to obtain strong experimental guarantees that the usual Gaussian model for noise is conservative and that a refined model based on Irwin-Hall distribution is valid. This is realized through an algorithm called importance splitting, which we adapt here to the cryptographic setting. We provide a detailed study in the context of TFHE bootstrapping and its variants. We believe our framework can serve as a baseline to be extended to other schemes, thereby ensuring both correctness and security across all FHE schemes.

Blockchains intend to provide long-term integrity guarantees through cryptographic primitives that may become vulnerable over time due to algorithmic advances or paradigm shifts such as quantum computation. While cryptographic agility, the ability to transition between algorithms without disrupting operation, is recognized as essential, existing blockchain systems lack comprehensive support for such transitions. We address this gap by designing an Ethereum virtual machine (EVM) compatible blockchain that introduces support for cryptographic agility from genesis. We first propose a flexibility framework that characterizes how algorithm choice can be distributed across blockchain components. We then present two technical contributions aligned with this framework: (1) cryptographically agile transactions (CATX), a new transaction format that decouples body and signature to enable user-selected signature schemes; and (2) a consensus-layer key registration mechanism that allows validators to migrate between signature schemes as operational upgrades without hard forks. We exemplify the agility of our design with ECDSA, Falcon-512, and ML-DSA signatures by conducting experimental evaluations over 30,000 blocks and 11 million transactions, showing that the CATX format introduces no measurable overhead.

The bottleneck complexity of a (secure) multiparty computation protocol is one measure of its communication-efficiency. It captures how well the communication load is balanced, and is defined as the maximum communication complexity required by any one party within the protocol execution. Prior works on this topic restricted attention to protocols with fixed communication graphs, i.e. whether or not a given party communicates to another only depends on the round number. We demonstrate the power of adaptively choosing communication graphs by developing various bottleneck-efficient protocols, both with and without security. Done naÏvely, protocols with adaptive communication graphs can exploit unnatural tricks, such as "communicating with silence." To ensure our protocols are meaningful, we additionally stipulate that they should run correctly even in asynchronous networks (where we make no assumption on the adversarial message-delays other than being finite). [Bottleneck complexity of arbitrary functions.] With fixed communication graphs, Boyle, Jain, Prabhakaran, and Yu (ICALP'18) established the existence of a function $f\colon\{0,1\}^n\to\{0,1\}$ requiring $\Omega(n)$-bit bottleneck complexity, which is matched by the trivial protocol of having all parties send their inputs to one party. By adaptively choosing communication graphs, we show that any function $f\colon\{0,1\}^n\to\{0,1\}$ can be computed (securely) with bottleneck $O(n/\log n)$ (which we prove is essentially optimal), even in \emph{asynchronous} networks. [Bottleneck complexity of symmetric functions.] Prior works have demonstrated that special classes of symmetric functions, such as additive [Eriguchi, Asiacrypt'23] or abelian [Keller, Orlandi, Paskin-Cherniavsky, Ravi, ITC'23] functions can be computed bottleneck-efficiently with fixed communication graphs. We both expand the class of symmetric functions achievable with low bottleneck complexity, as well as show how input-adaptive communication graphs can be leveraged to further reduce the bottleneck complexity of some of our protocols.

The security of lattice-based cryptography relies critically on the concrete hardness of the approximate shortest vector problem (Approx-SVP). For cryptographic-sized instances, existing Approx-SVP rank reduction conditions may be overly aggressive, as they implicitly assume access to a large number of extremely short lattice vectors. In this work, we systematize and refine Approx-SVP rank reduction conditions from a feasibility perspective. We identify that, in the context of the dimension-for-free (D4f) technique, the existence of a single sufficiently short vector is the essential requirement, and we derive two refined and compact rank reduction conditions accordingly. The first condition is based on geometric properties of lattice sieving, while the second incorporates a basis-quality-dependent probabilistic bound. These results are validated through extensive experiments on high-dimensional lattices, where the compact condition outperforms prior methods by up to a factor of $60$ in dimensions $850$ and $925$. To reliably realize these conditions in high dimensions, we present APBKZ, an adaptive Pump-based lattice reduction strategy that dynamically selects the blocksize and D4f parameters according to the evolving Gram-Schmidt profile. We further introduce HeadAPBKZ, a head-focused execution mode that restricts reduction to a critical prefix once the rank reduction condition is satisfied. Combining these advances, we develop an improved concrete security estimation framework for the MSIS problem. Applied to Dilithium, our analysis indicates that, when compact rank reduction behavior is integrated with the D4f technique, the estimated concrete security of Dilithium is reduced by 3.65-6.09 bits relative to the conservative Core-SVP baseline, providing a more realistic concrete assessment. We also derive an analytic approximation whose closed-form estimates remain close to the numerical estimation, with discrepancies of only about 1.1 bits.

Heterogeneous cross-device side-channel attacks remain a critical yet underexplored challenge, as models trained on one device often fail to generalize across architectures. This paper presents PD-Net, a domain generalization framework that learns device-invariant features by disentangling algorithmic content from device-specific style and aligning feature distributions using prototypical and Maximum Mean Discrepancy (MMD) losses. PD-Net is trained on nine heterogeneous source domains spanning ARM/AVR/FPGA and power/electromagnetic leakage modalities, including 32-bit ARM Cortex-M0/M1/M3/M4, 8-bit AVR ATmega (three series), and 128-bit Xilinx Virtex-5 FPGA, and evaluated in a zero-shot setting without target-specific adaptation. Experimental results demonstrate robust zero-shot cross-architecture transfers between 8-bit and 32-bit devices, with consistent gains over existing generalization and transfer-learning approaches. In particular, PD-Net delivers 29 successful attacks with only 10 divergences across 70 settings, markedly outperforming the state of the art, which succeeds in only 4 cases and diverges 19 times. To the best of our knowledge, this is the first domain generalization (DG)-based deep learning framework to systematically demonstrate practical zero-shot heterogeneous cross-device side-channel attacks.

(Bi-Directional) Proxy Re-Encryption ($\mathsf{PRE}$) is a public-key encryption scheme that allows a proxy, holding a re-encryption key from $i$ to $j$, to transform a ciphertext intended for $i$ into one intended for $j$. $\mathsf{PRE}$ has numerous applications, including secure data sharing and cloud computing. However, most existing $\mathsf{PRE}$ schemes experience significant security degradation when adversaries are allowed to adaptively corrupt re-encryption or secret keys. Prior to this work, only a few $\mathsf{PRE}$ schemes achieved quasi-polynomial security loss in the adaptive setting, and even those were limited to restricted re-encryption strategies. In this paper, we propose four distinct $\mathsf{PRE}$ schemes with tight security guarantees in the adaptive setting, based on the $\mathsf{MDDH}$ assumption: - $\mathsf{PRE}_0$, $\mathsf{PRE}_1$: Single- and multi-challenge $\mathsf{aHRA}$-secure $\mathsf{PRE}$ schemes with tight security focusing on efficient constructions. - $\mathsf{PRE}_2$, $\mathsf{PRE}_3$: Single- and multi-challenge $\mathsf{aCCA}$-secure $\mathsf{PRE}$ schemes with (almost) tight security focusing on $\mathsf{CCA}$-type security. To achieve tightly $\mathsf{CCA}$-secure $\mathsf{PRE}$ schemes, we introduce a novel concept called tag-based language-malleable $\mathsf{NIZK}$ with special simulation soundness. This primitive provides simulation-sound $\mathsf{NIZK}$ while preserving a restricted form of malleability. We construct both one-time and unbounded versions of this primitive under the $\mathsf{MDDH}$(Matrix Decisional Diffie-Hellman) assumption.

We describe the methodology and scope of CatCrypt, a library for machine-checked cryptographic security proofs in Lean. CatCrypt provides an end-to-end pipeline from Rust reference implementations to security proofs in the computational model in Lean. The translation from Rust to Lean is done using the Hax tool. CatCrypt covers 172 cryptographic protocols and constructions with machine-checked security theorems in the computational model. Of these, 110 have the full Rust-to-Lean pipeline. All bounds have been systematically cross-referenced against their published sources (IETF RFCs, NIST standards, and academic papers). Some proofs were ported from SSProve (Rocq), EasyCrypt, ProVerif, CryptoVerif and Squirrel; most are independent formalisations with no prior machine-checked treatment. CatCrypt also includes a verified Lean implementation of a substantial part of the hax transpiler pipeline. This work is an experiment of what can be done by a researcher working with GenAI. Until recently, the formalization of one protocol required months of expert effort. In contrast, the whole of CatCrypt was developed in a period of two months. Because it was developed with AI, we develop a new methodology to increase confidence that the specifications are correct. Moreover, we will continue to audit the code in the coming months to gain even more confidence in the specification of the results. We hope this work will facilitate the adoption of formal methods in the development of security-critical software. This is especially urgent due to AI's increased hacking capabilities, the explosion of AI generated software and the ongoing post-quantum transition, which requires the development of new cryptographic protocols and their secure implementation.

Heavy-hitter detection is a fundamental primitive in stream analytics, with applications in network monitoring, telemetry, and large-scale data systems. In many practical deployments, this computation must be maintained continuously on remote infrastructure that offers higher availability and centralized operational control, even when the underlying streams contain sensitive identifiers or proprietary activity patterns. Existing privacy-preserving approaches either incur substantial statistical noise or rely on multi-server trust assumptions. Fully Homomorphic Encryption (FHE) offers an attractive alternative by enabling exact computation over encrypted data on a single untrusted server, but the high cost of encrypted comparisons has historically made stateful stream processing impractical. We present Oblivious SpaceSaving, a privacy-preserving reformulation of the classical Space-Saving algorithm for fully encrypted execution. Our central idea is the Moving Floor abstraction, which exploits a monotonicity invariant in the summary state to replace repeated magnitude comparisons with equality-based selection against a tracked encrypted floor. We further combine this with parallel victim selection and a hierarchical asynchronous ingestion pipeline, yielding an end-to-end encrypted heavy-hitter architecture that preserves the deterministic accuracy guarantees of the original algorithm. Our design reduces the cost of encrypted updates by up to $2.74\times$ over a naive oblivious baseline and sustains end-to-end encrypted ingestion throughputs of up to 4.30 items/s with sub-second amortized latency. These results show that, with the right algorithmic reformulation, classical streaming summaries can be made practically viable under fully encrypted execution, bringing privacy-preserving stream analytics significantly closer to deployment.

We introduce Confidential Transfers for Multi-Purpose Tokens (Confidential MPTs) on the XRP Ledger, a cryptographic extension of the XLS-33 token standard that enables confidential balances and hidden transfer amounts while preserving public supply verifiability. The protocol replaces plaintext per-account balances with EC–ElGamal ciphertexts and employs non-interactive zero-knowledge proofs to enforce transfer correctness, balance sufficiency, and the invariant OutstandingAmount ≤ MaxAmount without requiring decryption by validators. Confidentiality is scoped to transaction amounts and account balances; sender and receiver identities remain public, preserving XRPL’s account-based execution model. Our design maintains full compatibility with existing MPT semantics: public and confidential balances coexist, issuance rules remain unchanged, and theissuer’s designated second account is treated identically to other holders. The protocol further supports issuer-controlled operations, including freeze and clawback, without weakening supply soundness. To accommodate regulatory and institutional requirements, Confidential MPTs provide cryptographic auditability through an on-chain selective-disclosure model based on multi-ciphertext balance representations and equality proofs, while remaining compatible with simpler issuer-mediated audit models. We present a complete protocol specification, a security analysis under standard discrete-logarithm assumptions, and an open-source reference implementation (mpt-crypto) that realizes the required cryptographic primitives. Experimental evaluation demonstrates that confidential transfers can be verified within XRPL validator performance constraints, with proof sizes and verification costs suitable for production deployment.

This paper presents a security evaluation of the RRSC lightweight stream cipher in its 64-bit and 128-bit variants. The analysis examines the key update process, internal component interactions, and diffusion behavior during initialization, supported by an avalanche study. Based on these observations, several cryptanalytic scenarios are explored, including time-memory-data trade-off attacks, full key-recovery attacks in the known-plaintext setting, and partial key-recovery attacks targeting the linear feedback shift register and nonlinear feedback shift register components. It is shown that the effective key space is reduced from \(2^{128}\) to \(2^{96}\) for the 128-bit variant and from \(2^{64}\) to \(2^{48}\) for the 64-bit variant.

We explore distributed training in a setting where features are held by one party and labels are held by another. In this context, we focus on label Differential Privacy (DP), where the labels require privacy protection from the other party who learns the trained model. Previous approaches struggle to train accurate models in high-privacy settings (i.e. when $\epsilon \leq 1$), or typically require a trusted third party. To eliminate this trusted party while preserving model utility, we present PostScale, a novel Homomorphic Encryption (HE)-based protocol suited for high-privacy regimes with ciphertext multiplicative depth of two. Our protocol is suitable for a wide variety of models in the semi-honest setting and avoids leaking the model architecture as well as costly ciphertext operations like bootstrapping and rotations. We also present a multi-party sampling protocol for generating DP noise, and Hadal, a general-purpose dataflow-based framework for encrypted computation implementing our protocols. Hadal repurposes existing tools for use with HE, including comprehensive performance profiling capabilities, dual execution modes (eager and deferred), graph compiler-based optimization, and hyperparameter tuning. Our techniques achieve model utility similar to centralized DP while reducing communication by over 90% (from 1 TB to 8 GB per batch) and training time by 99% (from 54 minutes to 33 seconds) compared to related work that protects both features and labels. These improvements unlock larger models; we train Bert-tiny of Devlin et al. (2019), with 6.5 MB of parameters, in 20 ms per example in a LAN setting.

In code-based cryptography, dual attacks for solving the decoding problem have recently been improved. They are now competitive and beat information set decoders for a significant regime. These recent dual attacks, starting from Carrier et al. (Asiacrypt 2022), work by reducing decoding to an LPN problem where the secret and the noise involve parts of the error vector coming from the decoding problem. However, currently, the analysis of all these dual attacks is heuristic. In the original Asiacrypt 2022 work, a simple LPN modeling was used to carry out the analysis but Meyer-Hilfiger and Tillich (TCC 2023) showed that this assumption could not be used. Consequently, they proposed an alternative analysis based on Fourier theory and on heuristically modeling the weight enumerator of a random linear code as a Poisson variable. The analysis of the newest and most efficient dual attack, doubleRLPN, introduced by Carrier et al. (Eurocrypt 2024) also relies on this technique and on this model. Our main contribution is to devise a variant of doubleRLPN that we can fully prove without using any model. We show that our variant has the same performance, up to polynomial factors, as the original doubleRLPN algorithm. The final algorithm and its analysis are also simpler. Our technique involves flipping the coordinates of the noisy codeword and observing the fine changes in the amount of noise in the related LPN problem to reconstruct the entire error. The analysis is based on the second-order behavior of the bias of the noise which was already used in the original analysis. Secondly, the performance of our algorithm, as it was the case for doubleRLPN, heavily depends on having access to a good code along with an efficient decoder. We instantiate this code by choosing a Cartesian product of a constant (instead of sublinear in the original proposal by Carrier et al.) number of random linear codes. We use a decoder based on blockwise error enumeration that was already used by Guo et al. (Asiacrypt 2014). We show that our approach is optimal up to polynomial (instead of superpolynomial) factors.

To penetrate more rounds with Meet-in-the-Middle (MitM) attack, the neutral words are usually subject to some linear constraints, e.g., Sasaki and Aoki's initial structure technique. At CRYPTO 2021, Dong et al. found the neutral words can be nonlinearly constrained. They introduced a table-based method to precompute and store the solution space of the neutral words, which led to a huge memory complexity. In this paper, we find some nonlinearly constrained neutral words can be solved efficiently by Khovratovich et al.'s triangulation algorithm (TA). Furthermore, motivated by the structured Gaussian elimination paradigm developed by LaMacchia et al. and Bender et al., we improve the TA to deal with the case when there are still many unprocessed equations, but no variable exists in only one equation (the original TA will terminate). Then, we introduce the new MitM attack based on our improved TA, called triangulating MitM attack. As applications, the memory complexities of the single-plaintext key-recovery attacks on 4-/5-round AES-128 are significantly reduced from $2^{80}$ to the practical $2^{24}$ or from $2^{96}$ to $2^{40}$. Besides, a series of new one/two-plaintext attacks are proposed for reduced AES-192/-256 and Rijndael-EM, which are the basic primitives of NIST PQC candidate FAEST. A partial key-recovery experiment is conducted on 4-round AES-128 to verify the correctness of our technique. For AES-256-DM, the memory complexity of the 10-round preimage attack is reduced from $2^{56}$ to $2^{8}$, thus an experiment is also implemented. Without our technique, the impractical memories $2^{80}$ or $2^{56}$ of previous attacks in the precomputation phase will always prevent any kind of (partial) experimental simulations. In the full version, we extend our techniques to sponge functions.

Fully homomorphic encryption (FHE) is a cryptographic scheme that can take ciphertexts as inputs and compute a new ciphertext of a function of the underlying messages without decryption. FHE has been attracting attention along with the growing interest in privacy-preserving technologies. In terms of privacy-preserving technology, deniable encryption is also important. Deniable encryption enables a user, who may be forced to reveal the messages corresponding to the user's public ciphertexts, to lie about which messages the user encrypted. Agrawal et al. (CRYPTO 2021) introduced deniable FHE (DFHE) that combines FHE with deniable encryption, and proposed a transformation from an FHE scheme that satisfies specific special requirements, called special FHE, to a DFHE scheme. They also showed a construction of a special FHE scheme based on the BGV (Brakerski--Gentry--Vaikuntanathan) scheme. However, in the construction by Agrawal et al., one must store all the extensive randomness used for encryption in order to lie, and a bootstrapping operation, which takes a long time to execute, is a bottleneck in execution speed. In this paper, we show that by providing a tighter upper bound on deniability, we can reduce the size of the stored randomness and the required number of bootstrapping in the construction by Agrawal et al. In addition, we show that TFHE (Chillotti et al., J. Cryptol., 2020; Joye, CT-RSA 2024), which is known as a FHE scheme with fast bootstrapping, satisfies the requirements of special FHE, and thus can realize a faster DFHE scheme than the BGV-based construction.

We address the challenge of constructing a proof system capable of handling multiple computations that involve diverse types of tasks, such as scalable zkRollup applications. A central dilemma in this design is the trade-off between generality and efficiency: while arithmetic circuit-based SNARKs offer fast proofs but limited flexibility, zkVMs provide general-purpose programmability at the cost of considerable overhead for circuit translation. We observe that typical workloads for such applications can be naturally divided into two parts: (1) diverse, task and data-dependent application logic, and (2) computationally intensive cryptographic operations, e.g., hashes, that are common and repetitive. To optimize for both efficiency and adaptability, we propose Gryphes, a hybrid framework that composes matrix lookup, a generalization of lookup arguments, together with SNARK solutions tailored for cryptographic operations. At the heart of Gryphes is a novel and efficient linking protocol, enabling seamless, efficient composition of matrix lookup + Plonk with general commit-and-prove SNARKs. By integrating Gryphes with Groth16 for signatures and RSA accumulators for membership proofs, we build a zkRollup prototype that achieves efficient proving, constant-size proofs, and dynamic support for thousands of transaction types. This includes our matrix lookup implementation incorporated with Plonk, as well as practical optimizations, comprehensive benchmarks, and open-sourced code. Our results demonstrate that Gryphes strikes a very good balance between functionality and efficiency, offering highly expressive and practical zkRollup systems.

Mobile access within public finance and enterprise environments often requires lightweight anonymous authentication, allowing users to prove authorization without disclosing their identities. Group Time-based One-Time Passwords (GTOTP) has recently been proposed as a lightweight primitive meeting this need with post-quantum security. To address dynamic group membership, Cao et al. introduced DGTOne, the first dynamic GTOTP construction. It employs chameleon hashes to precompute a fixed set of Merkle-tree leaves (mount points), into which conventional TOTP verification points (VPs) contributed by group members are adaptively inserted. However, DGTOne partitions mount points by time epochs, so they can expire and become unusable, causing capacity waste due to unpredictable join times. Moreover, its outsourced proof generation requires verifiers to be online each epoch to fetch refreshed credentials from Registration Authority (RA), defeating offline verification needed in mobile access. We address these limitations with two new schemes. First, we propose NWDGT, a no-wastage DGTOTP design that constructs Merkle trees of members' verification points (VP-trees) on demand, eliminating expired mount points at the cost of added handling latency. To mitigate this latency, we introduce LWDGT, which instantiates multiple small one-time signature (OTS) trees whose leaves (OTS public keys) serve as mount points. New members' VPs are signed immediately using unused leaves, achieving low wastage. We formally prove that the wastage rate of LWDGT is, with overwhelming probability, lower than that of DGTOne. By modeling the registration process and optimizing OTS-tree size, for deployments with up to 500 members (209 initially, 20 added monthly), LWDGT reduces mount point wastage rate by 10.2% over one year compared to DGTOne.

We construct compilers to generically transform any dynamic Searchable Symmetric Encryption (DSSE) scheme that is secure against a semi-honest server into one that is secure against a malicious servers, thus yielding a Verifiable dynamic SSE (VDSSE). Our compilers achieve optimal overheads while preserving forward and backward privacy, which are the standard and widely accepted security notions for DSSE. We focus on optimizing communication overheads and client storage requirements. Our first compiler $\mathsf{FLASH}$ incurs $O(1)$ communication overhead between the client and the server, which is optimal, while incurring mild storage overhead at the client. Our second compiler $\mathsf{BOLT}$ incurs $O(1)$ storage overhead at the client while incurring mild communication overhead. Towards this, we define a new authenticated data structure called a set commitment and we provide an efficient instantiation of this primitive. We prototype implement our compilers and report on their performance over real-world databases. Our experiments validate that our compilers incur concretely low overheads on top of existing semi-honest DSSE schemes, and yield practically efficient VDSSE schemes that scale to very large databases.

We propose the first blind signature scheme that simultaneously achieves the following properties: - It uses a pairing-free group and random oracles in a black-box manner; - It provably achieves concurrent security based on standard assumptions (DDH) without the algebraic group model (AGM); - It requires only three moves. Moreover, the public key, signature, and communication of our scheme all consist of only a constant number of group/field elements. Prior to our work, black-box, three-move pairing-free schemes were only known in the AGM. A recent line of work proposed and optimized schemes without the AGM, but they all require at least four moves.

This work presents a constant-time hardware design for HQC (Hamming Quasi-Cyclic), a code-based key encapsulation mechanism selected for standardization by NIST's Post-Quantum Cryptography process. While existing hardware implementations of HQC have achieved limited performance due to area constraints, our work demonstrates that high performance can be attained with minimal hardware overhead using higher datawidth. We present a fully parameterizable, flexible data width, hardware design, configurable for both performance targets and security levels, implementing HQC key generation, encapsulation, and decapsulation in Verilog for FPGA deployment. The three operational modules share a common SHAKE256 hash core to minimize area overhead while maintaining throughput. Our design significantly outperforms existing HQC hardware implementations in terms of latency, while achieving a similar or smaller value of the area-time (AT) product compared to existing implementations. The improved performance results from the optimizations introduced in the sparse polynomial multiplier and fixed weight vector generator modules. We achieve upto 35% improvement in the AT product when compared to other most efficient unified HQC hardware designs in the literature. For our fastest configuration targeting HQC-1 (the L1 security level), key generation completes in 0.020 ms, encapsulation in 0.040 ms, and decapsulation in 0.081 ms when implemented on a Xilinx Artix 7 FPGA, showcasing a 40% improvement in latency when compared against the fastest design, while maintaining a competitive area footprint.

A recent Accordion mode has been proposed by Öztürk et al.: HCTR++ construction proposed in [OKY26, Cryptology ePrint Archive, Paper 2026/383]. I identify a fundamental correctness flaw in the design. Specifically, I demon- strate that the decryption algorithm (Algorithm 2) does not correctly invert the encryption algorithm (Algorithm 1), rendering the scheme undecryptable as specified. The authors have acknowledged the use of AI to refine the conclusion section of their paper. I have discovered this vulnerability completely independently of any AI tools. However, as an exercise, I have provided the algorithm to both ChatGPT and Claude (free versions) in retrospect, to see if they can identify the flaw, and I report my comments/observations. I wish to emphasis that the authors have made no claims or acknowledgment of using AI tools beyond drafting and refining the introduction and conclusion sections, and I make no such claims either. The purpose of this note is point out the vulnerability (mistake) in the design, and to look into how free AI models approach finding it. I would like to also point out that the authors have since updated their design, and this note only refers to the original version. I have not studied the updated design and make no claims about it. Any comments made in this note are my own and do not reflect on the opinions of any affiliations or funding agencies.

Standard hash-to-curve constructions first hash the message to a field element through a cryptographic hash-to-field step, then map this field element to an elliptic-curve point. Inside constraint systems, this inner cryptographic hash is often the dominant cost. Groth, Malvai, Miller and Zhang (Asiacrypt 2025) introduced \emph{constraint-friendly map-to-elliptic-curve-group relations} that bypass this step, achieving substantial reductions in circuit size. Their security proof works in the Elliptic Curve Generic Group Model (EC-GGM). We identify three gaps. First, the security bound in terms of the message space size $M$ and tweak bound $T$ is not explicitly analyzed, and the bounds stated for the concrete instantiations are loose. Second, the EC-GGM does not capture the algebraic structure of most deployed curves; we exhibit a concrete signature forgery using the parameters claimed secure. Third, the construction requires a congruence condition on the field that is not satisfied by all deployed curves; we extend it to any field, although witness generation remains practical only for fields of low 2-adicity. As a countermeasure we propose a $y$-increment variant that, on the $j=0$ curves used in practice, neutralizes the algebraic attack, removes the field restriction in practice, and preserves a comparable constraint count. We implement and benchmark both constructions in the open-source gnark (Go) library; the attack is additionally demonstrated via a self-contained SageMath simulation and confirmed at the circuit level against the authors' own Noir (Rust) implementation.

FROST is a pragmatic method of thresholdizing Schnorr signatures, permitting a threshold quorum of $t$ signers out of $n$ total individuals to sign for a message. This scheme improved on the state of the art, resulting in an efficient protocol that aborts in the presence of up to $t-1$ malicious users with strong resilience against chosen-message attacks, assuming the hardness of the discrete logarithm problem. In this work, we build upon the foundation introduced in FROST by presenting FROSTLASS, which additionally enjoys novel linkability criteria and anonymity guarantees under the general one-more discrete logarithm problem, utilizing a "Schnorr-shaped hole'' technique to prove desirable security results. This scheme is highly practical, tailor-made for use on-chain in the Monero cryptocurrency; indeed, we also showcase a Rust implementation for this protocol, demonstrating its real-world application to improve the security and usability of Monero.

Curve5453 and Curve6071 are Montgomery curves over the primes $2^{545}-3$ and $2^{607}-1$, providing 271- and 302-bit classical security, respectively. Their TMVP-based field multiplication in 10-limb representation costs 77 multiplications. We reduce this to 60 for Curve5453 ($22\%$ fewer) using a 9-limb radix-$2^{61}$ representation, and to 54 for Curve6071 ($30\%$ fewer) using a 12-limb radix-$2^{51}$ representation with hierarchical block-level TMVP. Choosing the limb count to produce $3 \times 3$ Toeplitz blocks aligns the structure with the size-3 TMVP formula, computing each block product in 6 multiplications rather than 9. Portable C implementations benchmarked on ARM64 and x86-64 confirm speedups of up to $16\%$ in field multiplication and $13\%$ in scalar multiplication. On ARM64, Curve5453 reaches $90.6\%$ of OpenSSL's assembly-optimized NIST P-521 ECDH throughput with 12 additional bits of classical security, and Curve6071 delivers 302-bit classical security at $80.8\%$ of P-521's throughput.

The sum-check protocol is a foundational primitive in modern cryptographic proof systems, but its prover-side cost has emerged as a concrete bottleneck. This paper introduces three complementary techniques that significantly reduce sum-check proving time and memory, especially in the context of zero-knowledge virtual machines (zkVMs). First, for applications involving products of many multilinear polynomials, we develop a new algorithm that significantly reduces the number of field multiplications required for proving. Second, we develop a "small-value sum-check prover" algorithm. This significantly speeds up the prover in the common setting where the polynomials being summed evaluate to 64 or 32-bit integers, or to elements of a small sub-field within a larger extension field. Even outside of the small-value setting, this algorithm yields a faster "streaming prover", by which we mean a small-space algorithm that applies whenever the terms being summed can be enumerated in small space (as arises, for example, in zkVM applications). Third, we nearly eliminate prover overhead in the ubiquitous case where one factor is an equality polynomial by exploiting its decomposable tensor structure. We implement these techniques in Jolt, a state-of-the-art zkVM, and evaluate their performance. In Jolt, we observe over an order of magnitude runtime speedup and memory reduction on the Spartan sub-protocol, and $1.7\times$ to $2.2\times$ speedups for a key high-degree sum-check sub-protocol in the Shout batch-evaluation argument.

We present Bulletproofs* (BP*, BulletproofsStar), a folding scheme for arithmetic circuit proofs under standard assumptions and without preprocessing, i.e., for the arithmetic circuit satisfiability language of Bulletproofs (S&P 18), following the recipe of ProtoStar (ePrint 2023/620). To this end, we first adapt the algebraic verifiers of the arithmetic circuit proof of Bulletproofs to the algebraic form required by ProtoStar, and prove that the modified protocol remains secure. Then, we design the Bulletproofs* folding scheme that is complete and knowledge-sound. Finally, we analyze the resulting verifier cost after the folding-to-IVC transformation. The result shows an asymptotic linear gain compared to repeated invocations of the monolithic Bulletproofs verifier.

We study the problem of provably-secure format-preserving authenticated encryption scheme for images, where decryption is successful even when ciphertexts undergo compression. This novel primitive offers users more control and privacy when sharing and storing images on social media and other photo-centric, compressing platforms like Facebook and Google Photos. Since compression is usually lossy, we cannot expect the decrypted image to be identical to the original. But we want the decrypted image to be visually as close to the original image as possible. There is a vast number of works on image encryption, mostly in the signal processing community, but they do not provide formal security analyses. We formally define security, covering the goals of image confidentiality and integrity. While we first treat the problem generically, we are particularly interested in the construction for the most common compression format, JPEG. We design a scheme for JPEG compression using the standard symmetric cryptographic tools and special pre- and post-processing. We formally assess the security guarantees provided by the construction, discuss how to select the parameters using empirical experiments, and study performance of our scheme in terms of computational efficiency and decryption quality. We also build a browser plug-in that helps users store and share photos privately.

DTLS-SRTP was designed to secure real-time media communication and is found in prominent audio and video call platforms, including Zoom, Teams, and Google Meet. Notably, it is part of Web Real-Time Communication (Web-RTC), a web standard enabling real-time communication in the browser. To this end, WebRTC uses multiple technologies, including HTTP, TLS, SDP, ICE, STUN, TURN, UDP, TCP, DTLS, (S)RTP, (S)RTCP, and SCTP. This amalgamation of technologies results in an overly complex system that is very challenging to audit systematically and automatically. As a result, the security of deployments of this core modern communication technology remains largely unexplored. In this work, we aim to close this gap by developing an automated MitM testing framework (DTLS-MitM-Scanner (DMS)) to test the DTLS channel of a DTLS-SRTP connection. We use our framework to study the current state of the ecosystem in a case study spanning 24 service providers across their browser and mobile applications. Our analysis puts special emphasis on the authentication mechanism in DTLS-SRTP, where we test for 19 potential vulnerabilities that could lead to authentication bypasses for both the client and server. We find that among the 33 tested media server implementations, 19 contained vulnerabilities allowing an attacker to break authentication at the DTLS layer. For 9 of the affected systems, which serve hundreds of millions of users, we could also demonstrate that they could be exploited by an attacker to retrieve media data, assuming only Man-in-the-Middle capabilities. We highlight the impact of these vulnerabilities by building a Proof-of-Concept exploit to listen to Webex video conference calls.

Updatable (public-key) encryption is a broad concept covering (public-key) encryption schemes whose keys can evolve over time to support secure key rotation and limit the impact of key compromise. The essential feature is that the encryption keys (and possibly also ciphertexts) can be updated from one epoch to the next via so called update tokens. This concept is useful in various applications, among them secure outsourced storage, secure messaging or low-latency forward-secret key-exchange protocols. The term, however, is used with varying meanings across the literature. Some works define key-updatable schemes, where only the public and secret keys evolve. Others extend this idea by also allowing ciphertexts to be updated during key evolution. Variants further differ in how evolution is triggered: in some schemes, the receiver performs key updates locally, while in others, the sender initiates the evolution by embedding update information in ciphertexts. Beyond achieving forward secrecy, many formulations also aim for post-compromise security, ensuring that once a compromised key is updated, future ciphertexts regain confidentiality under the new key. In this paper, we systematize this field with a focus on updatable public-key encryption schemes. Our aim is to first provide a taxonomy that sheds light into the currently fragmented terminology. It then compares their formal definition, syntaxes and formal security models found in the literature, clarifies their interrelations, and identifies common design patterns underlying current schemes. Beyond mapping the definitional landscape we provide a comparative analysis of existing instantiations, focusing on their properties and efficiency, and highlighting their main trade-offs. The paper concludes with open challenges outlining directions for advancing the field.

Cold boot attacks, first introduced by Halderman et al. (USENIX'08), are a class of attacks that aim at recovering cryptographic secrets stored in volatile memory after a computer is powered off, using the fact that DRAM modules retain their contents to a large extent for some time, especially at low temperatures. Cold boot attackers can recover the original contents of memory with some flipped bits, with bit flip probabilities of <10% for one-to-zero and much lower (<0.1%) for zero-to-one shown to be easily achievable. The cryptanalytic goal is then to recover full secret keys based on this noisy data. Successful key recoveries from cold boot attacks have been shown to be feasible for various symmetric and public-key schemes, including AES, RSA, and more recently some lattice-based encryption schemes with secret keys stored in the number-theoretic transform (NTT) domain. In this paper, we investigate cold boot attacks against NTRU-based signature scheme Falcon and its ancestor, the signature scheme of Ducas–Lyubashevsky–Prest (DLP). Those schemes significantly differ from other schemes previously considered for cold boot attacks, since, in particular, the memory representation of secret signing keys mostly consists of floating point values. As a result, the various relations existing between key coefficients only hold up to floating point errors, which makes key recovery more complex. Nevertheless, at the typical bit flip probabilities achievable with cold boot attacks, we manage to fully recover Falcon and DLP keys with good probability across all parameters in simulations carried out in a simple bit flip model. Furthermore, we validate our techniques using concrete cold boot experiments againt Falcon on a Raspberry Pi single board computer. Finally, we propose countermeasures with negligible computational cost that significantly reduce the memory footprint of signing keys for Falcon and DLP, and at the same time make cold boot attacks considerably harder.

We introduce vkproof, a preprocessing SNARG which enables verification of the Varuna verifying key (or that of any similar proof system based on Marlin [Chi+20]) for the R1CS compiled from a given higher-level program. It has constant proof size and affords linear verifier costs in the number of instructions of the program rather than the density of the compiled R1CS, which makes it especially appealing in contexts where complex-to-arithmetise functions (such as hashing) appear as program instructions frequently. This verifier succinctness is achieved through modular compilation of programs and the use of fingerprints to verify polynomial correctness. We augment the algebraic holographic proof (AHP) model of Marlin by allowing oracles to witness polynomials in the instance and queries to linear combinations of indexed polynomials, resulting in a primitive we refer to as extended algebraic holographic proofs (eAHP).

ML-DSA implementations face a serious risk from partial leakage of the mask vector $\boldsymbol{y}$. Recent research has shown that this threat is practical. Even highly noisy, single-bit leakage accumulated over many signatures can suffice to recover the secret key. We carefully analyze the number of signatures with bit leakage required for successful key recovery using a stochastic model, rather than relying on a concrete attack method. On the practical side, we develop new attack methods capable of recovering the key using almost the minimal number of signatures required in theory. Our attacks work for bit-error probabilities as high as 0.49 and for leakage at every bit position of index at least four or five (depending on the ML-DSA parameter set), making them more widely applicable than prior attacks, which were not reported to succeed for bit positions below six. In the most favorable scenario, leakage at bit index four keeps our attack practical for leaked bits with an error probability of 0.499, and in the absence of noise reduces the signature requirement to below 1000.

Privacy-preserving data aggregation has become a fundamental tool for large-scale analytics in AI-driven and cloud-based systems. While existing solutions provide the default privacy guarantee, i.e., input confidentiality, most assure a semi-honest adversary model and fail to simultaneously ensure user anonymity, selective disclosure, and result privacy in the multiple data customers environment. In this work, we introduce PRIVADA, a maliciously secure data aggregation solution that uses MPC in the SPDZ framework. Unlike prior data aggregation schemes using MPC with/without SPDZ, PRIVADA supports multiple data customers while preventing inference of user participation and resisting collusions in real-world data aggregation applications. Moreover, our work guarantees user privacy and result privacy, in addition to input privacy. PRIVADA outperforms the state-of-the-art solutions by providing security against participating parties, including malicious data owners, aggregators, and data customers. Our proof-of-concept implementation also supports the new privacy-preserving data aggregation by combining malicious security, being available for multiple data customers, and ensuring strong privacy guarantees in large-scale deployments. The aggregation operation on the aggregator side becomes simpler with PRIVADA, and experimental results show a 12–15 times speedup compared to the state-of-the-art. This confirms that malicious security and strong privacy guarantees can be achievable without sacrificing practicality.

Some consensus protocols, including Proof-of-Work (PoW) and Proof-of-Stake (PoS) designs of Ethereum, contain incentive misalignment because the protocol cannot technically verify whether a block producer or validator has executed (or omitted) validation of transaction correctness before producing a block or issuing an attestation. The incentive to omit validation stems from the risk of losing a fraction of the reward due to a late attestation in PoS, or the risk of missing timely block production (and thus its inclusion) in PoW. This problem is referred to as the Verifier’s Dilemma (VD), and it has been investigated in prior work in the context of PoW, as well as in hybrid PoW and PoS settings of Ethereum. In this work, we focus on Ethereum PoS, and we investigate how rational, minimally compliant validators affect long-term network decentralization due to VD and operational costs. Using evolutionary game theory and the replicator equation, we model competition among three validator phenotypes: the honest strategy, the lazy strategy, and the join pool strategy. While the honest strategy, which performs validation, requires the operational cost of expensive hardware to run a full validator node, which is currently about 20% of rewards earned, the lazy strategy, which omits validation (based on VD), enables operation of a reduced validator node at five times lower expense, which is currently about 4% of rewards earned. Moreover, the join pool strategy enables amortization of operational costs among pool members and can incorporate the lazy strategy to further reduce costs. We analyze the profits of these strategies co-occurring under varying late attestation rates and operational cost levels using our slot-level simulator. Our findings demonstrate that the lazy strategy consistently outperforms the honest strategy in earned profits. Our next experiments reveal that the join pool strategy, combined with a variant of the lazy strategy, forms an evolutionarily stable equilibrium that rapidly collapses the validator population into a single shared pool. These results suggest that Ethereum decentralization can erode through rational economic drift even in the absence of late attestations.

Identity-based Identification (IBI) schemes have gained significant popularity in the field of cryptography due to their superior efficiency and scalability. However, the increasing number of proposed IBI schemes in recent years has made it challenging to compare and evaluate them effectively. To address this issue, this survey presents a comprehensive literature review and analysis of IBI schemes that offer security under various hardness assumptions. Employing a rigorous survey methodology, we introduce the first general taxonomy of IBI schemes, allowing for a systematic classification and evaluation of these schemes based on their security assumptions. Furthermore, we assess the computational and communication costs associated with the deployment of IBI schemes, considering the various challenges and limitations involved. For each class of schemes, we calculate and compare their security, efficiency, benefits, and drawbacks. Researchers and developers are actively involved in implementing and analysing the runtime of IBI, particularly in diverse applications such as mobile and IoT devices. We present implementations and provide essential insights for guiding future advancements in this dynamic field. The survey concludes by identifying current research gaps and proposing future directions for IBI schemes, providing researchers and practitioners with an in-depth understanding of the state-of-the-art in this rapidly evolving field.

Chenu and Smith introduced the notion of $(d,\varepsilon)$-structures, pairs consisting of an elliptic curve over $\mathbb{F}_{p^2}$ and an isogeny of degree $d$ from the curve to its Galois conjugate. They also defined an ideal class group action on a set of supersingular $(d,\varepsilon)$-structures, inherited from the action on oriented supersingular elliptic curves. As cryptographic applications of this action, they outlined extensions of the CSIDH key exchange and of the Delfs-Galbraith algorithm for the supersingular isogeny problem. In particular, their extension of the Delfs-Galbraith algorithm, called the generalized Delfs-Galbraith algorithm, is expected to be more efficient than the original one by a constant factor. Therefore, it is important to find efficient methods for evaluating the ideal class group action on $(d, \varepsilon)$-structures. In this paper, we focus on the case $d=2$ and present explicit radical 3-isogenies for evaluating the action of the class of a prime ideal above 3. Our approach relies on two representations of $(2,\varepsilon)$-structures: (i) reductions of degree-2 $\mathbb{Q}$-curves and (ii) Montgomery curves. In particular, we show that any $(2,\varepsilon)$-structure can be represented as a pair of a curve coefficient (of a degree-2 $\mathbb{Q}$-curve or a Montgomery curve) and a single sign. From these representations, we derive radical 3-isogenies that efficiently implement the action of the class of a prime ideal above 3. As an application of our radical 3-isogenies, we give an explicit algorithm of the meet-in-the-middle method for finding an ideal class connecting two given $(2, \varepsilon)$-structures, which is a part of the generalized Delfs-Galbraith algorithm.

We present RoKoko, a new lattice-based succinct argument system that achieves a linear-time prover alongside polylogarithmic communication and verifier complexity. Asymptotically, our construction improves upon RoK and Roll (ASIACRYPT 2025), the first post-quantum SNARK with $\tilde{O}(\lambda)$ proof size, by a multiplicative factor of $\Theta(\log \lambda)$. Practically, our system yields proofs of roughly $200$KB, while outperforming the state-of-the-art polynomial commitment scheme Greyhound (CRYPTO 2024) with a $100\times$ faster verification time, similar prover time, and competitive proof size. Our framework natively supports (tensor-)structured relations, such as polynomial evaluation and sumcheck relations. At a high level, our construction follows the recursive split-and-fold paradigm: the prover first splits the witness into $\rho$ sub-witnesses, sends the corresponding cross-terms, and then folds them into a single witness that is shorter by a factor of $\rho$ using verifier challenges. Prior works typically restrict $\rho = O(1)$ to preserve succinct verification and maintain the optimal $\tilde{O}(\lambda)$ proof size. We overcome this “constant barrier”, which enables larger $\rho$ and thereby reduces the proof size. To achieve this, we introduce the following technical contributions. (i) Committed folding. Instead of sending $O(\rho)$ cross-terms in the clear, the prover commits to the messages and later proves that the committed vector satisfies the verification relations. This enables the use of a larger shrinking factor, thereby reducing the number of recursion rounds. While this strategy has been successfully used in LaBRADOR (CRYPTO 2023), additional care is required here to preserve succinct verification. (ii) Recursive commitments. We generalise the double-commitment technique from LaBRADOR into a framework for recursive commitments, yielding further compression in commitment size. This results in concrete improvements in communication within each recursion round. (iii) Sumcheck-driven structured recursion. We extend the sumcheck framework from SALSAA (ePrint 2025/2124) to prove substantially more complex constraints arising in our construction (and open for future extensions), including correctness of random projections, inner-product claims and well-formedness of recursive commitments. While expressing these constraints as sumcheck relations requires considerable technical effort, the resulting protocols compose seamlessly with the structured recursion, yielding both linear-time proving and succinct verification.

We construct compilers that convert any secure signature scheme into a single-round blind signature scheme. An important property of the construction is that the final blind signature has exactly the same format as the underlying signature scheme, making the blind signature scheme backwards compatible with the underlying scheme. Our compilers make use of (two-key) fully homomorphic encryption and zero-knowledge proofs to ensure unforgeability and blindness of the final scheme. We present three compilers where the main differences is which party does the bulk of the work: the client, the signer, or both. Along the way we introduce a new notion of verifiable FHE that we call committed verifiable FHE, where the verifier does not see the circuit in the clear.

The BBS+/BBS signature scheme is a key building block for anonymous credentials and privacy-preserving authentication and is currently being standardized and increasingly deployed in practice. To avoid the problem of single-point-of-failure, many threshold BBS+ protocols have been recently proposed for general $t$-out-of-$n$ settings. In practice, however, a $2$-out-of-$2$ policy between a server and a mobile device is sufficient to distribute trust while keeping the system lightweight. Yet, existing threshold designs still require at least three rounds/passes and multi-kilobyte communication in the two-party setting. In this work, we focus on the two-party setting and show that one can achieve reduced interaction while maintaining low computational and communication overhead. Specifically, we present a two-pass two-party BBS+ signing protocol that requires only 0.85KB of communication per signature, about 27% of the currently most bandwidth-efficient work (S&P'25) in the $2$-out-of-$2$ setting. It achieves competitive signing times (roughly 62ms for one party and 46ms for the other) and remains efficient even for large message vectors (e.g., $\ell = 500$), making it attractive for practical deployments. Overall, our protocol is only slower than the fastest OT-based design (S&P'23) but uses nearly two orders of magnitude less bandwidth. We provide a full simulation-based security proof in the standard real-ideal paradigm. As an extension, our protocol can be generalized to a $2$-out-of-$n$ threshold setting naturally.

Multi-signatures are a fundamental cryptographic primitive in distributed systems, enabling a set of parties to jointly produce a compact signature on a common message. Of particular interest are constructions instantiated over pairing-free cyclic groups with a two-round signing protocol, as such schemes offer improved efficiency and deployability in practice. Support for key aggregation is an additional highly desirable property, allowing multiple public keys to be combined into a single succinct aggregate public key against which aggregate signatures can be verified. To improve concrete security guarantees, several works have proposed constructions with tight security reductions. However, existing tightly secure constructions have significant limitations. Notably, T-Spoon by Bacho and Wagner (Crypto 2025) is currently the only pairing-free two-round multi-signature scheme that simultaneously achieves tight security and supports key aggregation. Despite these advantages, T-Spoon incurs substantial efficiency overhead: its signatures comprise nine field elements and two group elements, resulting in prohibitively large signature sizes for many practical applications. In this work, we introduce Earpick-MS, a tightly secure two-round multi-signature scheme over pairing-free cyclic groups that supports key aggregation while achieving compact signatures. Concretely, signatures in Earpick-MS consist of only three field elements and a single bit, thereby reducing the signature size by a factor of approximately 3.5 compared to the state-of-the-art T-Spoon construction. We further present Earpick-TS, a threshold signature variant of our scheme. Earpick-TS retains the same compact signature size and constitutes the first pairing-free two-round threshold signature scheme with a tight security proof. Prior to our work, achieving tight security in pairing-free threshold signatures required at least three rounds of interaction (Chen, PKC 2025; Bacho and Wagner, CiC 2026). Finally, we propose Earpick-muMS, an additional variant that achieves tight security in the multi-user setting while retaining the same compact signature size.