International Association
for Cryptologic Research

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

Real-time group communication protocols, such as Zoom and Microsoft Teams, aim to provide end-to-end security for audio and video conferences even in the presence of a malicious server. Despite their widespread deployment, particularly since the COVID-19 pandemic, their intended security guarantees lack comprehensive formalization. Prior work largely focuses on Zoom, and analyzes its security in models that rely on restrictive assumptions, such as the existence of a trusted server at certain points in time or a long-lived leader that never leaves the group. Moreover, existing analyses assume that group-specific session states of group members are secure and incorruptible, leaving the impact of potential full state compromise on group security unexplored.

In this work, we propose a set of essential security guarantees for real time group communication with state-compromise resilience against fully malicious servers and provide the first construction that provably satisfies all of these guarantees. To formally prove that our design achieves its goal, we formalize a novel continuous group key distribution protocol and introduce an associated security model that captures all the intended guarantees. We propose a generic construction that is provably secure in this model and suggest both classical and post-quantum secure instantiations.

Besides these main design goals, we introduce a novel multi-recipient authenticated key encapsulation mechanism, which serves as a building block for our generic construction. We define two core security notions for maKEM, propose both concrete and generic constructions, and prove their security in the random oracle model and the standard model, respectively.

Although the state-of-the-art neural network model extraction attack in the hard-label setting by Carlini {\em et al.} at EUROCRYPT 2025 has polynomial-time complexity in theory, its dual-point clustering relies on singular value decomposition (SVD) with a time complexity of $\mathcal{O}(n^2 \cdot (d^{(k)})^3)$, resulting in huge runtime in practice. To address this computational bottleneck, this work transforms Carlini {\em et al.}'s geometric-view hard-label attack into an algebraic framework, and proposes a novel Approximate Signature Vector (ASV) method to achieve efficient parameter extraction on Fully Connected Neural Networks (FCNNs) by leveraging two key observations: high-dimensional random vectors are nearly orthogonal, and neurons in practical DNNs tend to learn disentangled features. The proposed ASV method replaces SVD-based rank checking with simple inner-product operations, reducing the clustering complexity to $\mathcal{O}(n \cdot (d^{(k)})^3)$ on average. Furthermore, this paper presents the first model extraction attack against hard-label max-pooling Convolutional Neural Networks (CNNs) by proposing an advanced ASV method with a kernel-centric clustering scheme instead of the neuron-centric clustering, which fully exploits the property of weight sharing in convolutions and fills the cryptanalysis gap. Experiments on a 64-64$\times 4$-10 FCNN and LeNet-5 (CNN) with max pooling demonstrate that our ASV method drastically cuts clustering time, and improves the overall efficiency in the model extraction.

Functional bootstrapping combines ciphertext refreshing with the evaluation of a target function, and has become a central tool for evaluating non-linear functions in homomorphic encryption. In the CKKS scheme, functional bootstrapping typically represents the target function as a trigonometric polynomial over the exponential basis generated by the bootstrapping procedure. Existing CKKS functional bootstrapping methods then evaluate this polynomial using standard baby-step giant-step techniques, whose multiplicative depth grows logarithmically with the polynomial degree. As a result, non-smooth function evaluations or high-degree lookup tables require a large modulus budget and often a larger ring degree, leading to higher evaluation latency. This is especially inefficient for applications that require only hundreds of parallel evaluations, where the large SIMD capacity of CKKS is not fully utilized.

We present \textsf{SWIFT}, a shallow and SIMD-aware functional bootstrapping framework for CKKS. The key idea is to exploit the exponential map \(h(x)=\exp(2\pi i x)\) used in CKKS bootstrapping, which satisfies \(h(\ell x)=h(x)^\ell\) for $\ell\in \mathbb Z$. Thus, the powers required for trigonometric polynomial evaluation can be obtained directly as \(h(\ell x)\) during bootstrapping, rather than generated by homomorphic multiplications after bootstrapping. To realize this idea efficiently, \textsf{SWIFT} packs the scaled inputs \(\ell x\) into SIMD slots and evaluates the exponential map on them in parallel. It then reconstructs the target trigonometric polynomial from the resulting powers. As a result, the multiplicative depth of polynomial evaluation becomes independent of the polynomial degree and can be reduced to constant depth, even depth one.

