Hash-based constructions occupy a distinctive position among post-quantum signatures: their security reduces to well-tested properties of hash functions rather than to newer assumptions such as lattices or isogenies. This work focuses on stateful schemes instead of stateless, because the former are considerably more efficient. However, they have the problem of state handling, since reusing a one-time key twice enables signature forgeries. Despite threshold signatures mitigate this problem by spreading trust among a set of disjoint parties, building them from hash-based schemes is difficult, since these lack the homomorphic structure needed to recombine partial signatures, and generic multiparty computation can be expensive for hash-based constructions. Kelsey, Lang and Lucks recently proposed Haystack, the first threshold scheme for hash-based signatures producing standard LMS or XMSS signatures, at the cost of a fully trusted setup and a large common reference value. We analyze Haystack along two dimensions: performance and security. First, as Haystack lacks an implementation and realistic benchmarking, we implement the protocol in Java and produce a network-aware evaluation of its viability in real deployments, concluding that it performs comparably to other post-quantum threshold schemes. Second, we relax the trust placed in the dealer. For that, we introduce a variant of the setup built on an optimistic, lightweight MPC-based partial-DKG. It does not remove the dealer's ability to forge, but it prevents it from impersonating trustees within the signing protocol, while preserving the standard signature format. Also, an optional succinct-argument layer provides public auditability. We further consider a full-DKG setting with no dealer and where the trustees run the entire setup under MPC. Both variants are implemented in MP-SPDZ and their costs have been analyzed.

With the arrival of scalable quantum computers, classical key exchange protocols like RSA, elliptic-curve and finite-field Diffie-Hellman are vulnerable to harvest-now-decrypt-later attacks. Quantum key distribution offers information-theoretic security but is sensitive to channel noise, loss, and distance, while post-quantum cryptography provides quantum resistance on conventional hardware at the cost of larger keys and a dependence on hardware computational strength. Existing hybrid defenses generally rely on static configurations that require manual intervention when channel conditions degrade, and no prior software-defined system performs real-time three-way switching among these approaches while preserving uninterrupted key availability. This paper presents an adaptive multi-algorithm key generation and exchange framework that dynamically selects among quantum key distribution (BB84), post-quantum cryptography (Kyber512, standardized as ML-KEM-512), and classical Diffie-Hellman according to real-time monitoring of the quantum bit error rate and network latency, fusing key material from all active sources through an HMAC-based key derivation stage. The framework was implemented and evaluated in a controlled simulation environment built on Qiskit, liboqs, and the Python cryptography library. Across all five operating modes it attained a 100% key-generation success rate, with the quantum-resistant modes sustaining a secret-key throughput of approximately 3 kbps at a 256-bit key size and mode transitions completing without loss of key availability. A Kruskal-Wallis test confirmed that the timing differences among modes were statistically significant (H = 133.32, p < 0.001), and the security model was placed on a formal footing using the robust key-combiner framework. The results indicate that adaptive multi-algorithm key exchange can substantially improve the quantum resilience of secure communication systems in terms of security, availability, and performance.

The approximate Closest Vector Problem (CVP) is a core computational problem underlying many post-quantum lattice-based signature schemes, including Dilithium, one-more-ISIS, and HuFu. While the security of these schemes is typically expressed in terms of the Inhomogeneous Short Integer Solution (ISIS) problem, it is well-known that ISIS can be efficiently reduced to approximate CVP. Despite its foundational role, approximate CVP with non-negligible approximation factors remains far less explored than other lattice problems such as SVP or LWE, creating a critical gap in both theory and practice. In this work, we bridge this gap by advancing the Colattice framework for solving approximate CVP with large approximation factors. More concretely, (1) We define a practical version of the Colattice algorithm and propose a randomized Nearest Colattice for generating more than one approximate closest vector. (2) Define a formal strategy space for blockwise approximate CVP. (3) Propose a polynomial-time strategy selection algorithm and prove its correctness under standard lattice heuristics. (4) Building on this, we design an efficient security estimator for approximate CVP in both Euclidean and Infinity norms, and extend it to approximate batch-CVP attack settings. (5) By applying this estimator, we perform concrete security evaluations of Dilithium, HuFu, and one-more-ISIS. Our results reveal that almost none of the evaluated schemes withstand approximate batch-CVP attacks with $2^{32}$ queries. (6) We integrate a slicer and Colattice into G6K-CPU, leveraging the Locality-Sensitive Hashing (LSH) technqiue for nearest neighbors search (NNS). This is the first practical implementation of an NNS-accelerated slicer. Our results demonstrate the practical efficiency of approximate CVP and batch-CVP attacks, highlighting the need for more accurate security estimation. These findings underscore the practical importance of accurate approximate CVP modeling and call for a reassessment of current parameter sets in post-quantum signature schemes.

While deep learning is ubiquitous, centralized pro- cessing exposes sensitive sequential data—such as natural lan- guage—to untrusted servers, forcing an unacceptable privacy- utility trade-off. Fully Homomorphic Encryption (FHE) re- solves this by computing directly on encrypted data. However, standard neural networks ported to FHE suffer from severe latency bottlenecks, particularly because continuous non-linear activations dominate the computational budget. To overcome this, we introduce the Blind Spiking LSTM (BSLSTM), a TFHE-optimized recurrent architecture for privacy-preserving sequential inference. By co-designing the network with the cryptographic framework, we replace expen- sive continuous non-linearities with an efficient multi-threshold programmable bootstrapping paradigm. Evaluated on stan- dard NLP tasks, BSLSTM achieves an inference latency of 5.2 seconds for a 128-token sequence, significantly outperform- ing traditional homomorphic approaches while maintaining competitive accuracy. Operating at an amortized cost of 211 microseconds per bootstrapping operation, our work demon- strates the practical viability of low-latency, fully homomorphic inference for real-world applications.

In this work, we analyze the so-called Beyond UnForgeability Features (BUFF) security of the submissions to the current standardization process of additional signatures by NIST. The BUFF notions formalize security against maliciously generated keys and have various real-world use cases, where security can be guaranteed despite misuse potential on a protocol level. Consequently, NIST declared the security against the BUFF notions as desirable features. Despite NIST's interest, only $6$ out of $40$ schemes consider BUFF security at all, but none give a detailed analysis. We close this gap by analyzing the schemes based on codes, isogenies, lattices, and multivariate equations. The results vary from schemes that achieve neither notion (e.g., Wave) to schemes that achieve all notions (e.g., PROV). In particular, we dispute certain claims by SQUIRRELS and VOX regarding their BUFF security. Resulting from our analysis, we observe that two schemes (CROSS and PROV) achieve BUFF security without having the hash of public key and message as part of the signature, as BUFF transformed schemes would have. PROV essentially uses the lighter PS-3 transform by Pornin and Stern (ACNS'05). We further point out whether this transform suffices for the other schemes to achieve the BUFF notions, with both positive and negative results.

Retrieval-augmented generation (RAG) services outsource vector search over proprietary corpora, yet clients cannot verify that returned context conforms to the promised index, parameters, and snapshot. We present VERIF, the first dedicated zero-knowledge polynomial interactive oracle proof (PIOP) for complete, service-consistent IVF-Flat retrieval. VERIF proves top-$m$ centroid selection, authenticated routing, exact full-vector scoring of every routed candidate, final top-$k$ selection, and context binding. Its commitment-eliding reduction keeps query-dependent scores virtual and reduces selection claims directly to inner products over authenticated data. A unified, permutation-free top-$t$ relation with limb-decomposed range arguments handles both selection stages without sorting or score commitments. Against a matched, optimized implementation of the same retrieval relation using a general-purpose circuit-based zkSNARK (Plonky2), our prototype achieves up to an $86.5\times$ prover speedup and reduces peak memory by up to 99.1%. VERIF proves retrieval over authenticated SIFT and 768-dimensional Cohere indexes containing 32 million and 8 million vectors in 5.90 and 11.57 seconds, respectively; verification takes 0.62--1.48 seconds. These results demonstrate practical verifiable IVF-Flat retrieval for RAG-as-a-Service.

We prove two deterministic inapproximability results. First, for every fixed $0<\epsilon<1/2$, Euclidean $\mathrm{GapCVP}^{(2)}$ is NP-hard with gap factor $n^{1/2-\epsilon}$ under deterministic polynomial-time many-one reductions, where $n$ denotes the lattice rank. Consequently, the Euclidean closest vector problem is NP-hard to approximate within the same factor. This improves the previous $n^{1/400}$ hardness factor in Chapter 7 of the OpenAI report [Ope26]. Aharonov and Regev gave short certificates for both the YES and the NO case of $\operatorname{GapCVP}^{(2)}$ at gap factor $C\sqrt n$, placing that problem in $\mathrm{NP}\cap\mathrm{coNP}$ for an absolute constant $C>0$ [AR05]. An NP-hard problem lying in $\mathrm{coNP}$ would give $\mathrm{NP}=\mathrm{coNP}$, so the factor $n^{1/2-\epsilon}$ above cannot be improved to $C\sqrt n$ unless the two classes coincide. Second, for every fixed $0<\epsilon<1$, the gap versions of binary nearest codeword and binary syndrome decoding are NP-hard with factor $n^{1-\epsilon}$ under deterministic polynomial-time many-one reductions, where $n$ denotes the binary block length. Consequently, both optimization problems are NP-hard to approximate within the same factor. This improves the previous $n^{1/200}$ hardness factor in Chapter 7 of the OpenAI report [Ope26].

Gao et al. (IEEE Internet of Things Journal, 2025) proposed a medical data sharing system for digital twin environments using identity-based encryption (IBE), public-key encryption with keyword search (PEKS), and blockchain technologies. In this short note, we show that Gao et al.'s system allows unauthorized users to access other patients' medical data. We further show that the search server can obtain information about the queried keywords from the trapdoors (search queries). In addition, we analyze the procedure used to retrieve, from the blockchain, the IPFS (InterPlanetary File System) addresses storing encrypted medical data and encrypted keywords. Since these addresses are derived from labels that can be computed solely from public information and keywords, and because the keywords themselves are provided to the search server, we demonstrate that searchable encryption is unnecessary in the first place. Based on our security analysis, we argue that the proposed system requires a fundamental redesign.

Threshold ECDSA has been an active research topic in recent years, driven by its wide-ranging applications, particularly in blockchain domains. In these real-world applications, robustness is a critical requirement. It ensures that a signature is successfully generated as long as $t+1$ honest parties are present, regardless of malicious behavior from others. Existing robust constructions generally fall into two categories: those based on threshold linearly homomorphic encryption (TLHE) and those leveraging the Multiplicative-to-Additive (MtA) paradigm. The TLHE-based approach (e.g., WMC24 in NDSS'24) achieves constant sending communication per party but incurs an expensive online phase. In contrast, the MtA-based approach (e.g., TX25 in S\&P'25) is online-friendly, requiring only elliptic-curve group operations during the online phase. However, it has the drawback of requiring $O(n)$ sending communication per party when $n$ parties are involved. In this work, we propose ARES, a robust threshold ECDSA scheme designed to reduce both communication and computational overhead within the online-friendly MtA framework. To improve the communication efficiency of TX25, we propose verifiable non-interactive multiplication (VNIM), a new primitive which endows standard non-interactive multiplication with public verifiability. Simultaneously, we leverage super-invertible matrices and packed secret sharing to amortize the overall costs. Specifically, when setting the packing parameter of packed secret sharing to $\ell = 1$ (i.e., without secret packing), ARES exhibits linear communication complexity while already achieving an approximately $50\%$ improvement over TX25. When configuring $\ell = t/3$ with $t \ge 12$, ARES achieves lower communication overhead than WMC24, requiring a constant $\approx 4.5\text{ KB}$ per party. Furthermore, setting $\ell = t/2$ reduces the amortized communication cost to roughly $3\text{ KB}$ per party. On the other hand, amortizing across $\ell$ signatures incurs a trade-off by increasing the required party size by $\ell$.

Quantum indistinguishability obfuscation (qIO) aims to make a quantum circuit unintelligible while preserving its functionality. It serves as a foundational primitive for advanced applications, such as witness encryption (WE) for QMA, non-interactive zero-knowledge arguments for QMA, and attribute-based encryption for BQP. Despite its importance, constructing qIO from standard assumptions remains a major open problem. In this work, we prove that the security of WE for QMA cannot be based on any falsifiable cryptographic assumption via a restricted class of quantum black-box reductions. Because qIO for null quantum circuits implies WE for QMA, this also separates null-qIO from falsifiable assumptions. Since almost all standard cryptographic assumptions are falsifiable, our result presents a barrier to basing qIO on standard cryptographic assumptions. The reductions we rule out are restricted: the reduction must query the adversary classically, non-adaptively, at the same security parameter, and only on honestly generated ciphertexts. Moreover, our impossibility applies only to WE with classical ciphertexts, and therefore does not rule out qIO with obfuscators whose output is a quantum state. Ruling out more general reductions, as well as more general forms of WE and qIO, remains open. Our impossibility relies on the existence of a QMA-QCIP[2] gap problem, an average-case assumption postulating a QMA language that cannot be verified with two messages of classical communication.

We give the first $\mathsf{NC}^1$-computable Pseudorandom Function (PRF) constructions from well-founded (non-ad-hoc) code-based assumptions. Specifically, we give two constructions based on two different classical variants of the learning parity with noise (LPN) assumption: (1) An $\mathsf{NC}^1$-computable PRF from hardness of Sparse-LPN [Alekhnovich, FOCS~'03] (with respect to a sublinear-depth expander graph family). This PRF is also key-homomorphic. (2) An $\mathsf{NC}^1$-computable PRF from hardness of Ring-LPN [Heyse et al., FSE~'12]. Both of these assumptions have been studied for many years in cryptography and average-case complexity. Ring-LPN has been used in the context of silent preprocessing for MPC and has a stable cryptanalysis. The study of counterexamples for Sparse-LPN is an active area of research. Notably, within the range of parameters that we need, none of these assumptions is known to imply collision-resistant hashing, and the first is not known to imply public-key encryption. Prior constructions of code-based PRFs (let alone key-homomorphic) are either super-logarithmic depth, or rely on newly introduced assumptions. As a bonus, we give a similar result relying on the \emph{classical} LPN assumption, albeit with quasi-polynomial hardness: -A key-homomorphic $\mathsf{NC}^1$-computable PRF from quasi-polynomial hardness of the classical LPN [Blum et al., CRYPTO~'93]. Technically, all of our results are obtained via a refinement and substantial extension of the recent ideas of [Ding, Jain, and Komargodski, STOC~'25].

We present SALSAA, a more efficient and more versatile extension of the state-of-the-art lattice-based fully-succinct argument frameworks, ``RoK, paper, SISsors (RPS)'' and ``RoK and Roll (RnR)'' [Klooß, Lai, Nguyen, and Osadnik; ASIACRYPT'24, '25], integrating the sumcheck technique as a main component. This integration enables us to design an efficient norm-check protocol (controlling the norm during witness extraction) with a strictly linear-time prover while reducing proof sizes by 2-3$\times$ compared to the previous quasi-linear-time norm-check in RPS/RnR, eliminating a central performance bottleneck. The sumcheck integration also allows us to natively support a wider class of relations, including rank-1 constraint systems (R1CS), which are widely used to express real-world computations. To demonstrate the versatility and efficiency of our framework, we showcase three impactful applications achieved by different RoKs (Reductions of Knowledge) compositions: (i) a lattice-based succinct argument of knowledge with a linear-time prover, achieving a verifier time of $41$ ms, prover runtime of $10.61$ s, and proof size of $979$ KB for a witness of $2^{28}$ $\mathbb{Z}_q$ elements; (ii) a polynomial commitment scheme with matching performance; and (iii) the first lattice-based folding scheme natively operating on $\ell_2$-norm-bounded witnesses, achieving highly efficient verification in $2.28$ ms and producing a proof of just $73$ KB for a witness of $2^{28}$ $\mathbf{Z}_q$ elements, outperforming prior works for the family of linear relations. We provide a modular, concretely efficient Rust implementation of our framework, benchmarked over cyclotomic rings with AVX-512-accelerated NTT-based arithmetic, demonstrating the practical efficiency of our approach.

