Finding a nontrivial endomorphism of a given supersingular elliptic curve is a hardness assumption of isogeny-based cryptography. We prove the reduction from it to the problem of finding a splitting of a given principally polarized abelian surface. By using this new reduction, we also prove the heuristic equivalence of the splitting problem with a degree restriction and the endomorphism ring problem in dimension two.

Signatures with Post-Compromise Accountability (SPCA), introduced by Dayanikli et al. at SCN'26, are signature schemes that enable signatures generated before the compromise of a signing key to be distinguished from those produced after the compromise. In this paper, we extend this notion to static group signatures and introduce Group Signatures with Post-Compromise Accountability (GSPCA). GSPCA preserves the anonymity and traceability guarantees of group signatures while enabling pre-compromise signatures to be revalidated after key compromise. The coexistence of opening and revalidation algorithms gives rise to a new consistency requirement, which we formalize as opening--revalidation consistency. We present a generic construction of GSPCA from public key encryption schemes, signature schemes, and simulation-sound non-interactive zero-knowledge proof systems. A central technical difficulty is that the encryption randomness in our construction is derived from a randomized signature component and may therefore have high min-entropy without being uniformly distributed. To address this issue, we introduce adaptive hedged security against adaptive chosen-ciphertext attacks (AH-CCA), which extends indistinguishability under adaptive chosen-ciphertext attack (IND-CCA2) to adaptively chosen high-min-entropy message--randomness distributions, and show how to realize the required randomness-recovering encryption in the random oracle model. We also give a generic signature-based mechanism that provides the required min-entropy and key-binding properties. Finally, we show that ordinary IND-CCA2 security alone is insufficient as a general assumption for our construction by exhibiting an IND-CCA2 secure encryption scheme for which the resulting GSPCA scheme fails to satisfy anonymity.

Oblivious Transfer (OT) is a fundamental cryptographic primitive and a core building block for many multiparty cryptographic protocols. While existing OT extension techniques achieve excellent asymptotic efficiency for very large batches, their performance degrades when the total number of OTs is only moderate, since the cost of generating the required base OTs is no longer effectively amortized. In this work, we close this gap by presenting OT constructions that achieve square-root communication complexity for batched OT generation. Concretely, our most efficient protocol generates ell random OTs using O(lambda sqrt(ell)) bits of communication, where lambda is the security parameter. Our constructions are inspired by recent advances in homomorphic secret sharing and techniques for distributed discrete logarithm computation, and explore complementary points in the design space. The first construction is based on the Damgård-Jurik cryptosystem and standard assumptions, at the cost of a one-time trusted setup. The second eliminates the need for trusted setup, relying instead on a power-DDH assumption over prime-order groups. For 128-bit security, our schemes require approximately 2.6 KiB and 1.25 KiB of communication, respectively, to generate 128 random OTs, including the hash key in the power-DDH construction. Our best construction outperforms existing OT extension techniques for batch sizes of up to 32,768 OTs.

For public-key encryption with keyword search (PEKS), chosen-ciphertext attack (CCA) security has been studied in settings where an adversary is allowed to access the test oracle. Notably, the CHK transformation (Canetti, Halevi, and Katz, EUROCRYPT 2004) does not yield CCA-secure PEKS. To address this limitation, Abdalla, Bellare, and Neven (TCC 2010/JoC 2018) proposed a generic construction of CCA-secure PEKS from CCA-secure anonymous and weakly robust identity-based encryption. However, CCA security alone is insufficient to resist keyword-guessing attacks (KGAs) arising from trapdoor leakage in PEKS. To mitigate KGAs, public-key authenticated encryption with keyword search (PAEKS) has been studied. In particular, Li and Boyen (IACR CiC 2024) proposed a generic construction of PAEKS. In this paper, we propose a generic transformation that converts a PAEKS scheme into a CCTA-secure one, where CCTA denotes security against chosen-ciphertext and trapdoor attacks. Our transformation can be viewed as a variant of the CHK transformation. The key observation is that, unlike in PEKS, the receiver in PAEKS identifies and specifies the sender when generating a trapdoor, enabling keywords to be used as tags. The transformation directly upgrades PAEKS instantiations obtained via the Li-Boyen generic construction under various assumptions to CCTA-secure schemes. As a result, we obtain the first fully CCTA-secure PAEKS schemes from both pairings and lattices. As an additional benefit, the transformation improves search efficiency. By leveraging verification keys embedded in ciphertexts and trapdoors, sender-receiver matching can be performed without cryptographic computation, for example, by using hash tables. Consequently, for a trapdoor associated with a particular sender, the search complexity measured in cryptographic operations becomes independent of the number of senders and is essentially the same as that of PEKS. Although improving efficiency is not the primary goal of the transformation, this benefit is of independent interest.

Succinct Non-Interactive Arguments of Knowledge (SNARKs) for NP allow a prover to prove knowledge of a witness of an NP relation to a verifier with a short proof. The primary goal of a (static) SNARK is to make verification cheap: the proof should be short, and the verifier's work should be minimal. However, recent work has also focused on making SNARKs more prover-efficient: cheap verification should ideally not come at the cost of large prover overhead. One avenue for achieving prover efficiency is via Dynamic SNARKs, which allow a prover to efficiently update the proof when the witness is updated. For example, one may use a SNARK to issue a proof of a query being performed correctly on a database, and then issue a new proof of the query once the database is updated. If these updates are small compared to the size of the witness (only a single entry of a large database is updated), then the prover should ideally be able to use the old proof to generate a new proof in time proportional to the distance between the old and the new witness. While some constructions of dynamic SNARKs for NP have been recently proposed by Wang et al. [Eurocrypt 2026] and Zhang et al. [Eurocrypt 2026], they have many limitations, such as lack of post-quantum security, dependence on a setup by a trusted third-party, and poor asymptotic and concrete efficiency. In this work, we present a compiler for constructing a dynamic SNARK for Plonkish constraints (which capture arbitrary NP computations) by using a static SNARK for NP and a vector commitment scheme as black boxes. When instantiated with a state-of-the-art hash-based SNARK and Merkle trees, the compiler yields a dynamic SNARK that is post-quantum secure in the QROM, has a transparent setup, and achieves $O(n)$ initial prover time and $O(k \log^2 n)$ update prover time, with succinct proofs and verification, where $k$ is the Hamming distance between the old and new instance-witness pairs. Our Ligerito-based implementation achieves cumulative prover speedups of $147\times$ and $11.7\times$ over a static HyperPlonk baseline for 10,000 successive one-gate updates and 1,000 successive 128-gate updates, respectively, on a $2^{23}$-gate circuit, including the full dynamic initialization cost.

Most existing multiparty computation (MPC) protocols assume static and equal participation. All computing parties can dedicate resources and stay online for the entire computation, and they have equal influence on computation correctness and security (i.e., they are equally hard to corrupt). Supporting dynamic participation, so parties can join/leave at will, and associating weights to these parties reflecting their trust level, are essential to enable MPC in contemporary emerging applications. Existing solutions addressed these issues separately at varying security levels, and attempting to combine them while addressing malicious security raises several challenges and open questions. In this paper, we close this gap and develop maliciously-secure MPC protocols that support weighted participation in both static and dynamic (or fluid) settings. In particular, we extend prior work on weighted ramp secret sharing (WRSS) to support verifiability and proactivity, which could be of independent interest. Then, we show how to perform arithmetic operations over weighted shares in a verifiable way, thus enabling maliciously-secure weighted MPC with guaranteed output delivery under static participation. Utilizing the proactivity feature of our secret sharing scheme, we develop a state handover protocol and employ it to support dynamic participation in committee-based MPC with the same security guarantees. Both protocols are synchronous and assume honest majority. To the best of our knowledge, our work is the first to support both weighted and dynamic participation in MPC.

A distributed point function (DPF) is a cryptographic primitive that enables compressed additive sharing of a secret unit vector across two or more parties. Despite growing ubiquity within applications and notable research efforts, the best 2-party DPF construction to date remains the tree-based construction from (Boyle et al, CCS'16), with no significantly new approaches since. We present a new framework for 2-party DPF construction, which applies in the setting of feasible (polynomial-size) domains. This captures in particular all DPF applications in which the keys are expanded to the full domain. Our approach is motivated by a strengthened notion we put forth, of programmable DPF (PDPF): in which a short, input-independent "offline" key can be reused for sharing many point functions. * PDPF from OWF: We construct a PDPF for feasible domains from the minimal assumption that one-way functions exist, where the second "online" key size is polylogarithmic in the domain size $N$. Our approach offers multiple new efficiency features and applications: * Privately puncturable PRFs: Our PDPF gives the first OWF-based privately puncturable PRFs (for feasible domains) with sublinear keys. * $O(1)$-round distributed DPF Gen: We obtain a (standard) DPF with polylog-size keys that admits an analog of Doerner-shelat (CCS'17) distributed key generation, requiring only $O(1)$ rounds (versus $\log N$). * PCG with 1 short key: Compressing useful correlations for secure computation, where one key is of minimal size. This provides up to exponential communication savings in some application scenarios.

We consider methods for scalar multiplication on an elliptic curve where the scalar digits are processed from left to right, that is, from most significant to least significant. We analyze exceptions that may arise during point addition and doubling throughout the multiplication. Eliminating such exceptions is critical for achieving constant-time execution and preventing timing attacks. We establish conditions under which exceptions occur only at the final addition or not at all. Guided by these conditions, one can ensure constant-time behavior by performing all doublings and all intermediate additions using fast formulas that require no exception handling. We examine two variants of the Comb method: SAB-Set and LSB-Set. For both variants, we prove that the constant-time conditions are satisfied under mild restrictions on the base point order and Comb parameters. Additionally, we propose a convenient scalar recoding algorithm for the SAB-Set variant.

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.

The succinct LWE (CRYPTO~'24) and decomposed LWE (CRYPTO~'25) assumptions are two recently introduced variants of the celebrated LWE problem, known to imply the existence of numerous new cryptographic primitives. Yet, the hardness of these problems has thus far remained poorly understood, since there is no known reduction to LWE. In this work, we study these lattice problems from a foundational perspective. Our main technical contribution is a worst-case-to-average-case reduction from \emph{superlattice SVP} (SuperSVP) to succinct SIS. We introduce SuperSVP as a variant of SVP for general lattices in which the solver is additionally given, as a hint, a short basis for a related superlattice. Combining this result with our quantum reduction from succinct SIS to succinct LWE, which is an analog of Regev's SIS-to-LWE reduction, and with our search-to-decision reduction establishes worst-case hardness for succinct LWE. Finally, we show that succinct and decomposed LWE are equivalent, extending this conclusion to decomposed LWE. Overall, our work places succinct and decomposed LWE on firmer theoretical ground and, as a direct consequence, establishes the \emph{worst-case} hardness of a variety of cryptographic primitives, known to be implied by these assumptions.

Generic divisor-addition formulas require little arithmetic workspace but fail on exceptional inputs. We prove a randomized reduction that enables their use in quantum phase computation. The reduction uses two independent public group seeds in a finite abelian group of odd order. For every fixed input, the two child values at each internal node of a complete balanced addition tree are independent and uniform. The density of exceptional pairs therefore controls both the total failure probability and the error of the averaged quantum channel. We apply this reduction to an odd prime-order subgroup of size $r$ in a genus-two Jacobian over $\mathbb{F}_q$, where $q$ is an odd prime. The curve is represented by a monic quintic with zero quartic coefficient. An integer lift of weighted Mumford arithmetic, a terminal polynomial for phase computation, and an independently shifted Legendre symbol yield useful-sample probability $1-\mathcal{O}(L/q)$ on the exact domain $\mathbb{Z}_r^2$ when $r=\Theta(q^2)$. Here $\mathbb{Z}_r=\mathbb{Z}/r\mathbb{Z}$ and $L$ denotes the number of tree leaves. This probability bound assumes exact state preparation and Fourier readout. Explicit height certificates, streaming Chinese remainder reconstruction, and clean modular primitives give a sampler using $10n+o(n)$ logical qubits, including both scalar registers, where $n=\lceil\log_2 q\rceil$. The computational model permits intermediate measurements, reset, and classical feedforward. For the Gaudry--Schost instance over $\mathbb{F}_{2^{127}-1}$, a $16$-bit window gives an analytic allocation of $1{,}923$ qubits, compared with $2{,}172$ and $3{,}063$ qubits for the matched Huang et al.\ and Chen et al.\ module schedules, respectively. All three schedules retain the same scalar inputs. The Toffoli bound for a capped run is below $2^{60}$. A $32$-bit window reduces the allocation to $1{,}618$ qubits, with a Toffoli bound of approximately $2^{70.43}$ and at most $2^{36}$ classical table entries. Rotation synthesis is charged separately. These estimates quantify an explicit space--time tradeoff.

We present an identity-based blind signature scheme built on the SM9 Chinese national cryptographic standard. The scheme outputs standard SM9 signatures, removes all online pairing operations through a single setup-time pre-computation, and adds only one user-side exponentiation to achieve blindness. We prove two properties rigorously: \emph{restricted target-identity unforgeability} (RTU) under the $Q$-BCAA1 assumption, and \emph{computational blindness} against a malicious signer in the random oracle model (ROM), where the signer is given the final signatures and still cannot link them to its protocol views. We state clearly that RTU is strictly weaker than the standard one-more unforgeability (OMU) notion for blind signatures: RTU forbids signing queries on the target identity and is therefore meaningful only when that identity encodes a fresh, one-time issuance context, as occurs in coin-, ballot-, and credential-issuance protocols. The $Q$-BCAA1 assumption is the inversion-type assumption that matches the SM9 private-key structure $d_{\ID}=[s/(s+\tau)]P_1$; it lets the reduction answer adaptive key-extraction queries without any decisional (Gap) oracle. We give a partial-blind extension with a formal partial-blindness model, discuss implementation requirements, and compare costs against prior SM9-based proposals.

