International Association
for Cryptologic Research

Continuous group key agreement (CGKA), the cryptographic core of Messaging Layer Security (MLS, RFC 9420), provides key management for large end-to-end encrypted group chats. It refreshes the group's keys as members join and leave, but offers no way for a designated auditor to recover past epoch keys, and no way to check that such recovery remains possible. Regulated deployments in finance, healthcare, and government therefore resort to plaintext server logging, abandoning end-to-end encryption entirely. Simply adding a key escrow admits a silent escrow failure: the group accepts an epoch whose escrow holds unrecoverable material, with no visible anomaly until a later audit.

Addressing this, we introduce auditable CGKA (Au-CGKA), an MLS-shaped protocol in which every admitted epoch carries a proof. The proof binds that epoch's key material to a well-defined secret recoverable by a threshold auditor committee. Every member checks that binding against the epoch secret it derives and refuses the commit if the two disagree, so auditability guarantees that the secret of every epoch an honest member accepts is threshold-recoverable. We give a post-quantum protocol, Π_A, realizing this property with STARK proofs. The committer escrows the epoch secret to an auditor committee, and the escrow ciphertext is a STARK-friendly encryption of Shamir shares. Its well-formedness is proven in-circuit at MLS commit time.

We prototype Au-CGKA in Rust with the proofs on a zero-knowledge, post-quantum custom multi-stage STARK. On an Apple M5 Pro, an auditability proof takes 1.38 s with proof-size 15.31 MB and verifies in 0.17 s, at every group size; the relation it proves is independent of the group size. The proof is checked at admission and then discarded, so it costs bandwidth on the commit and nothing in storage; the only persistent overhead is the fixed-size escrow. Adaptive post-quantum security holds in the secure-erasure model with straight-line reductions in the quantum random-oracle model, and carries to the implemented backend under a stated assumption; privacy and escrow soundness follow as game-based guarantees.

Ring signatures have long struggled to balance absolute anonymity with traceability. While various extensions, such as traceable and accountable ring signatures, have been proposed, they typically apply a uniform anonymity or traceability rule to all potential signers. This paper introduces personalized-anonymity ring signatures (PARS), a novel primitive in which users are certified with different anonymity rights according to their roles or authority. Unlike ordinary ring signatures, PARS involves a group manager at key issuance; however, the group manager does not determine a fixed signing group. Instead, signers retain the ring-signature feature of choosing the ring at signing time, while the manager certifies whether each user's key permits fully anonymous signing or only traceable signing. This model is particularly suited for organizational governance, where ordinary members may require strong anonymity for internal reporting or expressing dissenting opinions, while users with institutional authority must remain accountable for official approvals or authorizations. We provide a formal syntax and rigorous security definitions for PARS, capturing both standard ring-signature requirements and traceability-related guarantees. We then present a generic construction from standard cryptographic primitives, including digital signatures, one-time signatures, public-key encryption, and non-interactive zero-knowledge proofs of knowledge.

SPHINCS+ provides stateless signing and self-contained verification, but its signatures are large: every message carries a FORS signature and a complete WOTS+/Merkle authentication chain to the long-term root. This cost is repeated even when messages arrive in a bounded episode whose maximum size is known in advance.

We introduce prepared-episode signatures and instantiate them as SPHINCS-PE. The construction splits a globally addressed hypertree at an episode boundary into upper and lower trees. Preparation authenticates the boundary root through the upper tree, while each online signature traverses the lower tree back to that root. Because the upper tree is computed before messages arrive, it can use fewer, taller layers. This removes WOTS+ blocks from full signatures at the cost of more preparation work. Full signatures remain self-contained, while recurring verifiers may cache the upper certificate. Our fixed-count exposure analysis pools colliding preparations and bounds post-selection of the target episode. The end-to-end theorem reduces unforgeability to PE-ITSR and explicit PRF and hash-component games.

Compared with the matched FIPS 205 SLH-DSA profiles, SPHINCS-PE reduces full-signature sizes by 3% to 12% for the short profiles and by 25% to 40% for the fast profiles. With the upper certificate cached, online signatures are 24% to 48% smaller for short profiles and 56% to 70% smaller for fast profiles. These results show that prepared episodes can shorten hash-based signatures without giving up self-contained verification.