This shallow structure reduces the required modulus budget and enables high-degree polynomial evaluation at smaller ring degrees. It also lowers the key-switching cost from the standard \(\Theta(\sqrt d)\) cost to \(\Theta(\log d)\) or \(\Theta(d^{1/4})\), depending on our parameter regime. Our implementation shows that computations previously requiring \(\log N=16\) or \(\log N=17\) can be performed at \(\log N=15\). For lookup tables, \textsf{SWIFT} achieves up to a \(38.1\times\) latency improvement over prior CKKS functional bootstrapping methods at batch size \(128\). For ReLU evaluation at batch size \(256\), it achieves a \(5.21\times\) latency improvement over the previous method. These results demonstrate that CKKS functional bootstrapping can be made latency-efficient for batch sizes on the order of hundreds by using SIMD capacity as a computational resource rather than only as a batching mechanism.

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

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

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

Asynchronous distributed key generation (ADKG) is a fundamental primitive for building threshold cryptosystems and fault-tolerant distributed protocols in adversarial network settings. A central objective in this line of work is to achieve ADKG with $O(n^2)$ communication and constant round complexity under minimal setup assumptions. Recent progress has led to subcubic-communication ADKG protocols under different trade-offs. Feng and Tang (CRYPTO 2025) presented an ADKG protocol with $O(n^2)$ communication and $O(1)$ rounds, but at the cost of a cubic-communication setup phase in which each party posts a linear-sized public key on a public bulletin board. In contrast, Abraham et al. (PODC 2026) achieved an ADKG protocol with a standard setup phase, where each party posts only a constant-sized public key, but with $O(n^{2+1/k})$ communication and $O(k)$ rounds for a tunable parameter $k\leq \log{n}$. These results leave open whether one can simultaneously obtain constant-round complexity and quadratic communication under a standard setup phase.

In this work, we resolve this open problem by presenting the first ADKG protocol that achieves $O(n^2)$ communication and $O(1)$ rounds while requiring only a standard setup phase in which each party posts a constant-sized public key on a public bulletin board. Our protocol is resilient to a strongly adaptive adversary corrupting up to $f < n/3$ parties and assumes only random oracles and secure erasures, both of which are also assumed by prior subcubic-communication ADKG constructions.

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

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

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

Our algorithms are randomized and their correctness and (statistical) security hold with high probability. The algorithms are based on a combination of techniques: Karger's sampling, tree packing and sparse recovery sketches.

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

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

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

Malicious-secure multiparty computation protocols protect against an adversary's arbitrary misbehavior. In the honest-majority four-party setting, one common technique relies on all communication between parties being duplicated. Under this approach, all correct messages are sent twice, while corrupted messages are only sent by the adversary and will not match concurrent correct messages. When a receiver observes that inconsistency, it announces cheating has occurred (and possibly aborts). Existing implementations often optimize this procedure by batching many such checks into a single hash and running a final consistency check just before revealing the result of a computation.

Brüggemann and Schneider (Eurocrypt 2026) recently showed that these delayed consistency checks in honest-majority, malicious-secure protocols can violate privacy. Adversaries can introduce errors such that subsequent incorrect hashes reveal their missing secret share and allow plaintext secrets to be recovered just before the honest parties abort. Their suggested fix evaluates the hash comparison under multiparty computation, rather than in plaintext. In this report, we detail our fix for the Fantastic Four protocol in ORQ, a recent system for secure analytics that is vulnerable to the attack. The new implementation has a modest overhead that amortizes with larger inputs. The complexity of the modified protocol highlights the difficulty of implementing malicious-secure systems in practice; even seemingly harmless optimizations can break privacy.

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

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

We show that private-key function-hiding inner-product functional encryption (FH-IPFE) is impossible in the generic group model (GGM). This impossibility extends to (non-compact) two-input quadratic functional encryption (QFE) under a weak security notion that allows only a single key corruption. Our results apply both to the variant where decryption outputs the result directly, and to the variant where the result is encoded in the exponent of a group element.