Blockchain light clients (LCs) are agents with limited computational or storage resources that cannot maintain a fully validated copy of the ledger. They rely on service providers (SPs), typically full nodes, to access data required for tasks such as constructing a transaction (Tx) or interacting with off-chain applications. We introduce Cavefish, a novel protocol for UTxO-based platforms that enables LCs to interact with the ledger and submit a transaction (Tx) with minimal trust, storage, and computation, without having to synchronize to the chain. The LC specifies a Tx (e.g., by specifying a source address rather than source UTxOs, a destination and value, and a change address), and the SP constructs it, including a payment to the SP as an additional output. The LC needs to verify Tx before signing it, but the SP cannot reveal it without fear of losing its compensation. In order to resolve this two-sided trust problem, we propose a variant of the predicate blind signature (PBS) scheme of Fuchsbauer and Wolf (Eurocrypt 2024), which enables the SP to obtain valid Schnorr signatures on Tx, but only after proving to LC that Tx satisfies the specification. Cavefish achieves a trustless interaction in which the LC fulfills their transaction goal, and the SP receives fair compensation for their effort. As transactions only need to stay private until posted, our PBS variant relaxes the unlinkability requirements of blind signatures. We implement and benchmark the Non-interactive Argument of Knowledge component of Cavefish on two major UTxO-based blockchains, using two different zero-knowledge proving systems.

Rotation-symmetric Boolean functions form an important class of cryptographically significant Boolean functions. In 2017, Su and Tang proposed in [IEEE TIT 63(7): 4658–4667, 2017] an infinite class of rotation-symmetric bent functions of every possible algebraic degree. In this paper, we present two constructions of rotation-symmetric bent functions outside the completed Maiorana--McFarland class on $n=30\cdot 7^j$ variables with $j\geq0$ and $n=70t$ variables with $t\geq1$, respectively. Each of the two constructions generates bent functions of every possible algebraic degree ranging from $3$ to $n/2$. Since the algebraic degree of an $n$-variable bent function is at most $n/2$ and every quadratic bent function belongs to the completed Maiorana--McFarland class, the interval from $3$ to $n/2$ is the full possible degree range for bent functions outside this class. To the best of our knowledge, these are the first infinite constructions of rotation-symmetric bent functions in which functions have algebraic degrees ranging from $3$ to $n/2$ while remaining entirely outside the completed Maiorana--McFarland class.

A CNOT circuit is a quantum circuit where the only type of gate appeared in the circuit is the CNOT gate. Given an n × n binary matrix which specifies the relationship between input and output, existing greedy algorithms generate corresponding CNOT circuits of n qubits, with the goal of minimizing depth of the circuits. This short paper presents two new greedy algorithms, which can be considered as generalized versions of existing greedy algorithms. The new algorithms are inspired by the algorithm presented in the Asiacrypt 2024 paper “Quantum circuits of AES with a low-depth linear layer and a new structure”. Although we have not run large-scale experiments, small-scale experiments suggest that the new algorithms are at least as powerful as existing greedy algorithms.

Recently, the notion of dynamic zk-SNARKs was introduced. A dynamic zk-SNARK augments a standard zk-SNARK with an efficient update algorithm. Given a valid source statement-witness pair $(x,w)$ together with a verifying proof $p$, and a valid target statement-witness pair $(x',w')$, the update algorithm outputs a verifying proof $p'$ for $(x',w')$. Crucially, $p'$ is not recomputed from scratch; instead, the update algorithm takes time roughly proportional to the Hamming distance between $(x,w)$ and $(x',w')$, analogous to how dynamic data structures update the result of a computation after a small change. In this paper, we initiate the study of designated-verifier dynamic zk-SNARKs: dynamic zk-SNARKs in which only a designated verifier, holding secret verification state, can be convinced by a proof. Following recent advances in designated-verifier zk-SNARKs---such as efficient post-quantum designated verifier SNARKs (CCS 2021) and designated verifier SNARKs with very small proofs (CRYPTO 2025)---we construct a designated-verifier dynamic zk-SNARK with $O(\log n)$ update time, constant proof size, and concrete efficiency. Our construction significantly outperforms Dynalog (both asymptotically and concretely), the only publicly verifiable dynamic zk-SNARK with polylogarithmic update time (Wang et al., 2024). The concrete efficiency of our construction enables, for the first time, an efficient implementation of a dynamic proof of index: Given a digest $d$ of an arbitrary set and a digest $d'$ of its sorted index (e.g., binary search tree), we produce a SNARK proof certifying the consistency of $d$ and $d'$. More importantly, this proof can be updated in sublinear time when the underlying set changes---for example, when an element is modified or inserted, potentially altering the sorted order. We demonstrate applications of designated-verifier dynamic proofs of index to verifiable dynamic database outsourcing, where a client outsources a database and later maintains verifiable indices for efficient query answering, even under arbitrary database updates.

Enhanced Privacy Identification (EPID) is one of the anonymous authentication mechanisms that found their way into the industry, being deployed in billions of chips and standardized at ISO. The linchpin of EPID lies in its decentralized revocation procedure that allows to revoke a signer by simply placing one of its signatures on a signature revocation list SRL. Each new signature must then include a proof that it has been generated with a key different from those used to produce the signatures on the SRL. This proof of non-revocation in current post-quantum schemes either relies on general-purpose NIZKs or on regular zero-knowledge proofs (ZKP) but with a witness dimension linear in the size of the SRL, which leads to large size and/or computational complexity. In this paper, we rethink the standard approach of non-revocation so as to avoid its heavy reliance on ZKP. Our construction indeed combines features from different tools (such as Falcon signatures) that are unusual in this context to pull most elements out of the ZKP, leading to significant performance improvements. Providing all these elements unconcealed creates many security challenges for our construction but we yet manage to address all of them and prove security under well-understood lattice assumptions, and in the strong model of Sanders-Traoré (CT-RSA'21) allowing malicious SRLs.

The rise of quantum computing threatens widely deployed public-key cryptosystems, driving the adoption of post-quantum cryptography (PQC) algorithms that rely heavily on modular arithmetic. Existing hardware accelerators of the PQC algorithms for resource-constrained Internet-of-Things (IoT) devices remain limited and lack integrated fault detection mechanisms. In this work, we present CMALU, a Compact, fault-tolerant Modular Arithmetic Logic Unit supporting six operations on a single reconfigurable datapath, with a 2-bit input selecting Mode-0 (un-protected baseline), Mode-1 (on-the-fly parity and invariant checking with a formal single-bit detection guarantee), and Mode-2 (extending Mode-1 along with hardware-reuse recomputation for deterministic silent data corruption (SDC) elimination without datapath duplication). Under system-level fault injection into CMALU internal registers on an NTT accelerator and an Ibex RISC-V core running ML-KEM-512, Mode-1 achieves 100% single-bit and stuck-at detection at zero latency overhead, and Mode-2 achieves 0% SDC. The synthesis results after the post-place-and-route stage on a field-programmable gate array (FPGA) and application-specific integrated circuit (ASIC) implementations with the NTT accelerator targeting 65nm CMOS and the Ibex RISC-V integration targeting Nangate45 45nm confirm CMALU's suitability for resource-constrained IoT deployment.

In this article, we first reformulate the wedge attack within a cleaner algebraic-geometric framework and then extend it to multi-homogeneous systems over fields of arbitrary characteristic. Building on these tools, we apply the resulting multi-homogeneous wedge attack to the security analysis of SNOVA.

We study the high-precision computation of $\ell_p$-Lewis weights for $p\ge4$ in the black-box exact-real full-vector leverage-score oracle model, measuring complexity by the number of adaptive oracle rounds. In this model, Gribling, Sidford, and Zhang [GSZ26] obtained an $O(p^2\log(m/\epsilon))$ bound for computing an $\epsilon$-estimate. We improve this bound to $O(p\log(mp)+\sqrt p\log(1/\epsilon))$. To obtain this result, we isolate the normalized fourth-moment operator governing the nonlinear Hessian of their log-determinant matrix potential and prove that each relative-gradient step with denominator $p$ resets the operator norm to a universal constant. This reset controls the entire update segment and yields an $O(p\log(mp))$ global entrance phase. After entering an $O(1/p)$ spectral neighborhood of the optimum, we switch to a restarted accelerated Bregman-gradient method for the vector potential.

To enhance the security of stealth addresses and protect user privacy, Liu et al. (EuroS&P 2019) proposed a Key-Insulated and Privacy-Preserving Signature Scheme with Publicly Derived Public Keys (PDPKS). In this scheme, the payee generates a master public/secret key pair, and the payer derives a public key from the payee's master public key and binds the cryptocurrency asset to the resulting derived public key. The payee then verifies, using the master secret key, whether the derived public key has been correctly generated from the master public key. In this paper, we show that a public-key encryption (PKE) scheme secure against chosen-ciphertext attacks (CCA) can be generically constructed from PDPKS. Specifically, we utilize unlinkability, which hides the master public key from which a derived public key originates, to conceal plaintext information from ciphertexts. We also simulate the decryption oracle by leveraging the derived public key checking algorithm. In addition, to guarantee the correctness of the proposed PKE scheme, we rely on the consistency of PDPKS introduced by Emura (IACR CiC 2025). Given the motivation behind PDPKS, namely the construction of stealth addresses in a provably secure manner, unlinkability is regarded as the core security property of PDPKS. Our result shows that achieving this core security property essentially requires CCA-secure PKE, or cryptographic primitives of equivalent strength, and that such primitives are indispensable for constructing PDPKS.

In any secret sharing scheme, the size of each share must be at least as large as the size of the secret. Schemes that attain this lower bound are called $k$-ideal, where $k$ is the size of the domain of the secrets and shares, or simply ideal if they are $k$-ideal for some $k$. An access structure is called $k$-ideal if it admits a $k$-ideal secret sharing scheme. The characterization of ideal access structures is a longstanding open problem at the intersection of cryptography, matroid theory, and information theory, previously solved only for $k=2$ and $k=3$. In this work, we solve this problem for $k=4$ and $k=6$. Our results exploit the connections between ideal secret sharing schemes and matroids and new techniques based on latin squares. For $k=4$, we show that an access structure is $4$-ideal if and only if it admits a $\mathbb{F}_4$-linear ideal secret sharing scheme, i.e., a scheme where the shares and the secret are elements of $\mathbb{F}_4$ and the sharing and reconstruction functions are linear. To prove this result, we show that the class of matroids determined by ideal $\mathbb{F}_4$-linear schemes coincides with those determined by $4$-ideal schemes. For $k=6$, we prove that an access structure admits a $6$-ideal scheme if and only if it admits a $k$-ideal scheme for every $k\geq 2$. This result shows that domains of size $k=6$ are the most restrictive domains for constructing ideal secret sharing schemes, and that $6$-ideal schemes can be essentially built by combining ideal $\mathbb{F}_2$-linear schemes with ideal $\mathbb{F}_3$-linear schemes via the Chinese Remainder Theorem. Beyond these characterizations, our main technical contributions are the introduction of new techniques for analyzing ideal secret sharing schemes, extending the connections between ideal threshold schemes and latin squares to the general case, and the classification of the values of $k$ for which some relevant matroids are $k$-entropic.

Motivated by applications to efficient secure computation, we consider the following problem of encrypted matrix–vector product (EMVP). Let $\mathbb F$ be a finite field. In an offline phase, a client uploads an encryption of a matrix $M \in \mathbb F^{m\times \ell}$ to a server, keeping only a short secret key. The server stores the encrypted matrix \(\hat{M}\). In the online phase, the client may repeatedly send encryptions \(\hat{ q}_i\) of query vectors \(q_i \in \mathbb F^\ell\), which enables the client and the server to locally compute compact shares of the matrix–vector product \(Mq_i\). The server learns nothing about \(M\) or \(q_i\). The shared output can either be revealed to the client or processed by another protocol. We present efficient EMVP protocols based on variants of the learning parity with noise (LPN) assumption and the related learning subspace with noise (LSN) assumption. Our EMVP protocols are field-agnostic in the sense that the parties only perform arithmetic operations over \(\mathbb F\), and are close to optimal with respect to both communication and computation. In fact, for sufficiently large \(\ell\) (typically a few hundreds), the online computation and communication costs of our LSN-based EMVP can be \emph{less than twice} the costs of computing \(Mq_i\) in the clear. Combined with suitable secure post-processing protocols on the secret-shared output, our EMVP protocols are useful for a variety of secure computation tasks, including encrypted fuzzy search and secure ML. Our technical approach builds on recent techniques for private information retrieval in the secret-key setting. The core idea is to encode the matrix \(M\) and the queries \(q_i\) using a pair of secret dual linear codes, while defeating algebraic attacks by adding noise.

Deep Neural Networks (DNNs) have attracted significant attention, and their internal models are regarded as valuable intellectual assets. Extracting a model via oracle access to a DNN is conceptually similar to extracting a secret key via oracle access to a block cipher. Consequently, cryptanalytic techniques, particularly differential-like attacks, have been actively explored recently. ReLU-based DNNs are the most common architectures. While early works (e.g., Crypto 2020, Eurocrypt 2024) assume access to exact output logits, more recent works (e.g., Asiacrypt 2024, Eurocrypt 2025) focus on the hard-label setting, where the attacker observes only the final classification result (e.g., "dog" or "car"). Notably, Carlini et al. (Eurocrypt 2025) demonstrated that model extraction is feasible in polynomial time even under this restricted setting. In this paper, we show that a key assumption of their attack becomes increasingly unrealistic as the target depth grows. While prior works have noted neurons whose activation states rarely change, we analyze their concrete impact on hard-label extraction: even a single neuron that is (almost) always active can prevent the attack from proceeding unless its parameters are recovered, and ignoring it inevitably incurs a non-negligible error. A straightforward solution is to recover these parameters from a state switch, but observing such a switch becomes exponentially harder as the depth increases, implying that hard-label extraction is not always polynomial time. To address this limitation, we propose cross-layer extraction. Rather than extracting the secret parameters (e.g., weights and biases) directly, we exploit cross-layer interactions to recover them from deeper layers, reducing query complexity and addressing limitations of existing model extraction approaches. The source code is available at https://github.com/ECSIS-lab/hard-label-cross-layer-extraction.

NTRU is one of the most extensively studied lattice-based cryptographic schemes and is widely regarded as a strong candidate for post-quantum security. The most effective attacks on NTRU are lattice-based or lattice-related, which naturally guide the choice of parameters to achieve the desired security levels. In 1997, Hoffstein and Silverman proposed a variant of NTRU based on a noncommutative algebraic structure, claiming that it would mitigate lattice attacks. However, their scheme was later shown to be vulnerable to an algebraic attack by Coppersmith. Although several subsequent attempts have been made in the literature to develop noncommutative variants of NTRU, most of these designs have either been shown to be vulnerable to algebraic attacks or have failed to directly address lattice-based attacks. In this work, we revisit the problem of constructing a noncommutative analog of NTRU that offers stronger resistance against direct lattice attacks. Firstly, we conceptualize the problem by introducing an almost unstructured variant, and then refine this idea towards a more compact instantiation by introducing a semi-structured variant. Our proposal may be viewed as a follow-up to the early noncommutative construction of Hoffstein and Silverman. We further discuss the requirements towards having a fully structured construction in this paradigm.

This work presents a private instant messaging protocol that leverages the public log layer of blockchains as the message transport layer, while the cryptographic state is kept only by client applications. Thanks to the properties of public ledgers, this approach achieves strong censorship resistance, while also revealing the economic and cryptographic limits of on-chain messaging. Notably, given the transparency of public ledgers, and since reading and writing operations are in most cases outsourced to third-party providers that may be curious, a well-known concern is direct metadata leakage. We address this both at first contact and during the conversation: for first contact, we propose two alternative discovery mechanisms, one based on long-term key encapsulation with trial decryption, the other on a private signaling service backed by trusted hardware. For the ongoing conversation, we show that topic rotation, driven by the off-chain cryptographic state, suffices to prevent topic and conversation linkability. As our main contribution, we provide an in-depth analysis of Verbeth's metadata leakage under different adversarial assumptions for both phases.

Poseidon/Poseidon2 and Neptune are prominent primitives for zero-knowledge proof systems. Their arithmetic circuit cost is reduced mainly through partial S-box layers and low-degree finite field operations. Algebraic attacks are therefore a central part of their security analysis, and Gr\"obner basis methods are a main tool for studying such attacks. For such attacks, controlling the algebraic degree of the polynomial systems induced by partial rounds is a central issue. Previous work has shown that linear subspace trails can reduce the algebraic degree of partial rounds in constrained-input-constrained-output (CICO) problems. Therefore, subspace analysis has become an important tool for evaluating the algebraic security of Poseidon-like permutations. The main contribution of this paper is to extend the existing linear subspace trail framework to nonlinear subspaces. More precisely, we first introduce a parametric Macaulay matrix method. This method transforms the search for algebraic constraints that reduce degree growth into the problem of solving a parametric system. It provides a general algebraic approach for constructing longer nonlinear subspace trails that suppress degree growth over more internal partial rounds. Second, for the CICO problem with $Ec$ extra constraints, we give a concrete constraint pattern that extends a linear subspace trail into a nonlinear one. In this nonlinear construction, the first $Ec$ subspace constraints generate an ideal, and further compatible subspace constraints can be added along the chain without enlarging this ideal. As a result, the nonlinear subspace trail can cover up to $2Ec$ internal rounds, whereas the previous linear subspace trail can cover up to $Ec$ rounds. We further show that the balancing matrix required by this construction is generically nonsingular. Furthermore, we propose subspace modeling variants without variable substitution. These variants impose linear or nonlinear constraints directly on high-degree intermediate states. For the Poseidon/Poseidon2 and Neptune instances proposed by Grassi et al. in ToSC 2025, our experiments show that, under the same complexity bound and the same Gr\"obner basis cost model, the nonlinear subspace model can analyze approximately twice as many internal partial rounds as the linear subspace model considered in ToSC 2025. For several concrete instances, our method reaches or even exceeds the recommended number of internal rounds given by the designers in sponge mode or compression mode.

Membership inference attacks expose whether individual records were used to train a model, yet existing attacks on diffusion models are largely heuristic and can require substantial query budgets. We introduce $\textbf{DIME}$ ($\textbf{D}$enoiser $\textbf{I}$deal $\textbf{M}$embership $\textbf{E}$rror), a theoretically grounded and query-efficient framework for membership inference on diffusion models. Our starting point is an exact characterization of the optimal diffusion denoiser for a finite training set, which reveals that membership leakage is governed by the denoiser's implicit reconstruction error. This error decomposes into two complementary signals: a $\textit{bias term}$, capturing reconstruction accuracy, and a previously unexplored $\textit{local crowding term}$, capturing the geometry of nearby training examples. Both admit efficient estimators using only model queries, yielding a practical attack with as few as two queries. Across CIFAR-10/100, STL10-U, CelebA, and ImageNet, $\textbf{DIME}$ consistently outperforms prior attacks at comparable or substantially lower query cost, improving TPR at 1% FPR by up to $3\times$; remarkably, its two-query variant can outperform existing 30-query baselines. Finally, we suggest, discuss, and evaluate specific defenses to counteract such powerful membership tests.

Post-quantum deployments need signatures that are both fast and small. ML-DSA gives a practical Fiat-Shamir lattice-signature baseline, but its signatures remain large enough to make bandwidth, certificate size, and signed-log storage first-order costs. Gaertner's iterative rejection sampling construction (CRYPTO'25) shows that this design family can be made much more compact. The open question is whether this theoretical design can be turned into a concrete, implementation-oriented signature scheme, where the parameters, algorithms, encodings, and optimized software work together without giving up the promised compactness. We present Lithium, a compact Fiat-Shamir lattice signature that makes iterative rejection sampling practical. Lithium co-designs its parameters, discrete Gaussian sampler, ApproxExp evaluation, iterative rejection sampling, and rANS encoder so that compact signatures do not come at the cost of an impractical signer. For the core components, we introduce algorithmic and vectorized optimizations and provide a portable reference implementation together with vectorized AVX2 and AVX-512 implementations. Lithium-120 targets a security level close to ML-DSA-44. Our experiments show that our fastest implementation signs faster than ML-DSA-44, at 166k versus 191k cycles, while producing signatures about half as large: 1,187 bytes versus 2,420 bytes. Compared with HAETAE-120, Lithium-120 is more compact and signs about 7.5x faster.