We study the Add/XNOR decision problem: given $n$ words of $n$ bits each, choose between addition modulo $2^n$ and bitwise XNOR at each position of a left-associative expression so that its final value is zero. We prove NP-completeness by a deterministic polynomial-time reduction from binary SUBSET-SUM. Independent four-bit guard fields force each successful four-operation gadget to consist entirely of additions or entirely of XNORs. Normalization by XNOR parity prevents later gadgets from repairing a failed guard, while control bits and zero padding enforce the target and the equality of operand count and word width. The reduction also yields a $2^{o(n)}$-time exclusion under the Exponential Time Hypothesis and NP-completeness when the word width is a fixed positive rational power of the operand count. An exact meet-in-the-middle algorithm uses $O^*(2^{(n-1)/2})$ time and space, where $O^*$ suppresses polynomial factors in $n$. We also quantify the reduction's solution multiplicity and the output marginals for independently uniform operands. The optimal exponential rate and average-case complexity remain questions for further work.

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.

In September 2026, an AI produced a Lean proof of Fermat's Last Theorem in eleven days, and AI provers have started on cryptography. Within a few years, an AI may hand you a machine-checked proof that Signal is secure. You won't need to read it, because Lean will have checked every step. What Lean can't check is whether the theorem says what you think it says. That depends on its definitions, which the AI will also have written at length for that one proof. This already happens. A Lean library's security theorem for Schnorr signatures passed the checker, yet as written it held for every adversary and so promised nothing. When proofs are cheap, the scarce resource is a person who can read what was proved. I argue that we should build high-level cryptographic languages for that person. A protocol's owners should write its model themselves, short enough for one or two people to read. Every claim the language makes should rest on a checked theorem. And definitions of protocol goals such as forward secrecy should be built in: a small set, versioned and agreed in public the way we agree on AES, so that a property's name means the same thing in every report. Today it may not: on a one-page Verifpal model, two of five verdicts would flip under other standard definitions, with neither answer wrong. Agreeing on definitions will take years of public argument that better provers can't shorten, so we should start now.

Fault attacks exploit transient hardware faults to bypass software-level security checks in embedded processors. Processor-level redundancy can detect such faults, but duplicating the whole processor is costly for resource-constrained devices. This paper proposes Staggered Instruction-Fetch Duplication (SIFD), a lightweight processor-level countermeasure based on instruction-fetch redundancy. SIFD fetches each instruction twice in consecutive cycles, while fetching two different instructions in every fetch cycle. This staggered schedule detects inconsistent fetch results without full processor duplication, compiler support, or cryptographic hardware. We implement SIFD on a custom RV32I processor and evaluate it on an Artix-7 FPGA using clock fault injection (CFI) and electromagnetic fault injection (EMFI). SIFD increases slice utilization by 15.0% and execution time by 16.3%. It reduces the attack success rate from 0.86% to below 0.01% under CFI and from 0.32% to 0.13% under EMFI. It also detects 73.18% of CFI attempts and 11.44% of EMFI attempts. These results indicate that SIFD can convert many fault effects into explicit detections and reduce successful fault-injection outcomes, especially under CFI.

Post-quantum signature schemes require efficient implementations to be viable in practice. MQOM, a third-round candidate in NIST’s additional call for digital signatures, is a promising target for SIMD optimization. This work leverages a transpose-enabled paired-matrix trick to develop a vectorized implementation of MQOM v2.1, corresponding to the Round-2 specification, with reduced wasted SIMD work and memory traffic. We evaluate MQOM v2.1 on Arm NEON, x86 AVX2, and x86 AVX-512, covering key generation, signing, verification, and memory; peak dynamic memory falls by up to 39.43%. We also include supplementary MQOM v3 experiments to assess how the matrix-layout optimization transfers to the Round-3 code.

Privacy-preserving credential systems typically focus on data protection during the presentation phase, overlooking potential privacy threats during issuance. A malicious issuer could use the non-minimal information it obtains to deny issuance selectively. Such a denial, going beyond the eligibility policy, is a form of censorship. In this work, we revisit the security of anonymous credential systems to protect users from malicious issuers during credential issuance. We first highlight the limitations of existing definitions and introduce a security model capturing censorship resistance. Next, we present a round-optimal (i.e., one message per party) construction built from blind signatures and specifically tailored for selective disclosure in the presentation phase. Finally, we present CRACS, an instantiation of our construction, deployable within the European Digital Identity Wallet (EUDIW) framework. CRACS improves on the current reference implementation of the EUDIW, maintaining selective disclosure and yielding unlinkability between presentation and issuance sessions in addition to censorship resistance. Unlike prior work, CRACS confines advanced cryptography to issuance, leaving secure elements, the standardized credential formats, signature schemes, and presentation mechanisms untouched. It can therefore be deployed incrementally alongside current EUDIW implementations, issuer by issuer and user by user, with no change for verifiers.

We introduce Confidential Error-correcting Codes (CECs), a new cryptographic primitive that enables reliable decoding from perturbed codewords while preserving message confidentiality. We formalize this primitive through three security properties: confidentiality, robustness, and soundness. To realize this goal, we develop a general framework for constructing CECs based on a Randomness-Security Separation (RSS) structure, which first encodes a nonce to introduce randomness and then masks the encoded payload with a pseudorandom function. Based on our RSS framework, we instantiate CECs, called Conc-CEC, using concatenated Reed-Muller and Reed-Solomon codes. The resulting Conc-CEC admits provable guarantees for all three properties. Notably, compared to PRCs (CRYPTO'24), another recent cryptographic primitive with error-correcting capability, CECs achieve significantly stronger concrete security guarantees under practical parameter settings. As a primary application of CECs, we further present CECMark, a watermarking scheme for AI-generated images. Our experiments on real-world generative image models show that CECMark consistently outperforms state-of-the-art watermarking methods, including Gaussian Shading (CVPR'24), PRCMark (ICLR'25), and T2SMark (NeurIPS'25). In particular, CECMark achieves higher robustness across all 56 evaluated perturbations and ensures a false positive rate below $10^{-5}$ without introducing side effects. Taken together, our work lays a novel cryptographic foundation for trustworthy watermarking schemes that, for the first time, unify provable security guarantees with strong practical reliability.

Non-interactive batch arguments (BARGs) for $\mathsf{NP}$ enable proving the validity of $k$ $\mathsf{NP}$ statements with a proof whose size is independent of $k$. Threshold BARGs are a natural generalization that enables proving that at least $t$ out of $k$ statements are valid. Unfortunately, existing threshold BARG constructions have the drawback that the size of the common reference string (CRS) grows polynomially with $k$. This is the case even when the statements have a short description (e.g., when considering index languages). Moreover, other than constructions based on indistinguishability obfuscation ($i\mathcal{O}$), prior constructions could only achieve computational soundness. In this work, we construct the first threshold BARG with statistical soundness for an expressive class of trapdoor threshold languages from either circular-secure fully homomorphic encryption or from witness encryption in combination with the learning with errors assumption. Moreover and importantly for our applications, the size of the CRS only scales polylogarithmically with $k$. Next, we combine our threshold BARG with a new technique for sampling pseudorandom permutations in order to build weighted threshold signatures with a statistical unforgeability guarantee. Then, in combination with witness encryption, we obtain a weighted threshold encryption scheme that supports $\lambda$-bit weights. Decryption is entirely non-interactive in our setting. Previously, such a scheme was only known from $i\mathcal{O}$. If we additionally work in the random oracle model, then we obtain a weighted threshold encryption scheme that supports arbitrary weights with silent setup. In the silent setup model, users choose their own public/secret keys and no longer need to rely on a central authority to generate and issue decryption keys.

Doubly-Efficient Lookup Arguments are specialized argument systems that enable succinctly proving the correctness of a batch of $k$ lookup accesses to a large table $\textbf{x}$ in time proportional to $k$ and sublinear in $|\textbf{x}|$. All existing such schemes suffer from one of the following limitations. Either they rely on elliptic-curve-based assumptions for their security, hence they are not secure against quantum adversaries, or are rather impractical, as they rely on algorithms for fast polynomial evaluations (that are mostly of theoretical interest), or operate over fields of small characteristic---making them incompatible with most modern argument systems. In this work, we use tensor codes to construct transparent and post-quantum secure updatable doubly-efficient lookup arguments that asymptotically outperform all existing schemes with the same properties, in terms of prover time and/or preprocessing. By further optimizing this approach for a specific type of two-dimensional tensor codes, we build TenseUp, a concretely efficient lookup argument that, as shown in our experiments, has comparable or even better performance than state-of-the-art non-post-quantum secure prior doubly-efficient lookup arguments. As an independent contribution, we propose a general-purpose compiler for building dynamic SNARKs from any ``static'' SNARK, via judicious use of updatable doubly efficient lookup arguments to store and access witness updates. Applying our compiler with different SNARKs and lookup arguments can lead to different novel results; e.g., combining a hash-based SNARK with our lookup arguments yields the first transparent and post-quantum secure dynamic SNARK.

We construct public-coin, succinct, zero-knowledge interactive arguments for NP relations decided by time-$T$, space-$S$ random-access machines. Assuming the existence of collision-resistant hash functions, our arguments give a frontier of tradeoffs between prover time and space, and proof size. We follow the streaming PIOP+PCS framework of Block et al. (TCC 2020, CRYPTO 2021), reducing the problem of constructing time- and space-efficient arguments to time- and space-efficient streaming multilinear polynomial commitment schemes (MLPCS). We develop two code-based streaming MLPCS inspired by Brakedown (CRYPTO 2023) and BaseFold (CRYPTO 2024), implementing each scheme when additionally given succinct access to the underlying encoding matrices. We instantiate this framework assuming row-sparse, column-sparse, and Reed-Solomon encoders, then apply a generic PIOP + MLPCS compiler to obtain our (zero-knowledge) time- and space-efficient arguments. Finally, as all our protocols are public-coin, applying Fiat-Shamir yields time- and space-efficient (zk)SNARKs from symmetric-key primitives (i.e., collision-resistant hashing). Our Brakedown-based constructions have \(O(\log T)\) rounds and \(\widetilde O(\sqrt T)\)-size proofs and verification time, with two complementary prover profiles: (i) \(\widetilde O(S)\) space (which is optimal) and \(\widetilde O(T^{3/2})\) time, and (ii) \(\widetilde O(T)\) time (nearly optimal) and \(\widetilde O(S+\sqrt T)\) space. Our BaseFold-based constructions achieve $\mathrm{polylog}(T)$ proof size and verification time with \(O(\log T)\) rounds. We again obtain two complementary prover profiles: (i) an encoder parameterized construction with \(\widetilde O(T+T_{\mathrm{Enc}})\) time and \(\widetilde O(S + S_{\mathrm{Enc}})\) space, where \(T_{\mathrm{Enc}}, S_{\mathrm{Enc}}\) are the running time and space of a streaming log-space encoder for a suitable linear code, and (ii) an unconditional sub-quadratic instantiation \(\widetilde O(T^{3/2})\) time and \(\widetilde O(S+\sqrt T)\) space.

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.

Asynchronous verifiable secret sharing (AVSS) allows a dealer to distribute a secret among parties while preserving privacy and consistent reconstruction, despite Byzantine faults and arbitrary message delays. It is a fundamental building block for Byzantine agreement, distributed key generation, and secure multiparty computation. Packed AVSS protocols share many secrets together to reduce communication per secret. The best known AVSS protocols achieve quadratic communication while sharing linearly many secrets. In particular, Bingo (Abraham et al., CRYPTO 2023) shares a batch of $\Theta(k)$ secrets among $k$ parties using $O(\lambda k^2)$ words of communication, while also achieving adaptive security, but relies on assumptions that are not post-quantum secure. Known post-quantum alternatives have higher worst-case communication for comparable batch sizes or require substantially larger batches to achieve linear amortized communication. We present Lattice Bingo, a lattice-based packed AVSS protocol with quadratic communication and linear packing. For every constant $\epsilon>0$, it shares $\Theta(k)$ secrets among $k\geq(3+\epsilon)f$ parties, tolerates $f$ Byzantine parties, and uses $O(k^2\operatorname{poly}(\lambda))$ words of communication. It additionally achieves one-shot adaptive secrecy: the adversary may adaptively choose its corruption and reconstruction requests based on the public transcript observed so far, but must submit these requests together in a single batch. Our main technical contribution is a commitment scheme for two-dimensional linear codes based on the PowerBASIS assumption. We combine PowerBASIS commitments with the linear code based secret sharing of Applebaum, Nir, and Pinkas, replacing the Reed–Solomon encoding and KZG commitments used in Bingo. Our commitment supports proof interpolation, enabling parties to recover missing shares and their opening proofs. It additionally achieves a notion that we call one-shot simulation hiding. Together, these properties allow us to adapt Bingo’s framework to obtain Lattice Bingo with the same efficiency and one-shot adaptive security.

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.

Abstract. Recently, Dupin and Abelard [11] proposed a broadcast encryption scheme, outperforming the Complete Subtree-based and Subset Difference broadcast encryption in terms of encryption cost and bandwidth requirement. However, Dupin and Abelard acknowledge that the worst-case bound for bandwidth requirement of Complete Subtree approach can be reached in their scheme as well. In this paper, we answer the call to further reduce this bandwidth bottleneck. We first provide concrete analysis to show how this worst-case upper-bound is reached from particular Boolean functions. Our proof on [11]’s worst-case complexity demonstrates and shows that those Boolean functions, out of all 2^2^l possible Boolean functions of n variables, produces the worst-case upper-bound. Then we present two improved broadcast encryption schemes to significantly reduce this worst-case bandwidth consumption for further optimization of Dupin and Abelard’s technique. Our proposed ADC-BE suite, composed of two primitives, AD-BE and AC-BE, can significantly optimize this worst-case complexity from O(n/2) down to O(1) for a system of n users. This is efficient especially for large number of users in the system. Our schemes combines the algebraic normal form, disjunctive normal form, and conjunctive normal form to optimize a Boolean function to its minimized representation. Furthermore, our approaches support full range of Boolean functions without any restrictions, i.e., general access structures. This is more versatile than monotone access structure, where the group attribute policy is solely restrained to the Boolean clauses without bit-inversion nor negation. Last but not least, both AD-BE and AC-BE can be straightforwardly extended to post-quantum broadcast encryption schemes as the underlying hardness depends on one-way function, e.g., secure hash function.