The quantum resource analysis of CSIDH has remained an active research topic. At Eurocrypt 2020, Peikert raised three open problems concerning the optimization of the corresponding quantum resources. In this work, we primarily focus on the first two: optimizing quantum resources for ideal class groups and choosing the collimation arity. Specifically, we reduce the T-gate complexity of class group actions for CSIDH-512 from $2^{52.6}$ to $2^{51.7}$. Furthermore, within our four-way permutation construction model and under a specified classical memory budget, we provide a detailed analysis of the classical and quantum resources associated with different collimation arities $r$. Among the evaluated configurations, $r = 4$ emerges as the optimal choice. By incorporating the hidden-shift quantum algorithms proposed by Peikert, we achieve a T-gate reduction of at least 85\% for solving CSIDH-512.

Liu et al. (2022 Phys. Scr. 97 045102) propose a quantum public key encryption scheme in which a qubit message is encrypted by a controlled-NOT gate driven by a four-state public key, followed by measurement of the message register, and claim information-theoretic security. I show that the encryption map reduces exactly to \( |M\rangle \mapsto R_{\theta}X^{m}|M\rangle \), where the outcome \(m\) is published. \(R_{\theta}\) is diagonal and the ciphertext reproduces the computational-basis distribution \((|\alpha|^2,|\beta|^2)\) of the plaintext, while the plaintexts \(|0\rangle\) and \(|1\rangle\) are perfectly distinguishable. The claim of information-theoretic security is therefore invalid.

In 2017, Aggarwal, Joux, Prakash, and Santha proposed an integer analogue of the NTRU cryptosystem, known as the AJPS cryptosystem. This scheme is based on Mersenne numbers, and is believed to be resistant to quantum attacks. This paper revisits the security of AJPS by reexamining its inherent hard problems. We propose novel attacks that apply the continued fraction-based method and the lattice-based solving strategy for modular polynomial equations, rather than directly using lattice reduction algorithms. Our methods significantly relax the size constraints on the unknown private key. Specifically, we either eliminate the need to estimate upper bounds on the unknowns or extend the attack range of vulnerable weak keys, while enhancing the success probability under unbalanced parameter settings. To validate our theoretical findings, we conduct extensive numerical experiments with parameters of various sizes. The experiments confirm both the practicality and the effectiveness of our proposed attacks.

The MQOM signature scheme is currently a third-round candidate in the NIST competition for additional signatures. It is based on the ``MPC-in-the-Head'' paradigm and relies on the hardness of the MQ problem. Some of its parameter sets expose a Boolean quadratic system in the public key. While the situation for MQ over larger fields has been relatively quiescent over the last decade, Boolean MQ has seen active progress, culminating with Dinur's algorithms at SODA 2021 and Eurocrypt 2021.

We propose yet another algorithm for Boolean MQ. It is a hybrid between the ``polynomial-method'' of Lokshtanov, Paturi, Tamaki, Williams and Yu from SODA 2017 and Dinur's ``second algorithm'' from Eurocrypt 2021. We remove some machinery from the latter to obtain a modest improvement of 1--4 bits in performance for MQOM parameters (``decremental improvement'').

MQOM optionally uses the ``correlated GGM trees'' technique to shorten signatures; in that case, its security also relies on the hardness of the ``Partial-Guessing One-Wayness'' problem for MQ (PGOW-MQ): given an MQ system supposed to offer $\lambda$ bits of security, the adversary has to find the first $\lambda$ bits of a solution, and they have access to an oracle that enables them to check candidate prefixes. The designers of MQOM implicitly assumed that PGOW-MQ is as hard as MQ itself. Our algorithm can exploit the availability of the solution-testing oracle to solve PGOW-MQ 2 to 4 times faster than it solves MQ, thus showing that the two problems are marginally different. This yields attacks against MQOM that are 3--4 bits below the expected security level, but that suffer from huge memory complexities.

Lastly, we survey old and new techniques to find an invertible linear change of variables that puts a few arbitrary polynomials in UOV shape. This leads to a small acceleration of our algorithm, and also incidentally improves upon the Thomae-Wolf and Furue-Nakamura-Takagi algorithms to solve underdetermined Boolean systems. A new idea based on matrix pencils was used to solve the largest underdetermined Boolean Fukuoka MQ challenges and may be of independent interest.