In the Internet of Vehicles (IoV), content-centric data sharing is essential for driving safety and user experience. However, the highly dynamic and distributed IoV network raises challenges such as unauthorized data access and inefficient information dissemination. Although existing proxy re-encryption (PRE) schemes with revocation partially mitigate these concerns, they still have key shortcomings: (i) computational costs that grow linearly with the number of attributes; (ii) heavy cloud-side overhead from re-encryption and outsourced decryption, causing delays or decryption failures; and (iii) revocation mechanisms that are inefficient or insufficiently responsive in handling malicious users. Recent studies have addressed these issues, but many schemes still struggle to ensure reliable message recovery in dynamic IoV scenarios. To overcome these limitations, we propose HRFPRE, an efficient proxy re-encryption mechanism based on multi-RSU outsourcing and hardware-assisted revocation. Our scheme provides constant-size public parameters and lightweight user-side decryption over asymmetric pairing-friendly groups, while supporting an unbounded attribute space. Re-encryption requires only four pairing operations and supports a novel "encrypt-then-offline hosting" model for vehicles. Simultaneously, Roadside Units (RSUs) provide outsourced re-encryption, key generation assistance, and decryption services to resource-constrained onboard units, effectively shifting computational load away from the cloud. By integrating a key-decoupled Trusted Execution Environment (TEE), HRFPRE enables immediate revocation and keeps plaintext recovery dependent on the user-held key even under TEE-side side-channel leakage. Under the Decisional Linear (DLIN) assumption, HRFPRE achieves adaptive security while resisting replay and collusion attacks. Theoretical analysis and experiments show that HRFPRE reduces computational and communication overhead, making it suitable for secure data exchange in dynamic IoV environments.

With the increasing deployment of resource-constrained devices in daily life, ultra-lightweight ciphers become a necessity to tackle the security and privacy concerns in resource-constrained devices. In 2023, G\"{u}l and Kara studied the question of how to design a secure ultra-lightweight stream cipher with a small internal state, and introduced a new small-state stream cipher called DIZY. The cipher utilizes Truncated Pseudorandom Permutations (TPP) and has a provable security in the indistinguishability model. It consists of two versions, called DIZY-128 with a 128-bit key and DIZY-80 with an 80-bit key, respectively. In this paper, effective key recovery attacks on DIZY-80 and DIZY-128 are proposed. Both attacks leverage the weakness of DIZY that the attacker can easily reach a weak state in the middle of the initialization using chosen IVs. Based on constructing Hellman tables, the key recovery attacks on DIZY-80 and DIZY-128 are further improved. The cryptanalytic results show that DIZY-80/DIZY-128 can only provide a 65/86-bit security level against the key recovery attack, while it is claimed to provide an 80/112-bit security level by the designers. Finally, an improved variant of DIZY, called DIZYa, is proposed. The analysis on DIZYa shows that the improved variant can provide better security resistance against all known attacks including our attacks on DIZY, while maintaining the commendable characteristics of DIZY. This makes DIZYa a more suitable small-state stream cipher choice for resource-constrained devices like RFID tags.

Single decryptor encryption (SDE) is public key encryption (PKE) where the decryption key is an unclonable quantum state. Coladangelo, Liu, Liu, and Zhandry (CRYPTO 2021) realized the first SDE assuming subexponentially secure indistinguishability obfuscation (iO) and one-way functions (OWFs), along with the polynomial hardness of the learning with errors (LWE) assumption. Since then, SDE has played a pivotal role in recent advances in quantum cryptography. However, despite its central importance in unclonable cryptography, many fundamental questions about SDE remain unanswered. For example, a line of works has proposed various security notions for SDE, but their relationships have hardly been discussed. Moreover, while many subsequent works have adopted the construction methodology of Coladangelo et al., none have explored its improvement, leaving the possibility of a more efficient approach to SDE. In this work, we address these fundamental questions concerning SDE. Our contributions are threefold. New security notion: We introduce a strengthened indistinguishability-based security notion for SDE, which we call CPA+ anti-piracy security. We show that CPA+ security unifies the existing security notions for SDE, as detailed in the third item. New construction: We present an SDE scheme that satisfies CPA+ anti-piracy security, based solely on polynomially secure iO and OWFs. In addition to relying on weaker and more general assumptions, our SDE scheme offers a significant advantage over the scheme of Coladangelo et al., as both the construction and its security proof are much simpler. Relationships among security notions: We demonstrate that CPA+ anti-piracy security implies all existing security notions for SDE, with the sole exception of identical challenge ciphertext security proposed by Georgiou and Zhandry (EPRINT 2020). Although we do not establish a direct implication from CPA+ anti-piracy security to identical challenge ciphertext security, we provide a generic transformation from an SDE scheme satisfying the former to one achieving the latter in the quantum random oracle model. Additionally, we establish various relationships among different security notions for SDE. By combining these results with our SDE construction, we derive several new feasibility results. We further show that our CPA+ anti-piracy security enjoys additional robustness properties. In particular, it is preserved under parallel composition, yielding a way to expand the message space of SDE while maintaining security. We also show that it is robust to arbitrary correlations between the challenge bits for the second-stage adversaries. To capture this setting, we introduce correlated-challenge-bits CPA anti-piracy security, parameterized by an arbitrary joint distribution on the challenge bits, and show that CPA+ anti-piracy security implies this notion.