Recently, the Institute of Commercial Cryptography Standards (ICCS) launched the Next Generation Commercial Cryptographic Algorithm Program (NGCC), which includes a standardization process for cryptographic hash functions. In this note, we analyze the mode of operation of Duet, one of the hash-function candidates. Duet is a permutation-based hash function directly inspired by the Alternating Sponge (ASP). Both constructions use two permutations on $b=r+c$ bits, split into an outer part of $r$ bits and an inner part of $c$ bits. We first present a distinguisher against ASP requiring $\mathcal{O}(2^r)$ permutation queries, which contradicts the claimed indifferentiability bound in a non-trivial parameter regime. We then introduce a distinguisher and a state-recovery attack against Duet. Both attacks require only a constant number of $h$-bit output blocks, with $h\leq c$, and $\mathcal{O}(2^{r+c-h})$ permutation queries. These attacks do not affect the claimed collision or preimage resistance, but they distinguish Duet's multi-block output from random, with consequences if Duet is used as a XOF or a KDF; state recovery also enables length extension.

This paper investigates hash-function constructions derived from lightweight block ciphers, that are suitable for evaluation in fully homomorphic encryption (FHE) settings. We focus on PRINCEv2, a 64-bit lightweight block cipher with 128-bit keys and low algebraic complexity, which is particularly amenable to FHE evaluation. However, the small block size of such ciphers limits the applicability of standard hash-function transforms. Indeed, achieving 128-bit collision resistance in the $(n, 2n)$ setting, i.e., with 64-bit blocks, requires a quadruple-block-length (QBL) compression function, for which no generic construction is known. In this work, we propose a concrete QBL compression construction tailored to PRINCEv2 and analyze its collision resistance. Candidate QBL designs inspired from existing double-block-length constructions are also outlined. As a further contribution, we describe a carefully optimized homomorphic circuit design for PRINCEv2. The resulting implementation outperforms previous works in both operation counts and computational depth. Experimental timings demonstrate the practical feasibility of evaluating the corresponding hash constructions under FHE with low latency, while providing cryptographically small failure probability.

Zero-knowledge proof (ZKP) schemes enable a prover to convince a verifier of the validity of a statement without revealing the underlying secret. These schemes have found extensive applications in secure communications, privacy-preserving transactions and blockchain technologies. However, the computational cost of proof generation remains a major obstacle to practical deployment. Although various acceleration techniques have been proposed, they often rely on specialized hardware that may not be locally available. A promising yet underexplored alternative is to offload computation to a more powerful third party, such as a cloud server, in a secure and efficient manner. Rather than outsourcing the entire proof generation process, selectively offloading the most computationally intensive operations offers greater flexibility and simplicity. In this work, we propose a secure outsourcing scheme for multi-scalar multiplication (MSM), which is the most computationally expensive operation in many widely used ZKP protocols. Our scheme enables users to delegate MSM computations to a server while preserving the confidentiality of the secret inputs (i.e., the scalars) and allowing verification of the server’s output. Our performance analysis shows that the proposed scheme significantly reduces the computational burden on the user while imposing only minimal overhead on the server.

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.

At CRYPTO 2016, Cogliati and Seurin proposed EWCDM as a nonce-based MAC construction making two block cipher calls and one almost-XOR-universal (AXU) hash evaluation and achieving beyond-birthday-bound (BBB) security. They noticed that a simplified variant of EWCDM named Encrypted Wegman--Carter (EWC) admits a birthday distinguishing attack. Later, at CRYPTO 2017, Mennink and Neves proposed EWCDMD, the dual of EWCDM, as a new candidate BBB-secure MAC, but at EUROCRYPT 2020 Nandi proposed a birthday distinguishing attack against EWCDMD. However, the distinguishing attacks did not yield forgeries, and whether EWC and EWCDMD have BBB unforgeability (or MAC security) remains open. We prove beyond-birthday unforgeability for EWC and EWCDMD and answer this long-standing open problem positively. Using an $n$-bit block cipher and an $O(2^{-n})$-AXU hash family, we prove that both constructions are secure up to $2^{5n/6}$ MAC queries and nearly $2^n$ verification queries, in the nonce-respecting setting. To bypass the birthday distinguishing attacks, our proofs directly analyze forgery events using auxiliary experiments indexed by hash values and messages. For EWC, we additionally employ conditional permutation analysis and collision multiplicity bounds with KL divergence, whereas for EWCDMD we use Hellinger distance and Fourier analysis.

We present a new framework for constructing practically efficient publicly verifiable secret sharing (PVSS) with $non-interactive$ $dealers$, in that the dealer may go offline after sending a single message, and is not involved in the share verification process. We use identity-based encryption (IBE) and commitments as the main ingredients and avoid expensive zero-knowledge proofs. By instantiating them with post-quantum secure schemes, a lattice-based IBE and a hash-based commitment, we obtain our first construction: a post-quantum secure PVSS with non-interactive dealers that outperforms the prior lattice-based practical construction by Gentry et al. [Eurocrypt 2022]. However, to enable the aggregation of PVSS transcripts (which facilitates many additional applications such as secure voting), we propose our second construction by replacing hash-based commitments with Pedersen's homomorphic commitments. While this does not achieve full-fledged post-quantum security (as Pedersen's scheme is not quantum safe), it still provides privacy against a post-quantum adversary. We prove the security of this construction in a new model, which we call long-lasting security. This model guarantees that the protocol is secure in the present (pre-quantum era) while maintaining privacy in the long term (post-quantum era). This new model is of independent interest for constructing efficient schemes that are resilient to the harvest-now-decrypt-later line of attacks. In this model, we propose a blockchain-compatible secure voting scheme using our PVSS scheme. Our PVSS schemes demonstrate practical efficiency: our post-quantum PVSS shares a secret among $1024$ receivers in $667$~ms and verifies the dealing in $<5$ ms, and communicates $4.4$MB, overall whereas the state of the art [Gentry et al., Eurocrypt 2022] communicates $251$MB and requires $2060$s for dealing the secret.

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.

The isogeny graphs of superspecial abelian surfaces with maximal real multiplication were first studied by Charles, Goren, and Lauter in 2009, when they constructed the RM-CGL hash function on these graphs and proved that they are Ramanujan. As a consequence, these graphs enjoy optimal expansion properties, which are either absent or difficult to establish in other higher-dimensional isogeny graphs. In this paper, we take a closer look at these graphs from a cryptographic perspective, and attempt to demonstrate that they are the natural generalization of the supersingular $\ell$-isogeny graph to dimension two. To this end, we tackle two algorithmic problems: We design and implement the RM-KLPT algorithm to solve the algebraic pathfinding problem in these isogeny graphs by solving a norm equation in ideals of a quaternion algebra over a real quadratic field. Further, we revisit the RM-CGL hash function, provide a proof-of-concept implementation, and showcase that knowledge of the initial surface's algebraic description leads to a second-preimage attack on the hash function through our RM-KLPT algorithm. RM-KLPT resembles the one-dimensional KLPT algorithm much more closely than KLPT$^2$ does. This is due to the existence of a higher-dimensional analogue of the Deuring correspondence in the RM setting, which yields significantly shorter paths ($\sim p^{3}$) compared to KLPT$^2$. Finally, we conclude by discussing potential cryptographic constructions that may be built from RM-KLPT.

We show that a variant of the Wagner/BKW-style algorithm for LWE of Kirchner and Fouque [KF15] solves decision and search LWE with secrets of size $n$ over prime moduli $q=n^{\kappa+o(1)}$, for any fixed $\kappa>0$, with errors bounded by $\exp((\ln n)^{o(1)})$, in time $2^{O(n/\ln\ln n)}$ given $n+O(n/\ln\ln n)$ original samples. Further, if each coordinate of the secret is also bounded by $\exp((\ln n)^{o(1)})$, the same time bound holds with errors bounded by $n^{o(1)}$ and only $O(n/\ln\ln q)$ samples. Earlier, it was known that Kirchner and Fouque's algorithm could solve LWE with these parameters in subexponential time with a much larger number of samples $m = \Omega(n\log{n})$ [HKM18]. Ducas et al. [DEL25] showed that an adaptation of this algorithm could solve the corresponding dual, the $\mathrm{SIS}^{\infty}$ problem, with a suitable norm bound $q/\operatorname{polylog}(n)$ and $m=n+\omega(n/\ln\ln n)$ variables in subexponential time. Whereas their analysis involves interpreting the algorithm in terms of chains of lattices, our approach is quite elementary and is based on bounding the lower moments of a Fourier statistic.

Verifiable computation systems often need to prove large matrix multiplication statements, but a direct SNARK arithmetization of a \(k \times k\) product requires \(\mathcal{O}(k^3)\) constraints. Freivalds' randomized check reduces the algebraic computation to vector-matrix products, but proving those products inside a SNARK still costs \(\mathcal{O}(k^2)\) constraints. We present LAMP, a matrix-multiplication checking protocol that combines Freivalds' randomized check with proximity testing over linear error-correcting codes. The prover commits to encoded matrices and intermediate vectors before the sampled query positions are derived. The CP-SNARK circuit then checks only the sampled codeword positions and commits to the values used inside the circuit, while Merkle openings and CP-Link proofs ensure consistency between the in-circuit witnesses and the externally committed values. We prove soundness for this committed-input setting under the soundness of the SNARK backend, the binding of the commitments, the correctness of the CP-Link checks, and the relative distance and unique-decoding radius of the Reed--Solomon code. For a fixed number \(t\) of sampled positions, the main in-circuit SNARK relation has \(\mathcal{O}(tk+E_{\mathsf{code}})\) constraints, with additional \(\mathcal{O}(t\log n)+E_{\mathsf{link}}(k,t)\) backend work for Merkle openings and CP-Link checks. We implement LAMP in Go and compare it with a Freivalds-based SNARK circuit. In the matrix benchmark at \(k=2^{12}\), LAMP reduces the constraint count by \(9.68\times\) and shortens proof generation time by \(5.81\times\); verification remains approximately \(0.13\,\text{s}\) across the measured range.

Committing security for authenticated encryption (AE) captures the difficulty of constructing a distinct input tuple, including the key, that yields the same ciphertext. This notion is relatively new but has attracted significant attention due to its practical relevance. A promising direction is to design generic transforms that convert any AE scheme into a committing one. A common approach to generic transforms, initiated by the CTX transform (Chan and Rogaway, ESORICS 2022), is to add a hash function that uses part of the AE input/output, assuming the hash is ideal, i.e., a random oracle. Because the baseline AE is assumed to be secure in the standard model, this approach inherently mixes standard-model and idealized-model assumptions. We revisit this approach. We show that a number of state-of-the-art generic transforms relying on a mixed model (Chen and Karadžić, Eurocrypt 2025, and Bhattacharjee et al., ePrint 2024), proposed after CTX, are vulnerable once the hash function is instantiated, by presenting practical counterexamples enabling efficient attacks. Our attacks/counterexamples exploit the fact that the baseline AE may depend on the instantiation of the generic transform, whereas the opposite is not true for the principle of the generic transform. In most cases, the attacks are effective with any instantiation, and the baseline AEs in the attacks have a natural structure, such as Enc-then-MAC with a counter mode encryption. We also demonstrate how to rectify these damaged transforms with minimal algorithmic modifications, relying solely on the standard-model assumptions.

The Noisy Linear Equations problem involves finding the solution to a random linear system over a finite field given noisy evaluations. This is a generalisation of various learning problems widely used in cryptography, including Learning with Errors (LWE), Learning with Rounding (LWR), and Learning Parity with Noise (LPN). We present a new sample-preserving search-to-decision reduction for Noisy Linear Equations that has complexity $\mathrm{poly}(n,m,\log q, q/\sigma)$, where $n$ is the dimension of the secret, $m$ is the number of samples, $q$ is the modulus, and $\sigma$ is the magnitude of the noise (defined suitably for the kind of noise involved). In particular, this implies search-to-decision reductions for LWE and LWR that run in time $\mathrm{poly}(n)$ even if the modulus $q$ is exponentially large, as long as the noise-to-modulus ratio $\sigma/q$ is non-negligible. Our reduction works for prime moduli $q$. If $q$ is composite, it instead produces a list that contains a small multiple of the solution. Prior to this work, known search-to-decision reductions for LWE and LWR either did not preserve the parameters of the problem (i.e., $m$, $n$, $\sigma$, and $q$), or had complexity that scaled polynomially with either $\sigma$ or the largest prime factor of $q$.

Many hash-based proof systems check that committed words are close to Reed–Solomon codewords by testing one random combination of them. Their soundness analysis uses a proximity gap: if the combination agrees with a codeword on many positions, so do the original words, on the same positions, except for a few exceptional challenges. Such gaps are known above the Johnson threshold, about $\sqrt\rho$ for rate $\rho$, and extending them below it would shrink proofs. Recent work does so in large characteristic, but not over binary fields, where some of the fastest proof systems run. We show that beyond-Johnson proximity gaps fail over binary fields. Our first construction applies to any additive domain (a binary linear subspace) filling a constant fraction of a containing binary field. Over a suitable extension challenge field and at rate $1/4$, it gives two words that can simultaneously match codewords on at most $25\%$ of the positions, while their combinations approach the $50\%$ Johnson threshold for superpolynomially many challenges. This rules out any $\mathrm{poly}(N)/|\mathbb F|$ bound on the exceptional probability below Johnson. On Binius64's domain (length $2^{27}$, $128$-bit challenges), the combination reaches $49.4\%$ agreement with probability above $2^{-30}$. The construction also rules out polynomial-size decoding lists below Johnson: one word agrees with superpolynomially many codewords at agreement approaching $50\%$, whereas earlier superpolynomial lists needed the rate, or the agreement–rate gap, to vanish. Our second and third constructions cover every additive domain, including the sparse domains used by LeanVM and Flock. At rate $1/16$, the second gives $(N-1)(N-2)/6$ exceptional challenges at the Johnson threshold itself, when the domain lies in a proper subfield of the challenge field. For domains larger than $2^{20}$, this rules out even $90$ bits of soundness from a single beyond-Johnson proximity-gap check over a $128$-bit challenge field. The third construction trades agreement for larger exception counts: at rate $1/2$ and length $2^{22}$, its combinations reach $53.125\%$ agreement from common agreement $50\%$, with probability at least $2^{-20}$ over a $192$-bit challenge field. Finally, at every fixed rate, some constant agreement above the rate makes every challenge exceptional, over $\mathrm{poly}(N)$-size challenge fields. All of our results are formally verified in Lean.