Our results hold in both Maurer’s and Shoup’s model, with different tradeoffs. In Maurer’s model, we prove that FH-IPFE over $\mathbb{Z}_q^n$ cannot be realized even when $q^n$ is polynomially bounded. Here, $q$ denotes the modulus of the inner-product functionality, not the order of the underlying group. This stands in sharp contrast to non-function-hiding FE, which can be constructed from minimal assumptions (one-way functions in the private-key setting and public-key encryption in the public-key setting) whenever the set of functions is polynomially bounded. We extend this impossibility to Shoup’s model when $q^n$ is super-polynomial. Conceptually, our proof simulates any construction in Shoup’s model as one in Maurer’s model equipped with a random oracle. Our techniques may be of independent interest, offering a general method for upgrading other impossibility results from Maurer’s model to Shoup’s model.

We match these negative results with two positive ones. First, we show that one-sided bounded FH-IPFE (i.e., either the number of key queries or the number of encryption queries is bounded) can be realized from one-way functions. Second, when both the number of key queries and encryption queries are bounded, we show the resulting notion of FH-IPFE can be achieved information-theoretically. These positive results show that our impossibility precisely characterizes the threshold for FH-IPFE.

A zero-evading generator with error parameter $\lambda$ is a distribution $Z$ on $\mathbb{F}^n$ such that for any non-zero vector $x\in \mathbb{F}^n$ the probability that $=0$ is at most $2^{-\lambda}$, when $a$ is chosen according to $Z$. We investigate the number of additions required to compute $$ given $x$. The traditional construction chooses a vector $v$ with random $\lambda$-bit elements. Pippenger's algorithm gives an addition complexity of at least $\Omega(\lambda n/(\log(\lambda n))$ for this approach.

We give a construction requiring only $O(n^2+\lambda)$ additions, which can be smaller when $n<\lambda/\log(\lambda)$. We highlight the impact of reducing the number of additions on aggregation of group-based commitments, such as KZG commitments[KZG10]. We pose improving this further to $O(n+\lambda)$ as an interesting open problem.

Two post-quantum upgrades to TLS 1.3 are being standardized in parallel: a hybrid key exchange (already deployed) that runs an elliptic-curve Diffie-Hellman exchange alongside ML-KEM, and a standalone mode that uses ML-KEM on its own. The Internet-Draft draft-usama-tls-risks-of-mlkem points out that the machine-checked symbolic proofs of TLS 1.3 rely on the commutativity of Diffie-Hellman, which ML-KEM does not share: a key encapsulation mechanism is asymmetric, one endpoint generating a key pair and the other encapsulating against it. The existing proofs therefore no longer apply, a new one is needed, and the draft argues that hybrids should be preferred.

We supply that proof. We extend the reftls ProVerif models with a faithful, non-commutative KEM and analyze classical (EC)DHE, standalone ML-KEM, and the hybrid together, as unbounded concurrent sessions against a single active attacker free to break any cryptographic component.

The central result is a sharp and tight contrast in robustness: standalone ML-KEM is a single point of failure, secure only while ML-KEM itself is unbroken, whereas the hybrid stays secure as long as either of its components survives: an attacker must break both, in one session, to learn anything. This single point of failure reaches authentication as well as confidentiality: with the sole key-exchange secret exposed and no secret pre-shared key salting the key schedule, the server Finished message becomes forgeable, so a client can complete a handshake that no server completed, while the hybrid stays safe unless both components break.

The three modes also interoperate without ever confusing one another's keys, so migrating from (EC)DHE to a hybrid is a strict improvement. Two further experiments address the draft's remaining concerns: reusing an ML-KEM key forfeits the forward secrecy that an ephemeral key preserves, and a principal acting as both initiator and responder exposes no role-confusion attack arising from the asymmetry. At the symbolic level, and under stated assumptions, the analysis substantiates the draft's case for preferring hybrid key exchange.