Multi-key fully homomorphic encryption (MKFHE) enables computation over encrypted data under multiple different keys. Constructing MKFHE without any trusted or interactive setup remains an open problem. In the context of MKFHE, a trusted setup is often assumed to mean the use of a common random string (CRS). In this paper, we present the first MKFHE scheme in the plain model (i.e., without any trusted or interactive setup) based on the RLWE assumption. Specifically, we construct a multi-key somewhat homomorphic encryption based on the RLWE assumption and extend it to a multi-key variant of the Gentry-Sahai-Waters (GSW) scheme with a circular security assumption. Our design yields a 2-round multi-party computation (MPC) in the plain model against semi-honest adversaries. Moreover, it can be applied to transform existing FHE schemes that rely on RGSW in their construction into a multi-key variant. We also provide concrete conversions for widely-used FHE schemes, including BGV, BFV, CKKS, FHEW, TFHE, and Carousel. Finally, we implement our scheme and present experimental results for the expansion algorithm from a single-key ciphertext to a multi-key ciphertext and the multi-key homomorphic multiplication algorithm.

Fully homomorphic encryption (FHE) allows arbitrary computation over encrypted data, but its secret key presents a single point of failure which limits its applications. Threshold FHE patches this gap by distributing the secret key to $K$ parties, requiring a threshold $t \leq K$ of them to cooperate for decryption. We focus on the asynchronous setting where a ciphertext can be decrypted by collecting decryption shares from any $t$ parties who do not need to coordinate or even be online simultaneously. Asynchronous schemes are sought in applications such as privacy-preserving Ethereum Virtual Machines (EVM), processing of long-lived private data with quorum-based decryption and the thresholdisation of any cryptographic primitive in general. We present Tulva, a practical threshold FHE scheme which equips a base FHE scheme with an asynchronous threshold decryption mechanism in a modular way. Our scheme simultaneously (1) is compatible with virtually any base FHE scheme and leaves its ciphertexts unchanged apart from an appended random tag, (2) supports a wide range of threshold profiles $(t,K)$ and ring degrees $\geq 256$ with 6--25 bits partial decryption per plaintext bit, and (3) achieves security in the presence of partial decryption queries on challenge ciphertexts based on the standard LWE assumption. We provide an open-source implementation, benchmark its threshold decryption performance and evaluate the end-to-end costs for typical privacy-preserving EVM use cases. For 16-out-of-512 threshold and a publicly preprocessed ciphertext, computing secret-dependent partial decryption and public share combination requires only 3.7ms and 0.5ms, respectively, on commodity hardware. Compared with the state-of-the-art synchronous scheme [Zyskind et al., CCS'25], we replace their ciphertext-independent yet interactive preparation of secret-correlated randomness with a public, ciphertext-dependent 0.5s preprocessing step, eliminate interaction in the online phase while maintaining similar decryption time on the same machine, and support 32$\times$ more total users.

Anonymous credentials are seeing widespread deployment. Notably, the European Commission plans to roll out age-verification solutions based on anonymous credentials by the end of 2026. Similarly, Google open-sourced Longfellow, a zero-knowledge proof system that lifts the standardized mobile Driver License framework into a full-fledged anonymous credentials, and is currently being integrated with Google Wallet. Any secure deployment of anonymous credentials must address two major challenges: 1) provide guarantees against credential sharing, and 2) support proof-of-personhood. The standard approach adopted by the industry to address both is device binding, which is mandatory for mDL and was only recently formalized for anonymous credentials by Friedrichs et al. (Eurocrypt '26). Simply put, the idea is to have the user's phone Secure Element sign a fresh challenge from the verifier, and to prove knowledge of this signature in zero-knowledge at each credential presentation. To date, all existing approaches, including Vega (S&P '26), have only considered non-post-quantum solutions based on legacy signature schemes. Crucial for near-term deployments and adoption is to work with standardized post-quantum signature schemes, such as ML-DSA, which were not designed for privacy. Because of this, solutions based on general non-interactive zero-knowledge proof systems (e.g., Longfellow) appear to be needed. This genericity, however, requires proving complex statements, significantly impacting proving time. In this work, we present a modular device binding protocol tailored to work with ML-DSA. We avoid the pitfalls of the generic approach by leveraging the structure of ML-DSA resulting in an efficient solution, but retaining the security underlying the post-quantum standard. Our most efficient variants additionally rely on a weak-MLWR assumption for unlinkability, which can be removed at the cost of lower efficiency. While tailored for ML-DSA and requiring no modification to the FIPS~204 signing interface, our solution is modular enough to be integrated with different anonymous credential schemes, allowing real-world solutions to pick the most efficient building blocks. To demonstrate the feasibility of our solution, we provide a proof-of-concept implementation.

Proxy re-encryption is a cryptographic scheme enabling a delegator (user $i$) to delegate its decryption right to a valid delegatee (user $j$) through a proxy, who cannot extract any information about the message during the procedure. An important security notion is the security against collusion between the proxy and the delegatee. In this case, the adversary has the secret key of the delegatee, $\mathsf{sk}_j$, and the re-encryption key, $\mathsf{rk}_{i\to j}$. The master secret security is first formalised by Ateniese et al. (NDSS'05) to capture the secrecy of $i$'s secret key during collusion. This notion was further formalised by Zhou et al. (ASIACRYPT'23) as the indistinguishability of re-encrypted ciphertext against chosen-message attacks, called collusion safety, which implies the master secret security. In this paper, we find that a PRE scheme is not master secret secure as they claimed, and many other schemes were not master secret secure. Then, we propose a generic construction to achieve collusion safety at the cost of doubling the key size from the IND-CPA secure PRE, enjoying a much better generality and efficiency than the existing technique by secret sharing.

We introduce Leakage-Resilient Incompressible cryptography, which simultaneously addresses two variants of side-channel attacks that have been tackled in theoretical cryptography. Leakage-resilience seeks to provide security against an adversary who learns a part of the secret-key and the entire ciphertext or signature; conversely, incompressible cryptography provides security against an adversary who learns the entire secret-key, but only a part of the ciphertext or signature. However, constructions in either of these security models can fail against an attack in the other model. In this work, we define a new model of security that subsumes both leakage-resilient cryptography and incompressible cryptography, and we present several non-trivial positive and negative results. On the positive side, first we present a transformation from incompressible symmetric-key encryption (SKE) to leakage-resilient incompressible SKE in the information-theoretic setting. Next, as one of our main results, we construct a leakage-resilient incompressible public-key encryption (PKE), combining an incompressible SKE and a new primitive that we call leakage-resilient non-committing key encapsulation mechanism (LR-NC-KEM). While an information-theoretic incompressible SKE suitable for use in both these constructions already exists in the literature (Dziembowski, CRYPTO 2006), we present a new construction achieving ciphertext-rate $\frac{1}{2}$ and compression-rate $\frac{1}{2}$, using an appropriate notion of invertible extractors; this leads to corresponding improvements in the final parameters we obtain in these constructions. We also construct a leakage-resilient incompressible signature scheme in the classical random oracle model, assuming $(\mathsf{DCR}\text{ or }\mathsf{LWE})$ and the Decisional Linear assumption, with signature-rate and compression-rate $1-o(1)$ and leakage-rate $1$. On the negative side, we show barriers to significantly improving the parameters we obtain, by showing impossibility of basing the security of such improved schemes on blackbox reductions. Apart from the general framework and the specific results we obtain, some of the intermediate tools that we define and instantiate, like LR-NC-KEM and invertible extractors, may be of independent interest.

Threshold public-key encryption (tPKE) has recently attracted renewed interest, largely due to NIST's call for Multi-Party Threshold Cryptography. While classical tPKE has approached a high state of maturity, its post-quantum counterpart has not. Indeed, thresholdizing the celebrated lattice-based Regev PKE, which forms the basis of ML-KEM, remains unsatisfactory. Interestingly, how to thresholdize Regev PKE has not fundamentally changed in over a decade --- the only thing that has gradually progressed is its security analysis. To this day, it remains open whether threshold Regev can be proven secure while simultaneously satisfying a polynomial modulus, non-interactive decryption, and CCA-compatibility, each of which is essential for practical deployment. We answer this affirmatively, providing the first proof that threshold Regev is secure under the MLWE assumption while satisfying all three requirements. In fact, we prove that it satisfies a very strong form of simulation-based security --- even stronger than what was known under a super-polynomial modulus --- allowing the adversary to obtain partial decryptions even of the challenge ciphertext. At the technical heart of our result is the adaptive hint-MLWE (AHMLWE) problem, an adaptive variant of hint-MLWE where the adversary obtains hints on the MLWE secret with adaptively chosen coefficients. We show that AHMLWE reduces tightly to standard MLWE, which may be of independent interest.

FIPS 204 Table 1 gives the expected number of iterations of the ML-DSA signing loop (ML-DSA.Sign_internal, Algorithm 7), citing CRYSTALS-Dilithium Equation (5). That equation covers only the validity checks on line 23 ($\lVert z \rVert_\infty$ and $\lVert r_0 \rVert_\infty$) and omits the two encoding-correctness checks on line 28 ($\lVert c \cdot t_0 \rVert_\infty$ and the hint weight), a scoping distinction the Dilithium specification states explicitly and FIPS 204 does not reproduce. We give a complete accounting of all four conditions. The $z$ check on line 23 is computed exactly by counting; the $c \cdot t_0$ term follows a closed-form Irwin-Hall tail, restating a peer-reviewed result by Yan, Luo and Wang; the hint-weight term's per-coefficient probability, conditioned on line 23 having passed, does have a closed form, but the tail of the sum over $256k$ such coefficients does not, since their probabilities are unequal, random, and correlated with each other, so we give the conditioned per-coefficient probability in closed form and estimate its tail by Monte Carlo. The corrected expected iteration counts are 4.36, 5.14 and 3.91 for ML-DSA-44, -65 and -87, matching a real end-to-end measurement to within 0.14% and already reflected in NIST's own errata to FIPS 204.

Multi-round public-coin proof systems have progressed rapidly, yet their simulators and extractors are rarely used as building blocks in other protocols, unlike those of 3-move $\Sigma$-protocols. Prior work [Abe et al., Eurocrypt~'26] addressed the simulator side with critical-round zero-knowledge. In this paper, we address the extractor side and introduce critical-round special soundness (CRSS): a witness is extractable from a small critical subtree of transcripts that branches only from one round, while the full tree of transcripts serves only as a fall-back that outputs a solution to a hardness assumption. We first establish an extract-or-extend theorem that bounds the failure probability of the critical extractor even when the critical-round challenges are chosen by the adversary, and then show that KKW-style MPC-in-the-head proofs, KZG-compiled polynomial IOPs including Plonk, and Protogalaxy satisfy CRSS. We also give a corresponding tree-extraction result for the sumcheck sub-protocol of Spartan. We present three applications: a hash-based witness sharing scheme that verifiably secret-shares an NP witness without interaction among recipients, the first offline trapdoor-extractable trapdoor commitment from a multi-round proof, where a trapdoor is extracted immediately upon a double opening, and a parameter improvement for the multi-round Fischlin transform [Rotem-Tessaro, Crypto~'25] that reduces the prover's complexity in practice.

Responding to China's 2025 call for commercial cryptographic standards mandating 128-bit, 256-bit, and 512-bit security (optional 384-bit), we propose DTRU, a versatile, compact, simple, and robust NTRU-based key encapsulation mechanism (KEM). Our principal design contribution is double $E_8$ encoding, which constructs 16-dimensional lattice codes from $E_8$ with low decoding complexity. We further provide a detailed analysis of decryption-failure probability under this encoding mechanism. DTRU's design achieves a careful balance among versatility, compactness, simplicity, and robustness. To accommodate diverse application requirements, it supports multiple ring structures, including power-of-two cyclotomic rings, tricyclotomic rings, and large-Galois-group prime-degree prime-ideal number fields (LPPNF). The double $E_8$ encoding enables DTRU to achieve enhanced error correction with compact bandwidth. The design prioritizes simplicity to facilitate deployment on low-power devices, achieved by eschewing additional coefficient compression techniques and redundant invertibility checks during key generation, while enabling circuit/code reuse. Security robustness is guaranteed through parameter selections that offer adequate security redundancy, mitigating potential cyclotomic ring risks via LPPNF, and precluding sparse noise distributions in the recommended parameter sets. Complementing our theoretical advances, we present comprehensive implementations of all the parameter sets with dedicated support for C, AVX2, and ARM platforms, leveraging architecture-specific optimizations. For example, compared to NTRU-HRSS and Kyber at the same security levels, our KEM is 49%-52% more compact and 3.84–15.69$\times$ faster than NTRU-HRSS in the round-trip time of ephemeral key exchange, and is 7%-27% more compact and 1.05–1.32$\times$ faster than Kyber.

Stateful hash-based signatures fail badly when a one-time key signs twice, as happens when the signer's state is lost or rolled back. We study what a second signature reveals in a broad class of hash-based schemes whose key is a tree of hash chains. In this class, a message selects a set of tree nodes that covers every leaf exactly once, together with a position on the chain of each selected node, and the signature reveals the chain values at those positions. For the whole class, we prove that the values derivable from several signatures are exactly the union of those derivable from each signature alone, and we bound forgery after $b$ signatures in the classical random-oracle model by a combinatorial coverage exponent $\lambda_b$, also when the signer grinds a counter. We then present CUTS (Chained Uniform-sum Tree Signatures), a member of the class built on one binary tree, in which both the selected nodes and their chain positions depend on the message, with the positions summing to a fixed value $S$. Signature length and verification cost are fixed by the parameters and do not depend on the tree height. For CUTS, we compute the two-use coverage exactly as one coefficient of a polynomial and derive deterministic lower bounds on $\lambda_2$; one parameter set with 1 424-byte signatures has $\lambda_2\ge128.6$. A counter variant, CUTS+C, trades a short counter and extra signing work for a proven grinding gain of $g$ bits in the coverage term.

We give a lattice identity-based signature scheme from annular NTRU trapdoors and Fiat--Shamir with aborts (FSwA). Countered hashing maps each identity to its first invertible DLP/NTRU syndrome $a$. Extraction returns a short witness to $s_0+s_1h=a\bmod q$, and signing normalizes this relation to a fixed-target two-response equation with public commitment recovery. Gärtner's iterative rejection method fits naturally into this signing layer: processing the challenge monomials separately reduces the Gaussian mask width and expected signing attempts, yielding shorter signatures. We report three parameter sets whose signing layer is calibrated against NIST security categories 2, 3, and 5, with fixed signature sizes of $8486$, $11309$, and $12727$ bytes, respectively.

The results in this paper establish the genericity of some properties of the ideals and varieties generated by UOV public keys, in particular the equidimensionality of the UOV varieties and the radicality of public key ideals. These genericity results justify the various regularity assumptions that are made on polynomial systems of equations arising in the cryptanalysis of UOV and its variants. We also provide examples in the recent literature showing how genericity questions arise in crypt- analysis and why genericity should be taken into consideration when de- signing cryptographic schemes. Lastly, we perform a retrospective study of various cryptographic schemes through the viewangle of genericity. We identify several cases in which non-genericity led to the cryptanaly- sis of the scheme, but also provide a counter-example of a scheme whose non-genericity does not seem easy to exploit.

Building on the wedge-attack framework of Ding, Li, and Tao , we reformulate the Schur-Macaulay matrix approach of Merz and Ran in polynomial terms and develop a unified treatment using truncated polynomial algebras over fields of positive characteristic $p$. By working in $p$-truncated polynomial algebras, our formulation applies to the Unbalanced Oil and Vinegar (UOV) problem over arbitrary finite fields. Divided powers and transfer relations yield additional public relations within the ideal-inclusion framework, leading to quotient-dimension criteria for recovering graded components of the hidden oil-space ideal. As an application, we analyze the third-round QR-UOV parameter sets and obtain lower estimates of attack complexity for some of them.

ML-KEM is a lattice-based IND-CCA secure key encapsulation mechanism (KEM) standardized by NIST in FIPS 203. ML-KEM achieves chosen-ciphertext security by applying the Fujisaki-Okamoto (FO) transformation to an IND-CPA secure public key encryption (PKE) scheme. The FO transformation uses de-randomization and re-encryption to ensure ciphertext non-malleability, but because ML-KEM's underlying PKE encryption subroutine is slower than the decryption subroutine, ML-KEM's decapsulation performance is dominated by re-encryption. In this paper, we revisit the ``encrypt-then-MAC'' paradigm as a generic KEM transformation: the PKE ciphertext is authenticated by a message authentication code (MAC) whose key is derived from the PKE plaintext. We prove that the transformation achieves IND-CCA security in the random oracle model when the underlying PKE is one-way under plaintext-checking attack (OW-PCA), and we introduce a fine-grained security notion, one-wayness under $q$-bounded plaintext-checking attack (OW-$q$PCA), under which the transformation achieves IND-$q$CCA security. In contrast to the tag-based IND-1CCA transformations of Huguenin-Dumittan and Vaudenay (Eurocrypt 2022), whose tag is a random-oracle hash of the plaintext and the entire ciphertext, our transformation applies the random oracle only to the short PKE plaintext, while the long ciphertext is processed by a standard-model MAC that needs only to be one-time existentially unforgeable. We present ML-KEM-EtM, an IND-$q$CCA secure KEM derived from applying the encrypt-then-MAC transformation to the PKE subroutines of ML-KEM, and McElieceEtM, an instantiation with Classic McEliece that achieves full IND-CCA security under the conjectured OW-PCA security of its Niederreiter PKE. We implement ML-KEM-EtM with a wide selection of MACs including Poly1305, GMAC, CMAC, and KMAC256. At the cost of minimal increase in encapsulation CPU cycle count and ciphertext size, ML-KEM-EtM achieves a substantial reduction of the decapsulation CPU cycle count.

Batch threshold encryption allows a committee to decrypt a selected batch of ciphertexts using one short pre-decryption key per party, while ciphertexts outside the batch remain private. This makes batch threshold encryption attractive for building encrypted mempools for blockchains, where validators reveal transactions selected for a block while pending transactions remain private. However, in proof-of-stake systems like Solana or Ethereum, authorization depends on each validator's stake, which motivates a weighted version of batch threshold encryption. Naive approaches to weighting existing batch threshold encryption schemes lead to communication costs proportional to the weight assigned to each party. Existing schemes that avoid this cost either associate every ciphertext with a batch label or an encryption-time index. We present the first weighted batch threshold encryption schemes that require neither batch/epoch labels nor encryption-time ciphertext indices, while keeping each party's communication independent of its weight. We obtain two constructions by virtualizing prior schemes: the BTX construction of Agarwal et al. and the partial-fraction construction of Boneh et al. In both schemes' decryption procedures, each party communicates a single group element for an entire batch, regardless of its assigned weight. We prove correctness, robustness, and security under weighted variants of the original schemes' assumptions, and analyze the assumptions in generic bilinear groups. For the BTX-based construction, we also give a specialized distributed key generation protocol that avoids the general purpose MPC-based setup required by the previous state-of-the-art schemes. Finally, we implement our schemes to demonstrate their practical performance at parameter sizes relevant to blockchains.

Learning with Errors (LWE) and its variants underlie many lattice-based cryptosystems, making accurate concrete attack-cost estimates important for parameter selection. Practical primal attacks combine lattice-basis reduction with a final shortest-vector search, and their performance depends strongly on how these components are scheduled. We formalize the two-step strategy space considered in this work and propose PSSearch, a pruning-based method that selects a minimum estimated cost strategy under a specified reduction simulator and cost model. We instantiate the framework with a Pump-and-Jump BKZ (PnJBKZ) simulator supporting jump parameters \(J>1\), practical dimension-for-free settings, and LLL effects, together with a refined estimator for the dimension of the final SVP call. We integrate these components into a practical solver in G6K-GPU-Tensor and compare the PSSearch-selected strategies with its default heuristic strategy under comparable settings. On six TU Darmstadt LWE Challenge instances, the selected strategies achieve speedups of \(7.2\times\)--\(23.4\times\). Under the stated primal-attack and classical gate-count assumptions, the optimized two-step primal estimates for selected ML-KEM and ML-DSA parameter sets are \(3.4\)–\(4.6\) bits below the corresponding previous estimates; relative to the prescribed two-step baseline \(\mathsf{S}_0\), PSSearch provides an additional \(1.2\)–\(1.3\)-bit reduction. Along the tested relation \(\log_2 q=0.198n^{0.832}\), the empirically fitted advantage satisfies \(\Delta(\log_2T)=0.01887n-0.98\), where \(T\) denotes the estimated attack cost. These figures concern the primal-attack branch; the overall attack-cost estimate is determined by the minimum cost among all applicable attack families.

We prove expansion properties of superspecial isogeny graphs in dimension $g \geq 2$, including arbitrary level structure. In particular, we provide explicit bounds for the spectral gap, and a fine characterization of obstructions created by level structures (disconnectedness and periodicity). Without the level structure (the only case which was previously studied), our bounds dramatically improve the state of the art. These isogenies in dimension greater than one have become increasingly important in isogeny-based cryptography, and previous works have already conjectured consequences of their expansion properties. We present several applications of our result: we transform conjectural predecessors into rigorous algorithms, and we give the first algorithm for computing endomorphism rings of superspecial principally polarized abelian varieties in arbitrary dimension, with complexity $\tilde O(p^{g-1})$.

Multivariate signature schemes are among the few post-quantum candidates capable of providing very short signatures, but designing secure constructions has proven challenging. HFE-based schemes such as G$e$MSS were compromised by algebraic MinRank attacks. This motivates the HFE$_\text{IP}^-$ framework, which combines IP and minus modifiers to address these attacks. We introduce James and D-James, the latter achieving signatures of only 156 bits at the 128-bit classical security level and 348 bits at the 256-bit classical security level, among the shortest signatures reported for practical post-quantum public-key signature schemes, with estimated signing and verification costs comparable to those of G$e$MSS. The main technical contribution is the introduction of Dragon terms, which decouple the number of public equations from the hash output length, allowing the signature size to be reduced independently of the security parameter. We characterize the algebraic structure introduced by Dragon terms and show that it does not enable known MinRank attacks when combined with the HFE$_\text{IP}^-$ countermeasures. We also show experimentally that the known differential attack does not appear to extend to the minus variant. We further present parameter sets over both binary and small non-binary finite fields. For small values of $q>2$, the public-key size decreases by a factor of about 3 to 5 for $q\in\{4,5\}$, and by up to a factor of 10 for larger $q$, at the cost of slightly longer signatures and slower signing.

Threshold traitor tracing (Boneh et al. Crypto'24) addresses collusion in threshold encryption by tracing parties who collude to build illegal decryption devices called decoders. However, the original definition does not capture settings where adversaries can access partial decryptions published during normal system operation. In such settings, decoders sold to external buyers could depend on inputting additional partial decryptions from honest parties. Moreover, colluders may exploit observed partial decryptions when constructing a decoder to evade tracing, or even frame honest parties. Recently, Bormet et al. (TCC'26) addressed this by introducing \emph{threshold traitor tracing in the presence of partial insiders}. Their construction, however, works only in a weaker model, where decoders are assumed to output the full decryption, and colluders are assumed to observe only partial decryptions of \emph{valid ciphertexts}. Additionally, they use a trusted dealer for key generation. In this work, we present the first construction resilient against partial insiders in the stronger model of distinguishing decoders. Furthermore, our construction does not rely on a trusted dealer and remains traceable when colluders have access to a partial decryption oracle. As part of this, we show how to generically lift traceability under a partial decryption oracle for \emph{valid ciphertexts} to traceability under a partial decryption oracle for arbitrary ciphertexts using NIZK-PoKs. This transform is of independent interest, directly strengthening prior results that consider only valid-ciphertext partial decryption oracles, and allowing future analyses to focus on the simpler valid-ciphertext setting.

We present conceptually simple and practically efficient constructions of a verifiable random function (VRF) that fulfills strong notions of unbiasability recently introduced by Giunta and Stewart (Eurocrypt 2024). Unbiasability is a crucial property for many applications of VRFs such as leader election in proof-of-stake blockchains. The only previous constructions provide heuristic security in the random oracle model or rely on the decisional Diffie–Hellman assumption with preprocessing which incurs significant overhead. In contrast, our compiler turns any VRF into an unbiasable VRF in the standard model (without any setup) using only symmetric-key primitives; and thus only with negligible computational overhead. Underlying our approach, we provide a generic black-box reduction for unbiasability of VRFs that incurs subexponential loss. Additionally, under a mild (verifiable) requirement on the underlying VRF we also show a novel non-black-box reduction that incurs only polynomial loss. This non-black-box technique allows us to replace the folklore "VUF-then-Hash" heuristic with a provably secure "Hash-then-VRF" construction at virtually no cost. In particular, if the underlying VRF hashes its input, our transformation requires only a single evaluation of a hardcore function, e.g. parity of the input (plus a PRF evaluation for full security).

We construct the first multi-key fully homomorphic encryption (MKFHE) scheme where the ciphertext size, public key size, and secret key size remain independent of the number of users, $N$. Our construction is leveled and relies on the standard Learning with Errors (LWE) assumption. All prior MKFHE schemes incur at least linear growth in ciphertext size with the number of users ($|\mathsf{ct}| \propto N$), a limitation that has persisted across more than a decade of research. Our results provide the first evidence that MKFHE with constant ciphertext size is achievable under standard assumptions and paves the way for many interesting applications. We also describe a single-round distributed decryption protocol for multi-key ciphertexts in our fully-succinct MKFHE scheme. More remarkably, we show that our MKFHE scheme simultaneously satisfies the following properties: (1) the size of each user's partial decryption share is identically equal to the plaintext length (i.e., partial decryption shares are truly rate-1), and (2) an honest user's partial decryption can be simulated. To the best of our knowledge prior to this work, we did not have any MKFHE with one-round distributed decryption from standard assumptions that simultaneously satisfied both these properties. We show that our MKFHE is significantly useful in designing various forms of multi-party computation (MPC) protocols with asymptotically optimal communication complexity.

Modern cryptographic protocols rely on a relatively small collection of standardized hash functions and groups, raising the possibility of preprocessing attacks in which a computationally unbounded offline attacker generates a bounded-size hint that accelerates a later online attack. Blocki and Lee (EUROCRYPT~2022) analyzed the preprocessing security of key-prefixed short Schnorr signatures, where the public key is included in the random-oracle input. Their analysis imposed an a priori restriction on the number of oracle queries made during preprocessing and did not extend to standardized implementations of Schnorr, such as ISO/IEC 14888-3, which do not use key-prefixing but instead reject signatures whose hash challenge is zero. The preprocessing security of these nonzero Schnorr signatures was left as an open question. We resolve this question affirmatively in the ROM+GGM. Moreover, our analysis holds in a stronger model that permits unrestricted offline computation and oracle access, subject only to the size of the resulting hint, as well as adaptive corruption queries during the online phase. Suppressing lower-order terms, an online attacker making \(q\) total oracle queries, including \(q_\mathsf{H}\) random-oracle queries, forges a nonzero Schnorr signature for one of \(N\) users with probability at most $O(\sqrt{Sq^2/p} + q_\mathsf{H} N/2^{\lambda_\mathsf{H}})$, where \(p\) is the group order and \(\lambda_\mathsf{H}\) is the hash-output length. We show that the factor-\(N\) loss is inherent by giving a matching \emph{target-switching attack} with success probability \(\Omega(q_\mathsf{H} N/2^{\lambda_\mathsf{H}})\). By contrast, key-prefixing prevents this attack and the corresponding term in the security bound is just $q_\mathsf{H}/2^{\lambda_\mathsf{H}}$. Consequently, at the same \(\lambda\)-bit security level, key-prefixing enables signatures that are approximately \(\log N\) bits shorter than that of nonzero Schnorr. To support these results, we extend the Bit-Fixing-to-Auxiliary-Input framework of Coretti et al. (CRYPTO/EUROCRYPT 2018) to applications involving multiple idealized primitives. We also address a subtle technical challenge introduced by rejection sampling in the standardized nonzero Schnorr signing algorithm: although long rejection sequences are exceptionally unlikely, a signing query has no deterministic worst-case bound on the number of random-oracle and generic-group queries made by the challenger.

We show an attack on a lattice-based blind signature proposed in Crypto'20. Formally it is a linear hash function based framework with a lattice-based instantiation. We first notice a bug in their security proof of blindness, which is overlooked these years. Then, we develop an attack under the honest key and the honest-but-curious signer setting against the blindness notion of the schemes by exploiting the coorelations between the leaves of the tree. We also discuss how to repair the scheme.

A recent work by Belohorec et al. (Crypto, 2025) shows that the well-known PST multivariate polynomial commitment scheme is black-box extractable under falsifiable assumptions. They show that a minimally modified (extended) PST is extractable under an assumption ARSDH($n$), and that the canonical PST is extractable under an assumption GARSDH($n$). Both of these assumptions are new and more specialized than the original ARSDH assumption proposed by Lipmaa et al. (Eurocrypt, 2024) to prove black-box extractability of the univariate KZG polynomial commitment. A natural question is whether these assumptions are actually stronger than the original ARSDH assumption. We answer this negatively: we show that both ARSDH($n$) and GARSDH($n$) are equivalent to the original ARSDH assumption. Secondly, we point out a gap in the proof that canonical PST is extractable under GARSDH($n$) assumption.

Origami is a multivariate signature scheme submitted to the NGCC round-1 public-key call. We show that the submitted bilinear construction is a Rainbow-type scheme whose central map is exposed. The verification map is the layered signing map in a public coordinate order. The public key therefore gives an equivalent secret key, allowing signature forgery at about the cost of one verification (about $0.01$s at Origami-128). Our attack exploits this public layered structure and succeeds against the unmodified reference implementation on all four parameter sets and the official test vectors. We also refute the security proof's inversion assumption in a bilinear independent-coefficient model. The hidden local algebras introduced by Origami do not prevent the attack. They raise a separate problem: the specification treats constrained matrix coordinates as independent, and honest signatures lie in a proper subspace.

Post-Quantum Cryptography is now in its deployment phase. Amongst the threats encountered in real-world applications is Side Channel Analysis, a cryptanalysis branch relying on the study of physical leakages from unsecured implementations. However, the FALCON post-quantum signature includes non-linear functions on real numbers, and applying the generic masking countermeasure to these functions has only been recently studied. In this work, we use convergent sequences to approximate the function and a minimax polynomial to compute the first term of the sequence. The method is applied to the computation of the inverse square root and the square root in FALCON, two operators for which masking has not been investigated before. A theoretical analysis of the security in the t-probing model using the NI criterion and its variants is proposed. Compared to the existing state-of-the-art using the same approach which covers the masked inversion for emulated floating-point implementation, this paper is generic and works with any representation and precision for real numbers.

Notions like identity-based encryption (IBE) and attribute-based encryption (ABE) augment public-key encryption to provide fine-grained access control to encrypted data. In these settings, there is a single master public key that anyone can encrypt to. Users in turn possess different secret keys that determine which ciphertexts they can decrypt. The standard, or full, security notion for these schemes stipulates that a ciphertext computationally hides the message if the adversary does not possess a key that is allowed to decrypt. A relaxed notion of security that is often much easier to achieve is bounded-collusion security, where we only require security against adversaries that have an a priori bounded number of keys (and the scheme parameters can grow with this bound). For instance, it is known that vanilla public-key encryption implies bounded-collusion IBE (and ABE) whereas there is a black-box separation between public-key encryption and fully secure IBE. In this work, we develop a general methodology to upgrade a pairing-based encryption scheme with bounded-collusion security into one that is fully secure. We illustrate our methodology by applying it to two main applications: batched IBE and multi-authority ABE. First, in the case of batched IBE, we obtain the first pairing-based construction of batched IBE where there are no tag restrictions (in the generic bilinear group model). All previous pairing-based batched IBE schemes require attaching a tag to ciphertexts and secret keys, and moreover, restrict the adversary to an a priori bounded number of secret keys for each tag. Second, we use our techniques to obtain a multi-authority ABE scheme that supports conjunction policies in the generic bilinear group model. This is the first pairing-based scheme that makes fully black-box use of the group. Previous pairing-based multi-authority ABE schemes require a random oracle whose output is a group element (which implicitly assumes the underlying group supports a procedure for explainable oblivious sampling).

Candidates for post-quantum migration carry additional costs compared to their pre-quantum counterparts, especially for signatures, and they lose attractive properties of schemes such as BLS: homomorphism, and hence direct signature aggregation. We propose a methodology through which a pre-quantum primitive may still be securely used past Q-day (the advent of quantum computers) in settings where forgery of signatures or cryptographic proofs need only be prevented for a bounded lifespan (transient quantum security). The idea is to bind a fresh, ephemeral, ordinary pre-quantum key to a long-term post-quantum identity once per lifespan window, so a forgery under the fresh key is useful only for that window, and to derive the fresh key so that its exposure never leaks the long-term secret. Our main case study is an application to Ethereum consensus, conditional on stated registration, inclusion, and slashing-evidence rules. The construction keeps ordinary BLS aggregation and needs no SNARK prover. Each same-message aggregate is a single 96-byte signature, and each validator publishes 592-688 bytes of reveal data per epoch. Each epoch key is bound to a seed derived from a checkpoint finalized before that epoch, so a committed key is opened under exactly one seed. We reduce unforgeability in the public-tag game to co-CDH' in the ROM and QROM, with explicit probability and resource costs. Transient quantum security requires hardness at the resulting budget; later checkpoint-derived seeds also require the stated public-environment condition. Transient security requires forgery resistance for the whole interval in which an exposed key can affect the chain. Under Ethereum's attestation inclusion rules, that interval is nominally two epochs plus the reveal lead time under prompt processing. Historical slashing and delayed-fork acceptance need additional rules, which we state as preconditions. Published quantum attack costs inform the resource discussion. They do not establish a security lower bound for this construction. We also provide a formal model and security analysis for the construction, and, of independent interest, a new analysis of BLS where the secret key is sampled similarly to the Dodis-Yampolskiy VRF (IACR PKC 2005) and the adversary is given a related group element as leakage.

Post-quantum cryptography currently rests on a small number of hardness assumptions, posing significant risks should any one of them be compromised. This vulnerability motivates the search for new and cryptographically versatile assumptions that make a convincing case for quantum hardness. In this work, we argue that decoding random quantum stabilizer codes -- a quantum analog of the well-studied LPN problem -- is an excellent candidate. This task occupies a unique middle ground: it is inherently native to quantum computation, yet admits an equivalent formulation with purely classical input and output, as recently shown by Khesin et al. (STOC '26). We prove that the average-case hardness of quantum stabilizer decoding implies the core primitives of classical Cryptomania, including public-key encryption (PKE) and oblivious transfer (OT), as well as one-way functions. Our constructions are moreover practical: our PKE scheme achieves essentially the same efficiency as state-of-the-art LPN-based PKE, and our OT is round-optimal. We also provide substantial evidence that stabilizer decoding does not reduce to LPN, suggesting that the former problem constitutes a genuinely new post-quantum assumption. Our primary technical contributions are twofold. First, we give a reduction from random quantum stabilizer decoding to an average-case problem closely resembling LPN, but which is equipped with additional symplectic algebraic structure. While this structure is essential to the quantum nature of the problem, it raises significant barriers to cryptographic security reductions. Second, we develop a new suit of scrambling techniques for such structured linear spaces, and use them to produce rigorous security proofs for all of our constructions.

Post-quantum (PQ) migration is usually tracked per asset, with Mosca’s inequality and a share of “migrated” systems. For a flow of sensitive data, the relevant questions are different: is every session that carries it keyed by a quantum-safe secret, what evidence supports that claim, and what can an assessor establish from outside? We propose an assessment method whose unit is the data path and whose verdicts are tied to evidence. Key lineage is an algebra on break dates: a derived key falls when all its inputs fall, and a key falls when any of its copies falls. This covers TLS 1.3 resumption, key transport and keys wrapped several times. A verdict is a pair of strong-Kleene evaluations, one taking claims at face value and one admitting only claims that meet an evidence policy; the reachable pairs form four ordered labels. We characterize what an external probe can establish. A probe of the server decides a hop only if the server enforces PQ or cannot negotiate it; enforcement must be shown by a negative test paired with a positive control; a server that resumes sessions without a fresh key exchange leaves the layer undecided; and behind a load balancer the confidence of a negative test follows a sampling bound only under an independence assumption that a default balancer violates. We implement the probe and validate its inference rules on 22 configurations of five server stacks built on three TLS libraries, including confounders and a heterogeneous load balancer. The same nominal configuration yields different states across implementations, so declared configuration cannot replace runtime evidence. A protocol for an internet-scale enforcement study accompanies the paper

We introduce MIKE (Module Isogeny Key Exchange), a post-quantum NIKE (Non Interactive Key Exchange) whose security relies on the CDH problem for the rank-$2$ Hermitian module action on supersingular elliptic curves. For NIST level~$1$, MIKE has very compact public keys of 80B, and using our constant time C implementation, the key generation takes 0.65ms and the shared secret takes 4.9ms (including key validation) on a AMD CPU at 3.3GHz.

Post-quantum assumptions may not rely on the difficulty of finding secret subgroups as many classical schemes did. Instead, several assumptions make use of more general group actions, with the hope that quantum algorithms are not helpful in this less structured setting. Group action-based constructions were first presented in the context of isogenies in which an ideal class group acts on elliptic curves, but equivalence problems in error-correcting codes and lattices also exhibit such structures. Previous works presented anonymity-preserving constructions in a generic group action framework; however, they were not general enough to encompass the group action underlying the Lattice Isomorphism Problem (LIP), for which the acting group is countably infinite and non-commutative. We bridge this gap by, from zero-knowledge proofs of OR statements, building generic blind signatures and strong designated-verifier signatures with non-delegability from standard assumptions corresponding to a generalised group action inverse problem.

SLH-DSA is a standardized stateless hash-based signature scheme based on SPHINCS$^+$, but its signatures remain large. PORS+FP uses forced pruning to reduce the size of the bottom few-time signature (FTS) component, while BPORS+FP distributes repeated uses among independent PORS child keys. In BPORS+FP, each selected leaf reveals a fixed secret value, and a single pruning budget limits the total number of authentication nodes across all coordinates. We introduce BPORS-C+BFP, which replaces each secret at a child leaf with a short hash chain and assigns a separate authentication budget to each block of coordinates. The child Merkle tree authenticates each chain endpoint. Each selected chain still contributes one hash value to the signature, while its opening depth provides an additional encoding choice. For a fixed set of selected chains, a constant-sum constraint prevents forward hashing alone from converting one valid depth tuple into another. Under repeated use, signatures may disclose different positions on the same chain. We derive a generating-function upper bound on coverage and an exact counting method for individual pruning blocks that accounts for these disclosures and target acceptance. Separate block budgets confine pruning-induced dependencies, reducing the number of coordinates counted jointly and making exact calculation practical for small blocks. Replacing FORS in SPHINCS+ while keeping the hypertree and one-time signature parameters fixed, BPORS-C+BFP reduces complete-signature sizes by $8.3\%$--$18.1\%$ across six standard settings, compared with $3.7\%$--$13.4\%$ for BPORS+FP. Across three limited-use settings, the reductions relative to FORS are $32.5\%$--$36.5\%$ for BPORS-C+BFP and $22.0\%$--$26.0\%$ for BPORS+FP.

Matrix-native fully homomorphic encryption, introduced by Gentry and Lee, multiplies encrypted matrices with a Trace product and returns its four-component output to an ordinary ciphertext with a BigSwitch, whose keys over an extended ring dominate the key material of the scheme. Existing BigSwitches follow two routes: they either store one key per source, as in the original construction, or factor the secret through the trace and relinearize at run time, as in the Trace-Factored BigSwitch (TFB) of Park et al., which halves the keys at the price of $50\%$ more key switches and a whole switching error multiplied by the secret. Meanwhile, the Galois splitting of Park (Eurocrypt'25) decomposes such switches into base-ring diagonals, but it has not been used to reduce their keys. However, whether a BigSwitch can publish only the keys of TFB and still run at the speed of the original one has remained open. In this work, we first propose the pair-merge BigSwitch, which observes that the diagonals of a split BigSwitch are indexed by an inversion-closed coset $\kappa H$ and rewrites the target of a diagonal as $x\,g(s)+y\,s\,g(s)=g\big(g^{-1}(x)\,s+g^{-1}(y)\,s\,g^{-1}(s)\big)$, so that it borrows the product key of its inverse at the cost of one Galois step; it makes the $2n$ key switches of the original BigSwitch with $n/2+1$ instead of $n$ product keys, and we prove that no per-diagonal BigSwitch with $2n$ key switches holds fewer than $3n/2+1$ keys. Building on it, we propose public key rebasing, which turns Galois keys into product keys with one relinearization key placed one small modulus layer above the chain, so that the client publishes only the keys of TFB and a 10.6 MiB layer key, at the price of $1.5\times$ the resident keys of TFB on the server. Consequently, together with a Hermitian hop that finishes a partner diagonal of a Gram product with one Galois step, PairSwitch makes $2n$ key switches on general inputs and $3n/2+1$ on Gram products. On the parameters of Park et al. ($n=256$, $p=17$, $\log_2 PQ=200$), our implementation runs a BigSwitch $1.89$--$1.99\times$ faster than TFB and $1.28$--$1.38\times$ faster than the original BigSwitch, with $2.4$ bits less noise than TFB and $4.3$ bits more than the original, at a $128.3$-bit layer key; it is $2.45\times$ faster than TFB on Gram inputs. Our implementation and the raw logs are available at https://github.com/acprk/pairswitch-gl.

The One-Way-to-Hiding (O2H) theorem is a useful tool for analyzing reprogramming in the quantum random oracle model (QROM). It bounds the distinguishing advantage by the probability $\epsilon$ that a one-wayness attacker finds the reprogrammed point. A sequence of works has improved the tightness of this theorem. Currently, the Measure-Rewind-Extract O2H (MRE-O2H) theorem proved by Ge et al. (ASIACRYPT 2024) achieves the tightest known upper bound of $O(\sqrt{q}\cdot\epsilon)$, where $q$ is the number of quantum queries. This theorem follows the Double-Sided idea introduced by Bindel et al. (TCC 2019), which requires the one-wayness attacker to access both the original and reprogrammed random oracles, thereby imposing stronger requirements on the reduction. Moreover, it incurs a $q$-dependent loss of $O(\sqrt{q})$. In this paper, we address these limitations by proving two Extract-Amplify-Measure (EAM) O2H theorems. First, we prove a Single-Sided EAM-O2H (SSEAM-O2H) theorem, which achieves the same $O(\sqrt{q}\cdot\epsilon)$ upper bound as the MRE-O2H theorem, while the resulting attacker only needs access to either the original or the reprogrammed random oracle, reducing the requirements on the underlying reduction. Second, we prove a Double-Sided EAM-O2H (DSEAM-O2H) theorem, which retains the Double-Sided idea used in the MRE-O2H theorem but removes the $q$-dependent loss, yielding a tight $O(\epsilon)$ upper bound. As applications, we revisit the security of several Fujisaki--Okamoto variants proposed by Hofheinz et al. (TCC 2017) in the QROM, namely $\textsf{U}^{\slashed{\bot}}$, $\mathsf{FO}^{\slashed{\bot}}$, $\mathsf{FO}^{\slashed{\bot}}_{m}$, $\mathsf{FO}^{\bot}$, and $\mathsf{FO}^{\bot}_{m}$, and obtain the following results: The \textsf{IND-CCA} security of $\textsf{U}^{\slashed{\bot}}$ can be reduced to the \textsf{OW-CPA} security of the underlying PKE scheme. Compared with the previous proofs by Bindel et al. (TCC 2019) and Kuchta et al. (EUROCRYPT 2020), we avoid both the square-root loss and the $q$-dependent loss in the underlying adversary's \textsf{OW-CPA} advantage. The \textsf{IND-CCA} security of $\mathsf{FO}^{\slashed{\bot}}$, $\mathsf{FO}^{\slashed{\bot}}_{m}$, $\mathsf{FO}^{\bot}$, and $\mathsf{FO}^{\bot}_{m}$ can be reduced to the \textsf{IND-CPA} security of the underlying PKE scheme. Compared with the previous proofs by Ge et al. (ASIACRYPT 2024), we reduce the $q$-dependent loss from $O(q^{1.5})$ to $O(q^{0.5})$. Assuming unique randomness recoverability, the \textsf{IND-CCA} security of $\mathsf{FO}^{\slashed{\bot}}$, $\mathsf{FO}^{\slashed{\bot}}_{m}$, $\mathsf{FO}^{\bot}$, and $\mathsf{FO}^{\bot}_{m}$ can be reduced to the \textsf{OW-CPA} security of the underlying PKE scheme. Compared with the previous proofs by Ge et al. (ASIACRYPT 2024), we avoid the $q$-dependent loss in the underlying adversary's \textsf{OW-CPA} advantage.

SQIsign encodes its response isogeny via a two-dimensional representation on a product of elliptic curves, using the Kani construction. We analyze the algebraic structure of this encoding in detail, with a focus on the role of the auxiliary isogeny and its implications for strong unforgeability. We show that the anti-isometry $\psi$ determining the Kani kernel is publicly computable from the torsion-point images of the component and auxiliary isogenies alone, that the automorphism orbit $\{\psi, -\psi\}$ is the only torsion-level source of encoding non-uniqueness on a fixed product surface, and that every auxiliary of the correct degree is commitment-compatible by Kani's theorem. The sole barrier to producing an alternative encoding is the construction of a new auxiliary isogeny of the required (generically non-smooth) degree from the challenge curve. We demonstrate that this barrier falls whenever a single small prime divides the auxiliary degree $2^f - q$: the adversary reroutes the terminal $\ell$-isogeny step at the codomain of the honest auxiliary, preserving the total degree exactly. Since generic odd integers possess small prime factors with overwhelming probability, this establishes that canonicalization of the basis change matrix does not suffice for strong unforgeability. We analyze the signing algorithm's dependency structure to show that the auxiliary cannot be bound into the Fiat-Shamir hash without a protocol redesign, and conclude with a structural comparison of ECDSA (where canonicalization suffices), SQIsign (where it does not), and salt-PRISM (which achieves strong unforgeability via a salted hash-to-prime mechanism that eliminates the auxiliary freedom entirely).

The Fujisaki--Okamoto (FO) transform (Journal of Cryptology, 2013) is the standard route from weakly secure public-key encryption to chosen-ciphertext security, and it underlies many practical post-quantum key-encapsulation schemes, including ML-KEM. Security proofs for FO are set in the (quantum) random oracle models. FO uses two hash functions: the derandomization hash~$H$, which turns the base scheme into a deterministic trapdoor function (TDF) by Encrypt-with-Hash, and the key-derivation hash~$G$. We ask whether it is possible to instantiate the hash functions in the FO transform while retaining its security guarantees. While prior work mainly focused on the $H$ step, our focus is the $G$ step, and we take an underlying injective TDF as given. We first show that the message-only implicit-rejection variant \smash{$\UmIR$}, a key-encapsulation mechanism formulation of FO that follows ML-KEM's choices of rejection and key derivation, is \emph{uninstantiable} in general. Namely, assuming standard LWE and subexponentially secure indistinguishability obfuscation and puncturable PRFs, for every efficient hash function family~$G$ with superlogarithmic output length there is a one-way, perfectly correct injective trapdoor function for which the resulting KEM is not IND-CCA2 secure. We next give sufficient conditions on~$G$ to instantiate the TDF-based \emph{hybrid-encryption} formulation of FO, rather than the KEM version. To this end, we introduce \emph{distributional injective extractability} (\DINJEXT{}), a new hash function property defined relative to a partially injective ``wrapping function.'' Under this assumption relative to the FO-derived wrapping function, combined with an achievable form of universal computational extractor security (Bellare, Hoang, and Keelveedhi, CRYPTO 2013) on $G$ and suitable assumptions on the base schemes, we obtain standard-model IND-CCA2 security. As evidence that \DINJEXT{} is achievable, we show that a random oracle satisfies it for every partially injective wrapping function, and that a quantum random oracle satisfies a formulation of it for the FO wrapping function, in both cases even relative to an oblivious sampling oracle. We leave a standard-model construction open.

An additive positive accumulator represents a growing set by a short public digest. Each inserted element has a membership witness, which may have to be refreshed after later insertions. An execution of $n$ insertions therefore defines a labeled update vector $d=(d_1,\ldots,d_n)$, where $d_i$ is the number of strict post-insertion refreshes of the witness created at time $i$. Previous lower bounds concern scalar quantities such as $\max_i d_i$ and $\sum_i d_i$. Even when both are known, they do not determine how the updates are distributed among the labeled witnesses. Let $\mathcal T_w([n])$ be the set of left-depth vectors of inorder binary trees on $[n]$ whose right-depth is less than $w$, and define the convex upward region \[ \mathcal G_w^{(n)}:=\operatorname{conv}(\mathcal T_w([n]))+\mathbb R_{\ge0}^n. \] Our main result constrains the entire expected update vector. For polynomial-time update specifications, let $m=\Theta(1+L/\log\lambda)$, where $L$ bounds the accumulator length. For every fixed $\delta>0$ and all sufficiently large $\lambda$, \[ \mathbb E[d]\in(1-\delta)\frac{m}{m-1}\mathcal G_{m-1}^{(n)}. \] Equivalently, there is one distribution $\Pi_{\lambda,\delta}$ over feasible trees such that \[ \mathbb E[d_i]\ge(1-\delta)\frac{m}{m-1}\mathbb E_{T\leftarrow\Pi_{\lambda,\delta}}[\ell_T(i)] \qquad\text{for every }i. \] Thus the same tree distribution constrains all labeled coordinates. The region $\mathcal G_w^{(n)}$ is characterized by its nonnegative linear inequalities. If \[ V_w(a):=\min_{T:\,\max_i\rho_T(i)<w}\sum_i a_i\ell_T(i), \] then $x\in c\mathcal G_w^{(n)}$ exactly when $a\cdot x\ge cV_w(a)$ for every $a\ge0$. For arbitrary history-dependent update specifications, we establish the corresponding inequality for every predetermined efficiently computable nonnegative weight vector $a$: \[ \mathbb E\!\left[\sum_i a_i d_i\right]\ge(1-o(1))\frac{m}{m-1}V_{m-1}(a), \] together with a corresponding lower-tail bound. Indicator vectors give position-independent cohort bounds; in particular, every predetermined cohort of size $k$ has benchmark at least $(k-m+1)_+$ up to the same factor. The combinatorial basis of these results is that the temporal-blocking vectors used in replay attacks and the vectors in $\mathcal T_w([n])$ have the same upward closure. To transfer this characterization to accumulator executions, we use fractional tuple packing, interval rounding, and conditional resampling controlled by the $L$-bit accumulator state. For the vector theorem, a separating direction is computed from independent executions before the replay attack is applied to a fresh execution. At fixed width, the same tree vectors describe the coordinatewise lower boundary of online-merger update profiles. Every feasible tree vector is realized by an online merger and, through the standard Merkle-forest construction, by an additive positive accumulator.

In FHEW/TFHE, a programmable bootstrap evaluates an arbitrary function of the encrypted message, encoded as the \emph{test polynomial} of a blind rotation. We work in a prime-power cyclotomic ring whose prime is the plaintext modulus $p$ (a \emph{design choice} that leaves the ring degree free as a security parameter) and compare the \emph{Single-Value Mode} (SVM), one rotation per function, with the \emph{Multi-Value Mode} (MVM), one \emph{function-independent} rotation shared by all. Factoring the test polynomial as $v^*_f = \mathfrak B^*_f\cdot \mathfrak w$, the function carried by the dual module and the rotated factor by the torus, lets a single hypothesis (a centered accumulator error of \emph{arbitrary} covariance $G$) cover both modes: the two variances are values of one $G$-form, and their ratio is the exact amplification. The $f$-independent factorizations are then parametrized by a non-zero ring element, the cofactor, and by the integer lift of the table: at a random lift the cofactor is chosen by a shortest-vector problem for an explicit quadratic form, then the lift by a closest-vector problem of rank $p-1$. In the spherical model that form is a trace norm and two designs compete: the canonical cofactor, of noise cost $p(p+1)/6$, and the pivot, which reads the integer table itself at noise cost $2p$, at a random lift; the optimized lift then favours the canonical cofactor on the generic tables. Under the other natural covariance, the block Laplacian, it is optimal for every $p$. Both cofactors are measured, in the key-noise regime, on a complete implementation, publicly available.

For $N$ a power of $2$, the negacyclic number-theoretic transform (NTT) maps a degree $N-1$ polynomial to its evaluations at the $N$ primitive $2N$th roots of unity. In-place butterfly algorithms such as Cooley-Tukey and Gentleman-Sande compute the negacyclic NTT in $O(N\log N)$ time and output the evaluations in a specific, standard order. We give in-place butterfly algorithms for the negacyclic NTT and its inverse that instead output the evaluations in an automorphism-compatible order. These algorithms have the same structure as Cooley-Tukey and Gentleman-Sande, differing only in their precomputed twiddle factors. Our automorphism-compatible butterfly algorithms are applicable to the packed fully homomorphic encryption (FHE) schemes CKKS and BGV/BFV, where the negacyclic NTT is a major component of ciphertext arithmetic. Using our automorphism-compatible butterfly algorithms, Galois automorphisms can be applied to ciphertexts stored in double-CRT format via a simple cyclic shift or adjacent-pair swap of the data. This is contrast to butterfly algorithms currently used that output in the standard order, where applying an automorphism requires performing an arbitrary-looking permutation of the stored data. Our automorphism-compatible butterfly algorithms remove the need for a dedicated automorphism functional unit used in FHE hardware accelerators.

Explicit equations for the locus $\mathcal{L}_n$ of genus-two curves with a maximal degree-$n$ elliptic subcover have been computed only for $n \le 5$, and by elimination, whose cost is not predictable in advance. The degree formula of [22] changes this. It gives $\deg_w F_n = k(H_{n^2}) - 10\,\nu(n)$ in closed form, and with it a reduced monomial support for the associated Humbert modular form $G_{n^2}$, so that the reconstruction becomes a determined linear problem whose every dimension is known before any computation begins. We carry this out for the first new case it opens, discriminant $36$: we determine $k(H_{36}) = 720$, $\nu(6) = 12$, $\deg_w F_6 = 600$ and an admissible modular basis of size $41962$, and we compute the four Siegel generators explicitly along Kumar's rational parametrisation of $H_{36}$, obtaining in particular a complete factorisation of $\chi_{10}$ whose factors recover the degenerate loci of the family from the modular side. We then draw the consequences for isogeny-based cryptography. The equation $\overline{F}_n$ decides optimal $(n,n)$-splitting at every point of the moduli space in characteristic $p$, with no hypothesis on the Newton polygon; this is asserted but not proved in the cryptographic literature, and the available proof excluded exactly the superspecial locus where the question is asked. The weight $k(H_{n^2})$ bounds, unconditionally and with explicit constants, the number of superspecial nodes that detection at level $n$ adds to the target set of the best known attack in dimension two. And the same torsion count $\nu(n)$ that appears in the degree formula governs the cost of both known detection routes, which places a barrier on raising the level and singles out $n = 6$ as the one case where a new equation can matter in practice.

We present $\mathsf{ATLAS}$, a lattice-based digital signature scheme built on the Fiat--Shamir with aborts paradigm, with security based on the hardness of the Module Learning with Rounding ($\mathsf{MLWR}$) problem. Unlike $\mathsf{Dilithium}$'s $\mathbf{t} = \mathbf{As}_1 + \mathbf{s}_2$ construction or $\mathsf{HAETAE}$'s bimodal, hyperball-uniform instantiation, $\mathsf{ATLAS}$ derives its public key via deterministic rounding, $\mathbf{t} = \lfloor \tfrac{p}{q}\mathbf{As}_1 \rceil$, eliminating the error term $\mathbf{s}_2$ and the explicit noise sampling it requires. This reduces key-generation cost and secret-key storage, and removes a component that both $\mathsf{Dilithium}$ and $\mathsf{HAETAE}$ would otherwise need to support, while keeping $\mathsf{ATLAS}$ structurally close to $\mathsf{Dilithium}$ to inherit its well-studied design and cryptanalytic track record. $\mathsf{ATLAS}$ targets three classical security levels, 128, 256, and 512 bits, using the smallest feasible ring degree $n$ and challenge weight $\kappa$ for each, with module dimensions $(k,l)$ tuned per level. To our knowledge, this includes the first \mlwr-based signature parameter set at the 512-bit level. $\mathsf{ATLAS}$ further adopts power-of-two moduli (e.g., $q=2^{23}$, $p=2^{18}$), replacing modular reduction with bitwise operations and removing rejection sampling from key parts of the scheme. Since such moduli preclude conventional NTT-based multiplication, we design a hierarchical Toom-Cook/Karatsuba decomposition with degree-8 schoolbook multiplication as its base case, accelerated via AVX2 vectorization and strided memory access. Finally, $\mathsf{ATLAS}$ supports both $\mathsf{SHAKE}$ and $\mathsf{KDF-SM3}$ as interchangeable symmetric back-ends, and we quantify the overhead of the $\mathsf{SM3}$-based instantiation relative to $\mathsf{SHAKE}$.

We present SCORE, a tweaked version of the SlotToCoeff operation tailored to the context of encrypted real vectors in the CKKS scheme, where SCORE stands for “SlotToCoeff Optimization for Real-Vector Encryption”. This approach accelerates CKKS bootstrapping algorithms that employ the SlotToCoeff operation as their final step, provided the inputs are encryptions of real vectors. SCORE constitutes a conceptually simple refinement of the conventional SlotToCoeff step that can be seamlessly incorporated into existing bootstrapping algorithms. Despite its minimal nature, the technique yields tangible performance improvements. We demonstrate its utility through proof-of-concept implementations for two such algorithms: the conventional bootstrapping algorithm and the SPRU algorithm, which is particularly efficient for ciphertexts containing a small number of encrypted slots. Our results indicate notable performance gains of up to $2\times$ compared to the original formulations of the algorithms.

This paper considers the problem of building blind signatures in pairing-free groups. We provide the first three-move blind signature which is provably one-more unforgeable, in the random-oracle model, under the minimal assumption that the discrete logarithm (DL) problem is hard. Our construction in fact achieves one-more strong unforgeability, and also supports partial blindness. Blindness is statistical, also in the ROM. Our construction makes black-box use of the underlying group and does not rely on non-black-box techniques. For most such constructions, three moves are necessary by a recent result of Dietz, Kastner, and Tessaro (CRYPTO '26). We build on recent work by Chairattana-Apirom, Reichle, and Tessaro (CRYPTO '26), which achieved the same combination of round complexity and security guarantees, but under the stronger decisional Diffie--Hellman (DDH) assumption. In particular, we follow the same paradigm of boosting the security of a weakly secure scheme (namely, the Okamoto--Schnorr blind signature) to a fully secure one by authenticating the initial nonce. We provide, however, a substantially different instantiation of this paradigm that dispenses with the use of DDH and establishes security from DL alone.

Threshold signature schemes play a vital role in securing digital assets within blockchain and distributed systems. $\textsf{FROST2}$ stands out as a practical threshold Schnorr signature scheme, noted for its efficiency and compatibility with standard verification processes. However, under the one-more discrete logarithm assumption, with static corruption and centralized key generation settings, $\textsf{FROST2}$ has been shown by Bellare et al. (in CRYPTO 2022) to achieve only $\textsf{TS-SUF-2}$ security, which is a consequence of its vulnerability to $\textsf{TS-UF-3}$ attacks. In this paper, we address this security limitation by presenting an enhanced variant of $\textsf{FROST2}$, namely, $\textsf{FROST2}\texttt{+}$ which achieves the $\textsf{TS-SUF-4}$ security level under the same computational assumptions as the original $\textsf{FROST2}$. $\textsf{FROST2}\texttt{+}$ strengthens $\textsf{FROST2}$ by integrating additional pre-processing token verifications that help mitigate $\textsf{TS-UF-3}$ and $\textsf{TS-UF-4}$ vulnerabilities while maintaining practical efficiency. We show that $\textsf{FROST2}\texttt{+}$ can achieve $\textsf{TS-SUF-4}$ security not only under the same conditions as the original $\textsf{FROST2}$ analysis, but also when initialized with a distributed key generation protocol such as $\textsf{PedPoP}$. Our benchmark using ZCash's $\textsf{FROST}$ library shows that the performance of $\textsf{FROST2}\texttt{+}$ is comparable to $\textsf{FROST2}$ and about $64-79\%$ faster than \textsf{FROST} when precomputation is enabled

We introduce Output-Adaptive Security, a new intermediate security notion for Attribute-Based Encryption (ABE) that bridges the gap between selective and full adaptive security. In our model, the adversary selectively commits to a policy function structure $f$ but adaptively chooses a long target output value $y$ during the challenge phase. We construct the first Output-Adaptive ABE scheme for general circuits from the standard Learning With Errors (LWE) assumption by revisiting classical partitioning techniques and applying them to the output space of circuit evaluation. Our result demonstrates that adaptivity for expressive policies can be achieved from standard lattices without complexity leveraging or heavy tools like witness encryption and indistinguishability obfuscation. Furthermore, we show that output-adaptivity is sufficient for many real-world applications, including biometric matching, weighted thresholds, and wildcard search, where system architecture is static while policy targets remain dynamic.

We significantly expand the reach of isogeny-based cryptography by constructing, for the first time, two fundamental primitives that have long remained out of reach from isogenies: identity-based encryption (IBE) and semi-honest single-server private information retrieval (PIR) with communication polylogarithmic in the database size. Our IBE additionally achieves anonymity, which means that the ciphertexts hide both the message and the recipient identity. Our results are enabled by new techniques for constructing cryptographic primitives from structured isogeny computations, centered around the first construction of blind batch encryption from isogenies. To establish its security, we introduce a new hardness assumption, CDH with Mismatched Torsion (CDHwMT), which informally captures the hardness of a CDH-like problem in the presence of structured auxiliary isogeny information. We provide evidence for its plausibility by showing that, in the Algebraic Isogeny Model, CDHwMT reduces to well-studied isogeny assumptions. The same techniques yield further cryptographic applications: the first isogeny-based hierarchical IBE, laconic oblivious transfer, and public-key encryption simultaneously achieving high-rate leakage resilience and key-dependent-message/circular security. All of our constructions can be conjectured to be post-quantum secure. Beyond these individual primitives, our results demonstrate that isogenies can support substantially richer cryptographic functionality than previously known, and provide new tools toward building advanced post-quantum cryptography.

The ICCS Next-Generation Commercial Cryptography (NGCC) round-1 call received 84 public-key candidates for public evaluation. We present a design-level assessment that targets weaknesses no local code fix can close, identifying eight such flaws. Each recurs a pitfall already known from NIST PQC standardization: reducible-ring sub-ring projections that break IND-CPA below the claimed level; public data that fixes a value meant to remain secret, enabling public-key-only forgery or keyless decapsulation; static-key reuse without a chosen-ciphertext transform; and rejection sampling whose sign handling leaks an equivalent signing key. All findings were obtained with AI assistance. Artifacts: https://github.com/acprk/ngcc-round1-cryptanalysis.

Multisignatures compress many signatures on a common message into a single aggregate. In large distributed systems, aggregation occurs over multiple hops, where partial aggregates may overlap. The recent hint-free multisignatures of Hofheinz, Reichle, and Wagner (TCC~2026) eliminate aggregation-topology hints, but verification still requires the complete set of participating public keys. This leaves open whether the signer-set information itself can be eliminated. We answer this question negatively. We introduce idempotent multisignatures to capture unrestricted aggregation of overlapping aggregates and prove that any such scheme has a signature size linear in the number of signers. To circumvent this lower bound, we introduce unique multisignatures, a sequential alternative that eliminates this metadata and retains constant-size signatures. We construct unique multisignatures using incrementally verifiable computations. Finally, replacing signature chains in authenticated Dolev-Strong Byzantine Broadcast with our primitive enables two-round termination when the sender is honest and reduces communication from $O(n^3)$ to $O(n^2)$ against $t<n$ adaptive corruptions.

We revisit the three-round threshold Schnorr signature scheme Sparkle of Crites, Komlo, and Maller (CRYPTO 2023), as well as its variant Sparkle+. While Sparkle+ was accompanied by a claim of full adaptive security, subsequent work identified a gap in the analysis. The original—and simpler and more efficient—Sparkle scheme has so far lacked even a proof of static security. We resolve this by proving static security for Sparkle; our main result is then a tight proof of its full adaptive security in the pure random oracle model, i.e., without relying on the algebraic group model. The core obstacle is that, in the fully adaptive setting, rewinding arguments fundamentally break down. To address this, we base our proof on the Vandermonde circular discrete-logarithm (VCDL) assumption, an interactive strengthening of the circular discrete-logarithm assumption of Cho et al. (CRYPTO 2025), originally introduced to prove tight security of basic Schnorr signatures. Circular-style assumptions eliminate the need for rewinding. Beyond tightness, our analysis highlights circular-style assumptions as a new approach to achieving security in other settings where rewinding is problematic. We justify VCDL by reducing it to the low-dimensional vector representation (LDVR) problem of Crites et al. (CRYPTO 2025) in the elliptic-curve generic group model. Finally, we generalize VCDL (and similarly LDVR) and identify a different assumption within this framework that yields a tight proof of adaptive multi-user security for the basic Schnorr signature scheme, a result of independent interest.

Broadcast encryption (BE) allows a sender to succinctly encrypt a message to any dynamically chosen subset of recipients. The gold-standard for BE is $\textit{optimal succinctness}$ (parameters independent of the number of users) and $\textit{adaptive security}$. Attaining both from falsifiable post-quantum assumptions has been a central open problem. Recently, Goyal and Yadugiri (GY) [Goyal-Yadugiri; CRYPTO'26] gave the first adaptively-secure and optimally-succinct slotted distributed BE under a falsifiable lattice assumption, but their techniques inherently require an a-priori bound on the number of users and a slotted user structure. Two highly-sought-after generalizations thus remained open: $\textit{flexible BE}$ (FBE), where users asynchronously sample and register their own keys and $\textit{identity-based BE}$ (IBBE), where a trusted authority issues keys for identities drawn from a super-polynomially large space. In this work, we present the first adaptively-secure FBE and IBBE schemes with all parameter sizes independent of the number of users, both under the same falsifiable lattice assumption (decomposed LWE) and in the same model (Random Oracle Model) as the prior state-of-the-art for slotted distributed BE. Our FBE additionally enjoys a $\textit{transparent setup}$, in line with the trustless ethos motivating distributed and flexible BE. At the technical heart of our results, we extend the equivocal encryption framework of GY to capture $\textit{unbounded}$ and $\textit{dynamic}$ broadcast systems, and introduce $\textit{Equivocal Matrix Commitments}$ --- a strengthening of matrix commitments that supports adaptive equivocation of the committed matrix. We expect this new abstraction to find broader applications in designing adaptively-secure trustless lattice-based encryption.

We present the first Distributed Broadcast Encryption (DBE) scheme from falsifiable lattice assumptions that achieves adaptive security with optimal parameters (short public/secret keys and ciphertexts). Our construction enjoys transparent setup and offers flexible instantiation: we achieve a succinct CRS in the Random Oracle Model, or a long CRS in the standard model. Previously, no lattice-based DBE simultaneously achieved adaptivity and optimal parameters in either setting. To achieve this, we introduce a new methodology for proving adaptive security: $\textit{Equivocal Encryption Systems}$. This framework operates in two indistinguishable modes: a 'real' mode utilizing standard algorithms, and a 'fake' mode where keys and ciphertexts are jointly sampled with auxiliary trapdoors, enabling the dynamic equivocation of ciphertexts to arbitrary challenge values. While our approach is technically distinct from the celebrated Dual System Encryption (Waters, CRYPTO'09), we believe it could serve as a similarly powerful paradigm for realizing adaptive security across a broad class of lattice-based encryption systems.

Since its introduction, Solinas' window $\tau$-NAF algorithm has been a landmark method for accelerating scalar multiplication on Koblitz curves over binary fields. A long-standing open problem has been to identify a suitable family of elliptic curves over prime fields for which the window $\tau$-NAF approach can be effectively extended. In this paper, we settle this problem by establishing such an extension for the family $E_b: y^2=x^3+b$ over $\mathbb{F}_p$ with prime $p\equiv1\pmod 3$. This family includes several practically important curves used in blockchain applications (e.g., secp256k1) and pairing-based cryptography (e.g., BN254 and BLS12-381). By considering a nonzero nonunit element of minimal norm in the ring of Eisenstein integers $\mathbb{Z}[\omega]$, we identify the endomorphism $\tau=1-\omega$ as a natural choice for $\tau$-adic scalar multiplication on $E_b/\mathbb{F}_p$. In Jacobian projective coordinates, the map $\tau P$ can be evaluated using only $6\mathbf{M}$ (where $\mathbf{M}$ denotes a field multiplication). This also yields a new point-tripling formula requiring only $10\mathbf{M}$, improving upon the previous best cost of $15\mathbf{M}$. Furthermore, we optimize the pre-computation stage by choosing a set of coefficients invariant under the unit group $U\subset\mathbb{Z}[\omega]$. Exploiting this sixfold symmetry reduces the pre-computation cost by approximately five-sixths. The $U$-invariant structure also plays an important role in further accelerating window $\tau$-NAF evaluation. Our optimized method achieves performance improvements of $16.7\%$, $17.6\%$, and $18\%$ over the current state-of-the-art GLV method for $256$-, $384$-, and $512$-bit group orders, respectively. We also develop a regular window $\tau$-NAF variant as a countermeasure against side-channel attacks. Compared with the regularized GLV method, this variant reduces the scalar multiplication cost by $17.7\%$, $19.8\%$, and $20.9\%$ for $256$-, $384$-, and $512$-bit group orders, respectively.

Atomic swaps are the prototypical application of adaptor signatures. Practical constructions settle with two ordinary on-chain signatures and require no scripting, but they need two sequential online rounds: Alice samples a hard statement and sends its pre-signature, and Bob follows with his own pre-signature using the same statement. We ask whether the protocol can be compressed into a single online round (from Bob to Alice), which we call a non-interactive atomic swap, without relying on impractical universal adaptor signatures. In particular, we require that both parties continue to use standard signature schemes with unmodified verification algorithms. Our main result is a lower bound: for statistically unlinkable adaptors with negligible faithfulness failure, Bob's valid-signature space per message must be superpolynomially larger than the relation's witness space. This (1) reaffirms the impossibility result by Erwig et al. [PKC 2021] for unique signatures as a trivial corollary, and (2) excludes non-interactive swaps using the same signature scheme on both sides. However, the bound does leave room for asymmetric instantiations. We give one in which Alice signs with BLS and Bob uses a pairing-Schnorr adaptor whose witness is Alice's BLS signature, and prove its security under the native unforgeability of BLS in the random oracle model. To support more signature schemes in our non-interactive swap framework, we introduce atomic signature swaps with preprocessing: Alice publishes message-independent public data before the messages are chosen. These data, together with her public key and the messages, later determine a statement whose witnesses assemble into her native signature. The protocol requires a single online round carrying a pre-signature by Bob and falls into our non-interactive framework. We prove a Schnorr/Schnorr instantiation under the OMDL assumption in the random oracle model, and give a conditional ECDSA/Schnorr instantiation.

We present variants of blind Schnorr and blind Okamoto-Schnorr signatures that are not susceptible to ROS-style attacks. We prove the schemes unforgeable in the algebraic group model and the random oracle model: the Okamoto-Schnorr variant under the discrete-logarithm assumption; the Schnorr variant under the algebraic one-more discrete-logarithm assumption. Our Schnorr variant improves on the communication complexity of Snowblind (CRYPTO 2023), the state-of-the-art "pairing-free" blind signature scheme, while matching its signature size. Moreover, we show that this communication complexity is optimal: any blind "Schnorr-like" scheme whose first message is a single group element is susceptible to a variant of the ROS attack by Benhamouda et al. (EUROCRYPT 2021).

Secure Multi-Party Computation (MPC) enables collaborative and privacy-preserving computation over private inputs. Recent advances in Homomorphic Encryption (HE), particularly the CKKS scheme, have significantly improved the practicality of secure computation, making it suitable for real-world applications involving approximate arithmetic. However, the inherent errors introduced by CKKS pose substantial challenges in the design and analysis of CKKS-based secure computation protocols. In this work, we investigate the correctness and security of existing CKKS-based MPC protocols. Most prior constructions rely on the noise smudging technique, in which each party independently adds exponentially large noise to the output to guarantee the security of the protocol. However, we show that this approach does not achieve standard simulation-based security for MPC. To address this limitation, we apply an alternative method, called collaborative sampling, in which all participating parties jointly generate additive shares of the smudging noise. We consider both asymmetric two-party protocols between a client and a server, and symmetric multiparty protocols among mutually distrusting parties. For each setting, we present concrete protocol constructions based on collaborative sampling, explicitly define the corresponding ideal functionalities, and provide formal security proofs. We further provide concrete constructions and implementations of collaborative sampling protocols. As an alternative perspective, we show that existing protocols, despite failing to achieve standard simulation-based security, still satisfy a weaker security notion called liberal security for approximate MPC protocols.

Merz and Ran derive additional equations from divided powers of the public polar forms in characteristic two. We extend this construction to finite fields of arbitrary characteristic and apply it to the security analysis of QR-UOV.

Password-authenticated key exchange (PAKE) and obfuscated key exchange (OKEX) are widely used protocols, appearing in passport access control, Tor's censorship evasion, and more. As quantum threats grow nearer, there have been an increasing number of proposals for post-quantum PAKE and OKEX. All such protocols are similar in that they build on a KEM, obfuscating public keys and/or ciphertexts sent over the wire, e.g., by adding a random mask or applying an ideal cipher. Many propose instantiation with ML-KEM, a NIST-standardized lattice-based KEM. Unfortunately, ML-KEM is a poor fit for these obfuscating protocols. The algebraic structure of ML-KEM public keys and ciphertexts means that obfuscating these values requires custom procedures for hash-to-vector, matrix expansion, serialization/deserialization, and randomized ciphertext decompression. In order to be broadly useful, these procedures also must be constant-time to prevent side channels and must be standardized to permit interoperability. No such set of procedures exists today. We observe that the barriers to instantiating PAKE and OKEX disappear if some of the KEM's algebraic structure is removed, i.e., if ML-KEM is replaced with a KEM whose public keys and ciphertexts appear to be uniform as bytestrings. In this work, we specify Kopis, a Module Learning-with-Rounding (MLWR) KEM with public keys and ciphertexts that are uniform as bytestrings. Kopis is intended to be a drop-in replacement for ML-KEM, in size, speed, and security. Kopis is nearly identical to Saber, a NIST PQC finalist, and thus inherits its years of cryptanalysis. We demonstrate that Kopis bears the security properties needed for use in various PAKE and OKEX schemes and provide a formally verified Rust implementation complete with portable, AVX2, and NEON backends, and a non-formally-verified C implementation for Cortex-M4. We perform benchmarks and find that Kopis is comparable to and often outperforms the fastest known ML-KEM implementations.

Multi-key fully homomorphic encryption (MKFHE) enables computation over ciphertexts encrypted under keys independently generated by different parties. Recently, Min, Park, and Song (MPS, CRYPTO 2026) constructed the first RLWE-based MKFHE scheme in the plain model, i.e., without trusted or interactive setup. Their construction requires each local compact Gentry-Sahai-Waters (GSW) ciphertext to be extended to a joint-key GSW-like ciphertext before evaluation, incurring $O(dk^2)$ gadget products per input for $k$ parties and gadget length $d$. In this paper, we first construct an extension-free MKFHE scheme (called Levis-fast) in the plain model, eliminating the $O(dk^2)$ gadget products required for joint-key ciphertext extension before homomorphic evaluation. Our core technique is a compatibility technique, termed Cofactor Compatibility, which establishes a common projective decryption relation across ciphertexts encrypted under independently generated local keys, enabling their direct homomorphic evaluation. We further present a compact variant (named as Levis-small) that reduces the communication of each fresh ciphertext from $O(dk^2)$ to $O(d)$ ring elements with only a lightweight lifting operation. A proof-of-concept implementation shows that, compared with MPS, for $k\in\{2,4,8\}$, our construction Levis-fast achieves evaluation speedups of $67.7\times$, $52.8\times$, and $139.4\times$, respectively, while our compact variant Levis-small reduces communication by a factor of $2.5\times$, $8.7\times$ and $14.2\times$, and achieves evaluation speedups of $11.8\times$, $19.7\times$, and $54.4\times$, respectively.

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.

Migrating blockchain systems to Post-Quantum Cryptography (PQC) requires not only replacing classical primitives, but also analysing transformations that change how signatures are represented and verified. We study Falcon-PKR, a public-key-recovery variant of Falcon, motivated by Zcash-like transparent transaction workflows. Falcon-PKR replaces explicit storage of the full Falcon public key with a compact stored digest and reconstructs a candidate public key from the signature during verification. In our construction, this reduces the combined representation size of public key and signature by approximately 15%, but it also introduces a distinct security case in which verification depends on a reconstructed key derived from adversarially supplied signature data. We address this with a machine-checked EasyCrypt formalisation in the Random Oracle Model (ROM). We mechanically verify an EUF-CMA reduction showing that the security of Falcon-PKR is bounded by the security of standard Falcon together with collision resistance of a domain-separated public-key hash. The analysis therefore treats both assumptions explicitly and does not claim a proof of Falcon itself. We also machine-check correctness for honest signing under an abstract Falcon signing interface. We implement Falcon-PKR for Falcon-512 and Falcon-1024 in Python and C, and evaluate runtime and size against ECDSA and selected Post-Quantum (PQ) alternatives, exposing explicit verification and storage trade-offs. As a complementary case study, we implement and analyse an extended SECUER-based Multi-Party Computation (MPC) ceremony architecture. Together, the two case studies address both transaction-signature and ceremony-infrastructure layers of PQ blockchain migration.

Seur\'e and Suvanto (ePrint 2026/1102) recently showed that, for small-characteristic primes $p$, arithmetic over $\mathbb{F}_{p^r}$ can be homomorphically evaluated in CKKS via a technique they call \emph{spectral encoding}. Their construction is, however, restricted to small characteristic: ciphertext multiplication amplifies the error by the operator norm of the multiplied plaintext. Under the spectral encoding, a field element in $\mathbb F_{p^r}$ is encoded to a plaintext with operator norm at most $O(rp)$. The error therefore grows by a factor of $rp$ in the worst case, limiting the supported size of the characteristic prime $p$. In this work, we propose \emph{bi-spectral encoding}, which decomposes the coefficients of the plaintext polynomials used in the spectral encoding of Seur\'e and Suvanto. With a decomposition parameter $d$, a field element in $\mathbb F_{p^r}$ can be encoded to a plaintext with operator norm $O(rd{p^{1/d}})$, for a suitable choice of encoding parameters. We give a comprehensive analysis of error growth and derive a bound on error amplification under multiplication. For fields with a 256-bit prime characteristic (secp256k1) and extension degrees $1$, $2$, and $4$, we provide numerical simulations of error amplification and compute the maximum multiplication counts satisfying the decoding condition under stated error bounds. We further present a bootstrapping procedure that reduces both the size of the plaintext and its noise.

Supersingular abelian surfaces are essential in isogeny-based cryptography. Despite this, we have no efficient algorithm to verify if a given abelian surface is supersingular. In this work, we initiate this research topic by giving an efficient Monte Carlo algorithm to verify if an abelian surface over $\mathbb{F}_p$ is supersingular in $O(\log p)$ with negligible failure probability, and an efficient conclusive algorithm if the order is smooth. We derive this algorithm by a careful analysis on the structure of supersingular Jacobians over $\mathbb{F}_p$. Furthermore, we derive efficient algorithms to verify if an abelian variety of any dimension is minimal or maximal, and to verify if a Jacobian of any dimension is superspecial.

Batch decryption allows an authority to release a short key that enables public decryption of a selected batch of ciphertexts. Motivated by encrypted mempools, we study this capability through two constructions with different authorization semantics and assumptions. First, we provide a simple and compact epochless construction in an RSA group based on Fiat's Batch RSA [CRYPTO'89]. Its batch-decryption hint is just one group element, and its keys and ciphertexts have size independent of the batch size, with no batch bound fixed at setup. We prove adaptive security under the strong RSA assumption in the random-oracle model. The scheme permits repeated releases for overlapping batches, with each release authorizing decryption of the selected ciphertexts. Second, we give an adaptively secure generic construction of identity-based encryption with batch decryption in the epoch-based model, which permits at most one batch-key query for the challenge epoch. The construction combines deferred encryption via garbled circuits, non-inclusion secure registration-based encryption, and weak receiver non-committing IBE. We construct the latter primitive from ordinary IBE and pseudorandom functions, obtaining an instantiation of the epoch-based construction from the computational Diffie--Hellman assumption.

The Chinese NGCC post-quantum competition received a family of lattice KEMs whose decryption failure rates (DFRs) are certified by their designers with models that differ in detail. We recompute the failure probability of the first-round lattice KEMs whose claimed DFR, or a simple recomputation of it, lies near or below the nominal level, and we estimate the offline search for weak ciphertexts under a cap of $2^{64}$ or $2^{80}$ decapsulation queries. Three distinct mechanisms are relevant. (i)~\emph{Correlated decoding blocks.} DTRU decodes 16-coefficient DoubleE$_8$ blocks; in the tricyclotomic ring $\mathbb{Z}_q[x]/(x^n-x^{n/2}+1)$ and the LPPNF ring, the two octets of a block are ring-paired and the repetition code places the same bit on both. Our covariance-aware estimates raise the DFR of six of the seven sets by roughly $50$--$110$ bits. Their estimated uncapped first-failure costs are $2^{85}$--$2^{111}$ decapsulations. Under a fitted ciphertext-tail model, DTRU-648, DTRU-768, and DTRU-Prime fit within $2^{64}$ expected queries after $2^{22}$--$2^{26}$ estimated offline encapsulations. (ii)~\emph{Omitted compression noise.} Cheetah compresses its public key and both ciphertext components. Section~2.2 of the specification omits the public-key term $\langle e_b,r\rangle$, while the $v$-compression error can be treated as a known, ciphertext-dependent shift. Under the coefficient-independence model, exponentially tilted one-dimensional FFTs give DFR estimates of $2^{-79.1}$ and $2^{-51.8}$ for Cheetah128 and Cheetah256, rather than the claimed $2^{-129}$ and $2^{-176}$. Their expected random-query waiting times are below $2^{80}$. We check the noise model at observable rates on a scaled-down instance and against full-size shallow-tail samples. (iii)~\emph{Bounded noise in two-dimensional codes.} Rudraksh2 and Scabbard decode coefficient pairs with B2-Minal codes and already evaluate their joint distribution by two-dimensional FFT. We rederive the two-dimensional atoms and evaluate one-dimensional projections onto failure radii of the real decoder. The resulting projected-tail estimates are $2^{-103.9}$ for Rudraksh2-128-I and $2^{-102.1}$ for Scabbard-128, a few bits below the claimed $2^{-100}$ and $2^{-99}$. Under a $2^{80}$ query cap, the estimated classical totals are $2^{112}$ and $2^{188}$, respectively. No attack described here recovers a key. Under the first-failure DFR metric, several estimated costs lie below their nominal levels; the formal far-tail figures remain subject to the modelling, extrapolation, and geometric limitations stated in the paper.

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

POKÉ, introduced by Basso and Maino, is one of the most efficient isogeny-based public-key encryption schemes. The generic parallel-encryption approach yields a $(t,n)$-threshold variant by running $n$ independent POKÉ instances and secret-sharing the message, but this multiplies the public-key and ciphertext sizes by roughly $n$. We present S-TPOKÉ, a POKÉ-based $(t,n)$-threshold construction for every $1\le t\le n$, and Ch-TPOKÉ, an $(n,n)$ variant that arranges the parties' secret isogenies differently. Both schemes avoid repeating part of the isogeny computation that appears in every independent POKÉ instance. Compared with the trivial construction, they reduce the number of degree-$3^{b}$ isogenies computed during encryption from $2n$ to $n+1$ and reduce the ciphertext size by about a factor of two when $n$ is large. The two schemes differ in how the parties' secret isogenies are arranged. S-TPOKÉ is our main construction: the dealer samples $n$ independent secret isogenies, while encryption samples one sender-side secret isogeny and shares it across the parties. Ch-TPOKÉ instead arranges the parties' secret isogenies into a chain. For S-TPOKÉ, we prove SIM-CPA security under static corruption in the random oracle model from the $(k,n)$-S-C-POKE assumptions for all $1\le k\le t$, which extend C-POKE to the threshold setting. For Ch-TPOKÉ, we prove only SIM-CPA security under static maximal corruption from the $(j,n)$-Ch-D-POKE assumptions for all $j\in\{1,\ldots,n\}$, which extend D-POKE to a chain-based threshold setting. This guarantee is strictly weaker than SIM-CPA security under static corruption. We also give asymptotic parameter choices targeting $\lambda$-bit security and derive closed-form expressions for the public-key, ciphertext, and partial-decryption sizes in terms of $\lambda$ and $n$.

Threshold signatures for distributed systems require compact public keys and signatures to reduce communication overhead by avoiding packet fragmentation. However, with existing post-quantum threshold signatures, either the public key or the signature does not fit within a single unfragmented network packet. In this work, we present SPRITZ, an isogeny-based post-quantum threshold signature scheme whose public keys and signatures both fit within a single unfragmented network packet at every NIST security level. To the best of our knowledge, SPRITZ is the first post-quantum threshold signature scheme to do so with an arbitrary number of parties. While isogeny-based signatures such as SQIsign and PRISM are known for exceptionally compact public keys and signatures, their algebraic structure makes thresholdization for an arbitrary number of parties highly nontrivial. We address this challenge by introducing a novel graph-based threshold access structure tailored to the isogeny setting. For security against known attacks, we employ a non-interactive zero-knowledge (NIZK) protocol for the verification of isogeny push-forward procedures. At NIST security levels I/III/V, SPRITZ achieves public keys of 129/193/257 bytes and signatures of 223/335/447 bytes, respectively. Among the schemes submitted to the NIST MPTC (Multi-Party Threshold Cryptography) previews phase 2 whose public keys fit within a single unfragmented network packet, SPRITZ achieves the smallest signature size. We also provide a proof-of-concept implementation of SPRITZ.

\Falcon{} is a digital signature scheme based on NTRU lattices, known for its compact signatures. Its weak-smoothness variant, \FalconWS{} (ASIACRYPT 2025), reduces signature sizes by allowing narrower Gaussian sampling distributions. Further reductions require efficient sampling at narrower widths and a security analysis that accounts for the resulting distributions. We analyze the distribution of accepted preimages directly, without estimating the smoothing parameter of the NTRU lattice. We also modify the rejection-corrected Klein--GPV sampler to reduce sampling cost while controlling the resulting distributional error. We combine these results to construct \FalconPP{}, a variant of \Falcon{}, and give UF-CMA and SUF-CMA bounds in the classical random-oracle model. For ring degrees $512$ and $1024$, our estimates give signature sizes of $419$ and $921$ bytes, respectively. These are $37.09\%$ and $28.05\%$ smaller than \Falcon{} signatures, and $11.60\%$ and $5.92\%$ smaller than the estimates for \FalconWS{} at their respective parameter sets.

Recent CKKS-based constructions support homomorphic arithmetic modulo powers of two and more general moduli. We explore a complementary tradeoff: using polynomial rings native to CKKS simplifies arithmetic and refreshing but restricts the message spaces. Building on Kim's interpretation of GBFV ciphertexts as CKKS ciphertexts, we use the decomposition $\mathbb{R}[X]/\langle X^N+1\rangle \cong(\mathbb{R}[X]/\langle X^n+1\rangle)^{N/n}$ into $N/n$ polynomial lanes, where $2\leq n\leq N$ is a power of two dividing the RLWE dimension $N$. Following GBFV, each lane represents a message in $\mathbb{Z}[X]/\langle X^n+1,t\rangle$, where $t$ is coprime to $X^n+1$ over $\mathbb{Q}$. These message spaces include $\mathbb{Z}_{\beta^n+1}$ for $t=X-\beta$, products of modular integer rings, specific 128-, 256-, 512-, and 1024-bit prime fields, and extension fields such as $\mathbb{F}_{5^{16}}$, $\mathbb{F}_{17^4}$, and $\mathbb{F}_{37^{32}}$. Unlike the triangle encoding of Gao and Zheng's construction (GZ), our lanes occur at intermediate stages of conventional CoeffToSlot and SlotToCoeff transformations, avoiding additional encoding-specific linear maps. We thus "stay in our lane" by performing arithmetic and refreshing within CKKS-native polynomial rings. Our arithmetic bootstrapping restores ciphertext levels, bounds polynomial representatives, and reduces approximation error. At $N=2^{16}$, it takes less than 4.5 seconds in every tested configuration, with little variation across $t$ and $n$. Comparing our arithmetic modulo $2^n+1$ with GZ's arithmetic modulo $2^n$, same-machine, same-library experiments show a $2.2\times$–$3.8\times$ speedup for $2^3\leq n\leq 2^6$. Our bootstrapping time remains nearly constant as $n$ grows, whereas GZ's dense encoding-specific transformations increase its cost and, at larger $n$, exceed available memory, preventing direct comparisons. At $n=2^{14}$, extrapolating GZ's published timings suggests a $26\times$ speedup.

The BAG-Loong reference implementation samples its secret matrices X and Y from fixed, publicly known subspaces, although the specification calls for secret random supports. This makes the public-key relation S = HX + Y , with public H, amenable to Gaussian elimination. Expanding the relation over F2 and projecting away the support of Y leaves a linear system for X. We prove an exact recovery criterion based on its column rank. All 40 supplied known-answer-test records, covering four parameter sets, satisfy this criterion: two independent solvers recover each X exactly, and the unmodified decapsulation code reproduces the corresponding session keys. For the largest parameter set, the reduced system has 9360 equations in 728 unknowns per column; one elimination solves all 15 columns.

The security of isogeny-based signatures is almost exclusively studied in the single-user setting, leaving a gap for realistic multi-user deployments. This gap is especially crucial for CSI-FiSh, where the small challenge space and parameter sensitivity directly impacts security estimates. We address the multi-user security of CSI-FiSh and obtain tight concrete classical multi-user bounds in the random-oracle model (ROM) plus generic group-action model (GGAM). Crucially, our analysis only incurs an additive degradation in the number of users rather than a multiplicative one. As a byproduct, we show that CSI-FiSh attains $125$ bits of provable classical security even with $2^{46}$ users. We extend this analysis to preprocessing attacks, where an adversary with nation-state resources can perform offline precomputations. We capture this by extending the preprocessing security framework of Coretti et al. to ROM+GGAM and obtain concrete multi-user bounds for CSI-FiSh with preprocessing. Finally, we address the multi-user security of CSI-FiSh in the quantum random-oracle model and obtain results in the algebraic group action model which also avoids this multiplicative loss. This gives a unified concrete security treatment of plain CSI-FiSh in the deployment regimes where multi-user and preprocessing effects are unavoidable.

Polar-KEM is a lattice-based key encapsulation mechanism submitted to the Next-generation Commercial Cryptographic Algorithms Program. Its security is claimed to rely on a lattice isomorphism problem over polar-code-defined Construction-D lattices. In its core key-generation algorithm, a polar lattice basis is constructed from a polar-code chain, reduced using LLL, and left-multiplied by a secret orthogonal matrix. The resulting matrix is published as the public key. We show that the key-generation procedure does not instantiate a general lattice isomorphism problem. The reduced reference basis is generated through a public chain of computations: public parameters determine frozen sets, the frozen sets determine a polar-code chain, the code chain determines a Construction-D basis, and the basis is then reduced by the public LLL procedure. Under the natural executable interpretation of the specification, an adversary can reproduce the same reduced basis. If the public key is \ensuremath{B_{\mathsf{pk}}=O B_{\mathsf{red}}}, the secret orthogonal matrix is recovered by the single linear-algebra operation $$ O=B_{\mathsf{pk}}B_{\mathsf{red}}^{-1}. $$ The attack is polynomial time and recovers the exact secret isometry, or its numerical representation, without solving a shortest-vector problem or a general lattice isomorphism problem. We also examine the erasure parameter used by the frozen-set selection algorithm. The specification neither assigns it a concrete value nor defines it as a sampled secret with a distribution, encoding, entropy requirement, or storage mechanism. Treating this unspecified value or unspecified LLL tie-breaking as secret entropy would define a different scheme and would not repair the published construction. The present paper focuses on this direct basis-alignment weakness. Additional structural and correctness analyses are left to an extended version.

We solve the long-standing open question of designing a "truly" linearly homomorphic scheme -- meaning it supports homomorphic additions on arbitrary plaintexts, with no restriction, in contrast to "somewhat" ones -- that achieves CCA1 security under a standard assumption. We do so by introducing a new variant of Paillier-ElGamal, which we call Damgard-Paillier-ElGamal (DPEG) as its design follows a Knowledge-of-Exponent pattern. On top of being linearly homomorphic without any restriction, our scheme enjoys the following properties: - It achieves CCA1 security solely under the DCR assumption. To the best of our knowledge, it is the first "truly" linearly homomorphic proven CCA1 secure solely under this assumption (or any other standard one). - It can be extended to support one level of multiplication while still preserving its CCA1 security under the same assumption. This extension is then the first concrete scheme supporting both homomorphic additions and multiplications (even limited to one-level) that is proven CCA1 secure under DCR. - It also achieves Manulis&Nguyen's stronger notion of vCCA security under an additional non-falsifiable linear-only homomorphism assumption that is commonly used in proof-of-knowledge constructs. DPEG is then the first scheme that is proven vCCA secure while being CCA1 secure under a standard assumption. This also carries over to the multiplicative extension. Interestingly, DPEG achieves the above at only 1.5 times the cost of the baseline CPA-secure Paillier-ElGamal scheme. To establish the CCA1 security of DPEG, we introduce a new abstract framework that allows to prove CCA1 security of a large class of of group-based PKE that also covers other somewhat linearly homomorphic schemes previously known to achieve CCA1 security under falsifiable assumptions such as Damgard-ElGamal, Cramer-Shoup-Lite and the recent variant of Paillier-ElGamal with plaintext zero padding of Libert. This framework may be of independent interest to more easily prove the CCA1 security of other schemes. Lastly, on the negative side, we take a first step in connecting vCCA security to an impossibility result of Gentry&Wichs and show that, under mild assumptions, the vCCA security of DPEG cannot be established from any falsifiable assumption by means of a black-box reduction.

Constructing attribute based encryption (ABE) for unbounded circuits, namely circuits with both depth and width being unbounded, and for Turing machines are perhaps the most important open questions in ABE research. Recent years saw some much-awaited progress on these long-standing problems -- (i) the work of Hsieh, Lin and Luo [HLL23] (HLL23) provided the first construction of ABE for unbounded circuits from a new circular evasive LWE assumption, (ii) the follow-up work of Agrawal, Kumari and Yamada [AKY24b] and Cini and Wee [CW25] gave the first constructions of ABE for Turing machines. Unfortunately, all these works relied on different versions of the ``private-coin'' Evasive Learning With Errors assumption which was invalidated in a sequence of attacks [BUW25, BDJ+25, DJM+25, AMYY25, HJL25, HHY26]. Finding new constructions from better-understood assumptions (without relying on compact functional encryption or obfuscation) is therefore an important open problem. In this work, we make progress towards this goal. Our contributions are: 1. *KP-ABE for Unbounded Circuits from Circular Small-Secret LWE and Bilinear GGM.* We provide a new candidate for key-policy ABE for unbounded circuits from circular small-secret Learning With Errors (csLWE) and the Bilinear Generic Group Model (BGGM). Since the BGGM has a long history of study, we believe that this provides strong evidence for the security of our scheme. In the standard model, we argue security from a novel, falsifiable ``doubly circular'' assumption which combines csLWE with key dependent message security of a variant of ElGamal encryption in an inseparable manner. We show that in a restricted setting, it is implied by the standard SXDH assumption and csLWE. 2. *SK CP-ABE for Unbounded Circuits from Circular Small-Secret LWE. * In the symmetric key setting, we provide a new candidate for ciphertext-policy ABE for unbounded circuits from only the csLWE assumption. 3. *SK KP-ABE for Turing Machines from Circular Small-Secret LWE.* In the symmetric key setting, we provide the first key-policy ABE for Turing machines from the csLWE assumption. Curiously, each of our constructions is intrinsically key-policy or ciphertext-policy and stubbornly resists adaptation to its dual variant. Thus, our work exhibits a surprising (to us) dichotomy between the key and ciphertext policy versions of ABE for unbounded circuits. Finding dual versions of the above constructions, removing pairings altogether or dispensing with the symmetric key setting are fascinating open problems.

Multi-key fully homomorphic encryption (MKFHE) supports homomorphic computation over ciphertexts encrypted under independently generated keys. Known constructions accommodate independent keys by expanding every ciphertext under the concatenation of the participating secret keys, and then evaluating the circuit in that expanded dimension. A concatenated key is $N$ times longer than an individual key, so the ciphertext on each wire and the running time of each gate grow with $N$, the number of users. L\'opez-Alt, Tromer, and Vaikuntanathan, who introduced MKFHE, asked for a scheme in which all algorithms are independent of $N$. More than a decade later, no MKFHE scheme has a homomorphic evaluation whose cost is even sublinear in $N$. We construct the first MKFHE whose homomorphic evaluation asymptotically matches that of single-key FHE, while users still generate their keys and encrypt independently and the participating set is chosen only after encryption. We insert a public, deterministic, and non-interactive preprocessing phase between encryption and evaluation: key aggregation combines the selected public keys, and ciphertext preparation converts each independently encrypted input into a short single-key ciphertext under a \emph{virtual key}, namely the sum of the participating secret keys. Evaluation then runs on ordinary single-key ciphertexts, so every wire ciphertext, every gate, and the decryptable output are independent of $N$. We give two instantiations, a leveled GSW-based scheme over $\mathbb{Z}_q$ from standard LWE and a leveled BFV-based scheme over cyclotomic rings from circular Ring-LWE. Both retain single-round distributed decryption with statistically simulatable partial decryptions, where the published key material grows with $N$. As a proof of concept, we implement our ring-based construction in Go. For 32 users, its multiplication is $275.13\times$ and $45.50\times$ faster than CDKS and KKLSS, and its ciphertexts are $16.5\times$ smaller than both.

Aardal et al. (CRYPTO 2025) provided the first complete security proof of SQIsign; however, their reduction incurs a square-root loss in the prime characteristic due to the application of a loose bound on the min-entropy. For instance, at NIST security level I, an adversary making $2^{64}$ signing queries renders the security proof vacuous. In this note, we show that the min-entropy of SQIsign is optimal, namely $\mathcal{O}(1/p)$. Although this improvement does not yield full $\lambda$-bit security, we show that it preserves two-thirds of the expected bit-security. We show that this artifact comes from an information-theoretic loss in the zero-knowledge simulation of SQIsign, suggesting a new proof technique is needed to achieve full $\lambda$-bit security at the current parameters.

Consider a cryptocurrency exchange that secures the bulk of its reserves under a small set of keys, each of which is only used to transfer cryptocurrency once a year; or the backup codes for an account login or a password manager, which are again rarely used but provide access to crucial systems or information. Securing such infrequently-used high-value secrets is crucial, but existing solutions, such as threshold wallets and 'cold' (offline) wallets, are unsatisfactory. In this work, we envision a system that allows users to conveniently back up their rarely-used, high-value keys. This new setting necessitates a novel set of design requirements. Specifically: - We allow user keys to be threshold secret-shared among a large number of custodians where each custodian wallet comprises of a hot (i.e., online) and a cold (i.e., offline) portion. The cold part of the wallet is not touched during the backup process (thus, it is independent of the number of system users) but must be accessed for recovery. - We provide a mechanism to continually assure users that their keys are safely stored. This feature is critical because our system is not designed for frequent key use. We also enable proactive key refresh. - Finally, in our approach, restoring a backed-up key is equivalent to generating a signature. Thus, signatures made by users of this system should look the same as "normal" signatures to avoid exposing holders of high-value keys to targeted attacks. Based on these requirements, we develop new security definitions and a UC-secure protocol that implements threshold BLS signatures in our new model. Our protocol is practically efficient for the envisioned large numbers of custodians: for a 67-out-of-100 threshold configuration, creating a new backup takes 10s, while recovery takes less than 2ms.

Arithmetic logic units (ALU) combine word-level arithmetic with bitwise operations over encrypted data. The state-of-the-art scheme, GZ26 (CRYPTO'26), constructs an ALU in CKKS via triangle encoding, but has two limitations: the radix-$2$ design restricts packing capacity, while the arithmetic-to-Boolean (A2B) conversion requires $O(\ell)$ functional bootstrappings for $\ell$-bit message without batching independent ciphertexts. In this paper, we first generalize triangle encoding to arbitrary integer bases while preserving leveled modular arithmetic in CKKS. Larger bases reduce the number of slots required per message, allowing more messages to be packed into each ciphertext. %To ensure correct decoding despite rounding during CKKS plaintext encoding, we derive sufficient conditions relating the digit base to the encoding scale. For power-of-two digit bases, we introduce an A2B conversion using two functional bootstrapping after overflow refreshing, without batching independent ciphertexts. Our key insight is to transform triangle encoding into radix representation with unknown carries, from which candidate bits can be extracted using a single multi-value functional bootstrapping. Specifically, we first cancel the overflow shared by neighboring windows using one functional bootstrapping followed by linear operations, leaving expressions involving only radix digits and adjacent binary carries. Then we use a multi-value functional bootstrapping to jointly extract candidate bits and evaluate the local carry state, which determines how carries propagate between windows. Finally, we recover the canonical bits through parallel carry propagation and bit correction, using only leveled homomorphic operations. We implement our scheme in OpenFHE and evaluate it for 64-bit, 128-bit, and 256-bit message. The experimental results show that using \(d=2\) achieves the lowest latency for A2B conversion, yielding \(3.49\times\)--\(9.71\times\) speedups over GZ26 at the same packing capacity. In addition, using \(d=32\) increases the packing capacity and achieves the best amortized performance, yielding \(8.15\times\)--\(28.47\times\) speedups.

We present new constructions of the following primitives featuring succinct communication: - Batch threshold encryption: Assuming RSA and DCR, we construct a threshold encryption scheme in which a batch of ciphertexts can be decrypted via short hints from a quorum of decryptors. Previously, this was known only from bilinear maps. - Aggregate signatures: Assuming RSA, we construct a signature scheme where signatures on different messages from an arbitrary number of signers can be aggregated into one signature. Our construction achieves bounded-query security. In contrast to prior (fully secure) schemes in the standard model, ours makes black-box use of cryptography. - Broadcast encryption: Assuming RSA, we construct a secret-key encryption scheme where a sender can encrypt a message to multiple recipients via a short ciphertext. Our construction achieves bounded-query security. Previously, (fully secure) broadcast encryption was known from bilinear maps or obfustopia or nonstandard lattice assumptions. Our constructions are simple and achieve optimal succinctness in the key parameter (decryption batch size or number of signers or recipient set size). In this metric, they outperform or match known constructions. Our results are obtained by applying the lens of projective pseudorandom generators (PPRGs) to these problems. Towards this, we identify new enhanced properties for PPRGs and instantiate them from the RSA assumption.

Updatable Public-Key Encryption (UPKE) enables forward secrecy in asynchronous settings like secure group messaging. At EC'25, Albrecht, Benčina and Lai proposed the first plausibly post-quantum UPKE scheme supporting unlimited updates, based on permutation code equivalence (PCE) over finite fields and hollow lattice problems. However, it has impractically large public keys (4.8MiB) and ciphertexts (1.5MiB). In this work, we first replace the information-theoretic Hollow LHL with a computational assumption secure under binary-secret binary-error LWE, reducing key sizes by an order of magnitude. Second, we show that generalising to Module-LWE is not beneficial: PCE instances over $\mathbb{F}_{q^d}$ admit a linearisation attack via the $q$-Frobenius structure, enabling recovery of secret isometries unless code rates are inflated by $d$, negating any size benefit from module lattices. Third, we establish IND-CCA security in the model of Alwen, Fuchsbauer and Mularczyk (EC'24), but do not achieve `joiner security' like other post-quantum candidates. Finally, we introduce a heuristic multi-key variant using matrix-valued secret keys, enabling efficient encryption of $\ell$ bits per ciphertext. We define the Hinted SPCE assumption to capture the main cryptanalytic challenge and show that the performance gain is likely too small to justify adoption, unless the new assumption can be avoided. Overall, our `unlimited' scheme has update sizes 3.5 to 10 times larger than lattice-based schemes limited to $2^{20}$ updates, depending on the aggressiveness of parameter choices.

In this work, we propose novel security notions for encryption schemes that simulate an adversary in the black-box model equipped with additional side-channel power. More concretely, the adversary is allowed to probe values of the secret-key sensitive algorithms, i.e. key generation and decryption. We then prove a generalization of the well-known Naor-Yung (NY) transform, generically lifting IND-CPA secure encryption schemes to IND-CCA ones in this new probing context. Moreover, we instantiate the resulting framework from lattices, constructing Rutile, a masking-friendly IND-CPA encryption scheme inspired by Kyber, and then Topaz its IND-CCA secure extension. In our proposal, the masking-unfriendly parts of Kyber, namely the central binomial distributions and the FO-transform, are replaced by masking-friendly counterparts (sum of uniforms and the aforementioned NY-transform).

In this paper, we study multi-party non-interactive key exchange (NIKE) in the fine-grained setting. More precisely, we propose three multi-party NIKE schemes in three computation models, namely, the bounded parallel-time, bounded time, and bounded storage models. Their security is based on a very mild assumption (e.g., NC1 ⊊ ⊕L/poly) or even without any complexity assumption. This improves the recent work of Afshar, Couteau, Mahmoody, and Sadeghi (EUROCRYPT 2023) that requires idealized assumptions, such as random oracles or generic groups. Additionally, we show that all our constructions satisfy a natural desirable property that we refer to as extendability, and we give generic transformations from extendable multi-party NIKE to multi-party identity-based NIKEs in the fine-grained settings. Furthermore, we generalize the lower bound on users’ storage consumption in the bounded storage model by Dziembowski and Maurer (Eurocrypt 2004) to encompass any multi-party NIKE with extendability. This new lower bound suggests that the users’ storage consumption of our multi-party NIKE in the bounded storage model is optimal.

At Asiacrypt'25, Lapiha and Prest proposed a lattice-based IND-CCA threshold key-encapsulation mechanism (TKEM) obtained from a threshold identity-based encryption (TIBE) and a signature scheme. Their construction relies on a variant of the Boneh-Canetti-Halevi-Katz (BCHK) transform, instantiated with a lattice-based TIBE. However it suffers from large ciphertexts at 540 KiB for $\kappa = 128$ bits of security. We present substantial improvements to their TIBE, resulting in the first concretely efficient lattice-based IND-CCA TKEM, with ciphertexts just under 30 KiB for a threshold $T = 32$, $Q = 2^{45}$ queries, and the same $\kappa$. Our design simplifies the original framework by leveraging the power of random oracles already present in their construction. We further enhance efficiency by adopting approximate computations where appropriate and by replacing module-NTRU trapdoors with NTRU trapdoors, achieving a remarkable eighteenfold reduction in ciphertext size. Finally, leveraging recent developments in secret sharing, we ensure the verifiability of key-extraction shares even in the presence of malicious parties.

We explore the use of level structures to generalize the SQIsign signature scheme. We give a general framework where, given the public key and the commitment, the challenge is to exhibit an isogeny between them with an additional requirement, namely to map a chosen level structure to nother. We then instantiate the framework using 1-dimensional and 2-dimensional isogenies. In doing that we provide a new explicit Deuring correspondence for supersingular elliptic curves with level structures and solve new constrained norm equations.

The Round-3 SNOVA signer samples vinegar variables, which are elements of $\mathbb{F}_q$, by reducing uniform byte strings modulo a power of $q$. We show that the resulting bias leaks secret-key information for the six odd-characteristic alternative parameter sets. Even though the leakage is small (the most leaky variables leak at most $0.086$ bits of information), this still leads to efficient key-recovery attacks which we demonstrate in practice. Key recovery becomes a $q$-ary LPN problem of dimension $o\ell$ with a known, full-support error distribution. A naive algorithm needs some ten thousand signatures and $2^{90}$ to $2^{130}$ operations, which is already far below the $170$ to $331$ bits claimed for the six affected sets. Using more signatures makes the attack practical: using standard LPN machinery - BKW reduction with Fourier hypothesis testing - we recover the secret key for four parameter sets in practice using between $9$ and $180$ million signatures, and at most 16 minutes of wall clock time. Fixing SNOVA to sample the vinegar variables uniformly would prevent the attack completely.

Updatable Encryption (UE) allows ciphertexts to be updated under new keys without decryption, enabling efficient key rotation. Constructing post-quantum UE with strong security guarantees is challenging: the only known CCA-secure scheme, COM-UE, uses bitwise encryption, resulting in large ciphertexts and high computational costs. We introduce $\mathsf{DINE}_\ell$, a family of compact and efficient CCA-secure isogeny-based post-quantum UE schemes parametrized by an integer $\ell$, achieving increasing security levels for $\ell = 3,4,8$. Each encryption, decryption, or update requires only a few power-of-2 isogeny computations in dimension 2. At NIST security level 1, $\mathsf{DINE}_\ell$ supports 28B messages, 480B ciphertexts, and $\ell\times336$B update tokens, significantly smaller than prior constructions. Our C implementation demonstrates practical performance, with updates in $\ell \times 15$ms, encryptions in 65ms, and decryptions in 155ms. Our design combines high-dimensional isogeny representations with the Deuring correspondence. We also introduce new algorithms for the Deuring correspondence which may be of independent interest. Moreover, the security of our scheme relies on new problems that might open interesting perspectives in isogeny-based cryptography.

We formalize and construct $sparse$ arguments of knowledge, where given a length $N$ witness that contains $n$ non-zero values the prover time is $O(n) \circ o(N)$. In particular, we achieve a sparse argument of knowledge for the customizable constraint system relation, which generalizes circuit-satisfiability. We achieve this by first utilizing $sublinear$ lookup arguments to provably select only the subset of the constraint system that touches the non-zero entries of the variable assignment, and then running a standard argument of knowledge with mild qualifications. Our resulting sparse argument of knowledge is publicly verifiable and supports a universal and updatable setup. It features an $O(N \log N)$ preprocessing phase, an $O(n \log n)$ prover time, and an $O(1)$ verifier time, improving on the prior $O(n \log^2 n)$ and $O(n \log N)$ prover time.

Constructing a post-quantum signature scheme that is simultaneously compact and efficient remains a central challenge in code based cryptography. Existing schemes based on turning a zero-knowledge identification scheme into a signature exhibit either large signatures or slow verification procedures, while the design of hash-and-sign schemes has led to constructions such as Wave and MIRANDA, having small signatures at the cost of massive public key sizes and time-consuming signature algorithms. In this work, we present ASTRA-Sign: a quASi cyclic code-based full-distance decoding TRApdoor Signature Scheme, combining the hash-and-sign paradigm with quasi-cyclic moderate density generator matrix codes to obtain small signatures and small public keys. The security of our scheme is based on the hardness of finding low weight codewords in quasi-cyclic codes, and on the hardness of finding a codeword that has full Hamming distance from a given random vector. We analyse key recovery and signature forgery attacks against ASTRA, and we propose several parameter sets achieving 128-, 192- and 256-bit security. Our scheme exhibits public keys and signatures below 1 kiB for 128 bits of security, with 40 µs verification times.

We present a simple leveled fully homomorphic encryption (FHE) scheme that achieves IND-CCA1 security in the standard model without relying on SNARKs. Our construction combines the gadget trapdoors introduced by Micciancio and Peikert [Eurocrypt 2012] with the GSW leveled FHE scheme [Gentry, Sahai, Waters, Crypto 2013]. We make only minimal changes to GSW to obtain security: ciphertext size remains similar and the homomorphic operations are unchanged. We prove IND-CCA1 security under a new delayed-target LWE assumption. We provide evidence for its hardness in two ways: under a lattice knowledge assumption, we give a reduction from standard LWE; for a restricted parameter regime, we give a quantum reduction from the one-more inhomogeneous short integer solution assumption. Finally, using the randomized evaluation technique from Bourse et al. [Crypto 2016], we obtain IND-CPA-D security for branching programs using only polynomial noise flooding and without requiring statistical correctness.

The Learning With Errors (LWE) problem provides a conservative and well-established security foundation for lattice-based cryptography, while Learning With Rounding (LWR) improves bandwidth efficiency through deterministic rounding. However, the rounding noise in LWR is inherently correlated with the hidden linear term, preventing tight and sample-preserving reductions to standard LWE for polynomial moduli. Prior work on the Learning With Quantization (LWQ) problem established a tight security reduction from LWE, where standard additive noise is intrinsically replaced by quantization error. We specialize this framework by explicitly instantiating the quantization lattice as a scaled integer lattice. Under this geometric choice, specifically utilizing aligned power-of-two moduli, we derive the exact finite-support error distribution and construct an explicit bijection between transmitted split samples and normal-form LWE samples. These ingredients yield \(\mathsf{MAMBA\text{-}Frost}\), a plain LWQ-based key encapsulation mechanism that seamlessly pairs unstructured LWE security with quantization-based compression. Because its effective error stems entirely from public dithered quantization, \(\mathsf{MAMBA\text{-}Frost}\) operates strictly with hardware-friendly power-of-two arithmetic. Furthermore, the construction employs an \(E_8\)-coded message embedding to optimize the correctness margin without altering the underlying LWQ hardness argument. We instantiate \(\mathsf{Frost}\) at NIST security levels 1, 3, and 5 and provide a complete software implementation. Its power-of-two design realizes the core arithmetic with shifts and masks, keeping the implementation simple and amenable to constant-time engineering. At level 1, \(\mathsf{Frost\text{-}128}\) reduces the combined public-key and ciphertext size by about \(40\%\) compared with \(\mathsf{FrodoKEM\text{-}640}\) and by about \(8\%\) compared with \(\mathsf{SCloud}^{+}\text{-}128\). On an AVX2 platform, \(\mathsf{Frost\text{-}128}\) achieves speedups of \(2.3\times\), \(1.8\times\), and \(1.5\times\) for key generation, encapsulation, and decapsulation over \(\mathsf{FrodoKEM\text{-}640}\), and \(2.1\times\), \(1.5\times\), and \(1.3\times\) over \(\mathsf{SCloud}^{+}\text{-}128\).

Modern cryptocurrency wallets use Schnorr signatures together with public, deterministic key derivation: by repeatedly rerandomizing a single master public key, an unlimited number of public keys for incoming payments can be derived without access to secret data. Moreover, some wallets support multi-signature schemes such as MuSig2 for optionally aggregating derived public keys from $n$ distinct parties into "$n$-of-$n$" public keys, so that funds received on such aggregated keys can be spent only when authorized by all $n$ parties. However, these advanced key-management techniques stretch the underlying cryptographic schemes beyond the guarantees provided by existing security proofs. Although deterministic Schnorr wallets and MuSig2 have each been proven secure in isolation, the provable security of their composition---despite its deployment in wallets---has not been established thus far. The goal of this work is to narrow this gap between theory and practice. We provide the first formal security analysis of the joint use of single-signer Schnorr signatures and MuSig2, both under rerandomization and in deterministic wallets. First, we introduce the notion of a (rerandomizable) joint-signature scheme, in which an honest signer uses the same secret key for single-signer signatures and multi-signatures. Within this model, we prove tight security of Schnorr signatures plus MuSig2 under the algebraic one-more discrete logarithm (AOMDL) assumption in the combination of the algebraic group model (AGM) and the random oracle model (ROM). Finally, we provide a formal model of deterministic wallets with joint-signature schemes and show that Schnorr plus MuSig2 remains secure under public, deterministic key derivation.

Bootstrapping is the bottleneck of BGV/BFV homomorphic encryption, and for large plaintext primes $p$ its cost is dominated by digit extraction. Recently, this stage has been accelerated along two separate routes. The first lowers the degree of the digit-extraction polynomial: the bounded-support construction of Ma et al. (Eurocrypt'24) confines its support, and the order-four filter of Xiong et al. (to appear in Asiacrypt'26) removes three quarters of its monomials. The second lowers the depth of its evaluation: the Galois norm map of Okada et al. (Asiacrypt'23) and Zhao et al. (Crypto'26) evaluates a degree-$d$ factor in logarithmic depth. However, how the two routes relate and whether they compose has remained open. We propose a symmetry-graded framework that views the two evaluation routes as commuting group actions on the digit-extraction polynomial. Under this unified perspective, the existing evaluators correspond to different specializations of $\mathrm{cost}(D;r,d)$. For lower degree, we identify a novel rank-two lattice structure underlying digit extraction. The crystallographic restriction limits the filter order to $r\in\{1,2,3,4,6\}$. In particular, the methods of Ma et al. and Xiong et al. correspond to $r=2$ and $r=4$, respectively. Moreover, our framework derives a sparser order-six digit-extraction polynomial, enabling order-six symmetry for Mersenne primes. For lower evaluation cost, we construct a composed evaluator that first folds $P_A$ using the scalar filter and then evaluates the folded polynomial via the slot ring's Galois norm map. Since the rotation and Frobenius actions commute, the two optimizations can be combined within the same framework. Consequently, for any $(p,m)$ we select the optimal $(r,d)$ and evaluate digit extraction in $2\sqrt{D/(rd)}+O(\log D)$ non-scalar multiplications. On 13 general cyclotomic rings at $\geq 80$-bit verified security, our single-threaded HElib implementation improves upon the state-of-the-art evaluator of Ma et al., accelerating digit extraction by $2.4$–$4.9\times$ and thin bootstrapping by $1.3$–$2.8\times$, while modifying only the digit-extraction stage. In particular, on Ma et al.'s set IV with the Mersenne prime $p=8191$ and set V with $p=65537$, digit extraction is accelerated by $3.6\times$ and $3.8\times$, respectively, reducing the total bootstrapping time from 180.4 s to 85.5 s and from 217.6 s to 103.1 s. The implementation is publicly available, and the core analysis is machine-checked in Lean 4.

We present the first lattice-based, partially non-interactive threshold signature scheme that tolerates the adaptive corruption of up to T −1 signers, where T is the signing threshold. Our construction relies on the MSIS and MLWE assumptions, and has two rounds, of which only the second is message-dependent. We substantially improve upon prior adaptively secure lattice-based schemes (CRYPTO ’24 and EUROCRYPT ’26), which require at least two message-dependent rounds. In addition, compared to prior lattice-based partially non-interactive schemes (CRYPTO ’24, S&P ’25, CRYPTO ’25), we achieve better communication complexity.

We study the existence of bounded-degree supersingular isogenies under prescribed degree filters and exact torsion constraints. In characteristic $p$, a second-moment argument using the Brandt trace formula gives asymptotically positive coverage of independent uniform endpoints at $D=\lfloor c\sqrt{p}\rfloor$, for every fixed $c>0$ and every endpoint-independent binary filter retaining $\Omega(D^2)$ cyclic kernels. This avoids the logarithmic loss of a maximum-Petersson-norm estimate, but does not imply coverage tending to one. For curves equipped with a line in their $q$-torsion, where $q\neq p$ is prime, a cumulative Hecke estimate gives nonexistence $O\!\left(pq\ln^3(2pq)/D^2\right)$. Combined with a first-moment incidence bound, this separates two scalar-containing subgroups with the same upper-triangular span and additive Hom index $q$:their response-existence probabilities tend to one and zero when $q=p^{\beta+o(1)}$, $D=p^{1/2+\gamma+o(1)}$, and $0<\gamma<\beta<2\gamma<1$. The positive statement averages over a uniform source line and also yields an existential fixed-frame result; the exact challenge cardinalities differ. Determinant filters and finite odd-degree bounds at the SQIsign v3.0 parameters illustrate the results. All probabilities concern the stated arithmetic experiments, not the failure probability or security of a concrete signer.

Aggregate signatures play an important role in proof-of-stake systems, where many validators sign a block. There is a strong desire to aggregate all these signatures into one short signature that is fast to verify. Since all validators know the block number they are signing, this setting is well suited for synchronous (a.k.a stateful) signatures. Boneh and Kim (2019) showed that lattice-based one-time signatures (OTS) can be aggregated very efficiently. The Chipmunk and Lemur signature schemes extend this to an $\ell$-time synchronous scheme using a (homomorphic) Merkle tree of $\ell$ one-time public keys. Each leaf of the tree is used to sign one message, and these one-time signatures can be aggregated across many signers. Due to the Merkle tree, every aggregate signature includes a Merkle authentication path of length $O_\lambda(\log \ell)$. We present a different lattice-based approach to constructing a synchronous aggregate signature scheme. The length of an aggregate signature in our scheme is independent of $\ell$. The resulting signatures are asymptotically shorter than existing schemes, and concretely shorter for some parameter choices. The resulting signature verification algorithm is algebraic, which makes it amendable to efficient threshold signing. Moreover, we are able to prove security in an adaptive corruption model. We thus obtain an efficient lattice-based synchronous threshold signature scheme, where signatures from many signers can be aggregated into a single short signature. The scheme relies on a one time trusted setup to generate the public parameters.

Bootstrapping enables deep homomorphic computation in CKKS by replenishing multiplicative levels. It remains one of the scheme's most expensive operations. HEAAN reports a bootstrapping latency of 6.97ms, substantially faster than other publicly documented alternatives. However, the algorithmic and implementation techniques underlying this result have not been disclosed, leaving it unclear how such performance is achieved. In this work, we present a fully specified CKKS bootstrapping construction that achieves performance comparable to that reported by HEAAN. Building on SHIP (presented in Eurocrypt 2025), we introduce several algorithmic innovations that reduce communication and computational overhead while enabling efficient parallel execution. Our implementation bootstraps a single complex-valued ciphertext in 8.2ms and achieves an amortized latency of 4.6ms per ciphertext for a batch of 64. These results demonstrate practical sub-10ms CKKS bootstrapping.

Generalized BFV (GBFV) replaces the integer plaintext modulus of BFV with a polynomial plaintext modulus, yielding a flexible tradeoff between precision and SIMD parallelism. This framework encompasses both BFV and CLPX, with CLPX corresponding to the extreme large-precision endpoint where very large plaintext moduli can be supported without increasing the underlying RLWE dimension. However, bootstrapping remains a bottleneck throughout the large-precision GBFV regime: existing GBFV bootstrapping methods rely on BFV-style linear transformations, whose noise growth becomes prohibitive as the plaintext precision grows. We introduce a GBFV bootstrapping method that treats the noise of a GBFV ciphertext as a CKKS plaintext and bootstraps it through CKKS. The main obstacle is that the BFV-from-CKKS bootstrapping technique of Kim et al. (CCS'24) relies on integer plaintext scaling and does not directly apply to GBFV, whose scaling factor involves a polynomial plaintext modulus. We overcome this by developing a noise-extraction and recovery procedure tailored to polynomial plaintext moduli. Our implementation bootstraps large-precision GBFV instances, including CLPX for the first time, supporting plaintext moduli of more than $500{,}000$ bits in less than $20$ seconds. We also introduce GBFV-to-CKKS and CKKS-to-GBFV conversions, interpreting the former as an approximate digit-decomposition toolkit for non-arithmetic operations over large GBFV plaintext spaces.

Noisy linear algebraic assumptions (NLAs), such as $\mathsf{LWE}$ and Alekhnovich’s $\mathsf{LPN}$, have long served as the most reliable sources of post-quantum hardness. However, a series of recent classical attacks on assumptions once believed to be quantum-secure, coupled with the rapid progress in quantum technology, underscores the urgent need for assumptions that are plausibly hard even if both $\mathsf{LWE}$ and $\mathsf{LPN}$ turn out to be broken. A fascinating recent work of Ghosal et al. (Eurocrypt 2025) takes an important first step in this direction, constructing a PKE scheme by combining two NLAs that remain plausibly secure even if $\mathsf{LWE}$ and Alekhnovich’s parameter regime for $\mathsf{LPN}$ were to be polynomially broken. A critical weakness of their work, however, is that it is still $\mathsf{LPN}$-broken: namely, an oracle that breaks $\mathsf{LPN}$ with $n^{-\delta}$ noise rate can break their NLA, for some $\delta>0$. We ask: can this barrier be overcome? We answer this question positively, by introducing an NLA that is plausibly hard given an oracle that breaks even constant noise rate $\mathsf{LPN}$, while still being plausibly hard given an oracle that breaks $\mathsf{LWE}$. Along the way, we improve upon the work of Ghosal et al. significantly in several dimensions. Specifically, we introduce a single new natural NLA and provide constructions of (i) public-key encryption and (ii) two-round maliciously secure oblivious transfer protocol from this single assumption. We also construct a one-time circular-secure secret-key encryption from a binary variant of this assumption. Our assumption takes the form $(\mathbf{A}, \mathbf{A}\mathbf{s} + \mathbf{e})$, where $\mathbf{A}$ is a random unstructured square matrix, the secret $\mathbf{s}$ has short and sparse entries, and the error $\mathbf{e}$ is a mixture of two components: a small-but-dense error combined with a large-but-sparse error. We provide a comprehensive initial cryptanalysis, ruling out (1) efficient combinatorial attacks that exploit sparsity such as information set decoding, (2) dimension reduction attacks, and (3) dual lattice attacks. We also prove, via a reduction, that our assumption, and its binary variant, is at-least as hard as $\mathsf{LWE}$. Additionally, we show that for a broad range of parameters including those used by our constructions, our assumption does not appear to fall within the class of “lattice” assumptions, that is, there seems to be no reduction to approximate shortest vector problem solvers, and, crucially, it is plausibly hard even given an oracle that breaks $\mathsf{LPN}$ for any noise density parameter.

Threshold Decryption (TD) enables a set of decryptors, each holding a secret key share, to collaboratively decrypt ciphertexts. In this paper, we resolve the open problem raised by Devevey et al. [PKC 2021] of constructing an adaptively secure TD with polynomial modulus from lattices. As identified by Hwang et.al. [ePrint 2026/1585], solving this open problem is a particularly challenging task. The most challenging part is how to limit the leakage of secret key shares from decryption queries while keeping the modulus a polynomial. In this paper, we resolve the above open problem with two TD schemes TD1, TD2 from lattices in the random oracle model. -- TD1 is a non-interactive TD scheme achieving adaptive CCA-security with polynomial modulus for a small number of decryptors and bounded decryption queries. It can be extended to achieve robustness and works well in the asynchronous settings. -- TD2 is a non-interactive TD scheme achieving adaptive CCA-security with polynomial modulus for bounded decryption queries. Compared with TD1, it supports any polynomial number of decryptors and works well in the synchronous settings. To our best knowledge, our TD1 and TD2 are the first non-interactive TD schemes achieving adaptive security and polynomial modulus from lattices. The core techniques behind our schemes include the polynomial noise flooding technique and the coupled refined Leftover Hash Lemma (LHL) working for adaptive noisy linear leakage, which may be of independent interest.