Encrypted key exchange (EKE), introduced by Bellovin and Merritt (IEEE S\&P 1992), and Masny-Rindal OT, introduced by Masny and Rindal (ACM CCS 2019), are highly-efficient methods for compiling essentially any KEM into advanced cryptographic protocols, namely password-authenticated key exchange (PAKE) and oblivious transfer (OT), by relying only on idealized symmetric-key primitives. They have become leading candidates for practically-implementable PAKE and OT due to (1) their simplicity, (2) their plug-and-play nature, allowing for flexibility in the choice of KEM, and (3) existing proofs of UC-security (in the classical adversarial model). Due to point (2) above, these compilers yield attractive candidates for efficient post-quantum PAKE and OT, especially given the recent post-quantum KEM standardization efforts. This motivates the question of whether the (UC-)security of these compilers translates to the quantum adversarial model. In this work, we show that it does not. In particular, we prove that a general family of (O)EKE protocols, as well as Masny-Rindal OT, are not UC-secure against quantum polynomial-time adversaries, even when instantiated with a post-quantum KEM. To establish UC-insecurity, we devise an adversarial strategy that provably thwarts any attempt by the simulator to extract its input (the password in the case of PAKE, and the receiver's choice bit in the case of OT). These are the first naturally-occurring/non-contrived cryptographic protocols that are known to be secure in the (classical) ROM but provably insecure in the QROM. To complement these negative results, we establish that both compilers yield certain notions of game-based security. In the PAKE setting, we consider OEKE instantiated with the ``2-Feistel'' cipher, and prove its stand-alone game-based security in the quantum random oracle model. We view these results as a proof of concept that security of (O)EKE and Masny-Rindal OT can yet be redeemed in the quantum setting, though we caution that the situation will be more subtle than in the classical setting due to the breakdown of simulation-based security. Along the way, we establish a novel ``advantage-tight'' one-way to hiding lemma that may be of independent interest.

Verifiable Computation on Encrypted Data (vCOED) enables clients to outsource computation while providing both privacy and integrity. A promising vCOED paradigm is blind proofs, which use homomorphic encryption (HE) to evaluate verifiable computation (VC) proofs on encrypted data. Despite their efficiency, blind proofs do not provide strong client privacy: a malicious server can exploit reaction attacks to learn information about the client's inputs, intermediate values or final outputs. Our work addresses this limitation by introducing Homomorphic Encryption over Random Encodings (HERE). We formalize a new security notion, indistinguishability under chosen-plaintext attacks in the presence of an equality oracle over encodings (IND-CPA-E). We prove that combining IND-CPA-E-secure HERE schemes with blind proofs that verify computation over the encodings yields vCOED protocols with strong client privacy. We then instantiate a HERE scheme for functions of bounded degree $d$, using Shamir secret sharing at $(d+1)$ evaluation points under $(d+1)$ distinct HE keys. Finally, we demonstrate the concrete efficiency of our approach through an application to matrix-vector multiplication (MVM), a linear computation corresponding to $d=1$. The proof overhead (i.e. the ratio of the vCOED prover runtime to the homomorphic MVM runtime) in our combined vCOED protocol is as low as $2\times$, as demonstrated in our prototype implementation.

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).

Ducas, Engelberts and Loyer (CRYPTO 2025) turned Wagner's generalized birthday algorithm into a provable subexponential-time Gaussian sampler for unstructured short integer solutions. Recent preprints of Han, Gao and Hu, and of Chen, Jiang, Wang and Zhang, obtain low-sample decision learning-with-errors algorithms from this framework. We extend it to module matrices over power-of-two cyclotomic rings, for every residue degree of the prime modulus. For fixed module ranks $k,\ell\ge1$, let $n=kd$, $m=(k+\ell)d$, and suppose $\ln(q/\sqrt n)=(\ln n)^{b+o(1)}$. For every fixed $b,c,\xi>0$, we solve Module-SIS with coefficient infinity-norm bound $q/(\ln n)^c$ in worst-case time and space $2^{(1/(2b)+\xi)n/\ln\ln n}$. For matrix-independent errors satisfying $\|e\|\le\sigma\sqrt m$ with probability $1-o(1)$ and $\ln(2+\sigma)=(\ln n)^{a+o(1)}$, $0\le a<b$, decision and search Module-LWE take $2^{(1/(2(b-a))+\xi)n/\ln\ln n}$. Success is $1-o(1)$ using only the given $k+\ell$ ring samples; error coordinates need not be independent. The structural ingredient is a Chinese-remainder-support uncertainty bound: the loss of randomness of sparse dual labels is compensated by an arithmetic lower bound on their length. Scalar row perturbations give search over the base field, and small integer shears remove a singular-block loss. Projection, the Han--Gao--Hu martingale analysis, and a finite enumeration sampler give a common algorithmic framework. We also prove sample-preserving scalar search-LWE and narrow Module-LWE algorithms. In particular, for polynomial prime $q=n^{\kappa+o(1)}$, $\kappa>1/2$, one ring sample and growing rank suffice for decision and search in time and space $2^{(1/2+\xi)n/\ln\ln n}$ when the sample supplies $(1+o(1))n/\ln\ln n$ scalar responses. Here ``narrow'' restricts both secret and error. Separate heuristic estimates in the model of Ducas, Engelberts and Loyer suggest that Wagner-style attacks do not reach the NIST security targets of ML-KEM and ML-DSA.

Oblivious RAM (ORAM) allows a trusted client to access (encrypted) data stored in untrusted memory, such that the access patterns reveal nothing about the data or the queries. It is well-known that any ORAM scheme must suffer from a logarithmic overhead. More precisely stated, each request must incur $\Omega(\log_B N)$ block transfers on average, where $N$ is the size of the logical memory and $B$ is the block size of the oblivious implementation. Moreover, the same lower bound extends to oblivious Search Trees (ST). For upper bounds, however, we have been long stuck with a $(\log_B N)^2$ curse on two fronts: (1) Log-squared curse for statistically secure ORAMs: although optimality is known for computationally secure ORAMs for $B = \Theta(1)$ or $B \geq \log^{1+\epsilon} N$ (where $\epsilon > 0$ is an arbitrarily small constant), progress has been stagnant when it comes to statistical security. (2) Log-squared curse for oblivious search trees: for search trees, we do not know how to overcome the log-squared curse even when allowing computational assumptions. In this paper, we break this long-standing log-squared curse for both oblivious search trees and statistically secure ORAM on broad parameter regimes: (1) Our first result gives an optimal, statistically secure ORAM with $O(\log_B N)$ cost as long as $B \geq \log^{1+\epsilon} N$. (2) Our second result gives an optimal, statistically secure oblivious search tree with $O(\log_B N)$ cost when $B \geq \log^{2+\epsilon} N$, matching the performance of the best known non-oblivious search trees in this parameter region. Notably, this means that for search trees, we can get obliviousness for free! The assumptions on $B$ required to achieve optimality are standard and mild. They not only coincide with the standard wide cache-line assumption prevalent in the classical algorithms literature, but also align well with the hardware-enclave architectures that employ oblivious algorithms in practice, such as the implementations of Signal and Meta.

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.

Individual cryptography (Dziembowski et al. Crypto'23) and complete knowledge (Kelkar et al. CCS'24) aim at constructing protocols that ensure that some individual party must know a secret value in the clear, and so the computation cannot have been “outsourced” to an MPC computation. Two central primitives are proofs of complete (or individual) knowledge, which enforce that some party actually knows the secret witness, and secret sharing with snitching, which enforces that whenever the secret is reconstructed, some party must learn a certificate of this fact. The instantiations proposed by both papers (Crypto'23 and CCS'24) ensure that to compute a proof or reconstruct the shared secret, a large number of hash function evaluations is necessary. Thus, at least one party must compute many of these “in the clear” (and not via MPC) and from the hash function inputs one can extract the secret (in the random oracle model). In practice, they suggest using Bitcoin mining hardware. Sequential proofs of complete knowledge have recently been proposed, which use proofs of sequential work to enforce that the hashes are performed sequentially. As a consequence, it suffices to require a much smaller number of hashes, and thus such primitives can be implemented on standard hardware. Unfortunately, this approach does not work for primitives like secret sharing, as one would need to efficiently sample the challenge for the sequential computation together with its solution. In this work, we leverage ideas from time-lock puzzles to overcome this issue. We construct secret sharing with snitching and encryption with self-incriminating proofs where reconstruction/decryption is sequential. The security of our scheme relies on a new knowledge assumption, which informally states that whenever parties that hold secret shares of an RSA modulus N=pq jointly compute 2^2^T N for some large T (too large to perform a sequential computation of length T in MPC), then at least one of them must have learned a multiple of N.

We give provable classical subexponential algorithms for secret recovery in growing parameter families associated with NIST third-round lattice candidates. For the Kyber/ML-KEM, FrodoKEM, SABER, NTRU LPRime, and Dilithium/ML-DSA families studied here, polynomial moduli and polylogarithmic coefficient scales yield recovery of the short secret component in expected time and space $2^{(1/2+o(1))n/\ln\ln n}$. For noisy or rounded linear relations, we exploit an exact gap in the squared Euclidean norm of a comparison vector defined by each coordinate guess. One Gaussian list suffices to identify every secret coordinate by binary search, without enumerating the others. We establish the required sampling guarantees through new geometric bounds for structured public operators over prime and power of two moduli. The construction builds on the Wagner-style Gaussian sampling framework of Ducas, Engelberts, and Loyer (CRYPTO 2025) and the low-error decision-LWE algorithm of Han, Gao, and Hu (2026). For quotient relations of NTRU type, we develop an affine slice search: fixing coordinates restricts candidate pairs to slices of the public lattice, and their estimated Gaussian masses guide the choice of each next coordinate. In the stated modulus window, Falcon's key generation quality condition supplies the required mass bound. The algorithm then recovers an equivalent signing key with high probability in time and space $2^{O(n/\ln\ln n)}$. The same search recovers the short key core for cyclic NTRU-HPS/HRSS. Together, these results give subexponential algorithms for problem families associated with all seven NIST third-round lattice candidates. Despite the subexponential complexity, our results do not establish a reduction in the concrete security of the currently specified parameter sets.

Linear correctors reduce the bias of random bits via parity (XOR), but their guarantees are known mostly for independent bits, an assumption violated by many physical entropy sources. We give a general, exact formula for the parity bias of dependent bits from a (hidden, possibly non-homogeneous) Markov chain, as a product of twisted transfer kernels. Under next-bit unpredictability, i.e. conditional bias at most $\beta$, the decay is governed by $\beta$ itself: sharp for a one-bit context, $|\mathrm{bias}|\le\beta^{\lceil n/2\rceil}$, and \emph{near-optimal} for an $m$-bit context, within a factor $3^{1/3}\approx1.44$ of the best possible per-bit rate, which is at least $\beta^{1/(m+1)}$ (attained by a noisy LFSR) and asymptotically equal to it as $\beta\to0$. Against the best previous bound (Zhou and Bruck, ISIT 2011) we \emph{correct the exponent} and \emph{tighten the bound on $n$ bits by a factor of about $2^{\lfloor(n-1)/2\rfloor}/\beta$}, with a matching construction. The decay is non-monotone, so a corrector should be certified at every operating length, or via the envelope $\beta^{\lceil n/2\rceil}$. Finally, bounded memory is necessary: if unpredictability is imposed on the full history, XOR-ing does not reduce the bias at all.

Side-channel attacks can uncover sensitive data by analyzing information leakages of cryptographic hardware devices caused by the power consumption, timing, electromagnetic, glitches, etc. Threshold implementation (TI), introduced by Nikova et al. in 2006, was proposed to resist differential power analysis side-channel attack on hardware implementations of block ciphers and eliminate information leakage due to glitches. For a function of algebraic degree $t\ge 2$, a TI requires at least $t+1$ shares. However, achieving this bound without fresh randomness is challenging, and we refer to such TIs as optimal. While a universal construction using $t+2$ shares is available, attaining the $t+1$ lower bound depends on the target permutation. In this paper, we present four constructions for optimal TIs of bijective S-boxes. We first demonstrate how adjoining identity coordinate functions enables optimal TIs, and then prove that $\mathcal{Q}_{30}^5$ admits optimal TIs. Second, we derive a matrix criterion for a class of quadratic permutations with optimal TIs, which covers all known examples, and can yield new $6$-bit quadratic classes with optimal TIs. Third, we introduce a weighted interpolation construction, which yields power permutations admitting optimal TIs, thereby providing counterexamples to the conjecture by Piccione et al. in 2023 that nonlinear power permutations cannot meet the $t+1$ lower bound. Finally, we present a derivative-uniform framework. Although this construction is not algebraic-degree-preserving for TIs and comes at a high cost of implementation, it is of significant theoretical interest and enables us to prove that every $4$-bit cubic permutation admits optimal TIs.