Post-quantum migration of Transport Layer Security (TLS) is often described as replacing a classical key-exchange algorithm with a post-quantum alternative. This framing is incomplete: TLS distributes security across key establishment, authentication, resumption and pre-shared keys (PSKs), traffic-secret evolution, and the X.509/PKIX ecosystem. These functions have different security objectives, failure modes, lifecycle dependencies, and deployment constraints. This Systematization of Knowledge (SoK) develops a functional framework for analyzing post-quantum TLS migration as an architectural problem rather than a single algorithm transition.

We systematize classical, pure post-quantum, and hybrid key establishment; TLS 1.3 PSK modes and resumption; KeyUpdate; ML-KEM; ML-DSA and SLH-DSA; hybrid and composite authentication; X.509/PKIX and trust-anchor migration; HSM dependencies; interoperability; performance; deployment environments; cryptographic inventory; and crypto-agility. We classify evidence by mechanism, security objective, source of keying material, forward-secrecy behavior, quantum threat, post-compromise behavior, communication and computational cost, interoperability dependency, standardization status, deployment evidence, and migration complexity. We explicitly separate finalized standards from evolving Internet-Drafts and implementation-specific evidence.

The systematization produces four analytical conclusions. First, confidentiality migration and authentication migration are coupled operationally but distinct security programs. Second, hybrid ECDHE-ML-KEM is a strong transitional architecture for confidentiality migration when the relevant TLS integration and implementation support are available, because its security objective can tolerate failure of one component; the exact security claim nevertheless depends on the standardized construction and its assumptions. Third, PSKs, resumption, and KeyUpdate are not interchangeable forms of rekeying: their security depends on the provenance and role of the secret, while KeyUpdate remains within an existing traffic-secret lineage and does not create an independent post-quantum secret. Fourth, deployment readiness is constrained as much by certificates, trust stores, HSMs, middleboxes, inventory, and interoperability as by primitive availability. We therefore derive a migration decision framework that prioritizes HNDL-sensitive data, controlled hybrid deployment, interoperability testing, staged authentication and PKI migration, and observable retirement of classical-only mechanisms.

We prove that every finite two-player game $G$ with entangled value $\omega^*(G)=1-\epsilon$ satisfies \[ \omega^*(G^{\otimes n}) \le\exp(-\Omega(\frac{\epsilon^3}{\epsilon+ \ell }n)) \] for every $n\ge1$, where $\ell:=\log(|A| |B|)$, and $A$ and $B$ are the answer alphabets. Compared with Chapter 6 of the OpenAI report [Ope26], this improves the gap exponent from thirteen to three and matches the cubic gap dependence in Holenstein's general classical bound [Hol09]: \[ \omega(G^{\otimes n})\le\exp(-\Omega( \frac{ (1-\omega(G))^3}{1+\ell} n)). \] The proof replaces the randomly shifted logarithmic grid used in quantum correlated sampling by smooth soft labels. This makes the relevant label infidelity quadratic in the distance between state descriptions and avoids a Jensen loss when averaging over questions. Together with the postselection argument, these improvements yield the cubic gap dependence stated above.

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.

The quaternionic ideal-to-isogeny translation is a central building block of SQIsign. While the Qlapoti algorithm by Borin, Invernizzi, Corte-Real Santos, Eriksen, Mula, Schaeffler and Vercauteren significantly simplified and accelerated this step, it does not treat several technical details in sufficient depth, resulting in a flawed analysis of its failure probability. Additionally, several discrepancies between the implementation of Qlapoti and the paper's pseudocode were never analyzed explicitly. We address these shortcomings and add further improvements, resulting in a new norm equation solving algorithm with negligible failure probability. Our C implementations shows 6x to 9x speedups compared to Qlapoti's norm equation solver, and 1.3x-2.1x speedups for a SQIsign NIST2 signature (depending on NIST levels).

We present a practical framework $\mathsf{DumboMix}$ for asynchronous anonymous broadcasts with guaranteed output delivery (G.O.D., a.k.a. robustness), enabling a set of $n$ servers to privately solicit $N$ messages from distinct clients, such that these messages remain secret until they are simultaneously revealed in a uniformly random order. Here, asynchronous G.O.D. ensures that all solicited messages will eventually be randomly mixed despite (i) arbitrary malicious behaviors by up to $n/3$ Byzantine servers and (ii) unpredictable network delays and jitters.

