Using the language of categories, we introduce a novel framework abstracting the key algorithmic features of the Deuring correspondence between supersingular elliptic curves and quaternion orders and of the post-quantum signature scheme SQIsign based on it. We then show how to construct an interactive identification scheme and digital signature within this framework, and also instantiate more advanced primitives, such as a chameleon hash function. We present two distinct instantiations of the framework based on isogenies of supersingular elliptic curves: the first recovers (one-dimensional) SQIsign, while the second leads to the recently published SQInstructor.

FrodoKEM is an unstructured LWE-based key encapsulation mechanism (KEM), widely recognized for its conservativeness and robustness. However, there remains a performance gap of approximately one order of magnitude between FrodoKEM and structured LWE-based KEMs, which severely limits its competitiveness during the standardization process. This work proposes the fastest hardware implementation of FrodoKEM to date, which is also configurable, achieving up to 2.5× speedup over prior hardware designs. Specifically, for the most time-consuming module, modular matrix multiplication, a block matrix processing approach is adopted, where the computation is reformulated into block-level operations and further mapped to vector inner-product computations. Based on this formulation, two optimized architectures are proposed for vector inner-product computation using a carry-save-adder (CSA)-based Wallace tree structure, achieving improvements in resource efficiency while eliminating the use of DSP resources. By fixing the block size to 4×4, the data generation rate using parallel SHAKE-based random number generators is precisely matched with the data consumption rate of matrix multiplication, thereby improving hardware utilization efficiency. The proposed design is implemented in Verilog and verified on both Xilinx Virtex-7 and Artix-7 FPGA platforms, as well as ASIC implementation.