Motivated by recent constructions and barriers in secret sharing, we study multislice functions. These functions, parametrized by a width parameter $w$, take the value 0 on inputs of Hamming weight below a base value $k$, 1 on inputs of weight above $k+w$, and are monotone in between. We first investigate formulas over multislice gates, which generalize the formulas over slices model (Applebaum et al., TOCT 2026). We prove that, although multislices compute complicated functions, they do not help in computing the worst-case function when $w\ll n$; that is, there is an explicit monotone function such that for every $w$, every formula over multislice gates of width $w$ that computes it, regardless of its depth and gate fan-in, has size $2^{\Omega\left(n/((w+1)\log^2 n)\right)}$. Our lower bound is based on a randomized Karchmer-Wigderson protocol for multislices that can be amortized across the formula. As a complementary result, we show how to realize multislices using slice gates, i.e., multislice gates of width 0; the construction uses a simple peeling recursion. Consequently, every width-$w$ multislice on $n$ variables has a formula over slice gates of size at most $2n^{w+1}$ and depth $(w+1)$. The same construction allows to compute multislices with small monotone real formulas and circuits, two models introduced by Pudl\'ak (J. Symb. Log., 1997) in the context of proof complexity. This result also has an application to secret sharing: it yields, for sufficiently long secrets, multilinear secret-sharing schemes for width-$w$ multislices with maximal information ratio $n^{O(w+1)}$, which is polynomial for every fixed $w$. In addition, we prove that an explicit access structure requires shares of size $2^{\Omega(n)}$ in every secret-sharing scheme from a family of schemes that captures all currently known constructions for general access structures with share size $2^{cn+o(n)}$, for $c<1$. Our proof goes through an exponential lower bound on the size of formulas over so-called CDS gates and ideal linear gates.

Bleichenbacher's 1998 padding oracle attack against RSA PKCS#1 v1.5 has resurfaced repeatedly over the past decades, especially in TLS. Although modern browsers prefer TLS 1.3, many servers and clients still permit RSA key exchange for backward compatibility, enabling active network attackers to decrypt recorded sessions. Still, practical man-in-the-middle attacks remain challenging. The classical attack narrows the plaintext interval from the top down, spending many queries on secret-independent padding bytes before reaching the PreMasterSecret in the low-order 46 bytes of the RSA plaintext. As a result, prior attacks required multiple vulnerable servers in parallel to avoid connection timeouts. In this paper, we present Reverse-Bleichenbacher, a novel variant of the Bleichenbacher algorithm. In contrast to all previous Bleichenbacher-style algorithms, our algorithm recovers the least significant bytes first and terminates the search as soon as the target secret is recovered. When the secret occupies only a fraction of the plaintext, as with the TLS PreMasterSecret, this significantly reduces the number of required queries. Together with improved trimmers and a coverage-optimized search, this reduces the median number of oracle queries from 11.428 to 1801 against a standards-conforming PKCS#1 v1.5 oracle with 2048-bit keys, with an overall success rate of 84.8 %. Crucially, under realistic single-server conditions (a 2.6 ms median round-trip time we observe to vulnerable hosts and 2 round trips per query) 68.3% of all runs finish within a 30s timeout, compared with none of the prior algorithms. To remain feasible at higher latency, we parallelize independent queries: at 20 ms round-trip time, batching reduces the median end-to-end runtime from 59.3s to 8.3s, at the cost of additional queries. We identify 640 vulnerable domains in the Tranco Top 1 Million, many behind Alibaba Cloud load balancers. We demonstrate end-to-end impact on real software distribution channels: a man-in-the-middle attacker can inject malicious updates and achieve remote code execution on a victim device.

Research on cryptographic algorithms implemented in hardware and protected against side-channel attacks has advanced rapidly in recent years. Generalized masking schemes, such as Threshold Implementations (TI) and Domain-Oriented Masking (DOM), currently provide a solid theoretical security foundation. Security models, including the probing model and its various extensions, enable formal verification of these guarantees. In addition, established guidelines for designing securely composable gadgets, along with tools for the automatic generation of masked designs, have further advanced the field. Experimental security assessment approaches, such as the Test Vector Leakage Assessment (TVLA) complement these efforts. Consequently, the primary focus of the research community has shifted toward optimizing existing techniques and bridging the gap between theoretical and practical security models. In this work, we demonstrate a case in which side-channel leakage, caused by glitches, can be concealed during experimental assessment in a setup that is theoretically not robustly secure. This effect arises due to specific patterns of glitch propagation. We investigate whether a particular layout of the complete logic chain can further contribute to a design’s resistance to side-channel attacks, potentially reducing latency and area by relaxing glitch-mitigation requirements, such as reducing the number of pipeline registers. To this end, we introduce new adversarial model which further relaxes the model of Müller and Moradi, introduced at CHES 2024. To illustrate the practical relevance of our proposal, we provide experimental evidence by modifying a well-known, provably secure AES S-box design by De Cnudde, rendering it insecure under the robust probing model. We conduct TVLA of power consumption for both FPGA-based (physical) and ASIC-like (simulation) implementations of our netlists, demonstrating the absence of detectable leakage, similar to the originally robustly secure version of the algorithm.

Large-size Number Theoretic Transforms (NTTs) are key operations in modern Zero-Knowledge Proofs (ZKPs), where the NTT size often reaches millions of points and the arithmetic is over wide prime fields. To handle such NTTs on hardware, prior designs commonly rely on the decomposition algorithm, which makes large-size NTTs feasible by streaming sub-NTTs through limited on-chip buffers. However, in practical implementations, decomposition alone is insufficient to ensure high efficiency. Since coefficients and twiddle factors remain off-chip, performance tends to depend on data movement across the memory hierarchy and delivery to the processing elements (PEs). To address these remaining issues, we present RENTT, a resource-efficient accelerator for large-size NTTs with decomposition-oriented data movement schemes and memory hierarchy design. First, we design a precomputation-based twiddle factor management scheme that feeds multiple PEs without conflicts, both reducing on-chip twiddle factor storage and avoiding on-the-fly twiddle factor generation. Second, we develop a burst-optimized transpose method that fuses coefficient reordering into the element-wise twiddle-multiplication pass, reducing the latency of off-chip accesses for the subsequent NTTs. Third, we design a decoupled, multi-banked on-chip memory hierarchy that sustains high PE utilization under off-chip streaming, while remaining configurable across PE counts and maximum supported NTT sizes. We implement RENTT on an FPGA and experimentally verify that RENTT supports NTT sizes up to $N=2^{28}$ over 256-bit fields and completes a $2^{28}$-point NTT in 1.52 seconds with 16 processing elements. Compared with the state-of-the-art FPGA baseline SAM, RENTT provides $2.64\times$ speedup (1.52s vs. 4.02s), reduces 46.4% DSP usage (3629 vs. 6776 DSPs), and achieves a $3.58\times$ lower area-time product.

In cryptographic algorithms based on groups in which the discrete logarithm is supposed to be hard, it is frequent to perform polynomial arithmetic in the exponent of group elements. This old technique has become a critical operation in many recent advanced protocols, mostly related to commitments and zero-knowledge proofs, where polynomials of high degrees are involved. Number Theoretic Transform (NTT) techniques in the exponent are often implemented to gain speed. However, they require roots of unity to exist in the field GF(q) where q is the order of the group. In this work, we propose algorithms that preserve the quasi-linear complexity of the Fourier Transforms, even when no root of unity are available. For this, we develop a formalism for the algebraic structure of polynomials with coefficients in a group, that allows us to adapt asymptotically fast polynomial multiplication algorithms to the case of arithmetic in the exponent. In particular, we design an algorithm inspired by the Schönhage-Strassen algorithm, which runs about twice slower than NTT but does not require any arithmetic property on the order of the group. We explain how this can be adapted to batched KZG commitment proofs and the Bayer-Groth verifiable mixnet used in e-voting.

The 2019 edition of ITU-T X.509 adds three certificate extensions, colloquially called the Catalyst extensions, that let a single certificate carry a second, alternative public key and issuer signature beside the native ones, as a backwards-compatible path for migrating a public-key infrastructure to post-quantum cryptography (PQC). This paper collects the known problems of this multiple cryptographic algorithms (MCA) mechanism and adds several findings of its own. The central and previously known weakness is that a quantum attacker who recovers a single traditional certification-authority key can replace any certificate in a chain by a traditional-only one that a relying party still accepts. We give a precise attack model with a sub-CA and an end-entity-forgery variant to emphasize the inherent problem and propose three mitigating policies for relying parties which offer different degrees of protection and interoperability. As an example, we verify empirically that the susceptibility to this downgrade attack is present in the wolfSSL cryptographic library as a natural consequence. Our further findings concern the construction itself and details of the specification. For one, we analyze the formal violations of EUF-CMA that arise due to the possibility of re-purposing the extension signature to the established signed data format in X.509, which is formally manifest as soon as the alternative key in the extension is also certified as a native key. We show that several further aspects in the ITU-T mechanism remain undefined, which potentially leads to divergent behaviour of clients, and point out that a certificate accepted on its alternative signature alone, as allowed per ITU-T specification, can be invalid under RFC~5280 and potentially exposes an application to arbitrary injected data and even modified signatures chaining it to a certificate chosen by a non-quantum attacker in the positively validated certificate chain.

Fully Homomorphic Encryption for RAM programs (RAM-FHE), introduced by Hamlin, Holmgren, Weiss, and Wichs (Crypto 2019), allows a server to evaluate a RAM program on encrypted data at a per-step cost sublinear in the memory size $N$, whereas standard FHE must read the entire memory for every memory access. In a celebrated work, Lin, Mook, and Wichs (STOC 2023) gave the first, and to date the only, construction from a concrete assumption, namely Ring-LWE. In this work, we construct a RAM-FHE scheme from plain LWE that evaluates each step of a RAM program in $o(N/\log N)$ time. While the scheme is barely sublinear, even such a slight saving over the linear cost of standard FHE was not known to be achievable from unstructured, plain LWE. As Lin, Mook, and Wichs did, we build RAM-FHE by extending a Doubly-Efficient Private Information Retrieval (DEPIR) scheme. Since the only DEPIR from plain LWE, due to Lee (Crypto 2026), relies on a Common Reference String (CRS) that is incompatible with the extension, we show how to remove the CRS and obtain a DEPIR from plain LWE in the standard model, which may be of independent interest.

In a widely publicized recent announcement, Google established a formal 2029 deadline for completing its post-quantum cryptography (PQC) migration---one that deliberately preempts the 2035 deadline set by NIST and the US federal government to complete the deprecation of classical public-key algorithms. Google cited faster-than-expected progress across three fronts: quantum computing hardware development; quantum error correction; and revised estimates of the resources required for quantum computers to break current cryptographic schemes; as motivation for setting an ambitious internal target ahead of the regulatory horizon. This tightened deadline places particular pressure on existing cryptographic protocols that rely on classical key exchange primitives for secure communication. Our work aims to ease this transition by constructing a unified, formally analyzed security framework for migrating classical key exchange constructions to their post-quantum counterparts.

The distinguishing variant $\Delta$LIP of the Lattice Isomorphism Problem underlies the security proofs of a growing family of lattice-based schemes. As the special genus is the strongest efficiently computable invariant of a lattice, such a proof may replace the lattice used by the scheme with a random lattice of the same genus. This raises the question of how hard lattice problems actually are on such random lattices. We answer it, under GRH, with a worst-case to average-case reduction inside any special genus $\mathcal{G}$ of Hermitian lattices of fixed rank $r \geq 2$ over a cyclotomic field $K$ of degree $d$: for each of $\mathrm{(H)SVP}$, $\mathrm{HCVP}$, $(\Delta)\mathrm{BDD}$, $\mathrm{DSP}$ and $\mathrm{DGS}$, solving the problem on a random class of $\mathcal{G}$, drawn from its natural distribution, is as hard as solving it on the worst-case lattice of $\mathcal{G}$, at the cost of a factor $p = \mathrm{poly}(d) \cdot {\det}_{\mathbb{Q}}(\Lambda)^{O_r(1)/d}$ in the approximation factor. The reduction is a random walk on the Kneser $\mathfrak{p}$-neighbour graph of $\mathcal{G}$: neighbours stay close enough to transfer problem instances, while the walk equidistributes quickly, a fact we deduce from spectral bounds for the associated Hecke operators. As an application we give a direct and tight security proof for a minimal LIP-based KEM, resting on two independent assumptions: that the lattice it uses is indistinguishable from a random lattice of its genus, and that $\Delta$BDD is hard on that genus. Unlike existing LIP-based proofs, this requires neither an ad-hoc lattice of the form $q\Lambda \oplus (q+1)\Lambda$, nor the tightness loss caused by the dense sublattice such proofs rely on.

Succinct proofs for arithmetic modulo powers of two are crucial for verifying machine-word computations in practice. However, designing SNARKs over such rings is challenging, since they lack the algebraic properties that common SNARKs over fields rely on to achieve negligible soundness error. Existing approaches either work over Galois rings, whose arithmetic is expensive, or lift the statement to the integers and prove it over a large random prime field, which is also several times slower than the structured primes used in practice. We present $\mathsf{Rotor}$, an efficient SNARK for circuits over $\mathbb Z_{2^k}$. Unlike prior work, $\mathsf{Rotor}$ operates natively over power-of-two rings and derives its soundness from three levels of ring precision. To prove statements over $\mathbb Z_{2^k}$, we first construct a sumcheck-style interactive oracle proof with tensor queries over a larger ring $\mathbb Z_{2^m}$. We then establish a weakened proximity gap for linear codes, in which proximity testing over a still larger ring $\mathbb Z_{2^\ell}$ ensures that the underlying vectors are close to the code after reduction to $\mathbb Z_{2^m}$. This yields a Brakedown-style commitment with tensor evaluation proofs over $\mathbb Z_{2^m}$. In both cases, a sufficiently large gap between the precisions guarantees negligible soundness error. Finally, we introduce compatible commitments, which link ring witnesses to their binary-field representations and enable permutation checks over fields to verify permutations over $\mathbb Z_{2^k}$, completing the construction of $\mathsf{Rotor}$.

Secure multiparty computation (MPC) allows a set of parties to jointly compute a function while keeping their inputs private. Classical MPC protocols assume either a synchronous or an asynchronous network. Synchronous protocols tolerate more corrupted parties but rely on a timing bound, while asynchronous protocols make no timing assumptions but handle fewer corruptions. The network-agnostic model aims to combine the advantages of both. It requires security without knowing in advance whether the network is synchronous or asynchronous, guaranteeing resilience against up to $t_s$ corruptions in the synchronous case and $t_a$ corruptions in the asynchronous case. The optimal corruption threshold for perfect security has been established as $n = 2\max(t_s, t_a) + \max(2t_a, t_s) + 1$, but prior work either falls short of this threshold or requires exponential local computation. In this work, we present the first perfectly secure network-agnostic MPC protocol with polynomial communication and computation complexity under the optimal threshold. Our protocol achieves expected communication complexity $\mathcal{O}((|C|n + (D+C_I)n^2 + n^6)\log n)$ bits for a circuit of size $|C|$ over a finite field $\mathbb{F}$ of size $\mathcal{O}(n)$, depth $D$, and input size $C_I$. Our main technical contribution is a compiler that generates Beaver triples in the network-agnostic setting using synchronous and asynchronous triple-generation protocols in a black-box way. Beyond the cost of the underlying protocols, it only requires $\mathcal{O}(n^2)$ instances of network-agnostic Byzantine agreement.