At the core of $\mathsf{DumboMix}$, we first propose a couple of practical arithmetic circuits $\mathsf{DumboMix1}$ and $\mathsf{DumboMix2}$ for mixing in Shamir-secret-shared multi-party computation (MPC) over $\mathbb{Z}_p$, along with their server-optimized variants. When randomly mixing $N$ messages, their online phases require only $\mathcal{O}(1)$ multiplicative depth, expected $\mathcal{O}(N^2)$ scalar multiplications (between public and shared values), and up to $\mathcal{O}(N)$ MPC multiplications (between shared values). Moreover, assuming a robust underlying MPC framework, they guarantee that all revealed inputs are uniformly shuffled. In contrast, existing techniques fail to achieve all these performance and functionality features: The DC-net variant $\mathsf{Blinder}$ (CCS’20) may reveal a non-negligible fraction of inputs without shuffling them; Butterfly switching networks in secret-shared MPC (CCS’19) incur $\mathcal{O}(\log^2 N)$ multiplicative depth; RabbitMix (Security’24) requires $\mathcal{O}(N^2)$ MPC multiplications; and PowerMix (CCS’19) incurs $N^{3}/2$ scalar multiplications.

We also implement our mixing methods within $\mathsf{DumboMPC\text{++}}$, our computation-optimized implementation of the state-of-the-art robust AMPC framework $\mathsf{DumboMPC}$ (Security’25), which provides more concretely efficient offline preprocessing while preserving asynchronous G.O.D. and optimal resilience. We then conduct extensive evaluations with $n=4$ to $31$ servers under varying network settings, revealing that our new mixing circuits achieve 44.8--65.9× (resp. 37.1--52.7×), 4.8--7.1× (resp. 3.9--5.5×), and 2.7--4.0× (resp. 5.1--7.2×) speedups over RabbitMix, PowerMix, and the butterfly switching network, respectively, when shuffling 1024 messages in LAN (resp. WAN).

Sum-check and Fast Fourier Transforms (FFTs) dominate the computational cost of modern zero-knowledge proving systems, such as HyperPlonk (Eurocrypt 2023) and FRI-based schemes like DeepFold (USENIX Security 2025). Despite numerous optimizations, existing efforts remain fragmented across algorithmic, protocol, and implementation layers, leaving significant CPU performance potential untapped.

We present MamaBearZKP, a co-designed framework that bridges these layers to enable high-throughput ZK proving on modern CPUs. At its core, MamaBearZKP leverages MamaBear, a 49-bit prime field ($p = 2^{49} - 2^{34} + 1$), and introduces a systematic vectorization framework specifically tailored for the AVX-512IFMA execution model. By treating field arithmetic, protocol structure, and low-level hardware primitives as a unified optimization target, MamaBearZKP achieves unprecedented efficiency.

We instantiate our framework in a HyperPlonk-DeepFold prover and obtain single-thread speedups of up to $42\times$, $33\times$, $15\times$, $21\times$, and $21\times$ for ZeroCheck, ProductCheck, DeepFold Commit, DeepFold Open, and end-to-end proof generation, respectively, compared to a Goldilocks-based baseline on the same platform. With 8-thread execution, the corresponding speedups increase to as much as $64\times$, $47\times$, $81\times$, $45\times$, and $45\times$. Across our end-to-end evaluations, MamaBearZKP also achieves up to $18\times$ single-thread speedup over Plonky3, which already uses an AVX-512 BabyBear backend. Rather than resulting from isolated improvements, these gains arise from a synergistic cascading effect: the 49-bit field’s headroom enables efficient lazy reduction, which paves the way for high-performance fused fold-and-evaluate kernels. The efficiency of these kernels facilitates a unified stay-packed dataflow throughout the HyperPlonk and DeepFold stacks; it is precisely this end-to-end dataflow that materializes the hardware throughput of AVX-512IFMA into realized performance gains.

Function secret sharing (FSS) gives two parties succinct keys whose local evaluations add up to a hidden function value. Removing the dealer is the natural next step for preprocessing-based secure computation, but malicious security then requires more than checking a finished key: the generation transcript, the function the key actually computes, and every released evaluation share must all be bound to one execution. We call this the cross-phase binding problem, and we solve it.