Indistinguishability obfuscation (iO) combined with one-way functions (OWFs) serves as a powerful foundation for constructing a vast array of cryptographic primitives. However, this combination faces a known black-box barrier established by Asharov and Segev (FOCS '15), which proves the impossibility of constructing collision-resistant hash (CRH) functions. The Asharov-Segev barrier naturally extends to stronger primitives that imply CRH, such as fully homomorphic encryption (FHE) and somewhere-extractable non-interactive batch arguments (seBARGs). This work investigates the power of iO and rerandomizable primitives in constructing such "CRH-hard" primitives. First, we demonstrate the first direct and simple approach to building CRH from iO and rerandomizable OWFs. The only previously known construction was due to Arnon, Ben-David and Yogev (CRYPTO '25), and needed to go through the construction of the adaptively sound SNARG of Waters and Wu (STOC 24'). Using the same approach, we additionally construct a strictly stronger primitive than CRH, which we call perfectly partitionable hash (PPH), from iO and rerandomizable commitments. Second, we demonstrate the power of rerandomizability for building advanced non-interactive proof systems. Using iO and rerandomizable commitments, we provide a construction of seBARGs with statistical extraction, a security property not achieved by most existing seBARG schemes. By additionally relying on rate-1 fully-homomorphic encryption, we construct the first rate-1 seBARG with statistical extraction. Along the way, we introduce a SNARG that is "sometimes statistically sound", and construct it from iO and rerandomizable commitments.

Univariate-polynomial interactive oracle proofs (IOPs) over binary extension fields $\mathbb{F}_{2^m}$ underpin a class of plausibly post-quantum zkSNARKs, but rely heavily on polynomial arithmetic, where large-domain evaluation and division by subspace vanishing polynomials are the dominant prover costs. General-basis additive FFTs, such as Gao--Mateer and Lin-Chung-Han (LCH), accelerate the evaluation but impose a basis-conversion stage costing $O(n (\log n)^2)$ field additions and $O(n \log n)$ field multiplications that dominates in practice. To eliminate basis conversion entirely, we introduce a divide-and-conquer algorithm for polynomial division by vanishing polynomials that operates directly in the LCH polynomial basis, for arbitrary $\mathbb{F}_2$-basis elements, achieving optimal $O(n \log n)$ complexity. In the LCH polynomial basis, multiplying a vanishing polynomial by the random blinding polynomial reduces to appending random field elements, eliminating the multiplication entirely. We integrate native LCH-basis arithmetic and auxiliary optimizations across all phases of the Aurora IOP. Benchmarks on Preon (a NIST PQC Round-1 signature scheme candidate built on Aurora) show end-to-end signing speedups of $5.0\times$ for Preon-128A and $5.8\times$ for Preon-256C, with the polynomial transform alone $12.6$--$17.9\times$ faster.

Degree-sum-freedom is a local criterion for division-property propagation from affine input spaces. Immediately after defining this criterion, the published chapter asserts invariance under extended-affine (EA) equivalence. We show that this assertion does not hold beyond ordinary sum-freedom and quantify the resulting variation. First, the natural Gold APN pair $x^3$ and $x^3+x$ has exact proper-flat values 3 and 2 on an infinite sequence of dimensions. We then study a known complete-mapping family of EA-equivalent, differentially 4-uniform permutations $F_b,G_b$ on $2r$ bits. For every odd $r$ and every $1\le c\le\lfloor(r-3)/2\rfloor$, we determine their exact codimension-$c$ profiles: $\mu_c(F_b)=2c$ and $\mu_c(G_b)=r+c-1$, equivalently $\tau_{2r-c}(F_b)=2r-2c$ and $\tau_{2r-c}(G_b)=r-c+1$. Thus the gap is $r-c-1\ge(r+1)/2$ simultaneously over a linear-size range of proper affine codimensions. The mate upper bound follows by specializing known generalized-degree duality with the exact source profile established here. The matching uniform lower bound is family-specific: after an associated-graded reduction, odd codimensions are detected by one classical consecutive Moore determinant, whereas even codimensions require a jointly nonvanishing family of replacement minors. A cyclic carry classification proves that the selected coefficients are complete reduced coefficients. These results concern local affine-input division-property behavior; they do not yield a multiround distinguisher or an attack on a concrete cipher.

Additive Randomized Encodings (AREs) provide a lightweight route to non-interactive secure computation: each party locally produces a randomized encoding of its input, and an evaluator learns only the function value from the sum of these encodings. Prior frameworks for constructing AREs for general functions ultimately hinge on an efficient ARE for string oblivious transfer (SOT), making SOT the core efficiency bottleneck. We revisit this final step and present improved ARE constructions for SOT. First, we streamline the recent PKE-based approach by directly constructing the required one-sided ARE (OSARE) for SOT. This yields a perfectly correct, statistically one-sided secure OSARE for SOT of size $\mathcal{O}(\lambda)$, improving the intermediate overhead and, consequently, the overall size of the resulting PKE-based ARE. Second, we give a pairing-free ARE for SOT under the Squaring DDH assumption. Our construction is compatible with Halevi et al.'s efficient equality-to-SOT methodology: we build an ARE for Rabin-OT that embeds a message in the equality-checking procedure and then transform it to SOT while incurring only constant-factor communication overhead and no additional correctness error. The resulting ARE for SOT has size $\mathcal{O}(\lambda)$ and negligible correctness error.

Model extraction attacks aim to recover the internal parameters of neural networks through black-box queries. While significant progress has been achieved for fully connected ReLU networks, far less is known about structured architectures such as Convolutional Neural Networks (CNNs), which are widely used in practice. In particular, convolutional layers introduce locality and weight sharing, while max-pooling operations leak only relative activation information, both of which require rethinking and extending existing extraction techniques. In this work, we study the extraction of CNNs combining ReLU activations and max-pooling layers in the soft-label setting. We first demonstrate that max-pooling can be understood as a natural extension of the ReLU non-linear operation, where the attacker only has access to relative information between neurons. The local structure of convolution allows us to overcome this difficulty and reconstruct the underlying convolutional kernel. We also introduce optimizations that take advantage of the specific structure of CNNs: by using receptive-field analysis, we design efficient methods to filter noise and localize critical points. These improvements significantly reduce the computational cost compared to a naive reduction to a large sparse fully connected network. Finally, we validate our methodology experimentally on a compact VGG-style convolutional neural network trained on CIFAR-10. The results demonstrate successful layer-by-layer extraction in practice, accurate localization of critical points, and significant efficiency gains from receptive-field-based localization.

We present Thunderbolt, an off-chain protocol that transfers Bitcoin UTXO ownership with seconds-scale latency, requires no channel graph, no routing, and no liquidity rebalancing, and lets the recipient be offline at the time of transfer. A single UTXO is locked once on-chain under a fixed public key jointly held by the current owner and a threshold committee; ownership then passes through an unbounded sequence of holders; each transfer is a purely off-chain, asynchronous operation whose on-chain cost is zero. The chain sees exactly two transactions regardless of how many transfers occur. The core invariant is an algebraic cancellation: at each transfer the recipient's fresh secret is added to the holder's share and subtracted from the committee's share, so both shares rotate while the on-chain key stays fixed. To enforce this, the recipient publishes an invoice to a shared append-only ledger (the Thunderbolt Ledger): a public commitment, an encrypted copy for himself, and an encrypted copy for the committee, together with a zero-knowledge proof that all three encode the same fresh secret. The sender fetches the invoice, verifies the proof, homomorphically folds her secret into the recipient's ciphertext to produce a new ownership credential, and publishes the result with a second zero-knowledge proof. Both proofs use a single Sigma-protocol response to force the same witness across elliptic-curve and Paillier verification equations, requiring no trusted setup. The committee operates under a standard $(t,n)$-threshold honest-majority assumption: at most $t{-}1$ of $n$ members may be corrupted. The recipient decrypts at any later time; the committee subtracts the fresh secret from its share. By binding each transfer to a distinct fresh secret and context identifier, multiple UTXOs can be transferred independently in parallel. On our benchmark machine, a complete off-chain transfer finishes in 1022ms with a combined proof size of 3.8KB. General-purpose SNARK (Succinct Non-interactive Argument of Knowledge) backends are orders of magnitude slower on the same relations: even a reduced-parameter instantiation already exceeds our native proving time by two orders of magnitude, and a faithful realization at the deployed 3072-bit Paillier modulus exceeds the memory budget of consumer hardware.

The classic function-inversion problem considers the task of constructing a data structure which, given access to a constant-time oracle for a function $f : [N] \rightarrow [N]$, supports efficient inverse-queries on $f$. This problem has been studied extensively in the small-space/large-time regime, where one wishes to use space $S$, say, $N^{1 - \Omega(1)}$ bits, and where the query time is intended to be a small polynomial of $N$. Much less attention has been given to the \emph{small-time/large-space} regime, where $S = (N \log N) / t$ for some relatively small $t$, and where the goal is to achieve a good space bound as a function of $t$. In this paper, we give an optimal solution in the small-time regime, achieving space $S = O(N \log N / t)$ and time $O(t)$ for any $t \le O(\log N / \log \log N)$. This matches a lower bound by Yao (and is the first parameter regime where the lower bound has been matched for general functions). Additionally, we extend our solution to support point-updates to $f$, also in $O(t)$ time. Our techniques for supporting point updates also extend to the classic function-inversion solution of Fiat and Naor. All of our results are motivated by the data-structural perspective on function inversion, in which the goal is to supplement an already-existing data structure $\mathcal{D}_1$ (which, as part of its functionality, encodes some function $f$) with a small secondary data structure $\mathcal{D}_2$ that supports inverse queries. Our results allow $\mathcal{D}_2$ to be implemented in $(N \log N)/t$ bits with $O(t)$ query (and update) times -- if $\mathcal{D}_1$ is itself $\Theta(N \log N)$ bits, this results in the overall space usage increasing by only a $(1 + O(1/t))$ factor. As a sample application of our results, we show how to construct dynamic unordered graphs that use space $(1 + \epsilon)$-close to information-theoretically optimal while offering adjacency queries, neighborhood queries, and edge insertions/deletions in amortized time $O(\epsilon^{-1})$.

Linkable Ring Signatures (LRS) allow anonymous signing on behalf of an ad hoc ring, while making any two signatures by the same signer publicly linkable. Traceable Ring Signatures (TRS), introduced by Fujisaki and Suzuki [PKC'07], strengthen linking to tracing: two signatures on different messages additionally reveal the signer's public key. Since cheating almost always means signing two distinct messages, for example two conflicting transactions, traceability turns detection into accountability and makes misbehavior costly. However, TRS remain far less studied and deployed than LRS. We identify two gaps and address both. First, the security notions inherited from [PKC'07], anonymity, linkability, and exculpability, do not capture attacks specific to tracing. For example, they together do not imply unforgeability, a fundamental requirement for all signature-like primitives. We close this gap by introducing extended linkability and extended exculpability, which reflect the security requirements of TRS more faithfully than their standard counterparts. Second, all existing TRS schemes trace in $O(n)$ time for a ring of size $n$, whereas LRS link in $O(1)$. Over a pool of $\ell$ signatures, pairwise tracing therefore costs $O(\ell^2 n)$ against $O(\ell^2)$ for linking. We design a new TRS framework with $O(1)$ tracing for valid signatures. Instantiated from DDH with Bulletproofs [S&P'18], it yields signatures of $(64\log n+544)$ bytes on Curve25519. To our knowledge this is the shortest TRS for $n \ge 12$, and it is on par with state-of-the-art DLog-based LRS schemes. TRS thus gains traceability at essentially no cost over LRS.

Proving an elliptic curve scalar multiplication [k]P= Q ∈ E(Fp) inside a SNARK is much cheaper when the output Q is hinted by the prover and only verified in-circuit, rather than recomputed. The recent scalar multiplication techniques of Eagen, El Housni, Masson and Piellard (Latincrypt 2025) certify a hinted Q with a short lattice reduction (fraction) decomposition of the scalar and a single group identity, and yield the fastest known in-circuit scalar multiplications. We observe that the soundness of this whole family rests on an implicit prime-order hypothesis: the certifying identity is checked over the full group E(Fp), and only when E(Fp) has trivial cofactor does it force Q into the prime-order subgroup. On cofactor curves the certification is unsound. We give two concrete forgery classes against these hinted gadgets: an any-scalar attack that, for a target scalar fixed by the statement, adapts the decomposition so a small rational torsion point cancels from the identity; and a chosen-scalar attack that vanishes the output-side coefficients modulo a small cofactor prime and solves for the scalar afterwards. Both make the gadget accept Q′ = [k]P + T for a non-zero torsion point T as if it were [k]P. We quantify the reachable torsion in terms of the sub-scalar range bound and validate the attacks on widely deployed curves such as BLS12-381, BN254 and BW6-761. The straightforward fix is to check that Q lies in the subgroup but is expensive. We propose a cheaper one that binds the hinted output through a hinted preimage, with the minimal such constant that suffices against each attack model.

Distributed shuffling is a core primitive underlying mix-nets, electronic voting, and, more recently, single secret leader election (SSLE) protocols for proof-of-stake blockchains. In these settings, a collection of resource-constrained parties jointly permutes a list of ciphertexts or commitments in order to conceal the correspondence between inputs and outputs. Existing security analyses of such protocols typically rely on heuristic anonymity measures or implicitly assume honest behavior; therefore, they fail to capture statistical dependencies that arise when shuffling is partial and some participants are corrupted. In this work, we introduce a new security model for distributed shuffling that accurately reflects the setting of real-world attacks by explicitly accounting for adversarial corruption and information leakage. Our model allows an adversary to corrupt a subset of shufflers and track selected elements throughout the execution, as well as query the resulting permutation afterwards. We then turn to studying Whisk in this model, the shuffle-based SSLE mechanism proposed for Ethereum. Leveraging Markov-chain techniques, we show that security can only be guaranteed for more stringent parameters than currently proposed. We evaluate the performance impact of changing these parameters on the Ethereum network.

Multi-party private set intersection (MPSI) enables multiple parties to securely compute the intersection of their private datasets without revealing any information beyond the intersection itself. However, as the number of participants scales, the performance of multi-party PSI protocols is significantly influenced, with the number of interaction rounds emerging as a critical bottleneck. In this paper, we propose a novel MPSI protocol and its updatable extension based on function secret sharing and oblivious key-value stores, achieving optimal one-pass online interaction. Our construction guarantees security in the semi-honest model, resisting collusion among any $n-1$ parties when the Leader is honest, and among any $n-2$ parties when the Leader is corrupted—an assumption that aligns well with many practical deployment scenarios. Furthermore, our multi-party updatable PSI (MUPSI) protocol allows parties to efficiently compute the intersection over dynamically updated sets. Our MUPSI protocol achieves collusion resistance against any $n-1$ participants, assuming an honest Leader. It ensures that both computational and communication complexities scale exclusively with the size of the updates rather than the entire datasets, exhibiting superior performance particularly when handling unbalanced sets and large participant cohorts. All proposed protocols exhibit strong scalability with respect to participant count. We demonstrate the superiority of our protocols through implementation and comparison with state-of-the-art MPSI protocols. Experiments show that when the number of participants ranges from $20$ to $140$ and the set size ranges from $2^{12}$ to $2^{20}$, our MPSI protocol is competitive. Notably, in the WAN setting with $140$ participants and a set size of $2^{20}$, the running time is reduced by $49.1\times$ compared with GLW+24. Our MUPSI protocol avoids PSI operations on entire sets, achieving a reduction in running time by an order of magnitude.

The Kim mapping, which belongs to the only known CCZ-equivalence class in even dimension that contains an APN bijection, and the APN bijections in dimension 9 exhibited by Beierle and Leander, all have a univariate representation corresponding to a cyclotomic mapping (aka Wan-Lidl polynomial), and they are all linearly-equivalent to functions with a highly-structured multivariate representation. In this paper, we show that functions having these properties, which correspond to multivariate projective mappings, i.e. multivariate functions whose coordinates are homogeneous, actually appear in the CCZ-equivalence classes of almost all known infinite families of APN functions. However, this behavior is not inherent to the APN property. Indeed, we prove that the vast majority of the known sporadic examples of APN functions in dimension 6 and 8, including almost all APN functions whose automorphism group is reduced to the automorphisms derived from their affine derivatives, are not CCZ-equivalent to an affinely self-equivalent function.

XtM (XOR-then-MAC) is provably optimal against quantum adversaries. As of March 2025, no production cryptographic library implements it. HKDF, with weaker security guarantees, is deployed in 91% of the 44 libraries we examined. This gap is not accidental.This Systematization of Knowledge (SoK) introduces the (A, P, φ) framework to explain it: A measures authentication strength, P measures IETF standardization maturity, and φ measures implementation complexity. To our knowledge, this is the first falsifiable, quantitative model predicting cryptographic adoption grounded in observable software engineering indicators. We apply this framework to seven combiner families and 44 cryptographic libraries, validate φ against measured integration LOC across 9 real-world repositories, and derive predictions verifiable by 2028.Our evidence suggests that implementation complexity is a first-order explanatory factor in cryptographic adoption. The most deployable construction is not the most secure one in isolation: it is the most secure one engineers can integrate, audit, and maintain at scale.

An oblivious key-value store is a data structure that can encode and decode $n$ key-value pairs in a table of size $m$ obliviously. After encoding, one cannot distinguish the encoded key-value pairs from other key-value pairs in the input domain. In this paper, we first propose a data structure called Peelable Garbled Bloom Filter (PGBF), which encodes the key-value pairs in a similar way to peeling and unpeeling an \emph{onion}. Specifically, it can divide the key-value pair set (i.e., onion) as multiple subsets (i.e., peels) and order them from the outermost peel to the innermost peel by using a counting Bloom filter. However, using a small expansion rate (i.e., $\eta=m/n$) in PGBF will result in a non-empty core issue with non-negligible probability. To handle this issue, we propose Multi-PGBF by combining multiple PGBFs to do the peelings and unpeelings recursively. In addition, we propose a variant C-Multi-PGBF by clustering a large set into small sets to achieve faster encoding efficiency. Our experiments show that Multi-PGBF and C-Multi-PGBF obtain the best encoding and decoding efficiency. Multi-PGBF improves the encoding time of RR (CCS’22) by $65.1\%\sim 77.6\%$, while C-Multi-PGBF improves the encoding time of the clustered RR variant by $60.2\%\sim 64.7\%$. For decoding, Multi-PGBF is $28.6\%\sim 62.4\%$ faster than RR (CCS'22) and $89.7\%\sim 96.3\%$ faster than RB-OKVS (Usenix'23). When integrated into the state-of-the-art two-party and multi-party private set intersection protocols (Eurocrypt'21, Usenix'24), Multi-PGBF and C-Multi-PGBF lead to faster protocols than those using existing OKVS constructions in most settings.

In nonadaptive combinatorial group testing, given $n$ items with at most $d$ positives, the goal is to identify them using as few pooled tests as possible. A $t\times n$ binary matrix represents the design, where rows are tests and columns are items. The matrix is $d$-disjunct if no column is contained in the Boolean union of any $d$ others. Let $T(d)$ be the minimum $t$ for which such a matrix exists with $n>t$. Shangguan and Ge proved $T(d)\ge \frac{15+\sqrt{33}}{24}d^2$ by counting private pairs (IEEE Trans. Inf. Theory, 62(12):7518-7521, 2016). In this paper, we strengthen their argument by introducing a column-deletion recurrence in which the light-heavy threshold varies with the recursive state $z=(n-t)/d^2$, rather than remaining fixed. This yields the improved bound $T(d)\ge 0.9283d^2-O(d)$. The analytic core reduces to a first-order ODE, and a self-contained interval-arithmetic certificate verifies that the solution reaches the required contact point.

We revisit the notion of Simulation Extractability (SE) for SNARKs in the updatable setting. We demonstrate that existing formal definitions of SE in this setting are insufficient to guarantee the required non-malleability in real-world scenarios. Towards this, we first identify and frame a malleability vulnerability: a cross-SRS reinterpretation attack, which shows that an adversary can reuse or maul proofs across different, correlated SRSs generated through the update procedure. This is made possible because existing security definitions fail to model an adversary’s ability to observe simulated proofs relative to various derived SRSs. To close this security gap, we propose a revised and stronger security notion of Updatable Simulation Extractability (USE) which was originally defined in [GKK+22]. Our definition models a dynamic environment where the SRS is adaptively updatable by the adversary, who can also query simulation oracles for proofs under the resulting family of reachable SRSs. This captures the full extent of the adversarial capabilities observed in practice. Finally, we provide positive results for popular polynomial-IOP-based SNARKs, and show that these schemes satisfy our stronger USE notion, provided the circuit-specific SRS is securely bound into the proof transcript, e.g., via a correct implementation of the Fiat-Shamir transformation.

We present Grand Danois, a new post-quantum multilinear polynomial commitment scheme from lattices for polynomials over $\mathbb{F}_q$ that achieves polylogarithmic $O(\lambda \ell)$ verification complexity and proof sizes. We build on the general approach introduced in Hachi (ePrint 2026/156) with three key changes. First, we switch to the vanishing Short Integer Solution (vSIS) assumption to obtain structured public parameters for our commitment scheme and utilize this structure to design a sumcheck protocol amenable to succinct verification. Second, rather than casting ring relations into $\mathbb{F}_{q^k}[X]$, via the residual technique of Hachi, we express multiplication by fixed $\mathcal{R}_q$ elements through its rotation matrix, which lets the verifier fold each row of the constraint matrix in time linear rather than quadratic in the ring degree $d$. Third, we modify the quadratic relation used in Hachi and Greyhound (CRYPTO 2024) so that it becomes compatible with proving norm bounds using Johnson-Lindenstrauss projections. This is achieved through an adaptation of the structured projection strategy introduced in RoK and Roll (ASIACRYPT 2025). This has the benefit for communication complexity in that proving norm bounds and correct polynomial evaluation are integrated into a single protocol, reducing the number of commitments sent by the prover. Furthermore, we impose additional structure on our random projections to reduce the witness size even more aggressively during each round of recursion without sacrificing verification complexity. Under the vSIS assumption, our construction yields an estimated proof size of roughly $80$ KB for $2^{32}$-size polynomial evaluations.

The notion of Best-of-Both-Worlds introduced in the work of Ishai et al. (CRYPTO 2006) investigated whether an MPC protocol can simultaneously provide two incomparable security guarantees depending on the number of corrupted parties. As a special case of this, Chaum et al. initiated the study of protocols that tolerate unbounded corruption within a certain adversary structure and PPT corruption of any number of parties beyond that. More recently, Acharya et al. (CRYPTO 2023) formalized this notion as MPC with fall-back security. Although the feasibility of such protocols has now been thoroughly studied in prior works, most of the existing protocols require round complexity linear in the number of parties and the computation size. In this work, we study the round complexity of MPC with fall-back security in the threshold corruption setting, presenting constant-round protocols for optimal thresholds. We present a semi-honest fall-back secure protocol for $t < \frac{n}{2}$ with 3 rounds, in the plain model, whereas the best known protocol in the same setting takes at least 11 rounds. In the CRS model, we present a maliciously fall-back secure protocol for the same threshold with 4 rounds, satisfying unanimous abort (UA). Finally, we extend this to a 5-round protocol that satisfies fairness in the presence of unbounded adversaries for $t < \frac{n}{2}$ corruptions and UA tolerating PPT adversaries for arbitrary corruption beyond that. In the malicious setting, we construct the first constant-round fall-back secure protocols.

We present a practical framework $\mathsf{DumboMix}$ for asynchronous anonymous broadcasts with guaranteed output delivery (G.O.D., a.k.a. robustness), enabling a set of $n$ servers to privately solicit $N$ messages from distinct clients, such that these messages remain secret until they are revealed in uniform random order. Here, asynchronous G.O.D. ensures that all messages are eventually randomly mixed despite (i) arbitrary malicious behaviors by up to $\lfloor (n-1)/3 \rfloor$ Byzantine servers and (ii) unpredictable network delays and jitters. At the core of $\mathsf{DumboMix}$, we first propose a couple of practical mixing methods $\mathsf{DumboMix1}$ and $\mathsf{DumboMix2}$ for Shamir-secret-shared multi-party computation (MPC) over $\mathbb{Z}_p$, along with their server-optimized variants. When randomly mixing $N$ messages, their online phases require only $\mathcal{O}(1)$ multiplicative depth, expected $\mathcal{O}(N^2)$ scalar multiplications (between public and shared values), and up to $\mathcal{O}(N)$ MPC multiplications (between shared values). Moreover, assuming a robust underlying MPC framework, they guarantee that all revealed inputs are uniformly shuffled. In contrast, existing techniques fail to achieve all these performance and functionality features: The DC-net variant $\mathsf{Blinder}$ (CCS’20) may reveal a non-negligible fraction of inputs without shuffling them; Butterfly switching networks in secret-shared MPC (CCS’19) incur $\mathcal{O}(\log^2 N)$ multiplicative depth; RabbitMix (Security’24) requires $\mathcal{O}(N^2)$ MPC multiplications; and PowerMix (CCS’19) incurs $N^{3}/2$ scalar multiplications. We finally implement our new mixing methods within $\mathsf{DumboMPC\text{++}}$, our computation-optimized implementation of the state-of-the-art robust AMPC framework $\mathsf{DumboMPC}$ (Security’25), which provides more concretely efficient offline preprocessing while preserving asynchronous G.O.D. and optimal resilience. We then conduct extensive evaluations with $n=4$ to $31$ servers under varying network settings, revealing that our new mixing methods achieve 44.8--65.9× (resp. 37.1--52.7×), 4.8--7.1× (resp. 3.9--5.5×), and 2.7--4.0× (resp. 5.1--7.2×) speedups over RabbitMix, PowerMix, and the butterfly switching network, respectively, when shuffling 1024 messages in LAN (resp. WAN).

Masked hardware design is a central countermeasure against side-channel analysis (SCA), but its practical deployment remains costly due to the overhead and design complexity of secure implementations. To manage this complexity, modern masked circuits are increasingly built from composable masked building blocks, referred to as gadgets. However, improving the implementation quality of such gadgets is challenging because optimization must not violate formal security requirements. This paper studies the optimization of masked hardware gadgets under formal security by comparing conventional CAD transformations with a security-aware design automation framework based on evolutionary algorithms. The conventional CAD flow explores structural alternatives exposed by technology mapping, FRAIG-based rewriting, and retiming, whereas the evolutionary framework adaptively explores alternative gate-level realizations through circuit-specific mutation, crossover, and multi-objective selection. The resulting implementations are evaluated for power and area while enforcing functional correctness and compliance with the probing model through equivalence checking and pre-silicon side-channel verification. Our results show that conventional CAD techniques can yield substantial improvements in selected cases, up to 60%, but their behavior is not systematic under strict masking constraints. In contrast, the evolutionary framework provides a controlled, adaptive search over alternative gate-level realizations and produces security-preserving implementations with measurable improvements over naïve synthesis, reaching up to 15% reduction in power and area in selected cases. We validate the optimized designs using industry-standard synthesis and pre-silicon side-channel verification tools. We further show, for AES, that additional savings remain possible even relative to a state-of-the-art compressed masked design.

Remote state preparation (RSP) is a central primitive in quantum cryptography, enabling classical parties to remotely construct quantum states using only classical communication. As a result, RSP serves as a key building block in numerous protocols involving classical clients and quantum servers, allowing classical parties to leverage the advantages offered by powerful quantum computers. All known constructions of RSP rely on strong cryptographic assumptions, typically variants of trapdoor claw-free functions (TCFs). In this work, we initiate the study of a weaker form of remote state preparation, which we call eavesdropper-blind remote state preparation (EB-RSP). Informally, EB-RSP requires blindness only against external observers who see the transcript of the honest protocol, rather than against the quantum server itself. Despite this relaxed adversarial model, the resulting notion remains sufficient for useful cryptographic applications. In particular, we show that two-message EB-RSP already suffices to construct quantum public-key encryption with classical public keys and quantum ciphertexts. We then construct two-message EB-RSP protocols from specific one-way group actions, yielding a first step toward RSP-type primitives based on assumptions that do not rely on trapdoors. Finally, we observe that existing RSP constructions are likely naturally adaptable to the two-message EB-RSP notion; we demonstrate this explicitly for a concrete TCF-based RSP construction.

When two S-box layers of a round are separated by no key addition, the round correlation is a signed sum over all compatible intermediate masks, not a product of layer correlations, so the product rule can fail in either direction. Our central finding is that evaluating this intra-round sum exactly changes the assessment of the published linear cryptanalysis of SPEEDY, whose two S-box layers are separated only by ShiftColumns. We first develop the linear cryptanalysis of this setting: an exact one-round algorithm with a decidable exactness condition for the product rule, a dependency-graph decomposition, a covering-number bound strengthening linear-trail weight bounds, and a Walsh-support criterion in which the affine dimension of that support, limited by the endpoint key masks, fixes the key-recovery transform cost. Potentials use the independent-round-key model; complexities are in equivalent encryptions. Applied to SPEEDY, these tools revise published results: a reported five-round mask sequence has exact correlation $2^{-90.0962}$, not $2^{-93.0147}$; the new bound raises the unrestricted five-round weight bound from $53.7714$ to $62.2616$ bits; and the full-round attack on SPEEDY-7-192 reported at time $2^{158.06}$ needs at least $2^{199.97}$ encryptions in the pruning class considered. For SPEEDY-6-192 we give a six-round known-plaintext attack (data $2^{169.84}$, time $2^{170.20}$, memory $2^{156}$) and show that the attack class defined here contains no attack with data and time both at most $2^{128}$, its time being at least $2^{136.302}$. The same exact evaluation also revises a four-round differential-linear correlation.

\emph{Modular Polynomial Commitment Schemes (Mod-PCS)} extend standard PCSs by enabling provable evaluation of integer polynomials modulo a random modulus, providing a natural foundation for SNARKs that operate directly over large integers without emulating arithmetic in finite fields. Only two Mod-PCS constructions are known. The first (Campanelli and Hall-Andersen, IACR ePrint 2024) serves primarily as a feasibility result and is impractical and not post-quantum secure due to its reliance on groups of unknown order. The second (Garetta et al., CRYPTO 2025) introduces the weaker notion of \emph{relaxed} Mod-PCS, but is not fully succinct: committing to a multilinear polynomial with $N$ terms and $B$-bit coefficients requires $O(\sqrt{N}B)$ proof size and verification time. We present a black-box transformation that builds relaxed Mod-PCS from any standard PCS, enabling new constructions. Instantiating our transformation with a tensor-code PCS yields the first relaxed Mod-PCS with $O(\log (N+B))$ proof size and verifier time, which is transparent and plausibly post-quantum secure. Using this scheme within the framework of Garetta et al., we obtain the first fully succinct SNARK for the Customizable Constraint System over $\mathbb{Z}_B$, achieving $O(B\log N + N\log N \log B)$ prover time and $O(\log (N+B))$ verifier time and proof size. Our approach relies on a commitment-switching technique for integer polynomials and a new batched integer commitment scheme from any PCS. We further introduce improved arguments for integer addition and multiplication, correctness of the number-theoretic transform, and general Diophantine relations over committed integers.

Two novel symmetric multidimensional affine nested variations of the Hill Cipher are presented. The Hill Cipher is a block polygraphic substitution encryption scheme based on a linear transformation of plaintext characters into ciphertext characters. In the time since Hill first published his encryption scheme, variations, modifications, and improvements of theoretical and practical importance have been published every year indicating that the Hill Cipher is an active area of cryptography research. The first variation presented in this paper incorporated invertible key matrices of orders 2, 4, and 8 such that the matrix values of the 2×2 matrix rotate positions with each block of characters in a similar manner to the rotating letter wheels of a German Enigma Encoder, then results of the 2×2 key matrices output are passed to 4×4 key matrices, and 8x8 key matrix, 4×4 key matrices, and rotative-value 2×2 key matrices. The second variation is configured with invertible key matrices of orders 4, 8, and 16 without rotation of matrix values in a similar manner to the first variation. In both variations, plaintext characters of each block are operated on by exclusive-or (XOR) vectors prior to multiplication with the matrices to create the affine ciphers. Strengths, weaknesses, and other considerations are provided in the discussion. Two proposals are also argued with rationale for a more robust character set for encryption and the increase in modulus that the character set allows, and the possible advantages and disadvantages of affine XOR vectors.

MD-Hill-SPN is the first Hill-based construction to combine a multi-tier diffusion mix layer, a memory-hard KDF, and a simultaneous multi-metric empirical evaluation. Two independent runs of the full metric suite yield: (a) full plaintext avalanche from round 1 (mean 63.97–64.67 of 128 bits, ideal 64); (b) the differential-probability sampling floor of 2 × 10−5 reached at round 4 (50,000 of 50,000 output differences distinct, both sessions); (c) algebraic-degree lower-bound saturation at the maximum observable value from round 1; (d) linear-bias indistinguishable from random (combined exceedance 4.40%, below the 4.55% noise floor); and (e) branch numbers at the Singleton (MDS) bound for every tier (B = 5 for 4 × 4, B = 9 for 8 × 8, B = 17 for 16 × 16), computed exhaustively over weight-1 inputs. MD-Hill-SPN therefore moves beyond theoretical construction to a construction that passes a defined empirical evaluation suite: avalanche, differential sampling, linear-bias probing, algebraic-degree lower bounds, and MDS branch numbers under single-key, known-plaintext conditions with fixed parameters, an evaluation no prior Hill cipher variant has reported in full.

Threshold signatures are deployed in settings where an adversary may run many concurrent signing sessions and corrupt signers adaptively. Two-round schemes make this especially delicate. Their first-round messages are independent of the signed message and can be preprocessed offline, so a later corruption must reveal randomness that is consistent with commitments already published in prior transcripts. Existing adaptive constructions address this tension by adding rounds, relying on algebraic or knowledge assumptions, or paying non-tight losses from guessing the corruption pattern, the decisive session, or the final transcript. We construct $\mathsf{TPilaf}$, the first two-round threshold signature scheme that combines partially non-interactive signing with a fully tight proof against adaptive corruptions. The scheme is pairing-free and is built in prime-order groups from the $\mathsf{MDDH}$ assumption in the random-oracle model. Its first-round messages can be generated offline, and any threshold set of signers can aggregate their second-round shares into a single publicly verifiable signature. The proof combines two ingredients. First, we introduce a linearly homomorphic dual-mode commitment with targetable opening. This lets the simulator open an already fixed commitment to the aggregate target imposed by a later Fiat-Shamir challenge. Second, we use profile-wise zero-sum masking with posterior completion. Corruption openings and signing responses are therefore sampled from the exact conditional law while values already visible to the adversary remain cached. Together, these tools enable a delayed branch-decision argument. The reduction waits until the adversary's own queries determine the last touched coordinate, completes only latent state, and then binds the forged hidden branch. The final bound has no combinatorial loss in the number of users, threshold, sessions, or corruption patterns, and contains only the explicit bad-event and assumption terms appearing in the theorem.

Authenticated Key Exchange (AKE) is a cornerstone of secure communication, especially in resource-constrained IoT environments where lightweight and post-quantum security are paramount. While lattice-based cryptography offers promising solutions, existing post-quantum AKE protocols often prioritize strong security notions, such as the use of an IND-CCA encryption scheme, incurring overheads incompatible with IoT devices. This raises a critical question: Can one-way security (OW), a weaker but potentially more efficient notion, suffice for secure AKE in the post-quantum era? We address this challenge by revisiting the ALIKE framework (ISO/IEC 29192-4), which achieves OW-CCA-based AKE using deterministic RSA. However, RSA’s quantum vulnerability and the lack of lattice-based OW-CCA schemes hinder its applicability today. Our work bridges this gap through three key contributions. First, we prove that the Hash-Before-Encrypt (HBE) paradigm generically transforms deterministic OW-CPA schemes into OW-CCA-secure ones. We additionally present the Fujisaki–Okamoto transform and its security proof construction, providing a reference for understanding the efficiency advantages of the proposed HBE-based approach. Second, we modify Bai et al.’s efficient lattice-based OW-CPA scheme to a deterministic variant and rigorously prove its security. Third, we generalize the SPAKE framework to support our OW-CCA construction, enabling post-quantum AKE with minimal assumptions, implement and benchmark the resulting protocol, demonstrating state-of-the-art efficiency for lightweight, quantum-resistant AKE. By relaxing security requirements from IND-CCA to OW-CCA while preserving adaptive security we achieve a practical balance between robustness and performance, paving the way for deployable solutions in constrained environments like IoT and connected vehicles.

We give an explicit compression collision for all 28 rounds of the KoalaBear Poseidon instance with parameters $(t,\alpha,R_F,R_P)=(16,3,8,20)$, in the setting where the round constants are fixed before the MDS linear layer is chosen. The main problem is to construct a single linear layer that simultaneously controls two executions through both the full and partial rounds. We do this by tracking their midpoint and half-difference. In each two-round block, one prescribed image of the linear layer cancels the midpoint against the next round constant, so the following odd cubic S-box receives opposite states and resets the midpoint to zero. Two additional images are reused throughout the permutation to return the half-difference to the same one-dimensional subspace. The resulting trajectory constraints determine a linear layer, while a scalar recurrence closes the final difference under feed-forward. For the KoalaBear instance we obtain a collision in all sixteen output coordinates with an MDS matrix satisfying the prescribed linear-layer checks. The scalar construction reduces to low-degree equations and admits a family of parameter choices, so the collision is not an isolated instance. The result exposes an adaptive correlation between fixed round constants and a subsequently chosen linear layer that matrix-only checks do not capture.

Differential-based attacks represent the best known results for many block ciphers. Such attacks usually demand that the adversary an choose plaintexts (CP) or ciphertexts (CC) in subspaces to satisfy differential trails. However, many widespread modes of operation or applications prohibit the adversary from directly choosing inputs for the majority of primitive calls. While Biham and Shamir already suggested a straightforward trade-off for standard differential attacks in their work on the DES, studies on advanced differential-based types, such as impossible-differential, rectangle, or mixture attacks, have surprisingly received little attention so far. In this work, we study applications of differential-based attacks in the random known-plaintext model (RKP) of the above. For the AES as the probably most widespread block cipher, we derive the best existing distinguishers and attacks in the RKP model on all versions, improving earlier results by at least one round. Interestingly, we show that Demirci-Selcuk meet-in-the-middle attacks with differential enumeration, which require much related data, can also be effective in that setting without approaching the full codebook too closely. For several of our attacks, we showcase differences between the models as trails that lead to the best known attack complexities under chosen data are suboptimal in the RKP model, and can be replaced by better trails. While our results do not threaten the security of the full AES, and their complexities are too high to represent any threats, we hope to inspire cryptographers to also consider attacks in the RKP for future attacks.

We present a method for secure pattern matching over encrypted texts using TFHE. Our approach realizes a fully secure binary search algorithm by leveraging two operational modes of integer-input TFHE. While the BGV-based method of Bonte and Iliashenko (CCSW '20) requires $O(|P| \cdot |T|)$ secure character comparisons to find a pattern $P$ in a text $T$, our method reduces this to $O(|P|\log |T|)$ comparisons, achieving improved scalability for large texts. As a result, our method can find a pattern of length 100 in an encrypted text containing genomic data of one million characters in less than 5 minutes, where prior work would require approximately 5 days for the same task. These results highlight the practicality of TFHE and its potential for large-scale secure string search.

An adaptor signature scheme can be seen as committing to a signature using an NP statement, in such a way that (1) the commitment, called a presignature, is verifiable, (2) the corresponding witness enables opening the commitment (adapting the presignature), and (3) seeing a valid commitment-opening (presignature-signature) pair leaks the witness. In the blockchain space, where signed transactions must be broadcast to the public to take effect, this last property allows "forcing" a party to leak a witness for possibly multiple presignatures issued for the same NP statement. This then gives rise to many applications such as atomic swaps or payment channels. Importantly, in prevailing adaptor signature schemes, presignatures are already technically signatures, in that they are non-interactive zero-knowledge proofs of knowledge of the signing key. This has a number of consequences, most important being that the presignature constitutes evidence of intent to participate in a protocol based on adaptor signatures. Perhaps surprisingly, however, for many practical applications, this strong "binding" of presignatures turns out to be non-essential. In this work, we revisit the definitions of adaptor signature schemes, demonstrating that prevailing security requirements are often too strict. To this end, we formally define fair signature exchange (FSE) and abandon the assumption implicit in prior work that adaptor-based FSE must be "symmetric" with both parties using the same adaptor signature scheme. The resulting relaxation of security requirements leads us to the notion of presignature deniability, an extension to adaptor signature schemes that we define formally and construct from various assumptions.

Dynamic universal accumulators compress an evolving set into a short digest with membership and non-membership witnesses for each element. Bilinear Pairing (BP) accumulators offer succinct witnesses and fast verification, but their public parameters size, witness generation and dynamic costs scale linearly with the set size in the trapdoorless setting. To address this bottleneck, we present HACC, a trapdoorless hierarchical accumulator that organizes capacity-bounded BP accumulators over ordered buckets into a $t$-ary tree. By fixing the node capacity $t$, HACC is a pairing-based accumulator whose public parameters can be independent of the set size $n$. Its ordered buckets yield native non-membership proofs and $\mathcal{O}(t\log_t n)$ witness generation cost, and non-cascading bucket split and merge mechanisms keep it fully dynamic at worst-case $\mathcal{O}(t\log_t n)$ dynamic cost with amortized $\mathcal{O}(1)$ witness updates. Its witnesses are of size $\mathcal{O}(\log_t n)$ and verify with as many pairings, which an optional path compression via polynomial multiproofs reduces to a constant for read-heavy epoch-based settings. We prove HACC correct and sound under the $t$-SDH assumption in the random oracle model. Experimentally, under comparable budgets, HACC accelerates element update and witness generation by $8.0\times$--$5087\times$ over a monolithic BP accumulator (Nguyen, CT-RSA'05, Damgård et al., eprint'08, and Srinivasan et al., CCS'22) while consuming $15.6\times$--$15933\times$ smaller public parameters.

We present $\textsf{Sluice}$, a read-write streaming Groth16 prover that reduces $\textit{prove-phase}$ random-access working memory from $\mathcal{O}(N)$ to $\mathcal{O}(\log N)$ once the CRS, QAP, and witness are materialized as private streams. It preserves the standard Groth16 interface: a proof of 3 group elements, 3-pairing verification, and unchanged verifier contracts. Our key technical contribution is $\textit{Split-Butterfly-Merge}$ ($\mathsf{SBM}$), an NTT algorithm in the read-write streaming model with $\mathcal{O}(\log N)$ memory, $\mathcal{O}(N \log N)$ total I/O, and $\mathcal{O}(\log N)$ sequential passes over external storage. Combining SBM with streaming sparse R1CS evaluation and chunked Pippenger MSM yields a verifier-compatible Groth16 proving path that exchanges RAM for sequential storage I/O and wall-clock time. Our prototype uses a fixed-window MSM engineering point; the measurements validate memory reduction and proof compatibility, while the theorem states the asymptotically tuned MSM schedule. We implement $\textsf{Sluice}$ over BN-254. Direct prove-only runs produce valid 128-byte proofs through $N=2^{25}$. The same-size bounded-memory comparison is at $N=2^{23}$: $\textsf{Sluice}$ succeeds under an 8GB Linux cgroup cap, whereas the standard prover is killed under 8GB and 12GB caps and succeeds only at 16GB. These results position $\textsf{Sluice}$ as a storage-rich, RAM-limited proving option rather than a replacement for optimized in-memory provers.

The Bitcoin Lightning Network secures hundreds of millions of dollars, yet channel endpoints rely on vulnerable single online keys. Although threshold signatures are routinely used to protect on-chain Bitcoin, no practical deployment has been possible for Lightning channels. This is because thresholdizing a Lightning party requires nesting a threshold signature scheme inside of an established two-party MuSig2 protocol without altering its nonce exchange or message flow. In this work, we resolve this limitation by formalizing nested threshold multi-signatures, a new cryptographic primitive for thresholdizing one participant inside a multi-signature protocol. As an instance of this primitive, we present Iceberg, the first construction for nested threshold MuSig2 signatures. Iceberg enables one side of a Lightning channel to operate as a $t$-of-$n$ threshold group while appearing to the counterparty as a standard MuSig2 participant. As a result, threshold custody can be deployed unilaterally on today's Lightning Network without requiring any modifications to Bitcoin, the Lightning protocol, or channel counterparties. We prove the security of Iceberg, integrate a prototype into a production Lightning node, and benchmark its performance. Our measurements show that thresholdizing a Lightning channel incurs only modest overhead, since a threshold group tolerating one corrupted member sustains over $93\%$ of the payment throughput of an unmodified endpoint.

We construct (1-hop) fully homomorphic encryption (FHE) schemes with chosen-ciphertext (CCA) security from the learning with errors (LWE) assumption in the standard model. Security of our construction only relies on the circular-secure LWE, which matches the assumptions needed for FHE with the basic chosen-plaintext security. Besides, the scheme achieves a security notion that is strictly stronger than the CCA1 security. Prior FHE schemes with even just CCA1 security require either the random oracle model or non-falsifiable assumptions. The construction follows the well-known Naor-Yung double encryption paradigm. However, unlike previous works [Boneh et al., ITCS 2012; Canetti et al., PKC 2017; Manulis and Nguyen, Eurocrypt 2024], which employ general zero-knowledge succinct non-interactive arguments of knowledge (ZK-SNARKs), we design a special succinct argument to prove the validity of FHE ciphertexts. The succinct argument is constructed from batch arguments for NP and a new primitive called predicate extractable commitment, which may be of independent interest.

The current state of the art for cryptanalysis generic rank-2 module LIP schemes invokes an SVP oracle on the canonical real embedding, discarding the quaternionic structure made available by the reduction of rank-2 module LIP to the reduced-norm Principal Ideal Problem (nrd-PIP) over quaternion algebras (we note, that since writing, this is no longer the case for certain instances, such as Hawk). We address this gap by giving, to our knowledge, the first lattice reduction algorithms over quaternion rings applied in a cryptographic setting, and the first description of quaternion BKZ. We extend the celebrated LLL algorithm to leverage algebraic properties of quaternion orders and novel post-processing steps to design an LLL algorithm for lattices in not-necessarily-maximal orders. The strategy is to reduce over the Euclidean overlattice and then post-process, giving two routines: one returning a basis of a sublattice with the best bounds, the other a true basis of the original lattice at the cost of output quality. We further consider blocksize two BKZ as a generalisation of the LLL algorithm, and then extend this to arbitrary blocksize; utilising results on the shortness of Gauss and HKZ reduced bases and the relationship of successive minima for our specific sublattice. We then apply these algorithms to ideal lattices arising from nrd-PIP, including those instances given by rank-2 MLIP over cyclotomic fields such as Hawk, via a modification of the canonical embedding that preserves both dimension and quaternionic structure. This allows us to reduce a lattice basis of rank a constant factor of four smaller than the standard real embedding, improving basis bounds and asymptotic complexity in the generic setting.

Repeat--accumulate--accumulate (RAA) codes are sparse random linear codes with linear-time encoders. Although RAA ensembles can have linear minimum distance with high probability, this does not determine how often a randomly sampled code falls below a prescribed relative-distance threshold. We determine this lower-tail probability and identify the rare mechanisms that dominate it. Let \(n\) be the message length, \(r\ge4\) a fixed repetition factor, and \(N=rn\) the block length. For the randomly scaled ensemble \[ G=R\Pi_1V_1A\Pi_2V_2A, \] where \(R\) is repetition, \(A\) is the prefix-sum accumulator, \(\Pi_1,\Pi_2\) are independent uniform interleavers, and \(V_1,V_2\) have independent uniform nonzero diagonal entries in \(\mathbb F_q\), we prove that, for every fixed \(0<\delta\le1/2\) and \(\gamma>0\), \[ q-1\ge\gamma N \quad\Longrightarrow\quad \mathbb P[d_{\min}(G)\le\delta N] =\Theta_{r,\delta,\gamma}(N^{1-r}). \] For the unscaled ensemble \[ G_0=R\Pi_1A\Pi_2A, \] if \(\operatorname{char}(\mathbb F_q)>r\) and \(0<\delta\le1/10\), then \[ \mathbb P[d_{\min}(G_0)\le\delta N] =\Theta_{r,\delta}(N^{2-r}). \] Thus random scaling improves the failure probability by one power of \(N\). We also prove \[ \mathbb P[d_{\min}(G)\le\delta N] =\Omega_{r,\delta}\!\left( N^{1-\lceil r/2\rceil}(q-1)^{-\lfloor r/2\rfloor} \right), \] showing that linear field growth is necessary, in asymptotic order, for the constant-factor \(N^{1-r}\) law.

Expand–accumulate (EA) codes are sparse linear codes underlying constructions of correlated pseudorandomness and field-agnostic succinct arguments. In “Field-Agnostic SNARKs from Expand–Accumulate Codes” (CRYPTO 2024), Block et al. conjectured that a single fixed-row-weight EA component already achieves constant relative distance with inverse-polynomial failure probability. We prove this conjecture in a stronger, field-uniform form. For every rate $R\in(0,1)$, there exists $\delta_R>0$ such that, for every target exponent $C>0$, one can choose $\gamma=\gamma(R,C)>0$ for which the fixed-row ensemble with $t=\lceil\gamma\log N\rceil$ satisfies \[ \mathbb{P}\!\left[ \min_{x\in\mathbb{F}_q^{\lfloor RN\rfloor}\setminus\{0\}} \operatorname{wt}(xEA) \le \delta_R N \right] \le N^{-C} \] for all sufficiently large $N$. The same constants work for every prime power $q$; in particular, the field may vary arbitrarily with the block length. Thus, a single fixed-row-weight EA component is asymptotically good over all finite fields, and its polynomial reliability exponent can be made arbitrarily large by increasing the row-weight constant. The proof separates sparse and high-weight messages. Sparse messages are handled through expansion and a compact analysis of accumulator cancellations, while high-weight messages are controlled by a surplus of linear constraints over large fields and a stochastic accumulator analysis over bounded fields. A terminal-boundary obstruction shows that, for $t=\Theta(\log N)$, inverse-polynomial failure is qualitatively optimal.

Anonymous tokens with private metadata bit (ATPM) have received increased interest as a method for anonymous user authentication while also allowing the issuer to embed trust signals inside the token that are only readable by the authority who holds the secret key. However, all existing ATPM protocols require interaction during issuance as the client must send a blinded request and wait for the issuer to sign, introducing latency and scalability bottlenecks. In this work, we present the first Non-interactive Anonymous Token (NIAT) scheme with a private metadata bit. Our design builds on structure-preserving signatures on equivalence classes (SPS-EQ) and recent advances in non-interactive blind signatures. With NIAT, tokens can be issued without any online interaction, enabling asynchronous pre-computation and drastically reducing issuer workload. We formalize NIAT security definitions, propose an efficient construction under standard assumptions and experimentally evaluate its performance. We also present an extension to our NIAT construction that allows the identification of clients who attempt to double-spend a token (i.e., present the same token twice) and argue that non-interactive schemes are uniquely positioned to offer this essential feature.

Lattice-based blind signatures have attracted significant attention in recent years due to the rapid growth of digital currencies, the increasing demand for privacy-preserving digital interactions, and the ongoing transition toward quantum-resistant cryptographic primitives. While blind signatures provide anonymity guarantees, achieving fairness without compromising privacy to a third party remains a challenging problem. Blind adaptor signatures (BAS) address this limitation by enriching blind signatures with conditional-execution functionality, enabling fair exchange while preserving user anonymity. In particular, a BAS scheme allows a user to engage in an atomic swap with a verifier using an adapted blind signature obtained from a signer, thereby maintaining privacy against the signer while ensuring fairness between the user and the verifier. In this work, we observe that the ABDLOP commit-and-prove framework (CRYPTO 2022) exhibits a dichotomic structure that can be leveraged to realize adaptor functionality. Building on this, we propose a lattice-based blind adaptor signature (L-BAS) scheme that simultaneously achieves fairness along with the privacy guarantees of blind signing. Compared with the underlying lattice-based blind signature scheme, our construction incurs only a modest overhead, increasing the signature size by approximately 5.2 KB while largely preserving the efficiency of the original system. We formally analyze the security of the proposed construction and prove that it satisfies extractability, unique extractability, computational pre-verification soundness, one-more unforgeability, and blindness under standard lattice-based assumptions. Our results demonstrate that fairness can be incorporated into lattice-based blind signatures with minimal performance degradation, making the proposed scheme a practical candidate for privacy-preserving and quantum-resistant fair exchange applications.

In dynamic group signature schemes (GSS), forward security ensures that newly joined members cannot generate valid signatures for past time periods. Additionally, non-frameability prevents even privileged entities, such as the group manager or key issuer, from falsely attributing signatures to honest users. Most GSS either lack non-frameability or face significant efficiency challenges when updating signing keys to ensure forward security. In this paper, we introduce a forward-secure dynamic group signature scheme that guarantees non-frameability. We also present an alternative scheme that, while lacking non-frameability, offers higher efficiency compared to existing schemes with comparable security. For both protocols, we propose efficient revocation mechanisms that allow an authority to revoke users without requiring re-registering existing users. Additionally, we propose a technique that enables the verification process of both protocols to be performed in batches. We prove the security of our schemes, ensuring the standard dynamic GSS security notions; anonymity, traceability and non-frameability (second scheme). Experimental results demonstrate that our schemes are competitive in both computational and communication efficiency when compared to existing literature.

Updatable Public-Key Encryption (UPKE) augments the security of PKE with Forward Secrecy properties. While requiring more coordination between parties, UPKE enables much more efficient constructions than full-fledged Forward-Secret PKE. Alwen, Fuchsbauer and Mularczyk (AFM, Eurocrypt’24) presented the strongest security notion to date. It is the first to meet the needs of UPKE’s most important applications: Secure Group Messaging and Continuous Group Key Agreement. The authors provide a very efficient construction of an Updatable Key Encapsulation Mechanism (UKEM), implying UPKE, that satisfies their notion with classic security based on the Computational Diffie-Hellman (CDH) assumption in the Random Oracle Model (ROM). No existing post-quantum UPKE/UKEM construction is known to meet the AFM definition. We present and implement practical secret-key recovery attacks in the AFM adversarial model for all proposed parameter sets of two PQ schemes including the most efficient one to date, due to Abou Haidar, Passelègue and Stehlé (APS, Asiacrypt’23). If the UKEM schemes were used in a real-world group messaging application, the attacks would correspond to realistic execution scenarios, even when targeting a 100% success probability. Next, we present the first post-quantum UKEM construction meeting (a slight relaxation of) the AFM security notion. When based on the Module-LWE assumption, our construction is more efficient than prior PQ constructions, while achieving stronger security. More concretely, public key sizes are about 1/2 that of APS and ciphertext sizes are about 14% smaller. As the AFM security proof relies on random self-reducibility of CDH, which has no analogue for lattices, we develop a new proof technique for strong UKEM, identifying the core properties required from the underlying (lattice-based) encryption scheme.

Lattice-based zero-knowledge proofs are now efficient enough for practical use, but in all known constructions a single prover holds the entire witness and is therefore a single point of failure. Thresholdizing them is understood only for three-round $\Sigma$-protocols, which certify shortness only $\textit{approximately}$. The $\textit{exact}$ statements needed by applications such as anonymous credentials require more rounds and rely on rejection sampling, and neither property survives thresholdization. We construct the first lattice-based threshold zero-knowledge proof systems for exact relations. The witness is Shamir-shared among $\mathtt{n}$ parties, any $\mathtt{t}$ of them can jointly produce a proof, and the proof has the same form as a single-prover proof, only a factor $\sqrt{\mathtt{t}}$ larger, with verification unchanged. We thresholdize the product proof of Attema, Lyubashevsky, and Seiler (CRYPTO 2020) and the exact proof of Esgin, Nguyen, and Seiler (ASIACRYPT 2020), making both rejection-free using Hint-MLWE and evaluating them over threshold homomorphic encryption. We define threshold commit-and-prove protocols with the corresponding zero-knowledge and simulation-extractability notions, and prove our constructions secure against passive adversaries that statically corrupt at most $\mathtt{t}-1$ parties. Of independent interest, we show that the Fiat--Shamir transforms of both proof systems are simulation-extractable in the random oracle model, and that MLWE remains hard when secrets are drawn from the subring fixed by a ring automorphism.

Private Set Operations (PSO) enable mutually untrusted parties to securely compute arbitrary functions (e.g., union, intersection, and cardinality) over their private input sets. These operations have wide applications in many real-world scenarios. Existing PSO protocols fall short of practical deployment for several reasons. (1) \textit{Function-specific}. Real-world privacy-preserving applications often require multiple set operations within the same task, while existing solutions typically address individual functionalities (e.g., intersection or union) in isolation, making it difficult and costly to support diverse set operations in a unified and efficient manner. (2) \textit{Lacking malicious security}. As PSO is commonly employed in highly sensitive applications, it is often necessary to provide strong security guarantees against malicious adversaries. Unfortunately, most existing works only achieve semi-honest security, which limits their practical applicability. (3) \textit{Restricted settings}. The majority of existing works focus exclusively on the two-party setting. How to extend them securely and efficiently to the multi-party setting while tolerating a malicious majority remains unclear. To date, designing a maliciously secure multi-party PSO (mPSO) framework that efficiently supports diverse set operations remains an open challenge. This paper presents the \textit{first} maliciously secure mPSO framework, named UM-PSO, that supports a broad range of set operations with practical efficiency. At the core of our framework is a function-independent preprocessing phase that prepares a reusable pool of secret-shared items, which can then be leveraged to securely compute diverse set functionalities in the online phase. To achieve malicious security efficiently, we design verification mechanisms on top of SPDZ-based authenticated secret sharing, along with tailored techniques and optimizations to further improve practical performance. We implement our protocols and report concrete performance results. For a representative setting with 5 parties and a total of $2^{12}$ 128-bit items, our framework achieves an online running time of $0.627$ seconds and incurs $3.35$ MB of communication. Compared to the baselines, our framework achieves up to $51\times$ speedup and up to a $76\times$ reduction in communication.

Modern public-key cryptography is threatened by advances in quantum computing. As a result, there has been a shift towards cryptographic algorithms that can resist attacks by a quantum computer. However, these algorithms use significantly longer keys, and produce larger ciphertexts and digital signatures than their classical counterparts. These bigger sizes pose problems for devices that are bandwidth- and/or power-limited, and wish to establish a secure, quantum resistant communication channel with another device. In order to reduce the overhead of using these algorithms in challenging environments while maintaining security posture, we present Compact Authenticated Key Exchange – Hiding Identities (CAKE-HI). To evaluate our protocol, we compare the key exchange handshake size and computational efficiency of mutual authenticated TLS and CAKE-HI. Measurements show that CAKE-HI significantly reduces the handshake size and the computational overhead of establishing a quantum-secure link. In addition, we formalize and prove security properties about CAKE-HI in the symbolic and computational model using the protocol analysis frameworks Verifpal and CryptoVerif.

Oblivious transfer (OT) is a foundational tool in secure computation. Random OT-correlated pairs of the form $(r_0,r_1)$ and $(b,r_b)$, where $r_0,r_1,b \stackrel{{}_\$}{\leftarrow} \{0,1\}$, significantly speed up secure computation protocols. Pseudorandom correlation functions (PCFs), introduced by Boyle et al. (FOCS 2020), are an efficient means of non-interactively generating correlated pairs. In a PCF, two parties store short keys that are used to locally generate large amounts of correlated pairs. While pre-quantum PCFs for OT achieve highly compact key sizes (e.g., $30$ kB), a significant gap remains in the post-quantum regime, where existing solutions rely on lattices or learning-parity-with-noise-style assumptions and yield much larger keys. We construct compact post-quantum PCFs for OT. Our construction has key sizes in the range of $100$ kB, approaching the compactness of pre-quantum PCFs and seven times smaller than the most compact state-of-the-art post-quantum alternatives. The key size of our PCF remains invariant regardless of the target number of OTs, in contrast to prior alternatives. We estimate a throughput of $7$ OTs per second for our PCF. We additionally provide a security proof in the quantum random oracle model, constituting the first such analysis of a post-quantum PCF. The core of our construction is a new, compact constrained pseudorandom function (CPRF) for inner-product membership predicates. Its security is based on a natural extension of the parallelization problem, which we introduce as the parallelization problem with auxiliary inputs. We provide an extensive analysis of this assumption as well as an implementation of our construction.

We present the first fully distributed, code-based polynomial commitment scheme (PCS) that achieves linear prover time and polylogarithmic communication for multilinear polynomials. Our construction builds on Brakedown with proof composition. We design a distributed proof of correct linear encoding. Codeword validity is reduced to a sumcheck relation over the sparse parity-check matrix, whereas systematic consistency is verified through multilinear evaluation checks. These techniques preserve linear prover complexity while reducing the communication size between sub-provers to polylogarithmic scale. We implement our construction and evaluate it on multilinear polynomials ranging in size from $2^{22}$ to $2^{28}$. The prover exhibits near-linear parallel scalability. Compared with existing evaluated distributed PCS implementations with 8 parties, it reduces communication by at least $13\times$ at every tested polynomial size, while its prover time remains within $1.31\times$ of the fastest implementation. These results demonstrate that our asymptotic communication improvements translate into substantial concrete savings while retaining efficient proving.

Folding/Accumulation schemes are a powerful tool for building scalable proof systems. However, standard approaches for leveraging folding schemes, such as IVCs or PCDs, require embedding hash functions (modeled as random oracles) into recursive circuits, introducing both security concerns and significant proving overhead. We re-envision how to use folding schemes, and introduce Symphony, the first proving paradigm that leverages folding schemes as a black box without embedding hashes in SNARK circuits. It is memory-efficient, parallelizable, and plausibly post-quantum secure, with polylogarithmic proof size and verification. The (low-memory) prover requires O(log log n) passes of the input data and its computation is dominated by committing to the input witnesses. A core component of our construction is a new lattice-based folding scheme that compresses a large number of NP-complete statements into one in a single shot. Furthermore, we design a generic compiler that converts a folding scheme into a SNARK without embedding the Fiat-Shamir circuit into proven statements.

In the context of PKE schemes, Gagliardoni et al. proposed at PQCrypto 2021 a qIND-qCPA security notion (a superposition-based analogue of the classical IND-CPA security notion), by using the theory of so-called type-2 unitary operators. On one hand, this notion is very natural, closely mirrors the classical intuition, and can be handled without relying on complex techniques such as Zhandry’s compressed oracles. On the other hand, it is restricted to a certain class of PKE schemes (so-called isometric). Moreover, it is not immediately clear how to extend the definition to chosen-ciphertext attack (CCA) scenarios, mainly due to the possibility of decryption failures – something that is entailed by most quantum-resistant PKE schemes. In this work, we use the theory of type-2 operators to extend superposition-based security notions to any PKE schemes, in the CPA and CCA setting, without Zhandry’s compressed oracle technique. We start first by showing that a trivial extension of Gagliardoni et al.’s techniques to the general case is not possible, even for the CCA1 case, by identifying barriers preventing the realization of a ‘natural’ type-2 decryption operator. Then we define a subclass of PKE schemes (which we call ‘strongly decryptable’ ), for which it is easy to circumvent the aforementioned barriers and to define superposition-based CCA1 and CCA2 notions. Further, we introduce a novel transformation (that we call ‘purification’) which applies to any PKE scheme, producing a ‘quasi-PKE’ scheme, for which it is possible to define properties that mimic the security notions defined for strongly decryptable schemes; we can thus ‘unload’ the security definitions for an arbitrary PKE scheme on its purification. Finally, we show implications and separations between our security notions, as well as constructions.

Practical implementations of synchronous MPC protocols typically require each party to advance to the next round as soon as they have received all expected messages. This deviates from the theoretical synchronous round-based model, where instead each party advances in the next round after a timeout. To capture this gap between theory and practice, Asharov, Chandramouli, Cohen and Ishai in Eurocrypt 2025 proposed a new model where the adversary is super-rushing. In this, the adversary can see future messages of some honest parties before delivering current-round messages to slower ones. In this work, we study super-rushing security in both the computational and statistical settings, and design round-preserving compilers that transform standard synchronous MPC protocols into ones secure against super-rushing adversaries. Ours is the first work to investigate the security of computational MPC protocols against a super-rushing adversary.

This work describes a digital signature scheme constructed from a zero-knowledge proof of knowledge of a pre-image of the Rescue Prime Optimized (RPO) permutation. The proof of knowledge is constructed with the DEEP-ALI interactive oracle proof combined with the Ben-Sasson--Chiesa--Spooner (BCS) transformation in the random oracle model. The EUF-CMA security of the resulting signature scheme is established from the UC-friendly security properties of the BCS transformation and the pre-image hardness of the RPO permutation. The implementation of the scheme computes signatures in 13 ms and verifies them in 1 ms on a single core when the BCS transform is implemented with the Blake3 hash function. (The multi-threaded implementation signs in 9.2 ms and also verifies in 1 ms.) These speeds are obtained with parameters achieving 122 bits of average-case security for \( 2^{122} \)-bounded adversaries with access to at most \( 2^{64} \) signatures.

SQIsign is an isogeny-based post-quantum signature scheme whose public keys and signatures are remarkably compact. However, since SQIsign relies on arithmetic in quaternion algebras over the field of rational numbers, no fixed-precision integer arithmetic for SQIsign had been established until recently, hindering constant-time implementation and deployment on memory-constrained devices. Recent work by Kim et al. instantiated an SQIsign implementation with fixed-precision integer arithmetic by deriving uniform worst-case bounds for the quaternion algorithms used in key generation and signing. Nevertheless, the resulting precision budget remains large, exceeding 13 times the public key size. Consequently, this forces implementations to reserve wide integer buffers throughout the computation. This increases the memory footprint and reduces the suitability of fixed-precision SQIsign for constrained platforms. In this work, we present compact quaternion algorithms that substantially reduce the fixed-precision memory requirements of SQIsign. First, we modify and analyze quaternion algorithms for SQIsign, in which large intermediate integer values appear. Then, we derive the improved uniform worst-case size bound on integers during the key generation and signing procedures. As a result, we reduce the required precision budgets from 7026/10713/14150 bits to 1665/2521/3319 bits for the NIST-I/III/V security levels, respectively, corresponding to improvements of $76.30\%$, $76.47\%$, and $76.54\%$. We also provide a fixed-precision implementation of SQIsign applying these improved precision budgets and accelerating previous inefficient implementation of fixed-precision integer arithmetic. Compared with the previous fixed-precision implementation, our implementation achieves performance improvements larger than $99\%$ for both key generation and signing procedures at each security level.

RIPEMD-160 is an ISO/IEC hash function standard based on the Merkle-Damgård structure with a double-branch compression function. There have been many attempts at modular differential attacks on reduced RIPEMD-160, with the best previous result being a 40-step practical collision attack achieved in 2023. That attack constructs a simple local collision in round 2 of the left branch to minimize uncontrolled conditions. To achieve this, differences must be introduced into many message words, which constrains the maximum number of steps that can be attacked. To overcome this limitation and target more steps, we propose a new differential characteristic structure that abandons the sparse local collision in round 2 and instead uses a single continuous differential characteristic spanning rounds 1 to 2 for each branch. This structure allows us to inject a difference into only one message word. Using an automatic search tool based on the high-performance parallel SAT-solver PRS, we identify suitable differential characteristics by imposing more control over conditions, differences, and the probability of proper propagation. Based on the differential characteristics, we identify three colliding message pairs for 42-step RIPEMD-160 with theoretical time complexity of approximately $2^{47.4}$, thereby improving the best practical collision attack by 2 steps on this hash function.

A $(k,n)$-robust combiner for a primitive $\mathcal{P}$ combines $n$ candidate instantiations of $\mathcal{P}$ into a single scheme that remains secure as long as at least $k$ of them remain secure. Robust combiners have been extensively studied for primitives such as hash functions, public-key encryption, and oblivious transfer, but much less is known in the setting of cryptographic groups. In this work, we initiate the study of robust combiners for cryptographic groups in Maurer's generic group model (GGM), where algorithms access group elements only through abstract algebraic operations. We ask whether one can combine $n$ candidate groups into a single group that remains secure provided that at least $k$ of the underlying groups remain secure. A natural baseline is the direct-product construction, which preserves search hardness but fails for decisional assumptions and incurs substantial representation overhead. We show that these limitations are in fact inherent. Our first result is a complete impossibility for the decisional Diffie--Hellman assumption: for every polynomially bounded $n$ and $k$ with $k<n$, there is no generic $(k,n)$-robust combiner for cryptographic groups that preserves DDH security. Our second result gives a tight threshold for search assumptions in the regime where $n$ and $k$ are fixed constants. For the discrete logarithm problem, robust generic combination is possible when the combined group order is large enough to encode the secrets of $n-k+1$ components; concretely, if $\log N \ge (n-k+1)\lambda$, where the component groups have distinct $\lambda$-bit prime order, then a robust combiner exists. Conversely, if $\log N \le (n-k)\lambda$, then no generic $(k,n)$-robust DLog-secure combiner exists. These results identify a fundamental limitation of robust hedging at the group level. Decisional assumptions such as DDH cannot be robustly combined in the GGM, while search assumptions admit robustness only at essentially optimal representation cost. Consequently, robustness for group-based cryptography must in general be achieved at higher layers, such as protocol design or key derivation.

Threshold signatures have regained a strong interest recently, driven by applications in cryptocurrencies and NIST's ongoing call for threshold schemes. Among them, FROST - a classical threshold Schnorr signature scheme already in real-world deployment - stands out. Its appeal lies in three core features: partially non-interactive signing, non-interactive identifiable abort (IA), and proactive security. In contrast, while post-quantum (PQ) threshold signatures have seen significant advances in recent years, no existing scheme simultaneously provides even two of these features. Considering the imminent need to migrate to PQ cryptography, this state-of-the-art remains unsatisfactory. In this work, we propose Hermine, a lattice-based threshold signature that offers the full feature set of FROST under standard lattice assumptions. Hermine is designed to efficiently support the Medium scale of parties ($N \le 64$) as defined in the NIST threshold call, producing a small \Raccoon signature of size $11$ KB. Our main technical contribution is introducing an everywhere-short secret sharing, which splits a short secret vector $\mathbf{s} \in R_q^\ell$ into short shares and admits a short linear reconstruction algorithm. While the resulting construction appears intuitive, its security proof requires a non-trivial, fine-grained analysis of the information on $\mathbf{s}$ that is inherently leaked by the short shares. Furthermore, we formalize game-based unforgeability and IA definitions with proactive security, which may be of independent interest.

Zero-knowledge execution of high-level programs proceeds by repeatedly evaluating CPU steps. Each such step privately selects and evaluates an instruction (possibly involving memory access) from a rich instruction set. Building on this paradigm, ZEE (Heath et al., S&P'21) realized a full toolchain supporting arbitrary $\texttt{ANSI C}$ programs, demonstrating this capability by proving SIR- and CVE-reported bugs in off-the-shelf Linux programs $\texttt{sed}$ and $\texttt{gzip}$. We revamp the state of the art by building a new constant-round ZK system ZEE200, which is about $20\text{-}40\times$ faster than ZEE. ZEE200 is built on a novel and convenient cryptographic framework for efficiently proving general statements represented as real-world programs. Our framework integrates several crucial recent advances, such as Tight ZK CPU (Yang et al., CCS'24) and fast ZK RAM (Yang and Heath, USENIX Security'24). We develop better encodings for $\mathbb{Z}_{2^{32}}$ arithmetic, and numerous low-level optimizations. Compared to ZEE's $\approx 10$ KHz CPU speed on a limited ISA, ZEE200 runs at $\approx 200$ KHz (still on a commodity laptop and a LAN!), while supporting a much richer ISA. For example, we rerun a ZEE's benchmark, proving a SIR-reported vulnerability in off-the-shelf Linux utility $\texttt{sed}$. On a 2021 ThinkPad X1 Carbon Gen 9 under a simulated $1$Gbps LAN (single-threaded), ZEE200 completed the proof in $1.5$ seconds, compared to ZEE's $30.1$ seconds, a $20\times$ improvement.

We prove that row-wise interleaving does not impose a linear loss on two coding-theoretic soundness properties used in recent IOP/SNARK analyses: generator mutual correlated agreement and curve decodability. For generator-MCA, let $G:\Omega\to\mathbb{F}_q^\ell$ be a coefficient generator over a finite seed set and let $C$ be an $\mathbb{F}_q$-additive code. For every interleaving width $s$ and distance parameter $\delta$, we show $$ \varepsilon_G(C,\delta) \le \varepsilon_G(C^{\equiv s},\delta) \le \left(1+\frac1q+\cdots+\frac1{q^{s-1}}\right)\varepsilon_G(C,\delta). $$ Moreover, if $|\Omega|\le q$, then the transfer is exact: $$ \varepsilon_G(C^{\equiv s},\delta)=\varepsilon_G(C,\delta). $$ In particular, affine-line MCA is invariant under row-wise interleaving. This answers the known interleaving-loss question and removes the linear interleaving factor from the affine-line MCA bound. It also implies that polynomial-generator MCA bounds transfer to interleaved codes without an additional interleaving-width factor. We further establish interleaving stability for curve decodability. We introduce a marked formulation, prove its equivalence to the standard definition for $\mathbb{F}_q$-additive codes and $1\le b\le a\le q$, and use it to transfer curve decodability to row-wise interleavings. If $C$ is $(\ell,\delta,a,b)$-curve-decodable and $\binom{a}{b}\le q$, then $C^{\equiv s}$ is also $(\ell,\delta,a,b)$-curve-decodable for every $s$. We also give a field-size-weighted variant that transfers larger base-code witness parameters to smaller interleaved-code witness parameters.

Secure comparison is a fundamental building block frequently employed in various applications of secure multiparty computation, such as secure machine learning. Such protocols based on secret sharing (SS) typically excel in throughput, but they historically suffer from higher (online) round complexity. To address this issue, Attrapadung et al. (AsiaCCS 2022) proposed a protocol with two online rounds in the client-aided model (i.e., assuming a trusted third party in the offline phase), and Lu et al. (USENIX Security 2025) proposed a protocol with three online rounds in the plain model. In this paper, we propose a plaintext comparison protocol with two online rounds in the plain model. While keeping the lowest online round complexity, our protocol also reduces the total bit complexity. For example, for the case of 64-bit integers, the total bit complexity of our protocol is 25.7% of Lu et al.'s protocol and 23.3% of Attrapadung et al.'s protocol adjusted to the plain model.

We give a two-transcript key-recovery attack on TALUS-MPC in TALUS v4. TALUS was presented in the second round of the NIST Threshold Call Preview Talks. In Algorithm 3 of TALUS v4, the committee's nonce polynomials are evaluated at all $N$ points so that any $T$ parties can sign. An adversary controlling the coordinator and $T-1$ parties can reuse the same pooled nonce with two quorums whose only common members are corrupt. Each participating honest party uses its signing share once, yet the coordinator obtains $\mathbf{z}_0=\mathbf{y}+c_0\mathbf{s}_1$, $\mathbf{z}_1=\mathbf{y}+c_1\mathbf{s}_1$. The nonce cancels on subtraction. Moreover, no invertibility assumption in $R_q$ is needed: the response equations lift to $\mathbb{Z}[X]/(X^{256}+1)$, and every nonzero $c_0-c_1$ is invertible in the cyclotomic field $\mathbb{Q}[X]/(X^{256}+1)$. Thus two distinct challenges recover $\mathbf{s}_1$ exactly; since the TALUS v4 public key includes the full $\mathbf{t}=\mathbf{A}\mathbf{s}_1+\mathbf{s}_2$, the adversary also recovers $\mathbf{s}_2$ and forges signatures.

This note collects, in compressed form, some techniques for modular multiplication with word-size (“short-limb”), or at most a-handful-of-words sized moduli as they are used in implementations of lattice-based cryptography: Barrett reduction and multiplication (in signed and unsigned flavors, with exact error, range, and canonicality analyses), Montgomery reduction and multiplication (including the folded-constant form, the precise equivalence with Barrett multiplication, even moduli, the multi-limb case, and the k-reduction), Plantard multiplication (the original unsigned algorithm, the signed variant, and a variant taking signed inputs to the canonical unsigned representative in [0,q)), and modular multiplication via the explicit Chinese remainder theorem. These are compressed out of my lecture slides in the class Post-Quantum Cryptography at National Taiwan University 2020--2025 (EE 5176/921 U2540). All numerical examples, ranges, and windows stated here have been verified by exhaustive or randomized machine search; several constants and ranges correct typos and miscalculations that circulated after lectures.

Mutual correlated agreement (MCA) bounds how many points on an affine line of received words can agree with codewords on many coordinates when the line does not admit a common codeword explanation on those coordinates; the corresponding line parameters are called bad. MCA arises in the soundness analysis of code-based proof systems. For Reed-Solomon codes with arbitrary prescribed evaluation sets, existing deterministic bounds apply only at integer error budgets strictly below the exact Johnson boundary. Fix integers $r\ge2$ and $h\ge1$. For every sufficiently large $K$, let $L\subseteq\mathbb{F}_q$ be any set of $n=rK$ distinct points and set $C=\operatorname{RS}_{<K}(\mathbb{F}_q,L)$. At error budget $E=\left\lfloor{n-\sqrt{n(K-1)}}\right\rfloor+h$, we prove that every affine line has at most $O_{r,h}(K^6)$ bad parameters. Hence \[ \varepsilon_{\mathrm{mca}}(C,E)=O_{r,h}(K^6/q). \] Thus, at each fixed rate $1/r$, any fixed number of integer steps beyond Johnson admits a deterministic polynomial bound on the number of bad parameters; in relative-radius units, the gain is $O(1/n)$. We also derive a MCA upper bound for maximum distance separable (MDS) codes from a sharp lower bound on the number of rejected local membership tests. For Reed-Solomon codes over sufficiently large fields, the resulting endpoint bound is exact whenever at most $K+1$ agreements are required. It yields exact $2^{-128}$ thresholds for four explicit smooth-domain codes of length $64$: we identify the largest safe integer budget and prove that the next one is unsafe. As a concrete application to the Grand MCA Challenge, we exhibit a single prime field $\mathbb{F}_Q$, with $Q<2^{256}$, that supports the required smooth domains at all four target rates. With $K=2^{18}$, the first post-Johnson budget has MCA error below $2^{-128}$ at rates $1/2,1/4,1/8,$ and $1/16$, as does the second such budget at rate $1/8$.

At ITCS 2020, Bartusek, Ishai, Jain, Ma, Sahai, and Zhandry proposed a framework for witness encryption based on affine determinant programs and gave a concrete witness encryption candidate. Yao, Chen, and Yu later broke the separate ADP-based indistinguishability-obfuscation candidate, while noting that their attack did not apply to the witness-encryption construction. More recently, Soukhanov et al. proposed witness encryption from arithmetic affine determinant programs. Soukhanov subsequently described a commutator attack on that construction and noted that the original ADP construction is also subject to the attack for sparse circuits. The recovery of hidden column spaces in our attack uses this commutator technique. We give a deterministic polynomial-time attack that recovers the encrypted bit from the public ciphertext matrices of this candidate. It covers every $q\geq 1$ in the theorem's recovery range, including $q(n)=\lceil n^\varepsilon\rceil$ for all sufficiently large $n$. Outside a fixed finite set of primes, it applies to every SUBSET-SUM instance whose coefficient vector is nonzero modulo $p$ and that has no Boolean solution modulo $p$. On an explicit efficiently generated family of integer NO instances, the encrypted bit is recovered with probability $1-\mathrm{negl}(n)$ under the field-size convention of the original paper.

Goldreich-Levin reductions are ubiquitous in cryptography: they convert an algorithm capable of guessing $\langle r, m \rangle$ (mod $2$) for a hidden string $m$ and a random challenge $r$, to one that is capable of extracting the entirety of $m$. Here, we describe a "simultaneous" Goldreich-Levin reduction for two entangled parties who are capable of guessing $\langle r, m \rangle$ given uniformly random identical challenges $r$. This allows to upgrade any unclonable encryption scheme satisfying "search" security to one satisfying the gold standard of unclonable "indistinguishability". As a corollary, we show that the simplest candidate unclonable encryption scheme from BB84 states satisfies unclonable indistinguishability. This result was discovered by GPT-5.6 Ultra after a few interactions. Our prompts included recent results on unclonable encryption by Ananth and Sahai, and Ragavan.

Linear error-correcting codes with fast encoding and high minimum distance are a central primitive across modern cryptography. They appear prominently in at least two domains: (1) pseudorandom correlation generators (PCGs), which enable sublinear-communication generation of correlations such as oblivious transfer and vector oblivious linear evaluation, and (2) zero-knowledge proof systems, where linear-time encoders underpin proof soundness and scalability. In both settings, the prover or sender must multiply by a large generator matrix $\mathbf{G}$, often with dimensions in the millions, making computational efficiency the dominant bottleneck. We propose a generalized paradigm for building crypto-friendly binary codes with provable minimum distance. Roughly speaking, these codes are based on randomized turbo codes such as repeat-accumulate codes. We prove linear asymptotic minimum distance and compute the exact expected weight spectrum for concrete sizes. We observe that our codes approach the Gilbert-Varshamov distance bound and outperform prior constructions. We construct several novel codes, the most promising of which we call Block-Accumulate codes. Among codes with provable distance, our code is $8\times$ faster than the state of the art on a CPU and $50\times$ faster on a GPU; even against aggressive parameters with conjectured distance, it is $3\times$ and $20\times$ faster, respectively. Under these parameters, this yields overall PCG speedups of $2.5\times$ on the CPU and $15\times$ on the GPU, achieving a projected 200$+$ million OTs per second, or about 100 million binary Beaver triples per second, on the GPU (excluding the one-time 10 ms GGM seed expansion). We also observe a $2\times$ encoding speedup and half the peak memory consumption in the Blaze zero-knowledge (PCS) scheme of Brehm et al. (EUROCRYPT~'25).

Redeemable real-world asset tokens can trade onchain faster than their backing assets can be sold or settled. An immediate-exit facility cannot treat reported net asset value (NAV) as fully liquid. Within our scope, the mechanisms we compare do not jointly provide permissionless access, order-splitting resistance, and favorable small exits. In this paper, we propose a Proprietary Request for Quote (Prop RFQ), an onchain facility that prices exits against available reserves and mitigates, but does not eliminate, split-order incentives. Its quote combines NAV, an order-size curve, a funded-liquidity wall, decaying sell pressure, and a cadence response to repeated sells. The design seeks to keep isolated small exits useful while limiting reserve depletion and gains from splitting a concentrated exit. We evaluate the implemented Solana pricing path with fixed workloads and ablations, then sweep 15,120 parameter configurations. At the reference parameters, cadence reduces aggregate split advantage by 9.67% against matched pressure-only pricing, improves 34 of 40 split workloads, and raises worst-case reserve remaining from 10.49% to 17.66%. No simple policy or Prop RFQ ablation in our comparison dominates the reference configuration on common metrics. After correcting epoch rollover, implementation quotes match the explicitly rolled model at every tested recovery point. However, low-value sells enable cheap cadence griefing.

In 1978, Yao studied the subset product problem and proved its NP-completeness. Later, Galbraith, Zobernig, and Li considered a prime-based modular variant and studied its average-case hardness. More recently, Li introduced the general problem of unknown-coefficient multivariate exponential system solving and studied its hardness systematically in an abstract setting. Li's framework implies a noisy modular variant of subset product as a special case. In this paper, we study this noisy subset product problem in a concrete setting, prove equivalence relations among several related variants, and use these results to construct a post-quantum non-alternating key exchange scheme, with a natural one-sided interpretation as a key encapsulation mechanism. Unlike other noise-based schemes, such as lattice-based schemes, our construction does not rely on an additional reconciliation plaintext. Instead, the receiver is able to recover the sender's ephemeral secret key itself. Moreover, we reduce indistinguishability security directly to the search version of the noisy subset product problem, without relying on a separate decisional assumption.

Differential cryptanalysis is one of the main methods of cryptanalysis and has been applied to a wide range of ciphers. While it is very successful, it also relies on certain assumptions that do not necessarily hold in practice. One of these is the hypothesis of stochastic equivalence, which states that the probability of a differential characteristic behaves similarly for all keys. Several works have demonstrated examples where this hypothesis is violated, impacting the attack complexity and sometimes even invalidating the investigated prior attacks. Nevertheless, the hypothesis is still typically taken for granted. In this work, we propose AutoDiVer, an automatic tool that allows to thoroughly verify differential characteristics. First, the tool supports calculating the expected probability of differential characteristics while considering the key schedule of the cipher. Second, the tool supports estimating the size of the space of keys for which the characteristic permits valid pairs, and deducing conditions for these keys. AutoDiVer implements a custom SAT modeling approach and takes advantage of a combination of features of advanced SAT solvers, including approximate model counting and clause learning. To show applicability to many different kinds of block ciphers like strongly aligned, weakly aligned, and ARX ciphers, we apply AutoDiVer to GIFT, PRESENT, RECTANGLE, SKINNY, WARP, SPECK, and SPEEDY.

Update: We retract the claim that main construction in the paper is cryptographically secure. In particular, the trapdoor functions generated in Algorithm 1 from three dimensional tensors are efficiently distinguishable from random tensors, since their two dimensional slices (in the longest dimension) are rank deficient. We leave the article as a record, in hopes that some of the techniques are useful in other contexts. Weyman and Zelevinsky generalised Vandermonde matrices to higher dimensions, which we call Vandermonde-Weyman-Zelevinsky tensors. We generalise Lagrange interpolation to higher dimensions by devising a nearly linear time algorithm that given a Vandermonde-Weyman-Zelevinsky tensor and a sparse target vector, finds a tuple of vectors that hit the target under tensor evaluation. Tensor evaluation to us means evaluating the usual multilinear form associated with the tensor in all but one chosen dimension. Yet, this interpolation problem phrased with respect to a random tensor appears to be a hard multilinear system. Leveraging this dichotomy, we propose preimage sampleable trapdoor one-way functions in the spirit of Gentry-Peikert-Vaikuntanathan (GPV) lattice trapdoors. We design and analyse ``Hash-and-Sign'' digital signatures from such trapdoor one-way functions, yielding short signatures whose lengths scale nearly linearly in the security parameter. We also describe an encryption scheme. Our trapdoor is a random Vandermonde-Weyman-Zelevinsky tensor over a finite field and a random basis change. We hide the Vandermonde-Weyman-Zelevinsky tensor under the basis change and publish the resulting pseudorandom tensor. The one way function is the tensor evaluation derived from the public tensor, restricted so as to only map to sparse vectors. We then design the domain sampler and preimage sampler demanded by the GPV framework. The former samples inputs that map to uniform images under the one-way function. The latter samples preimages given supplementary knowledge of the trapdoor. Preimage sampling is a randomised version of interpolation and knowing the basis change allows efficient translation between interpolation corresponding to the public and trapdoor tensors. An adversary seeking a preimage must solve a pseudorandom multilinear system, which seems cryptographically hard.