We present KIFA (Kernel-based Integral Fault Analysis), an integral fault attack framework that mines its balanced properties with the kernel-based miner of Hwang et al. in place of Mixed Integer Linear Programming (MILP). The miner handles only small input structures fixed in advance, and a fault model provides exactly such structures. For DEFAULT, we present attacks at fault penetration (FP) $9$ under a random-position nibble fault and FP $10$ under a random-position byte fault, beyond the prior best integral fault attack at FP $8$. They leave a single master-key candidate under the simple key schedule and reduce the key space to $2^{64}$ under the rotating key schedule. For GIFT-128, we present the first integral fault attacks, at FP $7$ and $8$, against the prior best of $5$. For GIFT-64, we extend the prior best FP $6$ to $7$ with a byte fault, leaving $2^{32}$ master-key candidates. For BAKSHEESH, we extend the prior best FP $7$ to $8$, also when the fault position is uncontrolled.

In reaction to the emerging quantum threat, the National Institute of Standards and Technology (NIST) seeks post-quantum secure digital signature schemes. NIST's ongoing competition recently advanced to the third round, in which the Unbalanced Oil and Vinegar scheme (UOV) is a promising candidate due to UOV's conservative design, small signatures, and performant signing and verification. While these benefits make UOV attractive, the implementation aspects for compact hardware acceleration of UOV remain underexplored. Existing hardware accelerators optimize for performance and have large memory footprints. Yet, constrained devices require compact and low-memory hardware support. At the same time, lowering the memory consumption of UOV without sacrificing performance is challenging due to UOV's large public keys and intermediate results. In addition, low-end devices are prone to power side-channel attacks and benefit from lightweight countermeasures. In this work, we focus on the open challenges of compact UOV hardware acceleration. We design a low-memory UOV architecture with runtime-flexible support of NIST security levels 1 to 5. Our architecture uses a load-balanced 16-lane datapath supporting the critical matrix operations of UOV. In addition, we lower UOV's peak memory consumption using a slicing technique and enable on-the-fly data generation via streamlined data realignment. We also include a pipelined Gaussian Elimination unit and a streaming approach for the large public keys needed for signature verification. In addition to compact hardware acceleration, we defend against differential power analysis attacks through a lightweight blinding countermeasure relying on UOV's equivalent keys. Our blinding requires random non-singular matrices, which are not trivial to sample efficiently in hardware. We therefore assess existing sampling approaches and propose a novel technique based on the lower-upper decomposition of matrices. The resulting blinding solely re-uses existing datapath components and limits the runtime overhead to less than 30%. Compared to existing UOV accelerators, our efficient FPGA design reaches up to 5.1x lower signing and 3.2x lower verification latency, while reducing the memory consumption between 2.2x and 16x.

ECLIPSE is the prime-degree signature construction the PRISM authors describe beside their salted scheme, with that salt, implemented. It exists because a two-dimensional isogeny signature carries an auxiliary isogeny the hash does not bind: the SQIsign round-3 specification says SQIsign cannot be strongly unforgeable for that reason, and PRISM's prime-degree variant has no auxiliary isogeny but was published without parameters, code or a running verifier. This paper is the first implementation, on the SQIsign round-3 primes: a verifier that evaluates the paper's criterion through one isogeny chain and a pull-back, a canonical wire format whose strict decoder recovers one coefficient from two Weil pairings, randomisable keys, two independent implementations that accept each other's signatures, and one key in both roles: a MIKE key pair at the level I prime is an ECLIPSE key pair, the public curve re-encoded and the signing key derived from the MIKE secret alone, with MIKE's code untouched. The only post-quantum precedent is CSIDH with CSI-FiSh, a group action; this is the first shared key in the SQIsign family. Signatures are 206 bytes at NIST level I, within 15 bytes of SQIsign at every matched state. In one session against the SQIsign reference's assembly build, signing is 2.6 times faster and verification costs twice as much, 1.6 times with the public key prepared once. A formal strong-unforgeability (SUF-CMA) argument is left to future work.

Private Set Intersection (PSI) allows two mutually distrusting parties to compute the intersection of their sets without revealing any additional information and has found numerous applications. The approximate matching required by various applications has led to the development of Fuzzy PSI (FPSI), a variant of PSI that identifies approximate intersection elements under a public distance threshold \(\delta\). Reducing computation and communication costs remains an important challenge for FPSI. In this paper, we present a new FPSI protocol, called Mercury, which achieves logarithmic computation and communication complexity with respect to threshold \(\delta\). Our protocol exploits the correlation of the intersection and the point pairs held by the parties, and efficiently identifies the neighboring point pairs by a mixed protocol from homomorphic encryption and secure two-party computation using a "mask-then-compare" technique. We implemented Mercury and evaluated both its sender-private and standard FPSI variants. For balanced two-dimensional inputs, Mercury-SP achieves \(9.0\sim63.9\times\) runtime speedups and reduces communication by a factor of \(8.7\sim26.1\) across the evaluated thresholds and set sizes in the LAN setting, compared to the FPSI protocol by Dang et al. (CCS'25). In the completed unbalanced experiments, Mercury-SP achieves \(55.7\sim132.4\times\) WAN runtime speedups compared to the FPSI protocol by Piske et al. (CCS'25).

The Universal Composability (UC) framework provides a paradigm for security definitions that allows for arbitrary composition, but has been criticized for being unamicable to the concrete security approach, as the meaning of a concrete UC-security statement is hard to interpret in practice. This work aims at alleviating this concern in the context of Password-Authenticated Key Exchange (PAKE): we show that any concrete UC-security statement for PAKE can be easily converted to a concrete game-based security statement, whose real-life meaning is clearer. We also briefly discuss potential generalizations of our result to other cryptographic primitives.

Timed cryptography captures computations that inherently require a prescribed amount of time, even in the presence of parallelism, and has emerged as a central notion due to its broad applications in both practice and theory. A natural question is how timed cryptographic primitives relate to traditional cryptography, in particular to primitives in Minicrypt. Guan and Montgomery (CRYPTO 2024) show that sequential functions do not imply one-way functions (OWFs) via black-box reductions. Their result, however, leaves open whether adding public verifiability (a substantially stronger requirement) suffices to imply OWFs. We study this question via verifiable delay functions (VDFs), which require substantial sequential time to evaluate, yet produce a unique output that is efficiently and publicly verifiable. We show that VDFs do not imply OWFs via fully black-box, relativizing reductions. Combined with prior results showing that VDFs cannot be constructed in the random oracle model, this establishes that there is no black-box implication in either direction between VDFs and OWFs. Our proof develops a new oracle separation technique that combines the random oracle with a carefully designed complexity-theoretic oracle inspired by Kolmogorov complexity.

As zero-knowledge proofs are used in real-world systems, they face threats such as resetting attacks, where an attacker manipulates the prover's randomness. While resettable security has been studied for interactive protocols, whether modern non-interactive systems such as zkSNARKs remain secure under resets is still unclear. This work provides the first systematic study of resettable security for NIZK arguments with three main contributions: - New Definition: We define strong resettable NIZK (srNIZK), which captures adversaries that can selectively reset the prover's randomness, so that some parts are reused while others are generated afresh. This goes beyond the whole-tape resets considered in standard rZK and is motivated by fault injection on secure hardware and incomplete state restoration in virtualized environments. - Concrete Attacks: We demonstrate that widely used NIZK constructions are vulnerable to resetting attacks. We show witness-recovery attacks against (i) Fiat-Shamir-compiled $\Sigma$-protocols (e.g., Schnorr), (ii) succinct proof systems using independently sampled masks (e.g., PLONK and Bulletproofs), and (iii) salted Fiat-Shamir compilations of a broad class of interactive arguments. - Generic Defense: Our simple compiler transforms any NIZK into an srNIZK by modifying only randomness generation, using a pseudorandom function (PRF) secure under partial key resets. This prevents resetting attacks without changing proof size or verification. Our results demonstrate that resetting attacks must be considered in NIZK systems, and provide a simple defense with minor prover overhead.

Vector search on untrusted infrastructure exposes the \emph{query embedding}, a faithful summary of the user's intent. Fully homomorphic encryption can hide the query, but existing approaches still require a full scan followed by ranking of encrypted scores. Scalable private systems avoid encrypted ranking by either sending scores from a single cluster to the client or moving the search to the client, which must first stream the entire vector index for preprocessing. We present Carousel, which instead scores the full corpus under encryption and compresses the results for client-side ranking. The server scores every vector under encryption, raises the scores to a power that preserves their order by magnitude while suppressing all but a handful, and compresses the resulting sparse vector into a logarithmic number of ciphertexts using homomorphic additions alone. Because every vector is scored, Carousel incurs no recall loss from discarding candidates. Since clients hold no database-dependent state, insertions and deletions take effect immediately at the cost of a single vector write. Carousel searches $1$ billion vectors of BIGANN SIFT1B across multiple GPUs and achieves recall@100 of $0.9715$. At $100$ million SIFT vectors, it achieves recall@100 of $0.9845$ with a query latency of $3.735$ seconds on a single GPU.