We present VeriFSS, a dealer-free two-party FSS scheme with active security, proved in the standard simulation-based framework against one static malicious corruption. The construction rests on a two-plane key: the distributed generator produces a key for the paired function $x\mapsto(f_\theta(x),\Lambda f_\theta(x))$, where $\Lambda$ is a secret global authentication scalar. The second plane makes every local evaluation an authenticated sharing for free, which yields online report binding without vector commitments, extractable hashing, or per-point interaction. It also supplies the ingredient the audit was missing: we prove a moment-fidelity lemma showing that a corrupted party cannot misreport the full-domain moments of its own sealed key except with probability $3/|E|$ over the challenge set $E$, and a shape-identification lemma showing that three moment equations pin a point function down exactly, with error $2n/|E|$ over any field. The proof isolates the coefficient of the square monomial in the support polynomial and is therefore characteristic-free; in characteristic two an odd-size equal-weight support defeats the support equation on its own, and we show the position equation takes over. A discrete-derivative reduction carries both lemmas to comparison functions, and a Galois-ring variant covers fixed-point payloads over $\mathbb{Z}_{2^k}$ by a $2$-adic valuation argument, so no non-additive lift into a binary field is ever needed.

Generation costs two rounds and five field elements per party per level; certification adds $O(n)$ elements with no dependence on the domain size, and a dynamic cross-domain aggregation certifies arbitrarily many heterogeneous instances under one challenge and a constant number of rounds. We then lift the general-purpose FSS gates of Boyle et al. (EUROCRYPT 2021): every gate that is a public affine post-processing of a constant number of DPF/DCF evaluations---interval containment, splines, ReLU, arithmetic shift, bit decomposition, zero test, table lookup---inherits active security at no additional online cost.

We evaluate our construction using a C++ implementation that certifies keys over $\mathbb{F}_{p^2}$ ($p=2^{61}-1$) and $\mathrm{GF}(2^{128})$, realises the gate layer, and agrees bit‑for‑bit on every exported test vector. A certified DPF key at $n=16$ takes $5.7$ ms to generate and $3.3$ ms to certify. Certified DPF keys are $5.4\%$ larger than the semi-honest dealer-free baseline at $n=16$, and aggregated certification traffic converges to $1{,}282$ bytes per instance while the round count stays constant. Replaying the certified execution between two processes over TCP shows what that constancy is worth: at a $50$ ms round trip a session takes $1.15$ s, and the figure is unchanged whether one key or sixty-four are certified together, so wide-area certification of a whole preprocessing session is latency-bound by a single key. A campaign of $1{,}400$ injected generation deviations plus shape, moment and release forgeries is rejected without exception in six of seven deviation classes; the seventh is rejected in exactly the $105$ of $200$ trials in which the attacked index bit is one, which is a quantitatively exact confirmation of the single-bit selective-failure predicate that we model explicitly in the ideal functionality, matching the leakage profile of the best known actively secure distributed DPF.

Masking is a well-established software countermeasure against side-channel attacks, yet even algorithmically correct masked implementations can leak on real hardware once the compiler has performed instruction selection, register allocation, and stack allocation. Existing approaches either rely on leakage simulation, which is tied to a specific power model and computationally expensive, or on formal verification of the source program, which does not capture the effects introduced by the subsequent compilation stages. We address this gap from within the compiler and propose a leakage detection pass for the Jasmin language, integrated into its formally verified pipeline and operating on the intermediate representation before register and stack allocation. Rather than simulating power traces, the pass implements a configurable, microarchitecture-oriented leakage model that tracks the contact between shares, secrets, random values, and public values, making the root causes of the detected leakage explicit and enabling the detection of masking-order reductions. We validate the pass on 60 dedicated Jasmin test snippets covering all considered leakage sources and category combinations, and intend it as the foundation for a subsequent compiler stage that automatically removes the detected leakage, thus constituting a first step toward secure compilation.

A $(k,n)$-robust combiner for a primitive $\mathcal{P}$ combines $n$ candidate instantiations of $\mathcal{P}$ into a single scheme that remains secure as long as at least $k$ of them remain secure. Robust combiners have been extensively studied for primitives such as hash functions, public-key encryption, and oblivious transfer, but much less is known in the setting of cryptographic groups. In this work, we initiate the study of robust combiners for cryptographic groups in Maurer's generic group model (GGM), where algorithms access group elements only through abstract algebraic operations.

We ask whether one can combine $n$ candidate groups into a single group that remains secure provided that at least $k$ of the underlying groups remain secure. A natural baseline is the direct-product construction, which preserves search hardness but fails for decisional assumptions and incurs substantial representation overhead. We show that these limitations are in fact inherent.