Digital signature schemes based on isogenies are among the most compact signatures achieving post-quantum security. Recent advances, especially those leveraging higher-dimensional isogenies, have also made such schemes practically efficient. However, comparatively little attention has been devoted to endowing these signatures with additional privacy-enhancing properties, such as the re-randomization of keys and the adaptation of signatures to new public keys. Although some results exist in the isogeny group action setting, these signatures suffer from a subexponential quantum attack which renders them rather inefficient. In this work, we initiate the first systematic study of privacy-enhancing isogeny-based signatures outside the group-action framework. We base our exploration on the notion of signatures with randomizable keys developed by Celi et al. (FC'24), which aims to unify privacy notions related to key updatability and signature adaptation. In particular, we analyze which of their privacy notions can be achieved from the state-of-the-art signatures SQIsign, PRISM and the hash-and-sign signature scheme derived from the Deuring verifiable unpredictable function (DeuringVUF). To this end, we naturally extend SQIsign to an SWRK scheme that allows key randomization, and enhance both PRISM and the DeuringVUF signature to additionally allow for message adaptation. We show that, due to the deterministic nature of the signatures, the DeuringVUF signature achieves perfect adaptability. We formally prove all three of our modifications achieve unlinkability against unbounded adversaries, and remain unforgeable under the same assumptions as the original schemes.

The hardness of the Learning Parity with Noise (LPN) problem is a foundational assumption in cryptography, forming the basis of constructions ranging from symmetric-key primitives to public-key encryption and beyond. A central open question is whether the average-case hardness of LPN can be based on worst-case complexity assumptions, as has been achieved for the analogous Learning With Errors (LWE) problem. Existing worst-case-to-average-case reductions for LPN [BLVW19, YZ21] rely on statistical smoothing of linear codes, which inherently limits the resulting average-case hardness to noise rates as large as $1/2 - 1/\mathrm{poly}(n)$, which is insufficient for public-key applications. We explore a new approach towards obtaining such reductions: rather than requiring that random sparse combinations of the rows of the generator matrix of a code be statistically close to uniform, we only require that they be computationally indistinguishable from uniform. This leads to a clean win-win structure: we show that any efficient LPN solver can be transformed into a pair of efficient algorithms $(S, D)$ such that for every matrix $A$ of appropriate dimensions over $\mathbb{F}_2$, either $S$ decodes the code generated by $A$ from random noise, or $D$ distinguishes random noisy codewords of the dual of this code from uniform. By instantiating this reduction with appropriate parameters, we obtain the average-case hardness of LPN with inverse-polynomial noise rate $n^{-\alpha}$ for any constant $\alpha < 1$, assuming the worst-case simultaneous hardness of decoding a code from random noise and distinguishing random noisy codewords of its dual from uniform. In particular, setting $\alpha = 1/2$, our reduction yields LPN hardness in the parameter regime required for Alekhnovich's construction of public-key encryption [Ale03], a regime that was previously inaccessible via worst-case reductions.

We study the security of the Fiat-Shamir transformation when applied to multi-round oracle proofs in the standard model, showing that Interactive Oracle Proofs (IOPs) can be transformed via Fiat-Shamir into Non-interactive Zero-knowledge (NIZK) arguments. We obtain our result in two steps. First, we show that instantiating Kilian's transformation with an IOP satisfying a mild Zero-Knowledge (ZK) property called semi-Honest-Verifier ZK (semi-HVZK), and a commitment scheme that is extractable and equivocal, yields a ZK argument. We then obtain provably-secure NIZK arguments from our interactive ZK arguments by instantiating Fiat-Shamir with a Correlation-Intractable Hash (CIH) function. The second step involves carefully defining an appropriate "bad relation" for which CIHs are known to exist. Existence of CIH for our bad relation requires the underlying semi-HVZK IOP to have an additional "doom checkability" property which we introduce. Roughly, doom checkability guarantees that one can efficiently check whether a non-empty partial IOP transcript is "doomed" in the sense that it will lead the verifier to reject. We then show that IOPs based on the "MPC in the Head" paradigm are doom checkable. Our results show that the Fiat-Shamir paradigm can be applied to semi-HVZK IOPs to yield provably-secure NIZKs. This extends similar results known for single-round IOPs (i.e., Probabilistically Checkable Proofs) and interactive proofs (IPs), and establishes the soundness of this method. Along the way, we also prove composition theorems for semi-HVZK IOPs, which might be of independent interest, and use them to improve the soundness error of linear-time IOPs and interactive arguments from the literature.

Isogeny-based cryptography is a kind of cryptography whose security relies on the computational hardness of the isogeny problem. This field is gaining attention as a promising candidate for post-quantum cryptography. Among the notable schemes within this category is SQIsign, a signature schemes that has been submitted to the NIST Post-Quantum Cryptography Standardization competition. In this paper, we introduce a new isogeny-based signature scheme, $\Delta$-SQIsign, which represents a significant departure from existing isogeny-based signatures including SQIsign. The key distinction in our scheme lies in its use of the degree of isogeny as a challenge within the underlying $\Sigma$-protocol. Then, the prover outputs an isogeny of the given degree as a response. To construct such a scheme, we introduce a new algorithm, called $\Delta$-KLPT, which is a variant of GeneralizedKLPT. Similar to GeneralizedKLPT, our algorithm outputs an ideal equivalent to a given ideal with a fixed norm; however, under certain conditions, it can produce an ideal of smaller norm than GeneralizedKLPT.

Real-time group communication protocols, such as Zoom and Microsoft Teams, aim to provide end-to-end security for audio and video conferences even in the presence of a malicious server. Despite their widespread deployment, particularly since the COVID-19 pandemic, their intended security guarantees lack comprehensive formalization. Prior work largely focuses on Zoom, and analyzes its security in models that rely on restrictive assumptions, such as the existence of a trusted server at certain points in time or a long-lived leader that never leaves the group. Moreover, existing analyses assume that group-specific session states of group members are secure and incorruptible, leaving the impact of potential full state compromise on group security unexplored. In this work, we propose a set of essential security guarantees for real time group communication with state-compromise resilience against fully malicious servers and provide the first construction that provably satisfies all of these guarantees. To formally prove that our design achieves its goal, we formalize a novel continuous group key distribution protocol and introduce an associated security model that captures all the intended guarantees. We propose a generic construction that is provably secure in this model and suggest both classical and post-quantum secure instantiations. Besides these main design goals, we introduce a novel multi-recipient authenticated key encapsulation mechanism, which serves as a building block for our generic construction. We define two core security notions for maKEM, propose both concrete and generic constructions, and prove their security in the random oracle model and the standard model, respectively.

Although the state-of-the-art model extraction attack on the hard-label Fully-connected Neural Network (FCN) by Carlini et al. at EUROCRYPT 2025 has polynomial-time complexity in theory, its dual-point clustering relies on singular value decomposition (SVD) with a time complexity of $\mathcal{O}(n^2 (d^{(k)})^3)$, resulting in huge runtime in practice. To address this computational bottleneck, this work transforms Carlini et al.'s geometric-view hard-label attack into an algebraic framework, and proposes two efficient clustering methods: Normal Rank Check (NRC) and Approximate Signature Vector (ASV). The NRC and ASV methods replace Carlini et al.'s heavy SVD-based rank checking with simple rank checking or inner-product operations, reducing the clustering complexity to $\mathcal{O}(n (d^{(k)})^3)$ on average. Furthermore, this paper presents the first model extraction attack against hard-label max-pooling Convolutional Neural Networks (CNNs) by combining the ASV method with the kernel-centric clustering scheme instead of the neuron-centric clustering, which fully exploits the property of weight sharing in convolutions and fills a cryptanalysis gap. Experiments on FCNs and the max-pooling LeNet-5 demonstrate that our NRC/ASV methods drastically cut clustering time, and improve the overall efficiency in the model extraction.

The CKKS homomorphic encryption scheme can achieve high throughput for large batches, typically of tens of thousands of inputs, whereas DM/CGGI schemes offer low latency for a single input. In existing CKKS approaches, the multiplicative depth required for nonlinear function evaluation demands a large ciphertext modulus, which forces a large ring degree regardless of the input size. Practical applications, such as encrypted MLP inference, may require only a few hundred function evaluations at a time. For these moderate batch sizes, existing CKKS-based methods requiring large multiplicative depth incur high latency without fully benefiting from their high throughput. We present $\mathsf{SWIFT}$, a CKKS functional-bootstrapping method that reduces latency by using multiple slots to lower multiplicative depth. For input $x$, $\mathsf{SWIFT}$ packs its integer multiples $\ell x$ into unused slots. Exponential bootstrapping then generates the powers $\exp(2\pi\mathrm{i}\ell x)=\exp(2\pi\mathrm{i}x)^\ell=\alpha^\ell$ in parallel. Compared to previous approaches that compute these powers through homomorphic multiplications, $\mathsf{SWIFT}$ directly generates those powers and reduces the required multiplicative depth and ciphertext modulus, allowing a smaller ring degree and lower latency. We also introduce a trigonometric approximation method for singular functions such as $1/\sqrt{x}$, whose derivative is unbounded near zero. We observe that the previous Fourier extension method of Bian et al. (EUROCRYPT'26) can produce extremely large coefficient norms for these functions when focusing solely on reducing the polynomial degree. Instead, we solve an optimization problem to find a trigonometric polynomial that minimizes the coefficient norm while satisfying the required approximation accuracy for the target function. The resulting trigonometric polynomial can be evaluated efficiently and with numerical stability using $\mathsf{SWIFT}$. Our implementation evaluates $\mathsf{ReLU}$ on $[-1,1]$ and $1/\sqrt{x}$ on $[0.0005,1]$ with 12-bit absolute and relative precision, respectively, at ring degree $\log N=15$. For batches of 512 inputs, $\mathsf{SWIFT}$ achieves speedups of $3.94\times$ and $2.86\times$ over the corresponding CKKS baselines for $\mathsf{ReLU}$ and $1/\sqrt{x}$, respectively. Compared with latency estimates of DM/CGGI-based methods, $\mathsf{SWIFT}$ achieves lower latency for $\mathsf{8\text{-}to\text{-}8\ LUT}$ and $\mathsf{12\text{-}to\text{-}12\ LUT}$ at batch sizes as small as 32 inputs.

The recent study of fixed-key differential probabilities mainly follows two complementary approaches. The first derives key-dependent constraints from the internal structure of the primitive. This approach is intuitive, but a complete theory is difficult to build. The second approach is based on quasidifferentials. It is complete in theory when all quasidifferentials are considered, but exhaustive enumeration is usually infeasible in practice. In this paper, we relate quasidifferentials to concrete key-dependent constraints. This gives new insights into quasidifferentials. Each quasidifferential with a nonzero mask carries one relation, equating a linear parity of the involved key bits to a generally nonlinear Boolean function of the intermediate-state bits, and the relations that share these bits together constrain the key. Under the common threshold-based treatment, where only quasidifferential trails with sufficiently large absolute correlation are kept, some constraints on intermediate-state bits may be lost. This can produce an incomplete quasidifferential trail set with respect to the induced intermediate-state constraints. This, for example, can cause the fixed-key differential probabilities computed by quasidifferential aggregation to become negative on some key subspaces. To obtain a more precise distribution of fixed-key differential probabilities over the key space, we decouple quasidifferential trails according to their induced constraints. After decoupling, each resulting quasidifferential trail set is locally complete, hence satisfies the vector-space condition of Beyne and Rijmen as a coordinate subspace, so the derived probability distribution for the particular subspace is always valid. The decoupling also reduces the number of trails in each set, improving the efficiency of the quasidifferential method. As a result, our method yields a finer-grained key-space partition that could allow us to better approximate the true distribution under the quasidifferential framework. We instantiate this decoupling strategy in the threshold-based setting and apply it to differential trails of GIFT-64, GIFT-128, SKINNY-64, SKINNY-128, and RECTANGLE. The resulting locally complete trail sets always give valid fixed-key differential probability distributions and are no coarser than direct threshold-based quasidifferential aggregation. They coincide with direct aggregation when the retained trails are already locally complete. In our experiments, using our decoupling method is actually better for many evaluated trails and refines the key-space restrictions reported by prior constraint-detection frameworks. As each quasidifferential is a constraint, the same insight also lets us write the induced linear and nonlinear key constraints explicitly for the bit-wise ciphers GIFT-64, GIFT-128, and RECTANGLE, addressing a limitation of the Trail-Estimator constraint detector.

Synchronized multi-signatures allow for non-interactive aggregation of signatures generated within the same time step. This primitive is particularly well-suited for high-throughput blockchain protocols like Ethereum, where many distributed signers must validate the same block within a synchronized slot. In this work, we present Lemur, a post-quantum synchronized multi-signature from (module) lattices that improves upon the state-of-the-art in efficiency, scalability, and flexibility. Lemur follows the blueprint of Squirrel/Chipmunk (CCS 2022/2023) but introduces a fundamental redesign of the foundations of the overall framework. Our revisit of the framework is also motivated by the fact that our evaluation of Chipmunk's parameter sets, using the state-of-the-art lattice security estimation methods, suggests a substantially lower concrete security level (approximately 30 bits rather than the claimed 112 bits). First, we revisit the underlying building block of key-homomorphic one-time signature (KOTS) and introduce a novel security reduction based on a new lattice problem: the Dual Hint-MLWE assumption, which may be of independent interest. We then provide a formal reduction from the standard Module-LWE problem to Dual Hint-MLWE, which overall enables us to base the security of Lemur on the standard Module-LWE and Module-SIS assumptions. By shifting from a statistical security argument to a computational one, our KOTS design enjoys much better compactness and scalability. Second, we optimize the underlying homomorphic vector commitment (HVC) by transitioning from Ring-SIS to the Module-SIS setting and extending the commitment domain from vectors to matrices. This generalization reduces opening size and improves aggregation efficiency. After rectifying the parameters of Chipmunk for a fair comparison, our results show that Lemur's KOTS size achieves up to an order of magnitude improvement over Chipmunk's KOTS. In particular, aggregating 1 million one-time signatures requires under 8 KB. For the total multi-signature size, Lemur demonstrates around $2\times$ improvement over Chipmunk. To showcase our design, we provide a full-fledged Rust implementation. Our benchmarks demonstrate an aggregate signature size of 380 KB for $2^{20}$ signers. Stateful signing takes roughly 4.2 ms for a Merkle tree of height 20, while batch verification for an aggregate of 1024 signers completes in 15.0 ms ($\approx$ 14.6 $\mu$s per signer).

We study generic committing attacks—where ciphertexts decrypt under more than one context, i.e., key, nonce, associated data—for sponge-based authenticated encryption. As our main contribution, we give three new committing attacks which outperform existing attacks. One of our attacks provides a counterexample showing that the previous proof for the committing security of Ascon-like schemes with zero-padding does not extend to all parameter choices: in case of 128-bit tags and 256-bit zero-padding, the existing analysis claims 192-bit security; our attack reduces this by 62 bits down to 130-bit. Our attacks are applicable to the standardized scheme Ascon. As a further contribution, we analyze existing attack strategies for a generic sponge construction with various design features such as key-blinding, zero-padding, and state-update-functions.

Asynchronous distributed key generation (ADKG) is a fundamental primitive for building threshold cryptosystems and fault-tolerant distributed protocols in adversarial network settings. A central objective in this line of work is to achieve ADKG with $O(n^2)$ communication and constant round complexity under minimal setup assumptions. Recent progress has led to subcubic-communication ADKG protocols under different trade-offs. Feng and Tang (CRYPTO 2025) presented an ADKG protocol with $O(n^2)$ communication and $O(1)$ rounds, but at the cost of a cubic-communication setup phase in which each party posts a linear-sized public key on a public bulletin board. In contrast, Abraham et al. (PODC 2026) achieved an ADKG protocol with a standard setup phase, where each party posts only a constant-sized public key, but with $O(n^{2+1/k})$ communication and $O(k)$ rounds for a tunable parameter $k\leq \log{n}$. These results leave open whether one can simultaneously obtain constant-round complexity and quadratic communication under a standard setup phase. In this work, we resolve this open problem by presenting the first ADKG protocol that achieves $O(n^2)$ communication and $O(1)$ rounds while requiring only a standard setup phase in which each party posts a constant-sized public key on a public bulletin board. Our protocol is resilient to a strongly adaptive adversary corrupting up to $f < n/3$ parties and assumes only random oracles and secure erasures, both of which are also assumed by prior subcubic-communication ADKG constructions.

This paper introduces a geometric framework for Q2 quantum distinguishers by combining the geometric approach to classical symmetric-key cryptanalysis with the generalized correlation extraction algorithm. Our main technical tool shows that one superposition query, followed by appropriate (unitary) change-of-basis operations, prepares a ``correlation state'' whose amplitudes are the entries of the geometric correlation matrix in the chosen basis. This yields a unified preparation-measurement template that recovers several known quantum distinguishers: (1) hidden structure detection via support constraints in Fourier-type bases (e.g., Simon, Bernstein-Vazirani, Deutsch-Jozsa), and (2) event probability deviation tests via amplitude estimation (covering standard quantizations of linear and differential distinguishers). We analyze when relevant distinguishing mass is diluted across many basis states, identify it as a cause of poor query efficiency in several recent distinguishers, and provide basis-specific mechanisms to concentrate the signal (phase-oracle row restriction in the Fourier setting; chosen-plaintext subset-state restriction in the quasidifferential setting) to restore quadratic advantage. We illustrate the framework on Fourier and quasidifferential instantiations and discuss obstacles for non-unitary integral bases.

In this paper we introduce a simple and unified approach, based on generic proof systems, to prove knowledge of any isogeny between two principally polarized abelian varieties in any dimension, assuming that the $2^m$-torsion is accessible for sufficiently large $m$. Previous generic proof approaches were only able to prove knowledge of a smooth degree isogeny between elliptic curves, where for each small prime factor $\ell$ of the degree, bespoke constraints had to be derived, typically from (a variant of) the $\ell$-th modular polynomial. Our approach is much simpler in that it relies on proving knowledge of a $2^n$-isogeny between two principally polarized abelian varieties in any dimension. Furthermore, our approach is unified in that the constraints are essentially the same for each dimension, resulting in a simpler and easier-to-optimize algorithm. Our construction has immediate applications to proving knowledge of an isogeny of any degree between two elliptic curves, by using a higher dimensional representation. Indeed, by a result of Robert, any isogeny can be embedded in a $2^n$-isogeny by increasing the dimension, and conversely, the knowledge of a $2^n$-isogeny between products of varieties implies the knowledge of an isogeny of degree $\leq 2^n$ between a factor of the domain and codomain. Our generic proof does not disclose the degree of the secret isogeny, nor does it rely on knowing the endomorphism ring, thereby solving an open problem posed by Beullens, De Feo, Galbraith, and Petit in 2023. Two use cases are immediate. First, if one wants to prove knowledge of any isogeny between two supersingular curves over $\mathbb{F}_{p^2}$, e.g. during the generation of an elliptic curve with unknown endomorphism ring. Second, to prove knowledge of a secret isogeny coming from the class group action on oriented supersingular elliptic curves, e.g. CSIDH with curves defined over $\mathbb{F}_p$. Computing such group actions is typically done using qt-Pegasis, which naturally results in a 4-dimensional representation of the isogeny. Lastly, we propose two tailored zero-knowledge proof systems that improve proving time and proof size without loss of generality and provide the first implementation in dimension 2 and 4 by implementing both proof systems in Rust.

We present improved distributed broadcast and MST algorithms that are unconditionally secure against an eavesdropper controlling a fixed set of at most $f$ edges in an $n$-node $m$-edge $D$-diameter graph. We strive for secure algorithms with sublinear round and subquadratic message complexities (in $n$) for any $f$. This is in contrast to the exponential or polynomial dependence on $f$ in prior works. Our main results are: Secure broadcast algorithm, for sending an $O(\log n)$-bit message, that runs in $\tilde{O}(D+\sqrt{n})$ rounds and $\tilde{O}(n^{3/2})$ messages. This matches the state-of-the-art bounds for \emph{insecure} broadcast by [Ghaffari and Kuhn, and Gmyr and Pandurangan, DISC 2018]. Our bounds also improve over the $\tilde{O}(D+\sqrt{f n})$-round complexity and $\tilde{O}(\sqrt{f n}\cdot m)$ message complexity of secure broadcast by [Hitron, Parter and Yogev, DISC 2022]. Secure MST algorithm with sublinear round and subcubic message complexities that improve over the algorithm by [Hitron, Parter and Yogev, ITCS 2023] in the entire regime. In particular, when $f=\Theta(n)$, we improve the round complexity from $\tilde O(n^{3/2})$ to $\tilde O(n^{2/3})$, and the message complexity from $\tilde O(n^{3})$ to $\tilde O(n^{7/3})$. Our algorithms are randomized and their correctness and (statistical) security hold with high probability. The algorithms are based on a combination of techniques: Karger's sampling, tree packing and sparse recovery sketches.

Proximity testing is crucial to location-privacy applications, from discovering nearby friends to enabling UAV collision avoidance. In such settings, users must determine proximity without revealing their exact locations. This motivates privacy-preserving proximity testing (PPPT) protocols revealing only if the proximity condition holds, while hiding both parties’ inputs. However, most existing PPPT protocols rely on strong assumptions (e.g., non-colluding servers) or require simultaneous interaction, limiting their practicality. Moreover, they typically define proximity using metric distances (e.g., Euclidean distance), failing to support richer membership queries for complex regions like buildings or parks. To address these, we introduce a new primitive called Geometric Fuzzy Matching (GFM), which generalizes fuzzy matching to arbitrary $n$-dimensional regions. In GFM, the receiver specifies a region and learns only whether the sender’s location lies within it, without revealing either party’s input. This approach captures both classical distance-based proximity checks (for any Minkowski $\ell_p$ norm, $1 \leq p \leq \infty$), as well as membership tests for complex regions, providing a unified framework for diverse proximity queries. In low-dimensional settings, our protocol improves on distance-based checks compared to state-of-the-art van Baarsen et al. (EUROCRYPT 2024) for $\ell_\infty$ and maintains stable practical efficiency for $\ell_p$ norms under large distance thresholds or for $p \geq 4$, where previous approaches quickly become computationally prohibitive. It is also the first to support fuzzy matching over arbitrary geometric regions, enabling proximity queries in complex spaces. Our implementation confirms these results and demonstrates the protocol’s efficiency and applicability across diverse PPPT scenarios.

A leakage-tolerant circuit (LTC) can be viewed as a black-box implementation of a given functionality f with respect to a leakage class L in the sense that any leakage function L ∈ L applied to the circuit’s internal wires can be simulated by a similar leakage function L′ ∈L applied only to the circuit’s inputs and outputs. Previous works have demonstrated extensive applications of LTCs in constructing variants of leakage-resilient circuits (LRC): black-box construction of both stateless and stateful LRCs, and construction of deterministic stateful LRCs which only require external fresh randomness in the first invocation. However, feasibility results for LTCs are still limited to simple leakage classes, including only probing leakage, depth-1 AC0 leakage, and parity leakage. In this work, we instantiate the study of constructing LTCs and deterministic stateful LRCs against AC0 leakage, obtaining the following results: – We present the first construction of LTCs against generic AC0 leakage. As a corollary, we also construct LTCs against parity leakage with efficient simulation, refuting a conjecture proposed by Ishai and Song (Eurocrypt 2024). – We provide a generic framework to convert LTCs into computationally secure deterministic LRCs assuming one-way functions, and instantiate the paradigm for k-CNF leakage (with a sufficiently small k). This is the first instance of deterministic stateful LRCs against non-decomposable leakage.

Public-key authenticated encryption with keyword search (PAEKS), introduced by Huang and Li (Information Sciences 2017), was proposed to provide trapdoor privacy, whereby keyword information is protected from being revealed through trapdoors. To prevent the keyword guessing attack, however, a trapdoor needs to be generated separately for each sender, and the search complexity linearly grows with the number of senders even when searching for a single keyword. To address this inefficiency, we propose a generic construction of search-efficient PAEKS. We revisit the group-oriented approach of Wang et al. (IEEE Transactions on Information Forensics and Security 2024), in which senders are organized into sender groups. Our construction is simple yet effective where all senders belonging to the same group share a single public-secret key pair, and the search complexity depends only on the number of sender groups rather than the number of individual senders. We further introduce ciphertext indistinguishability against insiders, which ensures that no keyword information is revealed from ciphertexts, even if they are generated by other members of the same sender group. We also take into account an impossibility result by Yoshida and Emura (IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, 2026), which shows that trapdoor privacy against sender-group members cannot be achieved in the scheme of Wang et al. To address this limitation, we introduce trapdoor indistinguishability against outsiders, which guarantees that no keyword information is revealed from trapdoors generated for non-group members. Our generic construction yields search-efficient group-oriented PAEKS schemes from pairings and lattices.

Malicious-secure multiparty computation protocols protect against an adversary's arbitrary misbehavior. In the honest-majority four-party setting, one common technique relies on all communication between parties being duplicated. Under this approach, all correct messages are sent twice, while corrupted messages are only sent by the adversary and will not match concurrent correct messages. When a receiver observes that inconsistency, it announces cheating has occurred (and possibly aborts). Existing implementations often optimize this procedure by batching many such checks into a single hash and running a final consistency check just before revealing the result of a computation. Brüggemann and Schneider (Eurocrypt 2026) recently showed that these delayed consistency checks in honest-majority, malicious-secure protocols can violate privacy. Adversaries can introduce errors such that subsequent incorrect hashes reveal their missing secret share and allow plaintext secrets to be recovered just before the honest parties abort. Their suggested fix evaluates the hash comparison under multiparty computation, rather than in plaintext. In this report, we detail our fix for the Fantastic Four protocol in ORQ, a recent system for secure analytics that is vulnerable to the attack. The new implementation has a modest overhead that amortizes with larger inputs. The complexity of the modified protocol highlights the difficulty of implementing malicious-secure systems in practice; even seemingly harmless optimizations can break privacy.

In practice, the amount of side channel leakage related to the random polynomial generation of Dilithium can be limited. In this case, the coe cients of the random polynomial may not be recovered accurately, which then makes the secret key recovery with least square a difficult problem. Therefore, how to recover the secret key used by Dilithium with noisy equations becomes a meaningful concern. In light of this, the ne-grained residual interval screening is proposed to enhance the ability of least square to recover the secret key used by Dilithium. The core idea is to estimate the distributions of the residuals related to both correct and erroneous equations computed with the least square recovered candidate secret key in a pro ling scenario. Then, according to the distribution di erence of the residuals related to two types of equations, an interval can be screened. Note that a majority of erroneous equations are out of the screened interval while a majority of correct equations are in the screened interval. Therefore, least square can be used to recover a more accurate candidate secret key polynomial with equations in the screened interval. By iterating the process several times, the secret key polynomial can be successfully recovered. The e ciency of the proposed technique is veri ed with power traces measured from the Dilithium reference implementation running on a Cortex-M4 processor. The evaluation results show that only several hundreds of power traces are enough to recover the secret key used by Dilithium.

At CRYPTO 2025, Bhaumik et al. formalised the notion of Key Control (KC) security of Key Derivation Functions (KDFs). A KC adversary, on seeing the root key of a KDF, attempts to manipulate its auxiliary inputs (the `Context' string) to obtain a derived key from a pre-selected set of keys. In this paper we extend the notion of KC security to Key Combining Functions, which are KDFs that convert two root keys to a single derived key; we name the new notion Combining Key Control (CKC) security. We then investigate the CKC security of KDF Combiners and show that (up to certain limitations) it follows from the KC security of either of the component KDFs.

We show that private-key function-hiding inner-product functional encryption (FH-IPFE) is impossible in the generic group model (GGM). This impossibility extends to (non-compact) two-input quadratic functional encryption (QFE) under a weak security notion that allows only a single key corruption. Our results apply both to the variant where decryption outputs the result directly, and to the variant where the result is encoded in the exponent of a group element. Our results hold in both Maurer’s and Shoup’s model, with different tradeoffs. In Maurer’s model, we prove that FH-IPFE over $\mathbb{Z}_q^n$ cannot be realized even when $q^n$ is polynomially bounded. Here, $q$ denotes the modulus of the inner-product functionality, not the order of the underlying group. This stands in sharp contrast to non-function-hiding FE, which can be constructed from minimal assumptions (one-way functions in the private-key setting and public-key encryption in the public-key setting) whenever the set of functions is polynomially bounded. We extend this impossibility to Shoup’s model when $q^n$ is super-polynomial. Conceptually, our proof simulates any construction in Shoup’s model as one in Maurer’s model equipped with a random oracle. Our techniques may be of independent interest, offering a general method for upgrading other impossibility results from Maurer’s model to Shoup’s model. We match these negative results with two positive ones. First, we show that one-sided bounded FH-IPFE (i.e., either the number of key queries or the number of encryption queries is bounded) can be realized from one-way functions. Second, when both the number of key queries and encryption queries are bounded, we show the resulting notion of FH-IPFE can be achieved information-theoretically. These positive results show that our impossibility precisely characterizes the threshold for FH-IPFE.

A zero-evading generator with error parameter $\lambda$ is a distribution $Z$ on $\mathbb{F}^n$ such that for any non-zero vector $x\in \mathbb{F}^n$ the probability that $<a,x>=0$ is at most $2^{-\lambda}$, when $a$ is chosen according to $Z$. We investigate the number of additions required to compute $<a,x>$ given $x$. The traditional construction chooses a vector $a$ with random $\lambda$-bit elements. Pippenger's algorithm gives an additive complexity of at least $\Omega(\lambda n/\log n)$ for this approach. We give a construction requiring only $O(n+\lambda)$ additions. We highlight the impact of reducing the number of additions on aggregation of group-based commitments, such as KZG commitments[KZG10].

Two post-quantum upgrades to TLS 1.3 are being standardized in parallel: a hybrid key exchange (already deployed) that runs an elliptic-curve Diffie-Hellman exchange alongside ML-KEM, and a standalone mode that uses ML-KEM on its own. The Internet-Draft draft-usama-tls-risks-of-mlkem points out that the machine-checked symbolic proofs of TLS 1.3 rely on the commutativity of Diffie-Hellman, which ML-KEM does not share: a key encapsulation mechanism is asymmetric, one endpoint generating a key pair and the other encapsulating against it. The existing proofs therefore no longer apply, a new one is needed, and the draft argues that hybrids should be preferred. We supply that proof. We extend the reftls ProVerif models with a faithful, non-commutative KEM and analyze classical (EC)DHE, standalone ML-KEM, and the hybrid together, as unbounded concurrent sessions against a single active attacker free to break any cryptographic component. The central result is a sharp and tight contrast in robustness: standalone ML-KEM is a single point of failure, secure only while ML-KEM itself is unbroken, whereas the hybrid stays secure as long as either of its components survives: an attacker must break both, in one session, to learn anything. This single point of failure reaches authentication as well as confidentiality: with the sole key-exchange secret exposed and no secret pre-shared key salting the key schedule, the server Finished message becomes forgeable, so a client can complete a handshake that no server completed, while the hybrid stays safe unless both components break. The three modes also interoperate without ever confusing one another's keys, so migrating from (EC)DHE to a hybrid is a strict improvement. Two further experiments address the draft's remaining concerns: reusing an ML-KEM key forfeits the forward secrecy that an ephemeral key preserves, and a principal acting as both initiator and responder exposes no role-confusion attack arising from the asymmetry. At the symbolic level, and under stated assumptions, the analysis substantiates the draft's case for preferring hybrid key exchange.

We present the first constant-expected-latency protocols for Interactive Consistency (IC), also known as Parallel Byzantine Broadcast, that achieve either: (1) security in dishonest majority, namely $t \leq (1-\varepsilon)n$ for any constant $\varepsilon\in \Omega(1)$; or (2) quadratic communication $O\!\left(n^2(L_{in}+\kappa)\right)$ in honest majority (i.e., $\varepsilon >1/2$). In IC, $n$ processes must agree on a vector that maps every honest process to its input of size $L_{in}$, despite up to $t$ dishonest (Byzantine) processes that may collude and behave arbitrarily. IC is the strongest one-shot distributed task: by fully determining the honest input configuration, it subsumes every other solvable one-shot task in the same model. Moreover, most multiparty computation protocols rely on IC as a building block. These guarantees are qualitatively optimal. First, Garay, Katz, Koo, and Ostrovsky (FOCS~2007) rule out constant-round protocols unless the honest fraction is constant. Second, Pease, Shostak, and Lamport (JACM~1980) rule out setup-free information-theoretic solutions once $n\leq 3t$. Thus, to overcome this barrier, we rely on cryptographic objects of size $\kappa$, obtaining correctness with all but negligible probability in $\kappa$ against any adversary running in time polynomial in $\kappa$. This includes digital signatures, for which the corresponding public keys must be published on a bulletin-board public key infrastructure before the protocol begins. Third, IC trivially requires \(\Omega(n^2L_{in})\) communication, since every honest process must learn the inputs of all honest processes. Our results follow from a single generic compiler that transforms any constant-expected-latency Byzantine Broadcast protocol into an IC protocol with the same latency profile.

This short note shows that the conventional (2-subset) bit-based division property trail search problem is NP-complete.

We study the inherent barriers to constructing non-adaptively sound succinct non-interactive arguments (SNARGs) for NP with a CRS whose length is sublinear in the witness length. Our results cover both the standard SNARGs and SNARGs with an additional updatable feature (i.e. incrementally verifiable computation for NP). - For updatable SNARGs, we show a black-box separation from falsifiable assumptions for uniform polynomial-time reductions, assuming sub-exponential hardness of learning with error. - For general SNARGs, we show a black-box separation from falsifiable assumptions for non-uniform polynomial-time reductions that only non-adaptively make an instance-size-independent number of queries to the adversary, assuming the existence of sub-exponentially secure super-bit generators. We observe that all known SNARG constructions from polynomial hardness of standard assumptions have 1-query soundness reductions. Thus, our result complements existing constructions. Previously, the seminal work [Gentry-Wichs, STOC'11] showed a black-box separation of SNARGs from falsifiable assumptions in the adaptive soundness setting. We explore whether any barriers exist in the non-adaptive setting. To obtain our result, we derive a simulation lemma for unbounded polynomial-length auxiliary inputs assuming super-bit generators.

We initiate the study of the algorithmic complexity of finding collisions in single-layer binary neural networks. Given a random matrix $\mathbf{A} \in \mathbb{R}^{m\times n}$, an input $\mathbf{x} \in \{-1,1\}^n$ is mapped to a binary output vector $\varphi(\mathbf{A}\mathbf{x})\in \{-1,1\}^m$, where $\varphi$ is an activation function with constant behavior on $[\kappa, \infty)$ for some threshold $\kappa \geq 0$. We identify the threshold scale $\kappa=\Theta(1/\sqrt{\alpha})$, where $\alpha=m/n$, as separating two complementary phenomena. When $\kappa \ll 1/\sqrt{\alpha}$, we give a simple online algorithm that efficiently produces extensive collisions. When $\kappa \gg 1/\sqrt{\alpha}$, for a natural randomized non-periodic activation and suitable oscillation complexity, we prove that the extensive-collision space exhibits an overlap gap property (OGP), yielding an exponential lower bound against online algorithms. Ours is the first work to use the overlap gap property as a rigorous criterion for collision resistance. The key difference between collision finding and average-case search is that collision finding has a new 'worst-case' aspect: the collision finder has full control over the choice of colliding pairs. Our lower bound is proved in the online model; extending such guarantees to broader classes of algorithms, including spectral, algebraic, lattice-based, or quantum methods, remains an open direction.

We construct a new framework for cryptographers to work with principally polarized abelian varieties (PPAVs). This framework offers a computational approach to abelian varieties agnostic to the choice of a coordinate system, culminating in the definition of an efficient model for principally polarised abelian varieties. We exhibit an instantiation of our framework by means of the theta model, thereby streamlining the documented capacities of the model, and extending them with new fundamental algorithms, like the computation of automorphism groups. Our framework focuses on what can be done with these objects, computationally, while relegating low-level considerations to the background, like the specific choice of a coordinate system (and thus the necessity to rely on Mumford's theory of theta coordinates). We illustrate the utility of our framework by proving that we can interpolate polarised isogenies in any dimension, generalizing to higher dimensions the most disruptive algorithm for elliptic curves in recent years. We prove that this interpolation offers a universal, canonical, and compact way to represent isogenies.

We introduce DASTE, a decentralized encryption primitive for auditable access control in settings where users independently generate public keys, register them on an immutable ledger, and decrypt only through collaboration. In DASTE, a sender encrypts under an access structure (e.g., an access tree / LSSS) whose leaves are concrete registered public keys selected at encryption time. A ciphertext can therefore be opened only by a qualifying coalition of registered key holders that jointly reconstructs the masking secret. DASTE is designed for dynamic policy-governed environments in which access conditions may need to change after encryption. To support this, we provide ciphertext-only policy evolution operations, including semantically neutral insertion, threshold escalation, subtree revocation, and ciphertext rerandomization, that update ciphertexts without reissuing user secret keys and without requiring plaintext access. We give two instantiations: a classical discrete-log-based construction, included as a conceptual baseline, and a post-quantum construction based on decisional Ring-LWE. For the RLWE construction, we prove coalition-bounded IND-CPA security via a standard hybrid argument. Together, these results yield a ledger-anchored, access-structured, post-quantum threshold encryption framework suitable for decentralized key management and governance-oriented decryption workflows.

The Fiat-Shamir transform is a central tool in cryptography and understanding its soundness is both a theoretically challenging and practically pressing question. Correlation intractable hash functions offer a method to instantiate Fiat-Shamir in the standard model. In short, a hash function is correlation-intractable for a relation $\mathcal{R}$ if it is computationally hard to find an input $x$ such that $\mathcal{R}(x, \mathsf{Hash}(x)) = 1$. In this work we present the first construction of a correlation-intractable hash function family, where the complexity of the hash does not depend on the complexity of the relation. Besides being better aligned with the way Fiat-Shamir is used in practice, our construction implies correlation intractability for all (possibly inefficient) batched searchable relations, i.e., searchable relations that can be decomposed as a direct product of other searchable relations. Using complexity leveraging, we then compile our construction into correlation intractability for all sufficiently sparse batched relations. All of our results follow from the hardness of the decomposed short-integer solution (DSIS) problem, the natural search analogue of decomposed LWE, which we show to be at least as hard. As a direct consequence from prior work, our result implies that {sufficiently many parallel repetitions} of any perfectly complete public-coin three-message proof {for a language outside $\mathrm{BPP}$ are not zero-knowledge}. Moreover, we obtain non-interactive zero-knowledge (NIZKs) arguments for $\mathrm{NP}$ from the sub-exponential hardness of DSIS.

The Lattice Isomorphism Problem (LIP) is a computational problem that has recently been introduced into cryptography and is believed to be hard. Its search version, Search Lattice Isomorphism Problem (SLIP), is considered even harder than the Shortest Vector Problem (SVP), yet its complexity is still not well understood. Haviv and Regev (SODA 2014) showed that the decisional version (DLIP) lies in a statistical zero-knowledge class and is therefore unlikely to be NP-hard. This result does not apply to the search version, which motivates the question of whether NP can reduce to SLIP. Our main result answers this question negatively. We show that every language reducible to SLIP lies in AM and coAM, by analyzing the direct-sum structure of irreducible lattices. Consequently, NP cannot reduce to SLIP unless the polynomial hierarchy collapses, and there is no reduction from SVP to SLIP unless the polynomial hierarchy collapses. We also study several problems closely related to LIP and establish reductions between its search, counting, and decisional variants. These connections mirror known relationships for graph isomorphism. Finally, we propose a new algorithm that uses a KZ basis to compute an orthogonal decomposition of a lattice.

Unbiased and unpredictable randomness is a backbone of Web3 security, yet current Distributed Verifiable Random Function designs often entail a trade-off between performance and privacy. While established protocols like GLOW-DVRF achieve constant-size proofs, they rely on computationally expensive bilinear pairings that impose significant gas overhead in on-chain environments. Existing output-privacy frameworks, such as FlexiRand, are currently limited by the same expensive pairing-based operations that have high on-chain verification costs. In this paper, we present IcyVeil, an output-private DVRF that conjoins the architecture of FlexiRand with the pairing-free efficiency of Icy-DVRF. By integrating a blinding/unblinding mechanism directly into a FROST-inspired preprocessing scheme, IcyVeil enables users to mask inputs with a private nonce while the distributed committee generates partial evaluations and NIZK proofs over the veiled values. This approach eliminates the high cost of bilinear pairings during verification and maintains constant-size proofs. By adopting the pairing-free architecture of Icy-DVRF, IcyVeil inherits a 43% reduction in on-chain gas costs compared to conventional pairing-based protocols, establishing a scalable and cost-effective primitive for latency-sensitive applications such as decentralized gaming and asynchronous reward distribution.

In recent years, various RSA variants based on diverse algebraic structures have been proposed with the aim of enhancing its security. In this paper, we focus on type-A and type-B variants, which generalize RSA-type constructions over the ring of Gaussian integers modulo $N = pq$ and constructions based on the cubic Pell equation, respectively. First, we present a lattice-based method for finding, in polynomial time, solutions to the equation $xH(y)+cz\equiv 0 \bmod \beta$, where $H(y)$ is a monic polynomial, thereby generalizing previously established bounds. We then apply this method to factor the modulus in both type-A and type-B cryptosystems under multiple attack scenarios, such as partial key information attacks. Therefore, we provide certain bounds for the secret exponent under which these cryptosystems can be compromised.

Neural distinguishers for ARX ciphers can exploit information beyond classical difference distributions and several interpretability frameworks have been proposed. In this paper, we study two frameworks for SPECK32/64 by connecting their viewpoints: local constraints of modular addition and Fourier analysis of trained neural distinguishers. We show that the dominant Fourier parities of a raw-pair differential neural distinguisher can be rewritten in the local variables associated with the last modular addition. This representation separates value-dependent variant differential-linear terms from difference-dependent traditional terms, and explains their biases through specific local constraints and branch effects. We further extend the analysis to a boomerang right-quartet setting. We construct a neural distinguisher whose input is only the original ciphertext pair, while positive and negative samples are matched with respect to the observed ciphertext difference. Fourier analysis of this distinguisher reveals dominant value-dependent parities. We trace these terms to borrow synchronization in the first inverse step of the lower boomerang characteristic, yielding specific local conditions. Our results indicate that the dominant Fourier features learned in these settings are observable projections of concrete carry or borrow constraints of the ARX operation.

Private information retrieval (PIR) is a fundamental primitive for protecting user privacy. It enables a user to retrieve entries from a public database without revealing which entries are being retrieved. PIR has been studied in many settings, e.g., with information-theoretic or computational security, with a single server or multiple non-colluding servers, and with or without preprocessing to the database. In this article, we describe several PIR schemes that we believe are accessible to readers without prior knowledge in PIR. Although conceptually simple, these schemes capture the main ideas underlying mainstream design paradigms. We also describe extensions of PIR that support keyword queries and batch queries. Beyond describing the schemes themselves, we characterize the concrete efficiency of different PIR paradigms, provide guidance on selecting a paradigm in practice, and discuss practical applications of PIR. We hope this article helps readers understand the current research landscape in PIR and serves as a starting point for exploring more advanced topics in the field.

We introduce baseSPIDER and SPIDER, private information retrieval (PIR) schemes that embody two technical advancements. The baseSPIDER protocol operates with a single server and a stateful client that performs pre-processing and stores hints for future queries. In this setting, baseSPIDER introduces a new approach that matches the asymptotically optimal communication complexity of state-of-the-art schemes while improving constant factors--an advantage that is particularly significant for databases with large entries. In addition, baseSPIDER offers a conceptually simpler design relative to prior protocols. SPIDER operates over a default database interface and requires no cooperation from the server at any stage. To our knowledge, SPIDER is the first single-server PIR construction of this design, achieving privacy without specialized APIs, auxiliary server state, or protocol-specific interaction beyond conventional indexed access. SPIDER is built via a simple transformation of baseSPIDER to the default server setting, eliminating deployment barriers and enabling immediate applicability to existing systems. This transformation can be applied more broadly to three recent PIR solutions, adapting them for use in the default-server paradigm and yielding solutions of independent interest. SPIDER compares to the resulting modified solutions by exhibiting a simpler design while incurring higher client computational work.

Many modern SNARK constructions follow a paradigm that combines a Polynomial Interactive Oracle Proof (PIOP) with an appropriate Polynomial Commitment Scheme (PCS). In this paradigm, the PIOP reduces soundness to the verification of a collection of polynomial relations that are checked though oracle queries, while the PCS enables succinct commitments to the corresponding polynomials. Rather than transmitting the full polynomial representation, the prover commits to the polynomials and later provides evaluations at the points selected by the verifier. The verifier checks the consistency of these evaluation with the commitments and the prescribed polynomial relations. This combination of interactive polynomial queries and succinct commitments lies at the heart of the resulting argument system's efficiency, leading to compact proofs and efficient verification procedures. Focusing on this paradigm, we adopt the frontend and backend decomposition of SNARKs for general computation introduced by Thaler and develop a unified framework that refines this separation at a finer granularity. We present this framework as a single coherent structure and analyze its components in a systematic manner. Within this unified view, we incorporate lookup arguments and recursive proof composition, both of which are key to improving efficiency and applicability, as main components of the framework, showing how they interact with both the frontend and backend. This organization allows readers to reason clearly about the construction, composition and analysis of modern SNARKs.

A garbling scheme encodes a function and an input into two independent artifacts from which the output can be recovered, but nothing else is revealed. This clean separation between function and input has made garbling one of the most versatile primitives in cryptography. Yet it hides an asymmetry that has gone largely unexamined: while the input is cryptographically protected, the function is fully exposed to whoever performs the garbling. As garbling is increasingly deployed in settings where garbling is delegated to untrusted infrastructure, published on public ledgers, or distributed among multiple parties, this asymmetry becomes a fundamental barrier. The function, which may encode proprietary models, confidential policies, or sensitive decision logic, is leaked unconditionally to the garbling server. We introduce oblivious garbling, a new paradigm that closes this gap. In our framework, the garbler receives only a designated leakage of the circuit and remains oblivious to everything else. We present the first construction instantiating this notion where the leakage is the circuit topology alone, achieving linear complexity with no blow-up in the size of the garbled circuit. The construction extends to the malicious setting with no asymptotic overhead. Beyond its theoretical contribution, oblivious garbling has immediate practical consequences: it enables outsourced garbling without function exposure, garbling on untrusted hardware without leaking proprietary logic, and a multi-party garbling protocol in which no garbling party learns the function, all without resorting to universal circuits.

Side-channel attacks are a relevant threat to many modern cryptographic schemes and often have fatal consequences such as revealing partial information about secret keys. While leakage-resilient cryptography aims to solve this problem, existing works focus exclusively on showing security against classical leakage. Moreover, recent public key encryption (PKE) schemes utilizing quantum secret keys achieve security against unbounded classical leakage, but offer no guarantees on any amount of quantum leakage. Since security guarantees on classical side information do not necessarily translate to guarantees on quantum side information, showing PKE schemes that are secure in the presence of quantum leakage remains open. In this work, we address this problem by extending the definition of leakage resilience for PKE in the bounded-leakage model to allow for quantum leakage. We provide the following two constructions: - PKE with Quantum Secret Keys: We construct a PKE scheme that tolerates unbounded classical leakage alongside bounded, constant-rate ($\lambda <0.057$) quantum leakage. Our construction assumes the existence of polynomially secure post-quantum indistinguishability obfuscation (iO) as well as one-way functions (OWFs). - PKE with Classical Secret Keys: We construct a classical PKE scheme that is secure against bounded quantum leakage. Our construction offers a tradeoff between the achievable leakage rate and the underlying cryptographic assumptions. Assuming the hardness of the learning with errors problem (LWE) we obtain an optimal leakage rate of $\lambda \leq 1-o(1)$. Alternatively, assuming only post-quantum PKE, we obtain a leakge rate of $\lambda\leq \frac{1}{poly(n)}$.

The idea of Hybrid Homomorphic Encryption (HHE) is to reduce the computational cost of Fully Homomorphic Encryption (FHE) by encrypting bulk data symmetrically while only encrypting the short symmetric key homomorphically. Its efficiency depends on the multiplicative depth of the symmetric cipher's decryption circuit, motivating FHE-friendly designs. The Learning Parity with Noise (LPN) problem is a natural candidate for such designs, as it gives rise to simple encryption and decryption circuits over binary fields. In this context, Fouque, Hadjibeyli, and Kirchner proposed LPN-based symmetric encryption schemes based on the LPN-C cryptosystem of Gilbert et al. LPN-C is attractive for HHE while allowing parameter choices that bound decryption failures. However, the concrete security of LPN-C and its HHE-oriented variants remains poorly understood. We quantify how enforcing bounded noise via rejection sampling reduces the observed noise rate, an effect not captured in prior analyses. This yields immediate speedups for all attacks based on LPN instance solving. We then extend the Arora-Ge-style algebraic attacks to the bounded-noise setting and derive new bounds on the dimension of the induced linear spaces, refining and partially correcting earlier analyses. We show that some parameter regimes are more robust than previously estimated, while new algebraic strategies yield the best known attacks in others. Overall, our results improve our understanding of the concrete security of LPN-based symmetric encryption schemes, informing parameter selection for FHE-friendly variants.

In 2020 and 2024 respectively, NIST released a Special Publication (SP 800-208) and a Federal Information Processing Standard (FIPS 205) specifying hash-based signature schemes with natural quantum resistance thanks to their symmetric foundation. The former recommends the stateful hash-based signature schemes LMS and XMSS, whereas the latter standardizes their stateless counterpart SPHINCS+. While in principle all three constructions can be instantiated with any secure cryptographic hash function, the concrete instances recommended by NIST are currently limited to either the SHA-2 or the SHA-3 family. Building on the maturity of these standardized families is of course a sensible choice. Yet, we argue that neither is particularly well suited for this purpose, especially once physical security matters. As an alternative we suggest pSquare-hash, an arithmetization-oriented family of lightweight tweakable hash functions. We demonstrate that such dedicated tweakable constructions ideally suit the instantiation and security requirements of hash-based signature schemes, potentially leading to efficiency advantages over standard concatenation-based approaches through either a reduction of the permutation size or the number of calls. With respect to physical security, the presence of the tweak enables a clean separation between inputs that need to be protected against leakage/faults and those that are insensitive. The arithmetization-oriented nature and choice of prime enable the effective utilization of masking schemes with superior passive and active attack resistance (e.g., prime-field and/or inner-product masking) and keep the design suitable for zero-knowledge applications. We compare higher-order masked software (Cortex-M4) and hardware (NanGate 15 nm) implementations of pSquare-hash to equivalent SHA-2, SHA-3, SKINNY-Hash, Ascon-Hash and Poseidon2 instances and exhibit favorable characteristics whenever masking is applied.

Shor's algorithm represents the main threat of quantum computers to cryptography. In order to precisely understand its feasibility, many authors have worked towards reducing its costs, either at the logical level (assuming a fault-tolerant architecture), or at the physical level (taking into account the constraints of envisioned hardware). In particular, recent works by Chevignard et al. (CRYPTO 2024) and Gidney (arXiv 2025) used improved arithmetic to significantly reduce the qubit cost of factoring RSA public keys. Even more recently, Babbush et al. (arXiv 2026) improved the cost of computing elliptic curve discrete logarithms, with a reduction of a factor 2 to 3 in gate count and qubit count compared to a previous work by Litinski (arXiv 2023). Their result relies on optimized point addition circuits on elliptic curves over prime fields. However they did not reveal their logical quantum circuits, relying instead on a zero-knowledge proof. In this paper, we detail a quantum logical circuit architecture which gives similar results as Babbush et al., with a slightly higher number of qubits (around 1.5% increase) and a slightly smaller Toffoli gate count (between 6.5% and 10% reduction) for the curve secp256k1. We also give gate counts for a generic variant of the circuit, which is valid for any prime field.

We explicitly construct and benchmark the first lattice-based IVC scheme from folding. The scheme supports customizable constraint systems over rings which we exploit to obtain proofs of correct execution of an FHE bootstrapping, a critical component of verifiable FHE. Notably and of independent interest, we introduce a novel CCS relation capable of performing automorphism stability checks which yields better expressivity for CCS over rings. We use this new relation to arithmetize the folding scheme verifier as well as TFHE's bootstrapping operation, and measure the performance of our folding scheme implementation on this arithmetization. Benchmarks indicate smaller proofs compared to the state of the art at the cost of a sharp increase in prover and verifier time. Lastly, we consider the security of folding-based IVC schemes with a super-constant number of recursive rounds and give an argument for the knowledge soundness of our construction in the ROM. Our work also discusses and highlights key open questions for future work, such as the design of hash functions over rings that permit efficient arithmetizations.

Pseudo-random correlation generators based on the Quasi-Abelian syndrome decoding problem were first attacked in an article published at Asiacrypt~2025, using compressed sensing. In this paper, we revisit the security of the problem using a more traditional cryptanalytic tool, namely correlation attacks. As a result, we get a new cryptanalysis which outperforms the attack from Asiacrypt 2025 in several directions. It allows recovery of secret error polynomials with larger Hamming weights, runs approximately $1\,000$ times faster and uses $1\,000$ times less memory over $\mathbb{F}_3$. Over $\mathbb{F}_4$, the speed-up and memory gain are even higher. Due to this new attack, it becomes necessary to entirely revisit the parameters of several pseudo-random correlation generator proposals, including FOLEAGE.

Threshold cryptography distributes trust among multiple parties by enabling joint cryptographic operations without reconstructing secret keys. While post-quantum signature schemes based on the MPC-in-the-Head (MPCitH) paradigm are highly generic, recent impossibility results show that their thresholdization either incurs prohibitive distributed symmetric computations or leads to signature sizes growing with the number of signers. Achieving practical tradeoffs in this setting remains challenging. In this paper, we propose a generic framework for threshold MPCitH signatures based on Merkle-tree commitments. Our approach adapts the PIOP+PCS paradigm to the distributed setting by introducing and instantiating the notion of threshold polynomial commitment schemes (TPCS). We present a generic compiler combining a PIOP, a TPCS, and an arithmetic black box into a threshold signature scheme, and prove its unforgeability from the security of its components. We further provide a concrete Merkle-tree-based TPCS achieving moderate signature-size overhead, as low as 200 bytes per signer at the 128-bit security level. This is to be compared with an overhead of roughly 2 kB per signer for the previously suggested approach to thresholdize MPC-in-the-Head based on GGM trees. By compiling this TPCS with a standard PIOP, we obtain a generic threshold signature scheme from any hard problem or one-way function, which we showcase MQ-based and AES-based instantiations.

Functional adaptor signatures (FAS) are a novel cryptographic primitive introduced at CCS'24 that enable privacy-preserving, fine-grained data-payment exchanges between a seller and a buyer in a trustless and atomic manner. In this setup, the seller holds sensitive data \(x\) (e.g., patient records, climate data), and the buyer specifies a function \(f\) (e.g., aggregate, sum). FAS guarantees that the buyer learns \(f(x)\) (and nothing beyond) if and only if the seller receives payment in blockchain-based tokens. Unlike generic smart contracts, FAS-powered solutions excel in privacy, efficiency, and compatibility with diverse blockchain systems. However, prior FAS constructions were limited to linear functions (where $f$ was linear in $x$), restricting their applicability to more complex and prevalent applications including data analytics and ML model evaluations. In this work, we extend the capabilities of FAS to support higher-degree functions \((\textit{deg} \geq 2)\), significantly broadening its range of applications. Our core contribution is a novel FAS design leveraging homomorphic encryption, which simultaneously achieves enhanced efficiency and compatibility for general functions. This approach diverges fundamentally from the restricted design in CCS'24 which relied on connections to functional encryption. We implement our homomorphic encryption-based FAS for functions arising in applications such as data analytics and machine learning inference. Remarkably, even for linear functions, our new design achieves an order-of-magnitude improvement in performance compared to CCS'24 constructions. Furthermore, our solutions seamlessly integrate with prominent blockchain systems, requiring only a basic signature verification script on standard transactions, thus ensuring practical deployability. As a conceptual contribution, we introduce the general paradigm of a blockchain-based functional fair exchange (FFE) protocol, rigorously define buyer and seller fairness, and show that FAS implies the general goal of FFE.

Cryptocurrency lending is growing rapidly, and smart-contract-based loans are expected to grow further. However, existing systems are fundamentally limited: they only operate on smart-contract-enabled blockchains, and assets from other blockchains can be used only via tokenized representations. In this work, we propose an oracle-aided cryptographic protocol that implements the logic of collateralized loans without smart contracts, instead only requiring basic transactions from the underlying blockchain and hence, being compatible with limited-scripting blockchains, including Bitcoin. For that, we introduce verifiable graph encryption for signatures (VGES), a new cryptographic primitive that, on input a graph modeling the correspondence between transactions for collateral distribution (vertices) and loan repayments (edges), permits to encrypt the signatures on collateral-distribution transactions ensuring: (1) a signature can only be decrypted after completing loan repayments corresponding to a valid path in the graph from the root (graph enforcement); and (2) anyone can verify that encrypted signatures are valid and can be decrypted after doing the required loan repayments according to the graph (verifiability). We present two provably secure constructions of VGES and the evaluation of our implementation shows that they offer a tradeoff between the number of required on-chain transactions and off-chain computation, while both remain efficient on commodity hardware.

The concrete security of multivariate post-quantum signature schemes is coming under increasing scrutiny as the NIST standardisation process for additional signatures approaches its final stages. Among the leading candidates, the security of MAYO and QR-UOV relies on the hardness of the underdetermined multivariate quadratic (MQ) problem. This work revisits Hashimoto's algorithm for solving underdetermined systems of MQ equations, reinterpreting it as a computation of a pseudo-oil subspace. In light of this geometric point of view, we design a new algorithm that, by computing richer pseudo-oil structures, distributes algebraic work across more than two Gröbner Basis steps, subdividing the initial MQ problem into multiple subproblems that can be solved separately, while linearising multiple equations. Optimising a set of discrete parameters, we select the best trade-off between algebraic solving and combinatorial search. Concretely, our approach lowers the cost of the direct attack against Security Level I parameter sets of MAYO and QR-UOV by 7 and 8 bits, respectively.

A robust combiner for a cryptographic primitive $P$ takes multiple candidate constructions of $P$ and produces a secure construction of $P$ provided that sufficiently many of the candidates are secure. A closely related notion is that of a security amplifier, where given a weakly secure construction of $P$, we aim to obtain a (strongly) secure one. Intuitively, one may expect that any robust combiner should act as an amplifier by thinking of "good randomness" as inducing secure instances, and of "bad randomness" as inducing insecure instances. Formalizing this intuition, however, has turned out to be challenging. Despite significant progress, general results remain limited and confined either to specific primitives or only to the statistical setting. We establish a new framework of robust indistinguishability combiners, which greatly extends the class of combiners covered by prior work, and prove that they inherently act as security amplifiers. Our results extend to the computational setting, provided that the combiner makes a single query to each candidate. The new framework allows us to rederive previously known amplification results in a simplified manner, as well as prove new amplification results that have so far been out of reach. As our main application, we present the first security amplifier for functional encryption, resolving an open question that first arose in constructions of indistinguishability obfuscation, and for which a gap was discovered in previous proofs. Our amplifier transforms a weak scheme with any constant indistinguishability error into one with full negligible security.

The SHA-2 family is a U.S. federal standard and mainly includes SHA-256 and SHA-512. In particular, SHA-256 plays a central role in real-world applications and is widely regarded as one of the most important hash functions in use today. At CRYPTO 2026, Li et al. proposed collision attacks up to 37-step SHA-2, but they could not reach 38 steps due to the low-probability uncontrolled part in the corresponding differential characteristics. In this paper, we propose an improved search procedure to find high-quality differential characteristics for 38-step SHA-256 and SHA-512, respectively. Exploiting the special shape of the 38-step differential characteristics, the meet-in-the-middle method to fulfill the corresponding differential conditions is extremely memory-efficient. Consequently, we successfully achieve the first 38-step collision attack on both SHA-256 and SHA-512, whose time complexity is $2^{104.3}$ and $2^{125.4}$, respectively. The memory complexity of the 38-step collision attack is negligible. The methods are also applied to the 36-step and 37-step collision attacks on SHA-2 published at CRYPTO 2026, leading to a significant improvement in both time and memory complexity. In particular, the time complexity of the collision attack on 36-step SHA-256 is only $2^{57}$ and the memory complexity is negligible. We have verified this collision attack by providing the first colliding message pair for 36-step SHA-256. More remarkably, we apply the new method to 39 steps of SHA-2 and obtain the first effective collision attack on 39-step SHA-512, with a time complexity of $2^{178}$ and negligible memory complexity. However, the method does not yield an effective collision attack on 39-step SHA-256 due to the same issue arising from the low-probability uncontrolled part. Overall, this work further pushed the limit of memory-efficient collision attacks on round-reduced SHA-2 and significantly advances the state of the art.

Pre-constructed Publicly Verifiable Secret Sharing (PPVSS) extends conventional Publicly Verifiable Secret Sharing (PVSS) by requiring the dealer to publish a commitment or encryption of the shared secret, enabling more efficient and versatile constructions for a variety of cryptographic protocols. In this paper, we further enhance this paradigm by introducing Packed Pre-constructed PVSS (3PVSS), which allows a dealer to encode multiple secrets within a single polynomial while maintaining the pre-constructability property. We present two constructions of 3PVSS schemes. In the first construction, the dealer publishes a single commitment to all shared secrets, providing a compact representation that is particularly suitable for applications requiring efficient communication. In the second construction, the dealer publishes individual commitments to each secret, enabling greater flexibility in applications that require independent verification of multiple shared values. Both schemes preserve the key advantages of PPVSS, including the optimistic reconstruction approach enabled by pre-constructability. We demonstrate that these two variants naturally support different applications. Using the first 3PVSS construction, we revisit the ALBATROSS randomness generation protocol proposed by Cascudo and David (ASIACRYPT 2020) and present a more efficient variant with reduced computation and communication costs. As an application of the second construction, we extend the universally verifiable e-voting protocol recently proposed by Baghery, Knapen, Nicolas, and Rahimi (ACNS 2025) to support multi-candidate elections, while preserving universal verifiability. Our results show that the resulting protocols outperform their original counterparts in terms of efficiency.

This paper introduces AuditPay, a novel mechanism for blockchain mixers that enables controlled oversight through an ``auditing budget.’’ Auditors may monitor up to a budgeted number of addresses per epoch (e.g., an hour or a day), without revealing to users which addresses are monitored. Unlike traditional approaches that require users to voluntarily disclose viewing keys to trusted gatekeepers, AuditPay cryptographically enforces auditing compliance while preserving privacy for non-monitored user addresses and without introducing additional trust assumptions. At the core of AuditPay’s design is a selective encryption mechanism coupled with an efficient audit-key encoding scheme, enforced by a lightweight zero-knowledge proof. Users encrypt audit-relevant information under an audit key, which permits decryption only if the payment is to (or, alternatively, from) an address selected by the auditor for monitoring. We implement AuditPay as an Ethereum-based payment mixer and show through experiments on our prototype that its performance and gas-cost overheads are modest, providing a practical solution for balancing payment oversight with user privacy.

ML-KEM (FIPS 203) draws a fresh 32-byte coin at each encapsulation. The shared secret is a deterministic function of the public key and this coin, so a known coin is a recovered key. This is elementary. We ask instead how well the coin's secrecy is protected in practice, and we answer by experiment. On six unmodified libraries (OpenSSL 3.5, wolfSSL 5.9, AWS-LC, Go 1.26, Bouncy Castle 1.83, and CIRCL), and a from-scratch reference, the coin-recovery is reachable in every one; what differs is the guard, from a test-walled package in Go to an ordinary production call in wolfSSL. A second path needs no injection function at all: substituting the generator at build time makes the ordinary encapsulation predictable, while the public re-seed interface correctly refuses to. Outside the validated FIPS-140-3 configuration that most deployments do not yet use, the coin's secrecy rests on convention, not construction. The predictability this permits is externally invisible and parameter-controlled, of the class shown once before in Dual_EC_DRBG. We claim no backdoor; we claim only that the door is reachable, and say so while it is still being closed.

One of the main hallmarks of proof-of-work (PoW) consensus protocols is their ability to adjust the difficulty of the PoW, so that it accurately reflects the level of participation and hence maintains security in a setting where protocol participation is unknown and may over time change dramatically. Importantly, this enables the protocol to retain its fundamental characteristics (such as the regularity of dispensing new tokens) irrespectively of the number of parties running the protocol (also known as ``miners'') at any given time. The speed with which difficulty can be adjusted is a fundamental feature of a blockchain protocol: The faster the rate with which the difficulty is adjusted, the more agile the protocol is in the face of fluctuating participation. In this work, we put forward, for the first time, a blockchain protocol that performs difficulty adjustment in constant time; prior provably secure designs only offered protocols with, at best, poly-logarithmic overhead for difficulty adjustment. Our construction is based on the parallel-chain approach and a new target recalculation function that adjusts mining difficulty making use of information from all chains in the past epoch via a novel application of approximate-agreement techniques that may be of independent interest.

Tweakable block ciphers are important cryptographic primitives for secure memory encryption and partial mitigation of bit flip attacks. Rapid advancements in data-intensive applications such as artificial intelligence and machine learning have motivated the development of new memory technologies with very large data bus widths requiring wide-block memory encryption and its efficient implementation. Recently, the MATTER family of wide-block tweakable ciphers has been proposed for memory encryption in emerging applications. MATTER is a 512-bit balanced Feistel construction which uses the light-weight ASCON permutation as its round function. In this work, we present a comprehensive design space exploration of hardware architectures for accelerating different configurations of MATTER. We provide a detailed comparative analysis of power, performance, area and energy of round-based, unrolled and pipelined hardware implementations of MATTER based on digital synthesis using a 7nm FinFET ASIC standard cell library. We also discuss the suitability of these architectures for different application-specific memory encryption hardware requirements in emerging edge computing systems.

We give several examples of families of polynomials $p_1, ... , p_t \in \mathbb R[x_1, ... , x_n]/\langle x_i^d - 1\rangle_i$ on which the Low-Norm Nullstellensatz Hypothesis of [Devadas-Hopkins-Kalai-Kothari-Lombardi-Mathialagan, STOC 2026] fails to hold. That is, we prove the existence of polynomials $f \in \langle p_1, ... , p_t\rangle$ with coefficient $L^1$ norm $||f||_1 = 1$ but such that every decomposition $f = \sum_i p_i \cdot q_i$ has cost $\sum_i ||q_i||_1 = 2^{\Omega(n)}$. Our examples include one with $d=2$, the regime originally studied by [Devadas et al.], as well as generalizations that would also have sufficed for their purposes. Our counterexamples highlight an important class of polynomials for (potentially) falsifying the LNNH: for prime $d$, functions $f(x) = f_C(x)=\frac 1 {|C|}\sum_{c\in C} x^c$ that are indicator functions for the input $x \in \mu_d^n\simeq \mathbb Z_d^n$ belonging to a linear subspace $C^\bot \subset \mathbb Z_d^n$, or more generally a coset $C^\bot + \sigma$.

Existing lattice-based proxy re-encryption (PRE) schemes that achieve security against honest re-encryption attacks (HRA) typically rely on statistical noise flooding to hide dependencies between the source ciphertext, the re-encryption key, and the re-encrypted ciphertext. While effective, this technique causes large noise growth and significant parameter expansion. We present an owner-encrypted proxy re-encryption (OE-PRE) construction that achieves single-hop HRA security without statistical noise flooding. In the owner-encrypted setting, ciphertexts are generated directly using the data owner's secret key, yielding a clean inherited-noise term during re-encryption. To formalise the leakage argument, we use noisy error-leakage LWE (NEL-LWE), which captures LWE hardness in the presence of a noisy observation of the error and follows from a special case of the Leaky-LWE framework of Lai, Swarnakar, and Woo (CiC 2025). We prove single-hop HRA security from standard LWE/RLWE-style pseudorandomness assumptions, the NEL-LWE consequence of Leaky-LWE, and PRF security via a direct HRA hybrid proof. Our parameter discussion shows that the HRA-specific computational padding remains at the same scale as the encryption error, in contrast to the large flooding widths required in prior HRA-secure lattice PRE schemes. The proposed scheme targets single-hop owner-generated access delegation, such as encrypted file sharing and publish/subscribe delivery.

Large Language Models (LLMs) are frontier deep learning systems that have achieved remarkable success across a wide range of AI services. However, their substantial computational and memory requirements make them difficult to deploy and run on local hardware. Due to these resource requirements, users often rely on untrusted cloud infrastructure providers to perform model inference. However, outsourcing introduces the challenge of verifying that the returned output is the genuine result of the specified model. In this work, we present DeepProve, the first system to enable efficient end-to-end verification of full LLM inference (i.e., for all generated tokens of a prompt) on untrusted cloud servers using zero-knowledge proofs (ZKPs). In contrast, prior work either provides only a proof-of-concept partial implementation for a single token (zkGPT, USENIX'25), or focuses exclusively on specific components of the inference pipeline, such as Softmax (zkLLM, CCS'24). DeepProve achieves end-to-end verification by certifying the correctness of the output sequence rather than encoding the expensive inference computation in-circuit, an approach that would require either circuit size quadratic in the sequence length or costly in-circuit modelling of RAM operations. The core building blocks of DeepProve are sum-check protocol and lookup arguments, which enable efficient proof of correctness of all operators needed for GPT-2 and Gemma 3, such as multi-head attention and layer normalization for GPT-2, and grouped-query attention, root mean square normalization, and rotary positional embeddings for Gemma 3. Our evaluation shows that DeepProve can prove inference of GPT-2 and Gemma 3 at approximately 174 and 86 tokens per minute, respectively, which is 20-60 faster than the state of the art, without any significant loss in accuracy. Verification takes only 1 to 3.7 seconds. By distributing proof computation across multiple nodes, DeepProve can further improve the prover time while reducing the memory requirements for individual machines. With distributed proving, DeepProve can scale the throughput to 1855 tokens per minute. Our work represents the first full system for end-to-end LLM inference verification, thus paving the way for secure and trustworthy AI services.

Revocable and linkable ring signatures ($\mathsf{RLRS}$) provide a practical mechanism for controllable anonymity, enabling a revocation authority (RA) to mandatorily revoke the anonymity of the real signer. However, existing constructions often rely on the assumption of a fully trusted RA, where the correctness of the revocation is not publicly verifiable rendering honest users vulnerable to undetected framing by a compromised RA. Furthermore, the concrete deployment of these schemes is hindered by the certificate management burden of PKI and computation or communication overheads that scale linearly with the ring size, limiting their real-world applicability. In this paper, we formalize the notion of Identity-Based Revocable and Linkable Ring Signatures ($\mathsf{IB\text{-}RLRS}$), inherently eliminating cumbersome PKI management. Our primary contribution is the enhancement of \textit{revocability} alongside a newly adapted property termed \textit{revocation soundness}, guaranteeing that the real signer's identity can always be extracted, and that a malicious RA cannot frame honest users who did not participate in the signature generation. We present an efficient instantiation of $\mathsf{IB\text{-}RLRS}$ scheme, and prove its security in the random oracle model. Specifically, a novel ring signature construction is proposed, which features a transparent setup and achieves a logarithmic signature size, demonstrating its feasibility for large-scale, privacy-preserving applications.

Abstract. The TWEAKEY framework provides a generic construction for designing tweakable block ciphers. Prominent instances are Deoxys-BC and SKINNY, which have been standardized by ISO/IEC. In this paper, we analyze the tweakey schedules of these ciphers and identify strong dependencies between certain subtweakeys, which we call strong key bridges. We then exploit these dependencies in rectangle attacks under the related-tweakey setting. Moreover, we develop a comprehensive constraint programming model to search for rectangle attacks. Our model not only unifies the distinguisher and the key-recovery part while permitting arbitrary key-guessing strategies, but also integrates three new components, i.e., the state-test technique, explicit last-step computation, and the strong key bridges. As a result, we obtain significantly improved cryptanalytic results on both Deoxys-BC and SKINNY. For Deoxys-BC-384 and Deoxys-BC-256, we reduce the time complexity by a factor of $2^{40}$ and $2^{32}$, respectively, yielding the best attacks to date. Moreover, we extend the longest existing attacks on the authenticated encryption schemes Deoxys-I-256 and Deoxys-I-128 by one round. For SKINNY, we improve upon prior best attacks by one more round for SKINNY-128-384 and by two more rounds for SKINNY-64-192.

Public permissionless ledgers are append-only by design, yet are increasingly asked to host data subject to statutory erasure obligations (GDPR Art. 17, EDPB Guidelines 02/2025). The prevailing cryptographic response, rewriting the chain via chameleon hashes and redactable-blockchain constructions, is structurally unavailable on Bitcoin and Ethereum mainnet. This SoK systematizes the orthogonal application-layer design space, in which the ledger is left untouched and erasure is achieved by destroying the key material required to read the on-chain bytes. We organise the literature along two axes, data locus (on-chain ciphertext, anchor-only, or hybrid) and key custody (single-custodian, threshold, time-lock, or witness-encryption), into a twelve-cell grid with canonical constructions from 2006 to 2026. We extend standard IND-CCA security with a key-lifecycle adversary model parametrised by HSM side-channel leakage, coercion fraction over the custody committee, and algorithmic-break horizon, and establish an equivalence proposition between the resulting Destruction-IND notion and the EDPB "render unrecoverable" criterion. Evaluating seven reference architectures against eleven engineering, cryptographic, and regulatory criteria, including a production RegTech engine processing more than 10^4 events per second, we find that the literature has concentrated on chain-rewriting while the application-layer branch lacks a common threat-model vocabulary. We close this gap and identify five open problems: post-quantum equivalence, forward-secure destruction under leakage, decentralised lifecycle audit (with a multi-custody extension covering encrypted mempools), composition with ZKP selective disclosure, and erasure under multi-regime retention conflict.

End-to-end encryption (E2EE) provides strong confidentiality guarantees to users by preventing service providers from accessing their data. At the same time, it introduces new operational challenges, most notably the restoration of an E2EE-protected backup on a new device after loss of the original device. In recent years, major instant messengers have deployed increasingly sophisticated key-retrieval schemes for encrypted backups, ranging from simple recovery codes to designs that depend on trusted hardware or advanced cryptographic primitives such as oblivious pseudorandom functions (OPRFs), threshold OPRFs, and secret sharing. While recent work has largely emphasized stronger cryptographic guarantees, the practical costs and trust assumptions implied by hardware dependencies and complex primitives are often not made explicit. We present a structured framework for the comparative evaluation of E2EE backup key-retrieval schemes across usability, deployability, and security properties, and apply it to simple recovery codes, real-world deployments, and recent proposals from the literature, explicitly distinguishing recovery that depends on user-chosen low-entropy secrets from recovery using high-entropy material. Our evaluation shows that schemes whose recovery ultimately relies on user-chosen low-entropy secrets can provide substantially weaker resistance against large-scale adversaries than an approach using simple recovery codes. Even when assuming high-entropy recovery secrets, many recovery protocol designs introduce additional trust assumptions and potential single points of failure (e.g., compromise of specialized components or trusted setups) that can amplify the impact of large-scale adversaries. Overall, our results highlight that added system complexity often trades off against limited security gains under realistic threat models, motivating clearer accounting of cost and distribution of trust in future designs.

Stateful hash-based signature schemes such as XMSS and LMS are increasingly important in post-quantum cryptographic deployments, yet their verification paths remain difficult to fuzz effectively because key generation is substantially more expensive than verification. This paper presents a structured libFuzzer methodology for testing stateful hash-based signature verification in liboqs. The proposed approach uses pre-computed Known Answer Test (KAT) vectors to initialise valid public key, signature, and message buffers once during harness setup, enabling high-throughput mutation of verification inputs without repeated key generation. Using this methodology, we implemented and upstreamed two fuzz harnesses targeting XMSS/XMSSMT and LMS/HSS-LMS verification paths in liboqs. A ten-minute AddressSanitizer-enabled fuzzing campaign identified an OID-confusion heap-buffer-overflow in xmssmt_core_sign_open, assigned CVE-2026-46344. The flaw occurs when attacker-controlled public-key OID bytes derive a parameter set whose expected signature length exceeds the caller-allocated buffer, resulting in an out-of-bounds read during signature parsing. The issue was reproduced using a five-byte minimal crashing input and a standalone C reproducer, disclosed through the Open Quantum Safe coordinated disclosure process, and fixed in liboqs 0.16.0. We further identify a mutation-distribution bias affecting short-input LMS fuzzing and resolve it using a round-robin field-rotation strategy. The resulting framework provides a reproducible and upstream-integrated methodology for adversarial testing of stateful post-quantum signature verification implementations.

We present a Byzantine agreement protocol to address the inefficiencies inherent in multi-valued Byzantine agreement protocols, i.e., a version of the Byzantine agreement protocol where every party broadcasts its request, and at the end of the protocol, every party agrees on one of the party’s requests. The protocol we present is a validated asynchronous Byzantine agreement protocol, i.e., a party’s request must be validated by some external validity property before it is proposed for agreement. Differently from most of the MVBA protocols, we allow only a subset of total parties to broadcast their requests instead of all, and we make the subset selection stochastic each time the parties choose to broadcast a new set of requests. Then, at the time of the agreement, we choose a party from the selected subset, and the parties reach an agreement on the selected party’s broadcast. Extensive theoretical analysis shows that this approach can produce efficient output regarding messages and computation overhead, but the protocol is time-consuming.

Minimizing round complexity is a central goal in secure Multi-Party Computation (MPC), particularly for deployment on high-latency networks. While constant-round protocols with concrete efficiency have been constructed, they are typically designed for Boolean circuits and each gate incurs a bandwidth cost linear in the security parameter. Moreover, for arithmetic-heavy applications such as privacy-preserving machine learning and statistical analysis, compiling arithmetic operations into Boolean gates incurs another substantial overhead in circuit size and communication. Conversely, existing arithmetic MPC protocols, such as SPDZ, require interaction rounds proportional to the circuit depth, imposing significant latency. In this work, we bridge this gap by presenting the first concretely-efficient maliciously-secure MPC protocol that achieves both constant-round and constant-rate communication, where the rate is defined as the bandwidth cost per party divided by the number of gates and the size of the values each gate operates on. Our protocol computes over bounded integers and is secure against a static, malicious adversary corrupting up to $n-1$ parties. The protocol is built upon the arithmetic garbling framework of Ball et al. (Eurocrypt 2023) and follows the BMR template, assuming the Decisional Composite Residuosity for the garbling phase and Learning Parity with Noise for preprocessing. We evaluate our protocol on matrix-vector multiplication, a fundamental operation for data analysis. For standard computation parameters, we reduce communication bandwidth by $101\times$ to $247\times$ and improves end-to-end runtime by $4.4\times$ to $10.7\times$ compared to state-of-the-art constant-round Boolean MPC baselines, even when accounting for the overhead of a full bit-decomposition on the output vector.

Designing a secure symmetric-key cipher over a vector space over a field $\mathbb F_{p^n}^t$ is well known and understood by the cryptographic community. Even if the attacks are continuously improving, our current understanding regarding the design and security of the majority of the symmetric-key primitives has not fundamentally changed in the last 20 years. How does this picture change when we move to an integer ring $\mathbb Z_{p^n}^t$? Although the question is easy to state, it turns out to be far harder to answer. Indeed, there is a significant difference between the arithmetics of $\mathbb F_{p^n}^t$ and $\mathbb Z_{p^n}^t$ and attack vectors do not apply/translate directly between the two. As a case in point, a few ciphers have already been designed over integer rings, yet their initial versions have already been broken. In this paper, we lay the foundations for a more rigorous approach to designing ciphers over integer rings, noting that this is not only of theoretical interest, but also has concrete applications. We analyze how existing statistical and algebraic attacks will behave for these ciphers and also present new attacks that take into account that not all functions over integer rings admit a polynomial representation. Based on this, we discuss possible design strategies, in which we analyze the security effect of having/not having polynomial S-boxes. In particular, we introduce new properties for the non-polynomial S-boxes that measure their resistance against the attacks presented in this paper. Finally, we discuss how to design such non-polynomial S-boxes, presenting two concrete constructions, and one based on the "digit manipulation".

Few-time signatures cap how many signatures a signer can safely issue. Jevil is, to our knowledge, the first post-quantum and transparent (setup-free) few-time signature scheme with a sharp key-recovery cliff: its cap is enforced by a single sharp threshold rather than a slow slope. Signatures one through $n^{\star}$ are existentially unforgeable at approximately $124$-bit classical security; at the $(n^{\star}{+}1)$-th the entire secret polynomial becomes publicly recoverable, achieving catastrophic failure as a key design requirement. The cap is founded on a secret polynomial together with the degree-binding of a polynomial commitment, and is intrinsic to any accepted public key: even a malicious signer who chooses $\mathsf{pk}$ adversarially cannot construct one that lets them keep signing past the cliff without the same polynomial becoming publicly recoverable. All prior post-quantum few-time schemes (HORS, FORS, PORS, HORSIC$^{+}$, eBiBa, Syrga$_2$) degrade softly as $(nK/T)^K$. Every prior cliff-style construction misses at least one of post-quantum, transparent, sharp, and count-triggered: one-time Schnorr/ECDSA nonce reuse is neither post-quantum nor a designed property; polynomial-witness key-extraction signatures (notably DSKE) over KZG or IPA commitments are sharp but neither post-quantum nor transparent, while DSKE's hash-based variant is post-quantum and transparent but degrades softly; and double-authentication-preventing signatures (DAPS), post-quantum and transparent in their lattice form, fire a sharp key-recovery cliff on a message predicate (signing conflicting messages) rather than on a signature count, so they are not few-time schemes. Concretely, Jevil provides $68$-byte public keys, $32$-byte secret keys, and $\sim 40$~KB to $\sim 500$~KB signatures across the recommended signing budgets $n^{\star} \in \{1, 3, 7, 15, \ldots, 2^{14} - 1\}$, the range admitted by the working field's $2$-adicity. All primitives are believed to be post-quantum.

We propose a CKKS-based technique for evaluating arithmetic over finite fields F_{p^r} with small characteristic p under homomorphic encryption. The core of our approach is a pair of complementary ciphertext representations. In the so-called spectral encoding, ciphertext addition and multiplication realize addition and multiplication in the field F_{p^r}. In another encoding, coefficient encoding, the same operations act as slotwise addition and multiplication in the slot algebra (F_p)^r. We show that one can switch homomorphically between these encodings at cost linear in r, and that F_p-linear maps, such as taking p-th powers in F_{p^r}, can be folded into these switches or applied directly in either representation. We complement the construction with theoretical and practical correctness-management techniques. To support unbounded computations, we integrate our framework with existing CKKS bootstrapping techniques and benchmark it against BGV-based implementations of F_{p^r}-arithmetic, a natural baseline for high-throughput finite-field computation. Across the fields we tested, this yields speedups ranging from 1.7x to 178x in amortized multiplication time when bootstrapping is taken into account. The gains are parameter-dependent: roughly speaking, our advantage over BGV increases as the characteristic p becomes smaller and the extension degree r becomes larger.

Techniques to randomly select sets of anonymous parties are ubiquitous in efficient and adaptively secure consensus protocols, as well as in Multi-Party Computation in the YOSO model, where each round is executed by a different random anonymous committee. Anonymous committee selection aims at randomly selecting a set of $n$ parties (the committee), where at most $t$ parties are corrupted (except with negligible probability), drawing from a population of $N \gg n$ parties with at most $T$ corrupted parties. Additionally, each party knows (and can prove) if they belong to the committee, but ignores other members' identities. A very common and efficient instantiation of anonymous committee selection is to select parties according to a VRF output, this however, leads to committees of probabilistic size ($n$ behaves as a Binomial random variable). Despite wide adoption, only Blum et al. (CCS23) provides an analysis of VRF-based probabilistic anonymous committee selection that estimates the size of committees. This analysis relies on lose bounds (Chernoff) and approximations (Poisson). In this work, we revisit Blum et al.'s estimates and derive accurate closed-form formulas (based on a tight Binomial approximation), as well as an efficient high-precision library called Tail-Hammer for computing exact parameters. Notably, Tail-Hammer identifies smaller committee sizes (approximately -25% on average) than Blum et al. (CCS23) for the same security level, leading to improved efficiency in protocols relying on random committee selection, also when anonymity is not needed. Our analysis applies to committee selection techniques that employ unbiased (uniformly random), or bounded-bias randomness, to both synchronous and asynchronous communication settings, and it can account for inactive parties. As a new application, we present a verifiable consistent broadcast protocol that leverages quorums in anonymous committees to achieve efficiency without requiring threshold signatures.

Publicly verifiable secret sharing (PVSS) is a fundamental primitive in threshold cryptography that allows a dealer to share a secret $S$ among a set of $n$ parties via a publicly verifiable transcript. Any subset of $t+1$ parties can then use their individual shares to reconstruct the full secret $S$, whereas $t$ or fewer shares give no information about $S$. As such, the secret $S$ remains hidden from an adversary that corrupts up to $t$ parties. Recently, Bacho and Loss (CCS 2023) gave the first proof of any PVSS scheme under an adaptive adversary. However, their security proof relies on strong and non-standard assumptions such as the algebraic group model (AGM) and the hardness of the one-more discrete logarithm (OMDL) problem. In particular, any protocol (e.g., distributed randomness beacon or distributed key generation) that makes use of a PVSS scheme either inherits these limitations or is not provably adaptively secure. In this work, we present for the first time an adaptively secure PVSS scheme from well-established assumptions. In more detail, we provide two PVSS schemes with different properties. Our first scheme works over any pairing-free cyclic group and its security relies on the decisional Diffie-Hellman (DDH) assumption. Our second scheme works over an asymmetric pairing group, its security relies on the DDH and the co-computational Diffie-Hellman (co-CDH) assumption, and has the particularly valuable feature of aggregatability, which allows the aggregation of multiple PVSS transcripts into a single transcript while preserving verifiability. Notably, both our schemes are highly efficient, non-interactive, and work in the established plain public key model. These properties along with their provable adaptive security make them suitable candidates as building block in higher-level distributed protocols that aim to minimize communication.

VOLE-in-the-Head (VOLEitH) is one of the most promising frameworks to design post-quantum digital signatures based on symmetric primitives. However, all existing symmetric primitives do not capture the specialized characteristics of the VOLEitH framework and are not VOLEitH-friendly, leaving room for improving the efficiency of VOLEitH-based signatures. In this paper, we propose a VOLEitH-friendly symmetric primitive called Lynx, which is optimal in terms of the number of required VOLE correlations that directly determines the efficiency of VOLEitH-based signature schemes. In particular, Lynx adopts a multi-branch structure featuring a new truncation function: (a)~nonlinear components are set to minimize the witness length and polynomial degree, as well as the number of finite-field multiplications; (b)~linear layers are strategically interleaved to strengthen security. The security of Lynx is rigorously validated by covering all current attacks in the presence of both classical and quantum adversaries. Built upon Lynx, we design a post-quantum signature scheme, Lynxer, in the VOLEitH framework, which is shorter and faster than all known post-quantum signature schemes from symmetric primitives. According to our experimental results, compared to the state-of-the-art symmetric-based signature schemes in the same setting, i.e., Rainier (CCS'22), AIMer (CCS'23) and FAESTv2 (Crypto'25), our signature scheme Lynxer reduces the ``public-key size + signature size'' by 25%~51%, and improves the signing (resp., verification) time up to 90.5% (resp., 89.9%).

We present four quantum-safe schemes: the Kyber (ML-KEM) and FrodoKEM key encapsulation mechanisms, and the Dilithium (ML-DSA) and Falcon (FN-DSA) signature schemes. We also develop the mathematical background on lattices needed to understand why Kyber, FrodoKEM, Dilithium and Falcon are regarded as lattice-based cryptosystems, and we provide insight into the computational hardness of the underlying lattice problems. The exposition is intended to be accessible to senior undergraduate students and beginning graduate students.

Schnorr's signature scheme and many of its variants are among the most efficient group-based digital signature schemes. Schnorr's scheme has very compact signatures (consisting of only two exponents in its most compact form). However, its security reduction is notoriously non-tight and requires a strong (“programmable”) version of the random oracle model. Variants with a tight(er) security proof in a more realistic model exist, but are less compact and efficient. In this work, we investigate whether these disadvantages are inherent to Schnorr's signatures and its variants. In particular, we define a family of “Schnorr-like” signature schemes, which contains group-based signature schemes with verification similar to Schnorr's scheme. To explore the necessity of (heavy) random oracle abstractions for such schemes, we allow only for a very weak (“non-programmable, non-observable”) version of a random oracle in the security proof. Our main result is that there is no tight reduction of the security of any such “Schnorr-like” scheme to any group-based assumption that holds generically. We also show that this result itself is tight, in the sense that non-tightly secure schemes exist. Similarly, already for a slightly generalized definition of “extended Schnorr-like” schemes, tightly secure schemes exist. Our main result employs a meta-reduction with a new “filtering” technique that may be of independent interest.

Zero-knowledge proofs are a fundamental building block of modern privacy-preserving systems. In isogeny-based cryptography, existing zero-knowledge proof constructions are either limited to chains of small-degree isogenies or are quite inefficient. As a result, many relations used in recent cryptosystems lack support in generic proof systems. In this work, we take a step toward making zkSNARKs practically usable for a broader set of isogeny relations beyond the classical isogeny path knowledge language. Leveraging optimized Vélu-style formulas, we provide an efficient R1CS encoding for $3^m$- and $4^n$-isogenies, along with their masked evaluations. We also present an R1CS for non-smooth isogenies of special degree $q(2^e - q)$, where $q$ is an odd integer, together with their evaluation. This latter encoding is based on the efficient formulas for $(2,2)$-isogenies in the theta model. Finally, we demonstrate several concrete applications of our tools. We present a compiler that removes the ``one-more'' evaluation assumption in the signature based on DeuringVRF. We also discuss how to eliminate the hint-based assumption in SQISign and explain how to construct a key-validation mechanism for recent public-key encryption designs, such as POKÉ on the concept level. We provide the experimental results with respect to the constraint numbers under various isogeny NIST-1 primes for reference. Under the setting, the proof sizes considered in this work are bounded by 400 KB by the default setting. We hope our results will inspire further advances in isogeny-based constructions.

Quantum key distribution (QKD) enables the exchange of information-theoretically secure symmetric keys, but is fundamentally limited in range. Existing long-distance QKD networks rely on trusted relay nodes, any one of which can compromise the entire key. We propose a key-transport protocol that removes this trust assumption by combining proactive secret sharing with one-time pad encryption over pairwise QKD links. At each layer of relay nodes, shares are reshared so that corruptions across different layers cannot be combined; security depends only on the maximum number of corruptions within any single layer, not on the total number of corrupted nodes. We formalize a game-based security model for layered secret transport, identify a cross-layer attack that affects a prior construction, and prove our protocol information-theoretically secure against a semi-honest adversary corrupting up to $t{-}1$ nodes per layer.

Asymmetric Message Franking (AMF), proposed by Tyagi et al. at Crypto’19, is a sort of signature scheme that aims to provide privacy-preserving content moderation in secure messaging applications. In this work, we present the first generic construction of AMF using a public-key encryption scheme, a signature scheme, and a ZAP proof system for NP languages. This construction yields the first AMF scheme provably secure in the plain model from standard assumptions, and has tight security. To improve the efficiency of AMF in the plain model, we build a concrete scheme from asymmetric pairing groups based on our idea for the generic construction. It achieves a signature size of 47 group elements, which is significantly smaller than an instantiation of the generic construction. Also, we provide a variant of the generic construction that yields a post-quantum secure AMF scheme in the plain model from a polynomially hard LWE assumption, demonstrating its feasibility.

Demand Response (DR) in energy systems is a flexibility mechanism enabling consumers to modify their electricity demand in response to signals from network operators, designed to ensure power grid reliability. In particular, incentive-based DR programs, in which consumers provide load reduction in exchange for financial remuneration, have proven more effective than alternative approaches such as price-based programs. However, incentive-based approaches have taken only partial account of privacy considerations, mainly because they require smart meters to disclose user energy baselines and consumption patterns to aggregators in order to determine rewards. In this paper, we propose a privacy-preserving scheme that supports incentive-based DR programs while ensuring the confidentiality of user data and identities. We prove that our scheme provides data privacy, participation privacy, and public verifiability, and we present a prototype implementation together with a performance evaluation. Our results show that our construction is practical for real-world DR deployments with considerably large user populations.

In this short note, we show that two identity-based encryption schemes, introduced by Joye and Zhao et al., which appear different, are essentially the same scheme. The only difference between them is that one prioritizes speed (Zhao et al.), while the other prioritizes bandwidth (Joye). We also show how to speed-up Joye's scheme at the cost of adding at most one integer to the public key, thereby achieving a better encryption complexity, while having the same bandwidth requirements.

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.

While quantum position verification aims to certify a prover's location using quantum information, existing security definitions only guarantee that part of the successful adversarial party is in the claimed location. This leaves open the possibility that a distributed team of adversaries can jointly simulate a prover in a way that defeats the intended meaning of ``being at a location'' in position-based cryptography. We introduce stronger notions of position verification that we call quantum localization, which requires that there is a specified, unclonable state at the verified spacetime point -- and that this state can be found nowhere else. We show that quantum localization leads naturally to a meaningful notion of trajectory verification, in which quantum information is verifiably tracked through space and time. We construct quantum localization and trajectory verification protocols using quantum anchor states, which generalize coset states from unclonable cryptography. The security of our schemes is proven in the classical oracle (i.e. ideal obfuscation) model, which can be heuristically instantiated in the plain model using post-quantum indistinguishability obfuscation. We also introduce and instantiate the concept of functionality localization, which guarantees that the adversary has the ability to compute a secret function at the verified spacetime point, and this function cannot be computed anywhere else. This raises the intriguing possibility of localizing computational capabilities in space and time. More broadly, we believe our notions of quantum localization and subsequent feasibility results provide stronger foundations for position-based cryptography. At a conceptual level, our results also explore the tight link between two fundamental notions in physics -- location and information -- thus serving as a natural foundation for cryptographic capabilities tied to physical spacetime.

The cost of homomorphic multiplications for existing FHEs to evaluate a degree-$D$ polynomial $f(x)$ at some point $x$ is very expensive. When $x$ is encoded in a plaintext slot having a power-of-two degree $d = 2^\ell$ and $D \leq d$, one can efficiently evaluate $f(x)$ with \(O(\log d)\) multiplications using the heuristic algorithms of Okada et al. (ASIACRYPT 2023). However, neither $d = 2^\ell$ nor $D\leq d$ is satisfied for most practical FHE parameters, and the Paterson–Stockmeyer (P-S) method with \(O(\sqrt{D})\) multiplications remains the state-of-the-art for $d \neq 2^\ell$ or $D>d$. In this paper, we first present a polynomial evaluation algorithm with \(O(\log d)\) multiplications for any non-power-of-two $d$ and $D\leq d$, which achieves the same asymptotic complexity as that of Okada et al. Then, we gave a polynomial evaluation algorithm with $O(\sqrt{D/d})$ multiplications for plaintext modulus $p>2$ and $d < D\leq d\log p$, which beats the P-S method by a factor of $\sqrt{d}$ and essentially achieves logarithmic multiplication complexity when $D \leq d \cdot \min(\log^2 D, \log p)$. As a major application, we implement our algorithms in experiment to evaluate the digit extraction polynomials of the BGV bootstrapping with parameter $d$ ranging from $14$ to $45$ in HElib, and obtain a \(1.22-2.16\times\) speedup over the recent work of Ma et al. (EUROCRYPT 2024).

$1+1 \equiv 0$---while looking strange at first glance, this is certainly true in GF(2). In this paper we propose the two field-like structures \FlipInts\ and \FlipPolys\ as potential alternative building block for crypographic schemes---in particular in the post-quantum setting. Both structures have $2^d$ elements for some positive integer $d$ and are derived from the natural numbers $N$ in the first case and the univariate polynomial ring GF(2)$[t]$ in the second case. We call the generalization of these two structures FlipFields. In addition, we see examples how they can be used for post-quantum cryptography, in particular Unbalanced Oil and Vinegar, Learning with Errors and Saber. There is also a discussion of cryptographic primitives that are most likely not suitable for FlipFields or at least not easy to tweak. As the structures are very new, this paper also includes a list of OpenProblems.

The recent work [Devadas-Hopkins-Kalai-Kothari-Lombardi-Mathialagan, STOC 2026] proposed a low-norm Nullstellensatz hypothesis for the "AND code": every polynomial $f$ vanishing on the "AND-code ideal'' should admit a Nullstellensatz decomposition over the local AND constraints whose total coefficient \(\ell_1\)-norm is only polynomially larger than the \(\ell_1\)-norm of $f$. We give a counterexample to this conjecture by proving an exponential lower bound on the total coefficient \(\ell_1\)-norm. The core idea of the proof was discovered by ChatGPT 5.5 Pro, and we verified and reorganized the proof to improve its exposition. The proof constructs a dual linear functional, whose analysis leverages the rank of the quadratic forms to bound Fourier correlations. The counterexample can also be extended to give the first \(\ell_1\)-norm lower bound for Nullstellensatz refutations over the \(\{\pm1\}\)-basis. Previously, \(\ell_1\)-norm lower bounds for Nullstellensatz refutations were known only over the \(\{0,1\}\)-basis, due to Potechin and Zhang [ICALP 2024]. We believe this is of independent interest to proof complexity.

Hybrid signatures are a practical approach to post-quantum migration, but their security analysis becomes subtle when two Fiat-Shamir (FS) components are binded through a single shared challenge. This paper presents the first machine-checked proof of EUF-CMA security for the FS-FS hybrid construction of Bindel and Hale (2023) formalised in EasyCrypt in the Random Oracle Model (ROM). The proof is parametrised over abstract component interfaces and establishes the intended either-component security guarantee: for either choice of component, a hybrid forgery can be reduced to an EUF-CMA forgery against that component, together with the collision resistance of the message digest and a random-oracle guessing term. In this ROM formulation, the proof does not require an independent second-preimage-resistance assumption for the challenge hash. The mechanisation makes explicit two proof obligations arising from the hybrid structure and the abstract digest: an invariant linking the lazy-oracle state to an explicit query log at the verification point, and a module-restriction framing argument for the digest-collision reduction. We further machine-check honest-signing correctness for a concrete Schnorr-Schnorr instantiation and instantiate the abstract security proof with a Schnorr-Okamoto component pair without changing the core game-hopping argument. The formalisation thereby makes explicit the assumptions, invariants, and composition structure underlying the security argument for the FS-FS hybrid.

Unrolled cryptographic hardware architectures are increasingly deployed to maximize throughput, inherently intro- ducing massive algorithmic noise floors that frequently thwart traditional temporal Side-Channel Analysis (SCA). However, the reliance on structural combinational noise as a standalone coun- termeasure remains underexplored against adaptive, AI-driven profiling. This work presents a novel autonomous framework uti- lizing a Large Language Model (LLM) agent to orchestrate and execute differential power evaluations against a 161,000-gate fully unrolled AES-128 core on a target CW305 FPGA. We first estab- lish a baseline, demonstrating that standard Correlation Power Analysis (CPA) systematically fails to penetrate the unrolled noise floor, yielding statistically insignificant correlations (r ≈ 0.11). In response to this heuristic failure, the autonomous agent dynamically pivots to a Zero-State Differential Power Isolation methodology. By leveraging single-channel baseline subtraction, the agent mathematically cancels multi-round algorithmic noise from the global power trace, successfully isolating the target combinational leakage and achieving peak correlations exceeding r = 0.318 across all 16 state bytes. Furthermore, by comparing the extracted physical signatures to the logical target state, the framework autonomously extracts 16 unique physical-to-logical routing maps. This demonstrates that while automated Electronic Design Automation (EDA) synthesis inadvertently introduces physical bit-level obfuscation, these synthesis optimizations can be systematically reverse-engineered by agentic profiling. Ultimately, this work proves that unrolled combinational architectures can- not serve as a robust defense against adaptive, autonomous side- channel characterization.

Blind signatures are a central primitive for privacy-preserving applications such as e-cash, anonymous credentials, and e-voting. Classical constructions such as blind Schnorr adapt an ordinary signature scheme while producing signatures that follow the same format and distribution as those generated by the ordinary signing algorithm. This property is particularly relevant in settings where blind and non-blind signatures coexist within the same infrastructure. Achieving an analogous result for lattice-based Fiat--Shamir signatures, with security based on the underlying ordinary signature scheme, has remained open. We present $\mathsf{BRaccoon}$, the first concurrently secure lattice-based realization of the ``blind signatures from a signature assumption'' paradigm of Fuchsbauer and Wolf (EUROCRYPT~2024). Our construction builds on the rejection-free lattice signature scheme $\mathsf{Raccoon}$, yielding signatures that retain the algebraic format and verification relation of $\mathsf{Raccoon}$. At a high level, we introduce blinding at the commitment stage and enforce correct challenge and response generation via linearly homomorphic encryption combined with $\mathsf{NIZK}$ proofs. Since these proofs already bind the hidden message to the resulting signature, their relation can naturally incorporate predicates on that message, providing a direct route toward predicate blind signatures. A central technical challenge stems from discrete Gaussian sampling, where blinding induces a non-trivial distributional shift that precludes direct security reductions. To overcome this, we introduce a modified scheme $\mathsf{Raccoon}^\star$ that explicitly captures this shift. We analyze one-more unforgeability through non-rounded versions of $\mathsf{Raccoon}^\star$ and $\mathsf{Raccoon}$. The deployed blind-signing protocol retains rounding. For a concrete instantiation, we encode the lattice relations and the non-linear challenge computation in a common mixed Boolean and arithmetic relation. Our instantiation retains SHA3-256 and SHAKE256 and proves both protocol statements using the ZK-LaBRADOR toolkit. For up to $2^{32}$ signing queries, its total communication is estimated at approximately $862$ KB.

Functional encryption (FE) which covers the notion of attribute-based encryption (ABE), is the cryptographic tool to realize fine-grained control on the accessibility of encrypted data. The traditional FE requires a central trusted authority to issue secret keys. It depends on the full-trust model, and is vulnerable to the security issue caused by key-escrow. While the registered FE (Reg-FE) achieves the zero-trust model and addresses the security issue by removing the use of central authority. It allows users to generate secret keys themselves and join the system by registering corresponding public keys to a curator. This work introduces delegated Reg-FE, which is a primitive with a new registration paradigm. It allows the registration of certain authorities that can issue secret keys for their respective classical FE sub-systems, beyond the prior work of registering plain users. Delegated Reg-FE implements a hybrid trust model within a two-level hierarchy. By redefining key escrow as a functional mechanism rather than a security concern, this model employs a zero-trust upper level which removes key-escrow, while the subsystem of each authority is locally full-trust and retains key-escrow mechanism. We construct four delegated Reg-FE schemes for functionalities that can be described as the $2\times 2$ combinations of linear function and policy check. Namely, Delegated Reg-IPFE, Delegated Reg-ABE, Reg-IPFE with delegated ABE, and Reg-ABE with delegated IPFE. All concrete schemes support bounded registrations and delegations, and achieve standard adaptive security under MDDH assumption on prime-order bilinear group. Furthermore, these schemes only rely on black-box techniques. Technically, these schemes rely on dual-system techniques as prior registration-based works. And we devise a new "hierarchically invoked dual-system" technique on schemes which have sub-ABE delegation systems. Furthermore, we present a generic construction of Delegated Reg-FE from the combination of Reg-FE and FE. The instantiations of this generic construction demonstrate the feasibility of delegated Reg-FE, supporting arbitrary functions as well as unbounded numbers of registrations and delegations. However, this approach requires non-black-box techniques and achieves weaker semi-adaptive security without malicious registration, where the semi-adaptive means the adversary claims the challenge after seeing common reference string but before making any query. Its security relies solely on the underlying assumptions of the Reg-FE and FE components.

In this work, we present a generic side-channel protected design of Ascon that achieves high efficiency by dynamically reconfiguring the hardware countermeasures during message processing. The resultant implementation is protected and capable of meeting stringent performance requirements whilst minimising resource overhead. The experimental results obtained demonstrate that the implementation meets the required security and achieves superior throughput-to-area ratio across all protection orders. Ascon, recently selected by NIST as the lightweight cryptography standard, is widely deployed in resource-constrained devices that demand both high performance and resistance against threats such as side-channel analysis (SCA). Exploiting Ascon's mode-level structure, which does not require protection against differential power analysis during bulk operations, we introduce a modified masking gadget with dual functionality: serving as a countermeasure during critical operations, and processing multiple data paths in parallel to accelerate bulk computation. Our architecture supports any configurable security order and instantiates only the minimum hardware resources needed to maximize throughput per round. We also evaluate an enhanced Ascon architecture based on the Changing of the Guards technique, which eliminates the need for fresh randomness. Security validation is performed using fixed-vs-random t-tests on both first- and second-order masked implementations. Finally, we compare our masked design against state-of-the-art solutions.

The Learning With Errors (LWE) problem is a cornerstone of lattice-based cryptography and underpins the security of numerous cryptographic schemes. To enhance efficiency, practitioners often employ sparse secrets in LWE, where the secret vector $\mathbf{s}$ has a significantly lower Hamming weight than its dimension $n$. While this approach improves performance, it raises security concerns, particularly against side-channel attacks that can leak partial information, or “hints,” about the secret key. In this paper, we revisit the LWE with side information framework on sparse ternary secrets, focusing on approximate/perfect hints of the form $(\mathbf{v}, l)$ satisfying $l = \langle \mathbf{v}, \mathbf{s} \rangle + e$, where $e$ is a small error term, or $l = \langle \mathbf{v}, \mathbf{s} \rangle$. While previous results needed about $n/2$ perfect or modular hints to break LWE in polynomial time, we show empirically, supported by a conservative lower-bound analysis under the Gaussian Approximation Assumption (GAA), that the task can be accomplished with only $O(h \log_2 h)$ hints, where $h$ denotes the Hamming weight of $\mathbf{s}$. We demonstrate the effectiveness of our algorithm on practical parameter sets used in Fully Homomorphic Encryption (FHE) schemes. For instance, for a sparse-secret FHE bootstrapping regime with $(n, h) = (2^{15}, 32)$, our method requires only 320 approximate/perfect hints to recover the secret key, compared to the $2^{14}$ perfect/modular hints required by previous methods. For the OpenFHE library with $(n, h) = (2^{15}, 192)$, we heuristically confirm secret-key recovery via $O(h \log_2 h)$ perfect hints; approximate hints have not yet been validated in this setting. After collecting the necessary hints, our algorithm recovers the secret key in polynomial time in dimension $n$.

The SHA-2 family hash is standardized by NIST and mainly includes two variants, SHA-256 and SHA-512. Due to its widespread deployment, its security has attracted continuous attention from various parties. Although Li et al. have developed open-source SAT/SMT-based tools and proposed new memory-efficient collision attack frameworks for SHA-2 in recent two years, practical collision attacks are only achieved for 31-step SHA-256 and 29-step SHA-512, respectively. To push the limit of such an attack framework for SHA-2, we carefully investigate existing strategies to choose message differences used in 38/39-step semi-free-start collision attacks. We found that by selecting message words $(W_{4+i}, \ldots, W_{8+i}, W_{12+i}, W_{13+i}, W_{20+i}, W_{22+i})_{0\leq i \leq 3}$ to inject differences, and employing the open-source SAT/SMT-based automated tools to search for the corresponding differential characteristics, notable improvement can be achieved for practical and theoretical collision attacks. Specifically, the first practical collision attacks on 35-step SHA-256 and SHA-512 can be achieved for $i=0$, improving the best practical collision attacks on SHA-256 and SHA-512 by 4 and 6 steps, respectively. When $i\in\{1,2\}$, theoretical collision attacks on both SHA-256 and SHA-512 can reach up to 36/37 steps. We have also tried collision attack up to 38 steps by setting $i=3$, but the uncontrolled differential probability is too low to be used for effective attacks.

A witness pseudorandom function (WPRF) is a PRF which has an additional mode of public evaluation. Given the public key, it can be evaluated publicly if one provides a valid NP witness for that input, while the output remains pseudorandom to anyone without such a witness. WPRFs are powerful objects, and general-purpose constructions are currently only known from assumptions that imply indistinguishability obfuscation. In this work, we construct a WPRF for a specific language related to the Libert-Yung vector commitment (TCC 2010). More specifically, public evaluation of the WPRF on an input is possible if a valid local opening for that input is provided. Our construction relies only on standard assumptions on pairing groups and is fully black-box. We further show that this primitive enables us to solve several open problems in the study of communication-efficient secure computation: - Rate-1 Laconic Oblivious Transfer. We construct a laconic oblivious transfer protocol with total communication complexity $2k+\mathsf{poly}(\lambda)$ for $k$ executions. Previously, achieving this efficiency required non-falsifiable assumptions such as evasive LWE (Wee, CRYPTO'24). - Near-optimal Laconic Private Set Intersection. We construct laconic private set intersection for which the amortized communication complexity approaches $\lambda$ bits per element in the sender's set (assuming each set element is represented by $\lambda$ bits) and is independent of the receiver's set. This is within a constant factor of the information-theoretic lower bound. - Rate-1 Batch Registration-Based Encryption. We construct a registration-based encryption scheme in which, when the encryptor sends multiple messages to multiple receivers, the ciphertext overhead is only two group elements.

Advances in quantum computing technology have motivated the development of post-quantum cryptography (PQC) algorithms. HAWK is a new post-quantum digital signature scheme and the only lattice-based candidate selected for Round 3 of the "Additional Digital Signatures" phase of the NIST PQC Standardization process. HAWK offers compact key and signature sizes compared to NIST standard ML-DSA (Dilithium), and its simple design avoids the use of floating-point arithmetic unlike NIST standard FN-DSA (FALCON). This makes HAWK very well suited for resource-constrained applications. We perform software runtime profiling of HAWK signature computation and verification on a resource-efficient Vex RISC-V processor core, and identify Keccak permutations and polynomial transformations as the most computationally expensive functions. In this work, we demonstrate light-weight hardware-software co-design of HAWK with these operations accelerated using Vex RISC-V Custom Function Units and accompanying custom instructions. We present multiple design variants with different degrees of acceleration, and our best design achieves $\approx 3 \times$ speedup and $\approx 40\%$ reduction in area-time-product compared to the baseline when implemented on a Xilinx Artix-7 FPGA.

Authenticated Private Information Retrieval (Authenticated PIR) allows the client to retrieve the desired database entry without revealing any information about the query, while safely aborting if malicious behavior by the server is detected (presented in USENIX '23). However, two key challenges remain: existing single-server authenticated PIR schemes with sublinear online communication have not yet been clearly and fully implemented; incremental updates to the digest introduce unnecessary overhead. In this paper, we implement the previously outlined idea and present two complete and concrete single-server authenticated PIR schemes with $O(\sqrt{N})$ online communication, namely LWE-AuthPIR and DDH-AuthPIR, along with detailed security proofs. Furthermore, we introduce the notion of single-server authenticated and incremental PIR and propose a corresponding concrete construction, LWE-AuthIncPIR. LWE-AuthIncPIR supports immediate updates to individual entries and integrates a communication-efficient row aggregation for periodic update scenarios. When 1\%-8\% of the entries in a 1GB database are modified, LWE-AuthIncPIR reduces offline preprocessing computation by 19-88$\times$ compared to previous incremental update method. In the password breach detection, LWE-AuthIncPIR achieves a 67$\times$ reduction in preprocessing time and a 2.9$\times$ reduction in communication overhead.

Traitor tracing [Chor-Fiat-Naor; CRYPTO'94] has historically been formalized through the lens of a $\textit{single}$ trusted authority that samples the master keys and that, therefore, can read every ciphertext on its own. This $\textit{key escrow}$ problem makes traditional traitor tracing fundamentally incompatible with end-to-end encrypted broadcast networks. In this work, we study introduce $\textit{multi-authority traitor tracing}$ (MA-TT) [Goyal-Yadugiri; ePrint] a new decentralized model for traitor tracing in which the setup is split across $K$ asynchronous and non-interacting authorities, and a user can decrypt only by combining partial keys from $\textit{every}$ authority. We require that semantic security holds even when an arbitrary set of authorities is corrupted (as long as some honest partial key remains hidden for every user), and that traceability never accuses a user for whom an honest partial key remains hidden. We design MA-TT by combining any multi-authority attribute-based encryption (MA-ABE) scheme with a new primitive that we introduce, distributed mixed functional encryption (DMFE), a careful decentralization of the mixed functional encryption notion [Goyal-Koppula-Waters; STOC'18]. We construct DMFE from LWE via single-key key-homomorphic private constrained PRFs. Plugging in known MA-ABE schemes, we obtain MA-TT from LWE plus pairings with ciphertext size $K \cdot \mathsf{poly}(\lambda, \log N)$. As feasibility, we also give MA-TT from any PKE (with ciphertexts of size $K \cdot N \cdot \mathsf{poly}(\lambda)$) and from any multi-authority functional encryption (with fully succinct parameters).

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.

Public blockchains like Ethereum deliver transparency, but adding anonymity remains a fundamental challenge. Existing proposals either offer limited anonymity guarantees or rely on heavy cryptographic machinery, e.g., zero-knowledge proofs. We introduce \emph{Blockchain Anonymous Tokens} (BAT), a system for efficient \emph{sender}-anonymous transactions on transparent blockchains. Building on the observation that \emph{one-time-spendable tokens suffice for many applications}, BAT has a lightweight design using classic anonymous tokens due to Chaum (1983). Unlike such tokens, though, BAT is designed to work in a transparent decentralized setting, where issuers are untrusted (i.e., any single potentially malicious entity can be the issuer) and spends happen publicly. BAT issuance is compact: A client can receive $\ell$ tokens with just $\mathcal{O}(1)$ on-chain communication and computation. We formalize the notion for BAT, and provide a concretely efficient construction. Our BAT construction requires no on-chain verification of expensive zero-knowledge proofs; just a signature verification during spends and a single exponentiation on-chain during issuance. We present several applications of BAT in various blockchain contexts. We implement and evaluate BAT and show that compared to the closest baseline, Zcash transactions, BAT tokens are 50$\times$ shorter, 9$\times$ faster to verify, and 7,000$\times$ faster to generate.

Decentralized exchanges built on Automated Market Maker (AMM) protocols have become a cornerstone of Decentralized Finance (DeFi), offering token swaps without conventional order-book matching. However, supplying liquidity to these AMM pools exposes participants to distinctive market risks, most notably impermanent loss (IL) - the potential underperformance of a liquidity-provider portfolio relative to simply holding the underlying tokens. This paper presents a comprehensive overview of IL, unifying its main theoretical models, empirical evidence, and mitigation strategies. Our survey spans constant-function and concentrated liquidity market makers, synthesizes findings from leading DeFi protocols, and reviews mitigation methods that include both protocol-level adaptations and financial-engineering approaches. Across these perspectives, we highlight recurring trade-offs, cost, complexity, and security. Finally, we outline open questions for managing IL's systemic effects, keeping decentralized liquidity provision both profitable for participants and sustainable for the broader ecosystem.

Proactive secret-sharing (PSS) offers security for shared secrets in a setting of a mobile adversary which, over time, may corrupt the whole shareholder set. This remarkable property is achieved by having parties proactively and in a coordinated manner refresh their shares on a regular basis, while it assumes that the adversary never manages to corrupt more than a threshold number of parties between two consecutive share refresh operations. A common assumption for achieving PSS is the ability of parties to securely erase their private state once they have performed the refresh operation. Motivated by the difficulty in the real world to ensure secure erasure, we investigate whether it is possible to achieve PSS without erasures. As in the classic model of computation it can be easily shown that PSS without erasures is impossible, we hence ask whether it is possible to achieve PSS via quantum computation, while still requiring only classical communication. We answer the question in the affirmative by utilizing one-shot signatures and post-quantum classical extractable witness encryption. In the process of developing our result, we define and construct threshold one-shot decryption and make connections to quantum money with classical communication both of which may be of independent interest. Finally, we show how, by combining post-quantum secure functional witness encryption with our PSS, it is possible for the secret to be used without explicitly being reconstructed, something that paves the way towards proactively secure threshold cryptography without erasures.