A long-standing hypothesis in artificial intelligence and neuroscience posits that intelligence is closely related to compression: the ability to compress information efficiently intuitively reflects capacities associated with intelligence and learning. Indeed, recent experimental works verify this intuition by showing connections between the capabilities of large language models (LLMs) and their ability as compressors: for instance, Deletang et al. (ICLR'24) demonstrate that LLMs can be used as powerful compressors, and Huang et al. (COLM'24) show that the compression ability of LLMs is highly correlated with their performance on benchmarks for knowledge and reasoning. In this work, we initiate a theoretical study of this connection. Our main result is that LLMs (formally modeled as next-token predictors) are equivalent to monotone (a.k.a. order-preserving) compression algorithms---namely, compression algorithms where the encoding process preserves the ordering of the inputs---in the sense that the one can be constructed from the other while preserving the same error up to an additive gap of 2. We next show that the monotonicity is required for this equivalence to hold if and only if cryptographic (infinitely-often) one-way functions exist. As a direct corollary, we get a cryptographic result of independent interest: the notion of next-bit pseudoentropy (a computational analogue of entropy) of a distribution is equivalent to monotone incompressibility of the distribution. (Previously, it was only known (Haitner et al., ITCS'23) that incompressibility implies next-bit pseudoentropy.)

We present a polynomial-time quantum algorithm for the Dihedral Coset Problem (DCP). The algorithm is based on Regev's polynomial-time reduction of the Dihedral Subgroup Problem (DSP) to the modular subset sum problem, but uses a different technique to erase sample bits without use of a subset sum oracle. The algorithm can thus combine with Regev's reduction of lattice problems to DCP, improved by Brakerski, Kirshanova, Stehl{\'e} and Wen, to yield polynomial-time quantum algorithms for various lattice problems, such as finding a polynomial-factor approximation to the shortest vector in an $n$-dimensional lattice (SVP), and the ``learning with errors'' problem (LWE). The algorithm can tolerate a faulty sample rate as high as $1/O(\log{n})$, allowing the algorithm-reduction combination to efficiently solve, for example, SVP with a $\sqrt{n}$ polylog($n$) approximation factor, or LWE instances with $\alpha=\sqrt{n}$ polylog($n$). Note: The proof of Lemma 3 in the first draft incorrectly conflated pairwise independence over the uniform vs. actual distribution on D. The proof has been substantially updated, and now distinguishes clearly between them. Additional note: A new preprint, https://eprint.iacr.org/2026/1693, has been posted claiming to prove that the algorithm in this paper can't possibly work. We're in the process of evaluating it. Additional note October 7/26: The preprint has been updated with a note addressing the claims in https://eprint.iacr.org/2026/1693, as well as clarifications to the proof of Lemma 3 in response to comments by Sam Jaques.

Many recent constructions of probabilistic proofs achieve fast proving times but have high space complexity (much higher than that of the computation being proved). Empirically this arises due to the fact that error-correcting codes, a key ingredient of such constructions, suffer from limiting time-space tradeoffs. It remained open, however, whether such time-space tradeoffs exist for proofs themselves. We establish time-space tradeoffs for probabilistically checkable proofs (PCPs) as well as for their multi-round extension, interactive oracle proofs (IOPs), with straightline knowledge soundness. Our results hold for machine computations that have sequential input access, the same model for which similar tradeoffs hold for error-correcting codes. We complement this result by describing an IOP for R1CS that avoids the tradeoff but requires random access to the R1CS witness. Our techniques build on and extend results for codes of Cook and Moshkovitz (CCC~2024). A key difficulty that we encounter in establishing our tradeoff is that distance of the code plays a key role in prior results, while for probabilistic proofs there is no natural notion of distance. Nevertheless, we show that, assuming the existence of collision-resistant hash functions, we can establish time-space tradeoffs by carefully relating a small-space machine's information flow to the proof system's properties.

We present two key-recovery attacks against subcodes of generalized Reed–Solomon codes, including alternant and Goppa codes, extending the distinguisher recently introduced by Ghoshal, Ishai, Jain, and Sun. Both attacks recover the full secret key from a single run of the distinguisher. Because the public columns are evaluations of secret polynomials, they lie (up to scaling) on a hidden algebraic curve. The distinguisher holds out one column and finds polynomials vanishing with high multiplicity at the remaining columns, which forces them to vanish identically along the entire curve. From these polynomials, we recover the local geometry of the curve at the held-out column. Two finishing routes then turn the local geometry into the key. In the first route, a bootstrapping step uses this local geometry to recover the tangent planes of the curve at all public columns. From these planes, we construct a minor code, which heuristically turns out to be a full GRS code with the same hidden support, allowing the standard Sidelnikov–Shestakov attack to recover it. Based on a similar idea, the second route uses the local geometry to find two quadratic forms whose ratio at the public columns directly gives an equivalent support. After recovering the support, both routes end by reconstructing the full key, including the support elements removed by any preliminary shortening. We implemented both routes and recovered the secret keys of the TII McEliece challenges TII-173, TII-249, and TII-253, the first two of which had not been solved before, to our knowledge. We also succesfully tested the attacks on randomly generated binary Goppa codes, wild Goppa codes, alternant codes, and GRS subcodes. Under the stated rank and solver assumptions, the whole key recovery costs essentially one run of the distinguisher. In particulat, for Classic McEliece parameters, we estimate this cost at $2^{89.9}$ to $2^{98.6}$ bit operations.

We design a novel robust secret-sharing scheme in the honest-majority setting for $n$ parties that allows constant communication per opening per party when amortized over $\Theta(n)$ simultaneous openings. We attain this scheme by a novel application of list decoding of folded Reed-Solomon codes. This was stated as an open problem by Escudero and Fehr (2023), who could obtain this amortized complexity only for $\Theta(n^2)$ simultaneous openings. Additionally, the dealing of such shares for a random value in a finite field $\mathbb{F}$ can itself be done using an honest-majority MPC protocol using only $O(n^2)$ multiplications between Shamir-shared values. This allows us to build an offline-online fully-secure (GOD) honest-majority MPC protocol, which has a fast online stage with amortized communication cost only $O(n)$ per multiplication gate (assuming the circuit has width $\Omega(n)$) and with no additional overhead, and an offline preprocessing stage with incremental communication cost only $O(n^3)$ per multiplication gate. This improves the previous best protocol in this setting by Escudero and Fehr (2023), which required the circuit to have width $\Omega(n^2)$. Further, the earlier scheme had an incremental preprocessing cost of $O(n^4)$ per multiplication gate. Due to requiring non-responsive rounds, the online stage of these protocols may still be concretely far less efficient than the online stage of the offline-online BGW protocol. Since the BGW protocol only provides security against fewer than $n/3$ malicious parties, we also devise a novel MPC protocol that boosts the BGW protocol's correctness threshold to $n/2$, while maintaining privacy and robustness thresholds at $n/3$, and with minimal online overhead. This is useful in applications, such as elections and auctions, where certification of a correct result is paramount. To achieve this correctness against fewer than $n/2$ malicious parties and to keep the pre-processing cost low, we use our novel robust honest-majority secret-sharing scheme, but only once during a final SPDZ-style attestation.

Dynamic group signatures are commonly formalized in the model of Bellare, Shi, and Zhang (BSZ, CT-RSA 2005), whose security notions are defined relative to specific trust assumptions and registration state. We revisit these assumptions and systematically study which guarantees continue to hold when the trust assumptions on the issuer and opener are considered independently and no trusted registration structure is shared between them. In particular, we show that the meaning of traceability changes substantially in such settings. With a malicious issuer and an honest opener, the natural analogue of traceability only ensures that every valid signature admits an accepted opening; it does not ensure that the resulting identity obtained its membership through a valid join. With a malicious opener, classical accountability guarantees likewise fail to enforce this connection to group membership. We demonstrate this by constructing a scheme satisfying the BSZ-style security notions in which a malicious opener can produce valid signatures that are not associated with any membership established through the join algorithm, even though the issuer is honest. To capture the missing relations between joining, signing, and opening, we introduce three unforgeability-type properties. Certificate-unforgeability binds valid signatures to issued membership certificates. Key-unforgeability requires signature generation to rely on a corresponding member signing key. Opening-unforgeability prevents accepted openings to identities for which no membership was issued. We prove that these properties are logically independent and give a construction satisfying the classical and additional guarantees under mild assumptions. Our results identify precisely which aspects of accountability follow from trusted issuers, trusted openers, or shared registration state, and which must be required explicitly once these assumptions are removed.

Inner-product functional encryption (IPFE) allows the holder of a functional key for a vector $y$ to learn $\langle x,y\rangle$ from an encryption of $x$, and nothing more. Keys, however, accumulate: a coalition holding sufficiently many independent keys recovers the plaintext. We model each institution by the span $W_i\leq\F_q^n$ of its authorized key vectors and show that a coalition $I$ determines the plaintext exactly modulo $(\sum_{i\in I}W_i)^\perp$; for a uniform plaintext it learns exactly $\dim\sum_{i\in I}W_i$ field symbols. The resulting leakage function is a representable and entropic polymatroid. We then study authorization spaces of dimension $r$ whose pairwise intersections have dimension at most $h$. We prove that some coalition of size $c\geq2$ always learns at least $\min\{n,2r-h+c-2\}$ dimensions, and we give a Vandermonde-type construction in which every coalition of size $c$ learns exactly this amount, for all $c$ simultaneously. Hence the largest achievable reconstruction threshold is $n-2r+h+2$, which gives an exact tradeoff between functional diversity and collusion resistance. The optimal configuration is a sunflower, an equidistant subspace code and a generalized arc; its orthogonal complements form a generalized dual arc, and for $r=1$ it reduces to Reed--Solomon secret sharing.

While decentralized identity management systems strive for autonomy, most still rely on centralized mechanisms (e.g., phone numbers or government-issued IDs) to achieve Sybil resistance and prevent fake identity attacks. This article proposes a novel approach for decentralized identity management that ensures robust Sybil resistance, unlike the systems currently in widespread use. Our approach is based on a social graph of connected users. The main novelty resides in pairwise mutual facial biometric verification for connected users and anti-Sybil social graph analysis. By leveraging blockchain technology, zero-knowledge proofs, and privacy-preserving smart contract platforms, the system ensures the uniqueness, anonymity, and privacy of registered users without relying on centralized authorities. We implemented a proof-of-concept prototype of our approach using fast Plonky2 zero-knowledge proofs and evaluated its functionality through simulations on heterogeneous social graph models with 1000 entities. To the best of our knowledge, this is the first work to propose a Sybil-resistant identity system that neither sacrifices decentralization nor privacy and does not rely on any centralized credential issuers.

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.

Fully Homomorphic Encryption (FHE) enables one to implement low-round and low-communication complexity Multi-Party Computation (MPC) which is secure in the static malicious corruption model. By expanding on an idea presented in the full version of the FHE-based MPC protocol of Smart (IMA, 2023), we show how to completely remove the need for Zero-Knowledge Proofs-of-Knowledge in that protocol. This simplification makes the final security proof of the MPC protocol much simpler, and more modular. The new protocol makes use of an FHE scheme with an encrypted PRF functionality, and in addition to our main result we formalize the security of such encrypted PRFs and prove the construction of Deo et al. (CCS 2025) secure in this model.

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.

Lattice agreement is a relaxed version of the standard consensus problem: correct processes need not decide the same value, but their decisions must be ``comparable''. Namely, every process proposes a value from a join semi-lattice, and correct processes decide values that (1) lie on a single chain, (2) include their own proposals, and (3) include nothing beyond what was proposed. Lattice agreement has important practical applications, as it underpins atomic snapshot objects and replicated state machines with commutative operations. Yet, the best known protocols decide in $O(\log f)$ rounds, where $f$ is an upper bound on the number of faulty processes. In this paper, we break the logarithmic barrier. Namely, we present Join-IT, a synchronous Byzantine lattice agreement protocol that tolerates $f < n/3$ Byzantine processes and decides in $O\big( \frac{\log f}{\log \log f} \big)$ rounds. Join-IT uses no cryptography whatsoever, and its guarantees thus hold against a computationally unbounded adversary. Perhaps surprisingly, Join-IT is also remarkably simple. It sequentially composes two classical primitives: gradecast, which takes three rounds, and approximate agreement, which, at the precision Join-IT requires, takes $O\big( \frac{\log f}{\log \log f} \big)$ rounds. A single local step finally turns the output of approximate agreement into comparable decisions, at no additional cost in rounds.

We study the Batch Learning Parity with Noise (LPN) variant, where the oracle returns $k$ samples in a batch and draws the noise vector from a joint noise distribution $\mathcal{D}$ over $\mathbb{F}_2^k$ instead of from an i.i.d. product distribution. This model captures a broad range of correlated or structured noise patterns studied in cryptography and learning theory. Consequently, understanding which dependent-noise distributions preserve the hardness of LPN has become an important question. On the hardness side, we design several reductions from standard LPN to Batch LPN. Our reductions identify broader classes of noise distributions $\mathcal{D}$ that preserve LPN hardness, extending the prior hardness results of Golowich, Moitra, and Rohatgi (FOCS 2024). We show hardness in three regimes: 1. If $\mathcal{D}$ satisfies a mild Fourier-analytic condition $\sum_{\mathbf{s}\neq \mathbf0}|\widehat{P}_{\mathcal{D}}(\mathbf{s})|\le 2\varepsilon$, then Batch LPN is as hard as standard LPN with noise rate $1/2-\varepsilon$; 2. If $\mathcal{D}$ is $\Omega(\eta \cdot k 2^{-k})$-dense (i.e., every error pattern occurs with probability at least $\Omega(\eta \cdot k 2^{-k})$) for $\eta < 1/k$, then Batch LPN is as hard as standard LPN with noise rate $\eta$; 3. If $\mathcal{D}$ is a $\delta$-Santha--Vazirani source, then Batch LPN is as hard as standard LPN with noise rate $1/2-\varepsilon$ whenever $\delta\le O(2^{-k/2}\varepsilon)$, improving the previous $O(2^{-k}\varepsilon)$ dependence (in Golowich et al.). On the algorithmic side, we extend Arora and Ge's (ICALP 2011) linearization attack to show that Batch LPN can be solved when the noise distribution assigns sufficiently small probability to at least one point, complementing our second hardness result. We also observe that a nontrivial Fourier coefficient with magnitude close to one yields a simple reduction to low-noise LPN, giving an algorithmic counterpart to our first hardness result. Our reductions are based on random affine transformations and are analyzed through the lens of Fourier analysis, providing a general framework for studying dependent-noise LPN variants.

Hair and Sahai have recently proposed a construction of witness encryption for NP satisfying semantic security. In this short note we observe that this recent witness-encryption construction is unconditionally extractable in the generic group model. This yields a construction of extractable witness encryption without assuming subexponential soundness of SNARGs, in contrast to the recent work of Jin (eprint:2026/2063), which requires this assumption. The result in this note, moreover, complements the concurrent work of Chen and Vaikuntanathan (eprint:2026/2346), who show the same construction to be public-coin extractable under a knowledge-style assumption; our argument is unconditional, but in the GGM.

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.

Anonymity guarantees of privacy-oriented cryptocurrencies are garnering negative attention from lawmakers who view them as antinomic to accountability. Having recognized their potential for innovation, however, regulators may not want to outright ban privacy coins but instead seek a middle ground where financial oversight is effective, and still some privacy is maintained. Mature designs, such as Zcash, Monero, or Firo, are expected to facilitate this through so-called viewing keys that can be disclosed to third parties for the purpose of supervision. This paper studies which privacy guarantees continue to hold once they have been. In doing so, it fills the gap in provable anonymity guarantees for Zcash and Firo under the compromise of the incoming viewing key, but nevertheless shows that malicious parties may happily surrender all their viewing keys and still find very efficient ways of evading financial monitoring. Of independent interest are several shortcomings identified in the prevailing security arguments for Monero.

Deniable secret sharing (DSS; Canetti et al, TCC 2025) is designed for a scenario where an adversary is able to bribe or coerce all shareholders to divulge their shares of a secret. A deniable secret sharing scheme is equipped with a faking function that enables shareholders to produce fake shares that look like real shares, but do not actually reveal any additional information about the secret. Existing DSS constructions require the fakers to jointly compute on their shares, without considering how this computation might be realized. In this paper, we investigate two crucial properties of such computations: the extent to which the fakers themselves learn information about the secret (privacy against fakers), and the number of messages they need to exchange (message complexity). Message complexity can be seen as a measure of faking conspicuousness, if the adversary is able to observe network traffic. We prove that to obtain the strongest notion of DSS, any information-theoretic construction requires the fakers to exchange a non-zero number of messages, which could be large (depending on the access structure). We describe a general construction that matches this lower bound in many cases, e.g. for threshold access structures. Furthermore, for linear secret sharing schemes, we prove that certain unqualified sets must learn the secret as a result of faking. Moving to the computational setting, we describe two constructions which require no interaction beyond the knowledge of who the fakers are. This implies that both inconspicuousness and privacy against fakers are achieved. The first construction requires the share size to be exponential in the number of shareholders, but assumes only a PRG. The second construction has small shares, but assumes virtual black-box obfuscation. We see the latter construction as a stepping stone for a future iO-based instantiation. All of our lower bounds and constructions consider general access structures.

Oblivious RAM (ORAM) is a powerful cryptographic primitive that hides both the contents of outsourced data and the access pattern to the data. However, it offers only a restrictive array-based interface. A principal obstacle to its deployment is building an efficient oblivious dictionary upon it. To build such a dictionary, the state-of-the-art layers an oblivious AVL tree over ORAM, avoids an expensive local position map, but forces every operation to traverse a full root-to-leaf path, costing $\Theta(\log n)$ ORAM accesses. We show this trade-off to be suboptimal, particularly when deployed in a common setup within a trusted execution environment like SGX. There, a small amount of client memory can reduce the position map recursion depth to three levels or less, rendering its overhead relatively small. With low position map cost, probabilistic hash tables prevail as dictionary data structures due to their small, constant number of accesses compared to $\Theta(\log n)$ path traversal of a tree. We implement and analyze oblivious, probabilistic hash tables over Path ORAM, including several different strategies: chaining, power-of-two-choices, stash-less cuckoo, and de-amortized cuckoo hashing. Execution of these algorithms within a secure enclave requires "double obliviousness", which in turn needs strict concrete maximum cost limits for each access that current literature does not provide. We derive these concrete padding parameters bounding the hash table rebuild probability to $\le 2^{-40}$ via large-scale simulation. In an SGX deployment, our constructions outperform oblivious trees by up to $20\times$ for $\mathsf{lookup}$s and $12\times$ for $\mathsf{insert}$s.

Attribute-based credentials (ABCs) enable privacy-preserving authentication by allowing users to prove statements about certified attributes without revealing unnecessary information. However, while ABCs hide undisclosed attributes, the credential verification process inherently reveals the issuer's identity, which can leak contextual information such as a user's nationality or residency. Issuer-hiding ABCs address this by concealing the issuer during verification, but introduce a critical accountability problem: if an issuer is compromised or acts maliciously, previously accepted presentations originating from that issuer cannot be singled out without significant privacy violation and high burden on the central authority performing the inspection. We propose an issuer-inspection mechanism that enables retrospective attribution while preserving privacy. An inspection authority can release keys allowing verifiers to locally identify presentations originating from a specific compromised issuer and a defined time period, without affecting other issuers or earlier time periods. Concretely, we formalize the syntax and security requirements of issuer inspection and provide a generic construction from standard cryptographic building blocks; we further present a concrete pairing-based instantiation using Groth's randomizable structure-preserving signatures, Schnorr-style proofs and an adaptation of Gentry's anonymous identity-based encryption. Our analysis of computational and communication costs indicates that the proposed functionality remains practical for realistic parameter choices.

The complexity of many algebraic algorithms for solving non-linear polynomial systems of equations over finite fields, such as the XL (eXtended Linearization) algorithm or variants of the F4/F5 algorithms, is directly determined by the so called degree of regularity. In essence, we can form the Macaulay matrix at this degree, which can be thought of as the linearization of monomial multiples of the polynomials from the problem instance, and then solve the obtained linear system. The degree of regularity guarantees we can solve the system, however, it is a rather coarse parameter. This means that, sometimes, in order to provably show that we achieve overdeterminess, we end up with a heavily overdetermined Macaulay matrix which unnecessarily increases the computational cost. To reduce this coarseness, and thus avoid the unnecessary computational cost, we propose a technique for ``smoothing'' the degree of regularity that can be seen as operating at a degree in-between two integer values. Instead of the full Macaulay matrix, we consider specific submatrices that we show are sufficient to solve the given system. Under a mild assumption that generalizes the notion of semi-regularity, which we experimentally verify for a range of parameters, we show that our approach smooths the complexity of XL for the MQ (Multivariate Quadratic) problem. Finally, we apply our results to a recent UOV attack and demonstrate improvement of a few bits.

Falcon, a lattice-based signature scheme selected for NIST post-quantum standardization, is notable for its compact signature size alongside a complex signing procedure involving extensive floating-point arithmetic. Prior side-channel attacks on Falcon signing, while demonstrating vulnerabilities, have consistently required a large number of power traces for successful key recovery, which limits their real-world practicality. This paper presents a new single-trace attack on the Falcon signing procedure. We exploit side-channel leakage in the FP conversion and identify additional leakage in the FP multiplication at the first layer of the Fast Fourier Transform (FFT) during secret key expansion. By combining these leakages, we progressively partition the secret-key coefficients and establish a linear system to recover the entire key. Our attack is particularly devastating for the \texttt{sign\_dyn} design---the memory-efficient implementation widely adopted in cryptographic libraries---which executes key expansion during every signature operation. We validate our attack on an ARM Cortex-M4 microcontroller, achieving a 100\% key recovery success rate with just one power trace for Falcon-512 across the baseline \texttt{-O0}, size-optimized \texttt{-Os}, and highest \texttt{-O3} compilation levels of the PQClean implementation. Crucially, we also evaluate the Falcon team's highly optimized embedded assembly (ASM) implementation. Despite its reduced leakage, our adapted multi-trace attack successfully recovers 53 out of 100 test keys with only 10 traces. This marks the first successful single-trace attack at the \texttt{-O3} level and the first practical attack against the embedded ASM Falcon. Furthermore, our in-depth assembly analysis of these vulnerabilities provides critical guidelines for designing more secure, hardened embedded assembly implementations.

Proof-of-useful-work (PoUW) certifies computational hardness, not utility. We separate three properties of a work receipt: work soundness ($\mathsf{W}$), job binding ($\mathsf{B}$), and demand exogeneity ($\mathsf{E}$), the last defined relative to an attacking coalition. Job binding is cryptographically achievable; demand exogeneity is not derivable from endogenous receipts. Payments between coalition-controlled requesters and workers are recoverable transfers, so no attack-cost lower bound may count their nominal value (Lemma 1). Under free pseudonyms and endogenous observation, receipts cannot certify $\mathsf{E}$ (Theorem 1); against a stated class of provenance estimators, evasion costs the equivalent of an implicit tax on simulated volume, below one percent at the parameters we consider. A mechanism that must stay safe and live on the zero-demand path needs an election path independent of demand-derived receipt weight (Proposition 4). The quantitative consequence is a sizing rule. A receipt boost that a coalition can realize by paying itself must be capped against the demand-independent floor (Corollary 4), and pricing the boost with a burn changes its cost but not this cap (Corollary 5): a burn-priced boost capped at $\kappa$ times a participant's own stake lowers the floor share an attacker needs from $\tau$ to $\tau/(1+\kappa(1-\tau))$ once honest demand vanishes. In a stylized free-entry model, fork-independent salvage value of useful outputs leaves security neutral, lower, or higher depending on salvage asymmetry and demand. An irrecoverable tax on every settled payment makes the burn the security resource. We know of no production chain that weights leader election by endogenously attested demand, so the results constrain a design space; the deployed systems closest to it, Filecoin and Gridcoin, keep a demand-independent floor. Receipts suit payment, collateral, loss allocation, and a bounded, priced election boost. They cannot carry the leader-election floor.

Secure multi-party computation (MPC) enables $N$ parties to jointly evaluate any function over their private inputs while preserving confidentiality. While decades of research have produced concretely efficient protocols for small to moderate numbers of participants, scaling MPC to thousands of parties remains a central challenge. Most of the existing approaches either incur per-party costs linear in $N$, due to pairwise computations, or rely on heavy cryptographic tools such as homomorphic encryption, which introduces prohibitive overheads when evaluating Boolean circuits. In this work, we introduce a new lightweight approach to designing semi-honest MPC protocols with per-party, per-gate computation and communication costs that are independent of $N$. Our construction leverages the Sparse Learning Parity with Noise (Sparse LPN) assumption in the random oracle model to achieve per-gate costs of $O(k^2 \cdot c(\lambda))$ computation and $O(c(\lambda))$ communication, where $k$ is the sparsity parameter for the Sparse LPN assumption and $c(\lambda)$ is an arbitrarily small super-constant in the security parameter $\lambda$. Assuming Sparse LPN remains hard for any super-constant sparsity, this yields the first semi-honest MPC protocol in the dishonest-majority setting with per-party, per-gate costs bounded by an arbitrarily small super-constant overhead in $\lambda$. Structurally, our MPC instantiates a Beaver-style MPC with the required correlations generated efficiently. Departing from prior approaches that generate Beaver triples either silently (Boyle et al., 2019; 2020; 2022) or through homomorphic computation (Damgård et al., 2012), our focus is on efficiently generating a weaker correlation. In particular, using Sparse LPN we show that if we relax the correctness requirement in generating random Beaver triples to permit a tunably small inverse-polynomial error probability, such triples can be silently generated with arbitrarily small super-constant per-party computation. We then show that such correlations can be used in an efficient online phase similar to Beaver's protocol (with a tiny super-constant factor blow-up in communication).

We study the randomness required to share possibly correlated secret bits among parties connected by a graph. A dealer places shares on the edges so that each party can recover its own secret from its incident shares and learn nothing about the others beyond what its own secret reveals. Anilkumar et al. completely determined the minimum randomness required for three binary secrets. We extend this study to four secrets and obtain results for arbitrary numbers of secrets on general graphs. For four parties on a complete graph, we determine the minimum number of random states for every set of permitted secret combinations: the possible values are one, two, three and four. We also characterize when one random bit suffices on an arbitrary graph.

Secure weighted aggregation is essential for privacy preserving federated learning, yet existing schemes do not simultaneously provide post-quantum security, resilience to client dropouts, verifiability against malicious servers, and resistance to bounded collusion between the server and clients. This paper presents PQ-DVSA, a verifiable secure aggregation scheme that provides post-quantum security and resilience to client dropouts. PQ-DVSA protects both clients’ updated local models and aggregation weights, enables reconstruction of the aggregate mask for the active set after client dropouts, and allows clients to verify the server’s aggregation result under bounded collusion. Experimental results show that PQ-DVSA achieves learning performance comparable to exact weighted aggregation and reduces the runtime for encrypted submission at each client by up to 96% compared with SWAS, the closest existing scheme to PQ-DVSA.

We advance the study of best-possible security guarantees of two-round secure multiparty computation in the plain model. While Goel et al. (TCC '21) showed the infeasibility of Identifiable Abort in two rounds in the plain model with a standard honest majority (i.e. $t < n/2$), the effect of relaxing the setting to an honest supermajority has not been established. In this work, we close this gap. When $t < n/3$, we show that two rounds are sufficient to achieve identifiable abort. Notably, ours is the first two-round general-purpose MPC construction in the plain model tolerating more than one corruption that achieves a guarantee stronger than unanimous abort. We obtain our construction via a new compiler that lifts any protocol with unanimous abort to one that achieves identifiable abort. A core building block for our compiler is Oblivious Public Transfer with Intermediaries (OPTI), a new primitive that we introduce which may be of independent interest.

Secure multiparty computation with provable identifiable selective abort (PISA), introduced by Kondi and Ravi (CCS 2025), guarantees that every honest party either obtains the computation output or a certificate that convinces any external auditor that a specific party cheated. Crucially, honest parties need not agree: some may get output while others receive evidence of cheating. In contrast, secure computation with identifiable abort (IA) requires just such unanimity; however, in the event that an honest party doesn't get output, it need merely be able to point to a cheater - not to prove their guilt. Secure computation with IA classically requires broadcast. Kondi and Ravi demonstrated that secure computation with PISA, on the other hand, can be built over point-to-point channels alone. While PISA is feasible exactly when guaranteed output delivery is, i.e. for $t < n / 2$, the best known construction over point-to-point channels requires six rounds. We settle the round complexity of PISA for all but a narrow band of thresholds. We prove that two rounds are impossible for $t \geq n /3$, even with arbitrary setup and computational assumptions; we give a three-round protocol for any $t < n/2$, which is therefore round-optimal for $n / 3 \leq t < n/2$; and we give a two-round protocol for $t < n/4$. The two-round protocol introduces a new primitive called one-or-nothing secret sharing with omissions.

DAG-based Byzantine fault-tolerant (BFT) consensus lets all validators propose concurrently, and uncertified designs such as Mysticeti skip per-block certification to achieve low latency. In existing partially synchronous round-based DAGs that use only hashing and standard signatures, however, every block references a quorum of previous-round blocks, so block metadata grows linearly with the committee size and, even in the happy case, the metadata communicated per round grows cubically. We present Bluestreak, a partially synchronous uncertified DAG BFT protocol that sparsifies block metadata using only hashing and standard signatures. A non-leader block carries at most two references, to its author's previous block and, optionally, to the previous leader; the leader reference is a vote. It may also name the leader of two rounds earlier as certified, a claim that its author has seen $2f+1$ votes for it. Only the single leader block per round references the latest block it knows from each validator, so committing it orders their chains. Because a sparse ancestry cannot justify the claims it carries, a node references a block only after verifying every claim in the block's history, and a pull-based pacemaker fetches the blocks and votes it is missing. We prove safety and liveness under partial synchrony and show that, in the happy case, block metadata amortized over a round is constant, per-round metadata communication is quadratic in the committee size, and, under idealized timing, the average end-to-end latency equals Mysticeti's: 4.5 message delays. In experiments with emulated ten-region wide-area delays, Bluestreak cuts average block metadata from Mysticeti's 13 KB to about 320 bytes at 400 validators, and matches or beats its median end-to-end latency at every committee size from 10 to 400.

Retaining intermediate values can shorten a quantum cipher oracle but increase the logical qubits required by each parallel search worker. We propose a joint selection procedure for 80-round and revised 112-round CHAM-128/128 under a fixed global logical-qubit budget. It selects retained round addends, feasible integer allocations of search workers, and execution plans to minimize maximum scheduled logical depth subject to a target probability of recovering and accepting the original key. We evaluate libraries of 83 and 99 retention sets against a baseline whose retention choices are restricted to no retention and full retention. Both comparison groups use the same implementation and execution rules. Across 654 budget, success-target, and Toffoli-decomposition conditions per round count, the mean depth reductions are 11.12% and 8.39%, with strict improvements in 606 and 588 conditions, respectively. The selected retention count need not increase with the budget, and a fixed-circuit capacity discontinuity can disappear after reselection. The findings concern the measured libraries under an ideal-cipher success model and logical-layer costs.

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.

Secret-shared SQL-style join is a fundamental building block in secure collaborative data analysis. In practice, join operations frequently involve duplicate keys, giving rise to one-to-many (Join-OM) and many-to-many (Join-MM) relationships. Supporting such joins requires obliviously materializing all matching row pairs. Existing protocols achieve this in two costly ways: they either perform oblivious sorting over a larger expanded input or rely on multiple aggregation trees that incur additional logarithmic rounds. In this work, we present highly efficient protocols for Join-OM and Join-MM over secret-shared databases in the standard semi-honest setting. Our core contribution is Oblivious Sort Expansion (OSE), a novel constant-round protocol that may be of independent interest. Rather than obliviously sorting the expanded input from scratch, we sort only the original input and use OSE to derive the sorted order after expansion. For Join-OM, OSE eliminates the redundant sorting overhead introduced by input expansion in the state-of-the-art protocol by Asharov et al. (CCS 2023). For Join-MM, we combine OSE with local linear operations to obtain an aggregation-tree-free Join-MM protocol. Experimental results show that our protocols consistently outperform prior protocols, reducing both runtime and communication costs by approximately $27\%$ and $65\%$ for Join-OM and Join-MM, respectively.