Our first result is a complete impossibility for the decisional Diffie--Hellman assumption: for every polynomially bounded $n$ and $k$ with $k
These results identify a fundamental limitation of robust hedging at the group level. Decisional assumptions such as DDH cannot be robustly combined in the GGM, while search assumptions admit robustness only at essentially optimal representation cost. Consequently, robustness for group-based cryptography must in general be achieved at higher layers, such as protocol design or key derivation.

The uniform multivariate quadratic (UMQ) assumption states that it is hard to find a zero of a uniformly generated MQ function. It is the average-case hardness assumption about the MQ problem. In this paper, we investigate the relations among the UMQ assumption, the MQ one-wayness (MQOW) assumption, and the MQ second-preimage resistance (MQSPR) assumption.

We show that UMQ and MQSPR tightly imply each other, and MQOW tightly implies UMQ. Then, we show that UMQ implies MQOW when $m\leq n+O(\log\lambda)$, where $n$ is the number of variables, $m$ is the number of MQ equations, and $\lambda$ is the security parameter. In particular, when $m\leq n+O(1)$, this implication is tight.

As a corollary, we show that MQSPR implies MQOW under the same condition $m\leq n+O(\log\lambda)$, which is weaker than the compression condition $n=m+\omega(\log\lambda)$ required for the implication from SPR to OW for general function families. In particular, our result covers the square case $m=n$ as well as mildly overdetermined MQ systems satisfying $m=n+O(\log\lambda)$.

In this note, we formally show that the recent algorithm by Simon (ePrint:2026/1591, August 11 2026) does not extract the least-significant bit of the dihedral coset problem (DCP) secret with non-negligible guessing advantage, and therefore does not solve DCP. We emphasize that our result is not merely about Simon's analysis of his algorithm; we are showing directly that the algorithm cannot possibly work.

Our no-go encompasses a much broader class of algorithms than the specific algorithm by Simon. The main message of our no-go is that an algorithm for DCP following the template of the reduction by Regev (SIAM Journal on Computing, 2004) will probably have to make extensive use of the classical Fourier labels in the uncomputation stage. On the other hand, the algorithm by Simon can be implemented, up to error $\mathsf{poly}(n)2^{-n/3}$, using only the most-significant third of the classical Fourier labels, and therefore cannot succeed.

To help with verifiability, we release Lean 4 code for our results, available at https://github.com/sragavan99/lean-ePrint-2026-1591-refutation.

Poseidon [Grassi, Khovratovich, Rechberger, Roy, and Schofnegger; USENIX'21] is an arithmetization-oriented (AO) hash function designed to be efficient in real-world zero-knowledge (ZK) applications. We present GSR, a generalized S-box skipping gadget that absorbs a single initial full round and $t-2k$ partial rounds without increasing the polynomial degree of the Poseidon polynomial system with state size $t$ and input-output constraints $2k$. By restricting the subspace of the total constraints satisfying solutions, independent of the rounds constants and MDS matrix selection, the distinguisher expends input degrees of freedom to linearize the internal state transitions where the dense algebraic mixing usually occurs. This maps a computationally infeasible polynomial system into a bounded, low-degree ideal parameterized by $k$ free variables.

We show how to use the gadget to construct a probability 1 distinguisher over $t-2k+1$ rounds of Poseidon. We then show how this distinguisher can be used as a basis for interpolation-based attacks. We go on to present experimental solutions to the CICO-1 problem over 28 out of 31 rounds and CICO-2 problem over 25 out of 31 rounds in the setting set by the Ethereum Poseidon initiative (i.e., using the KoalaBear field with $t=24$ and $\alpha=3$). Crucially, since the subspace restriction approach is tuned only by $t$ and $k$, our results apply to the Poseidon structure regardless of the choice of round constants, MDS matrix, S-box exponent $\alpha$, or field size $p$.

The relationship between cryptography and learning theory has long been a central theme in the foundations of theoretical computer science: cryptographic primitives can imply hardness of learning, while hardness of learning can in turn be used to construct cryptographic schemes. Recent works have begun exploring analogous connections in the quantum setting, relating the average-case hardness of learning quantum states (AHL) to cryptographic primitives such as one-way state generators (OWSG). Despite recent progress exploring this for pure states, the relationship for mixed states has remained an open question.

In this work, we prove that the existence of AHL for mixed quantum states is equivalent to the existence of inefficiently verifiable one-way state generators (IV-OWSGs). As a consequence, this relates mixed-state AHL to EFI pairs. Moreover, as a corollary of existing results, we obtain a separation between IV-OWSGs and OWSGs relative to the SWAP oracle.