Papers updated in last 183 days (Page 8 of 2708 results)
Batched Oblivious Transfer with Square-Root Communication
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.
Chosen Ciphertext and Trapdoor Secure Public Key Authenticated Encryption with Keyword Search
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.
A Black-Box Compiler from Static to Dynamic SNARKs
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.
MPC with Weighted and Fluid Participation
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.
Programmable Distributed Point Functions
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.
Constant-Time Conditions for Left-to-Right Scalar Multiplication
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.
Extending the Schur--Macaulay Framework for UOV Attacks via Truncated Polynomial Algebras
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.
Worst-Case Hardness for Succinct and Decomposed Learning with Errors
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.
An Efficient SM9-Compatible Identity-Based Blind Signature Scheme for One-Time Issuance Identities
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.
Faster generic CCA secure KEM transformation using encrypt-then-MAC
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.
Nobody Will Read the Lean: A Case for High-Level Cryptographic Languages
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.
Staggered Instruction-Fetch Duplication: A Lightweight Processor-Level Countermeasure Against Fault Injection
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.
Efficient Vectorized Implementation of MQOM
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.
Censorship Resistance in Credential Systems and Application to the EUDI Wallet
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.
Confidential Error-Correcting Codes
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.
Threshold BARGs with Statistical Soundness: Weighted Threshold Encryption without Obfuscation
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.
TenseUp: Doubly-Efficient Lookup Arguments from Tensor Codes and Applications to Dynamic SNARKs
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.
Succinct Arguments with (almost) Minimal Time and Space Overheads from Symmetric-Key Primitives
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.
Weighted Batch Threshold Encryption with Efficient DKG
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.
ADC-BE: Optimizing Worst-Case Bandwidth in Broadcast Encryption with Boolean Functions
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.
Distinguishers for the Squeezing of the Alternating Sponge and Duet
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.
Hash Function Constructions from Lightweight Block Ciphers for Fully Homomorphic Encryption
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.
Secure MSM Outsourcing Computation for Zero-knowledge Proof Generation
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.
Rapid mixing in superspecial isogeny graphs
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})$.
D-James: Ultra Short Multivariate Signatures
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.
Beyond-Birthday MAC Security for Encrypted Wegman-Carter and EWCDMD
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.
Practical Post-Quantum Secure Publicly Verifiable Secret Sharing and Applications
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 with Partial-Insider Resilience
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.
RM-KLPT: Algebraic Pathfinding for Superspecial Abelian Surfaces with Maximal Real Multiplication
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.
Provably Subexponential Algorithms for Bounded-Error LWE with Few Samples
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.
Revisiting Generic Transforms for Committing Authenticated Encryption
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.
Sample-Preserving Search-to-Decision Reduction for Noisy Linear Equations over Large Moduli
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$.
Natural Barriers to Quantum Extraction: On the Post-Quantum (In)security of (O)EKE and Masny-Rindal OT
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 from Homomorphic Encryption over Random Encodings
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.
Efficient Unbiasable Verifiable Random Functions via (Non-)Black-Box Reductions
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).
Provable Subexponential Algorithms for Module-SIS and Module-LWE
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.
Optimal Statistical Oblivious RAM and Search Tree in the External-Memory Model
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.
Fully-Succinct Multi-Key FHE & Rate-1 Simulatable Threshold Decryption from LWE
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 from Iterated Squaring
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.
Provable Subexponential Algorithms for NIST Third-Round Lattice Families
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.
The Power of Multislices in Monotone Computation
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.
Reverse-Bleichenbacher: Bleichenbacher Attacks are Practical Again
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.
Can We Tolerate Small Side-Channel Leakages: The Role of Registers in Glitch-Stopping Circuits
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.
A Resource-Efficient Hardware Accelerator for Large-Size NTT via Algorithm–Architecture Co-Design
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.
Fast Polynomial Arithmetic in the Exponent without Roots of Unity
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.
An Analysis of the ITU-T Multiple Cryptographic Algorithms X.509 Extensions for PQC Migration
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.
Barely Sublinear RAM-FHE from Plain LWE
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.
Bridging the Cryptographic Transition: A Unified Framework for Post-Quantum Key Exchange
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.
Average-Case Hardness of Lattice Problems in Special Genera of Fixed Rank
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.
$\mathsf{Rotor}$: SNARKs for Power-of-Two Rings
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}$.
Perfectly Secure Network-Agnostic MPC Comes for Free
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.
KIFA: Kernel-based Integral Fault Analysis on GIFT-Family Ciphers
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.
Lightweight Hardware Accelerator for the UOV Signature Scheme with Oil Space Blinding
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.
Mercury: Fuzzy Private Set Intersection with Communication and Computation Logarithmic in the Threshold
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).
UC PAKE and Concrete Security
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.
Separating One-Way Functions from Verifiable Delay Functions
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.
Resettable Non-Interactive Zero-Knowledge: Attacks and Defenses
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.
CAROUSEL: GPU-Accelerated Private Vector Search via Homomorphic Sketching
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.
Language Modeling is Monotone Compression
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.)
Improved Robust Secret-Sharing for Honest-Majority Preprocessing-MPC
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.
Foundations of Dynamic Group Signatures: The Case of Malicious Openers and Issuers
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.
The Geometry of Collusion Leakage in Inner-Product Functional Encryption
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.
De-SyRIS: A Decentralized Sybil-Resistant Identity System Using Mutual Facial Biometric Verification and Social Graph Analysis
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.
On the Preprocessing Security of Nonzero Schnorr Signatures with Adaptive Corruptions
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.
Practical and Efficient MPC from FHE, without ZKPoKs
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.
Revisiting Lattice-based Blind Signatures Again
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.
Simple Byzantine Lattice Agreement in $O(\frac{\log f}{\log \log f})$ Rounds
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.
Hardness and Algorithms for Batch LPN under Dependent Noise
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.
Note on Extractability of PST Polynomial Commitment Scheme
A recent work by Belohorec et al. (Crypto, 2025) shows that the well-known PST multivariate polynomial commitment scheme is black-box extractable under falsifiable assumptions. They show that a minimally modified (extended) PST is extractable under an assumption ARSDH($n$), and that the canonical PST is extractable under an assumption GARSDH($n$). Both of these assumptions are new and more specialized than the original ARSDH assumption proposed by Lipmaa et al. (Eurocrypt, 2024) to prove black-box extractability of the univariate KZG polynomial commitment. A natural question is whether these assumptions are actually stronger than the original ARSDH assumption. We answer this negatively: we show that both ARSDH($n$) and GARSDH($n$) are equivalent to the original ARSDH assumption. Secondly, we point out a gap in the proof that canonical PST is extractable under GARSDH($n$) assumption.
Deniable Secret Sharing: Towards Practical Faking
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.
Hashing Beats Trees: Practical Oblivious Dictionaries in SGX
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.
Hide Now, Trace Later: Retrospective Attribution in Issuer-Hiding Credentials
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.
Smoothing the degree of regularity for polynomial systems
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.
One Fell Swoop: A Single-Trace Key-Recovery Attack on the Falcon Signing Algorithm
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 Demand Is Not Proof of Work: On the Limits of Demand-Weighted Consensus under Free Pseudonyms
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.
A New Approach to Large Party Beaver-Style MPC with Small Computational Overhead
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).
The Price of Privacy: Randomness Complexity of Graph-Based Multi-Secret Sharing
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.
Post-Quantum Dropout-Resilient Verifiable Secure Aggregation for Federated Learning
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.
Putting the OPTI in Round Optimal IA-MPC in the Plain Model
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.
Round Optimal MPC With Provable Cheater Identification
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.
Bluestreak: Uncertified DAG BFT with Sparse Metadata
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.
Retention Choices for Quantum CHAM Key Search under a Global Qubit Budget
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.
A Universal Forgery Attack on the Origami Signature Scheme from the Public Key Alone
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.
Masking, Sequences, and FALCON: A Theoretical Study on Masking Strategies Using Sequences for Non-Linear Operators in the FALCON Post-Quantum Signature
Post-Quantum Cryptography is now in its deployment phase. Amongst the threats encountered in real-world applications is Side Channel Analysis, a cryptanalysis branch relying on the study of physical leakages from unsecured implementations. However, the FALCON post-quantum signature includes non-linear functions on real numbers, and applying the generic masking countermeasure to these functions has only been recently studied. In this work, we use convergent sequences to approximate the function and a minimax polynomial to compute the first term of the sequence. The method is applied to the computation of the inverse square root and the square root in FALCON, two operators for which masking has not been investigated before. A theoretical analysis of the security in the t-probing model using the NI criterion and its variants is proposed. Compared to the existing state-of-the-art using the same approach which covers the masked inversion for emulated floating-point implementation, this paper is generic and works with any representation and precision for real numbers.
Lifting Bounded-Collusion Security to Full Security in Pairing-Based Encryption Schemes
Notions like identity-based encryption (IBE) and attribute-based encryption (ABE) augment public-key encryption to provide fine-grained access control to encrypted data. In these settings, there is a single master public key that anyone can encrypt to. Users in turn possess different secret keys that determine which ciphertexts they can decrypt. The standard, or full, security notion for these schemes stipulates that a ciphertext computationally hides the message if the adversary does not possess a key that is allowed to decrypt. A relaxed notion of security that is often much easier to achieve is bounded-collusion security, where we only require security against adversaries that have an a priori bounded number of keys (and the scheme parameters can grow with this bound). For instance, it is known that vanilla public-key encryption implies bounded-collusion IBE (and ABE) whereas there is a black-box separation between public-key encryption and fully secure IBE.
In this work, we develop a general methodology to upgrade a pairing-based encryption scheme with bounded-collusion security into one that is fully secure. We illustrate our methodology by applying it to two main applications: batched IBE and multi-authority ABE. First, in the case of batched IBE, we obtain the first pairing-based construction of batched IBE where there are no tag restrictions (in the generic bilinear group model). All previous pairing-based batched IBE schemes require attaching a tag to ciphertexts and secret keys, and moreover, restrict the adversary to an a priori bounded number of secret keys for each tag. Second, we use our techniques to obtain a multi-authority ABE scheme that supports conjunction policies in the generic bilinear group model. This is the first pairing-based scheme that makes fully black-box use of the group. Previous pairing-based multi-authority ABE schemes require a random oracle whose output is a group element (which implicitly assumes the underlying group supports a procedure for explainable oblivious sampling).
Faster Provable Lattice Sieving with Spherical Codes
We study the computational problem $\mu$-SVP, in which the goal is to find a $\mu$-approximate shortest non-zero vector in a lattice $\mathcal{L}$, for constant approximation factors $\mu > 1$. Prior to this work, there was a large gap between the fastest algorithms for this problem whose correctness had been proven and the fastest heuristic algorithms, whose correctness has not been proven (but which seem to work well in practice).
We construct a novel sieving algorithm that combines the key tool used in the fastest heuristic sieving algorithms (faster nearest neighbor subroutines) together with the perturbation argument used in sieving algorithms with proven correctness. The result is an algorithm whose correctness we prove and whose running time depends on a simple geometric quantity: the maximal size of certain spherical codes.
Under a reasonable assumption about the maximal size of spherical codes, our algorithm's running time is roughly $2^{0.3066n}$ for large constants $\mu$, which is quite close to the best heuristic running time of roughly $(3/2)^{n/2} \approx 2^{0.2925n}$ and much faster than both the previous best known algorithm with proven correctness, which runs in time roughly $2^{0.802n}$ [Liu, Wang, Xu, and Zheng, 2011] and the very recent concurrent and independent work showing a $2^{n/2}$-time algorithm [Hhan, 2026]. (However, the algorithm of Hhan also solves $\mu$-SVP for $\mu =1$, while our algorithm only works for large constant $\mu$.) Using the best proven upper bound on the size of such spherical codes (which is almost certainly quite loose), we obtain a running time of roughly $2^{0.6078n}$, which is much better than the previous best work but notably slower than the concurrent work of Hhan.
QuantumScouter: Reinforcement Learning-Based Optimization of Variational Quantum Circuits for Differential Cryptanalysis
Classical deep learning for differential cryptanalysis requires millions of ciphertext pairs, rendering attacks infeasible or easily detectable. This work overcomes this data limitation by introducing quantum differential distinguishers, enabling a practical attacker model where executing few queries is feasible. We design these distinguishers via quantum machine learning based on variational quantum circuits. To address circuit design challenges, we propose QuantumScouter, a reinforcement learning method that discovers compact quantum circuits. Unlike prior work, QuantumScouter explicitly targets metrics like gate count and circuit depth, producing circuits suitable for noisy intermediate-scale quantum hardware. We apply QuantumScouter to the SPECK32/64 and SIMON32/64 ciphers. The models are trained to distinguish ciphertext pairs possessing a meaningful differential from completely random pairs. For SPECK, our approach achieves $0.80$ accuracy, outperforming the $0.53$ of prior work while reducing required qubits from $16$ to $6$. For SIMON, we establish a novel quantum baseline with $0.75$ accuracy. Notably, under a restricted regime of merely $400$ training samples, classical deep learning models struggle. A simple MLP with $361$ parameters fails to capture differential characteristics, resulting in an accuracy of $0.51$, while a deep ResNet with $64{,}737$ parameters overfits to yield an accuracy of $0.55$. In stark contrast, our data-efficient quantum distinguisher extracts meaningful features using only $49$ gates, maintaining $0.80$ accuracy.
Adaptive Distributed Key Generation for Discrete-Log Cryptosystems
Threshold signatures are widely deployed in decentralized asset custody and blockchain infrastructure to eliminate single points of failure. In these systems, an attacker can adaptively corrupt committee members based on public membership and protocol transcripts. Recent cryptanalysis shows this threat is concrete: schemes exposing per-party key commitments enable practical forgeries for committees of roughly 200 signers at the cost of just one minute of the global Bitcoin hashrate.
While a new generation of signing schemes defeats this attack by hiding individual key shares, every distributed key generation (DKG) protocol used in practice exposes this information, voiding the adaptive security of any scheme built on top. Trusted dealers avoid the leakage but reintroduce the single point of failure that threshold cryptography exists to eliminate. True adaptive security must therefore span both key generation and signing.
We present Janus, the first DKG suite to achieve this end-to-end guarantee. Janus serves as a drop-in replacement for a trusted dealer in threshold schemes, hiding all key shares while outputting a standard DLog public key compatible with existing verifiers, wallets, and smart contracts. Assuming secure erasures, we prove security against an adaptive adversary that corrupts members mid-protocol and controls a dishonest majority.
We also show that Janus directly supports a variety of DLog-based primitives, including threshold Schnorr signatures and oblivious pseudorandom functions.
Our suite includes Janus2R, which achieves an unbiased key in two rounds, and Janus1R, which completes within a single round by tolerating an additive key shift.
When a node misbehaves, both variants generate a 259-byte universally verifiable proof for automated on-chain slashing, and both naturally allow committees to proactively refresh their shares without changing the public key. Our open-source Rust implementation completes key generation for a 16-node intercontinental committee in 310 ms and scales to 512 nodes.
Transient Quantum Resistance, with Application to Ethereum Consensus
Candidates for post-quantum migration carry additional costs compared to their pre-quantum counterparts, especially for signatures, and they lose attractive properties of schemes such as BLS: homomorphism, and hence direct signature aggregation.
We propose a methodology through which a pre-quantum primitive may still be securely used past Q-day (the advent of quantum computers) in settings where forgery of signatures or cryptographic proofs need only be prevented for a bounded lifespan (transient quantum security). The idea is to bind a fresh, ephemeral, ordinary pre-quantum key to a long-term post-quantum identity once per lifespan window, so a forgery under the fresh key is useful only for that window, and to derive the fresh key so that its exposure never leaks the long-term secret.
Our main case study is an application to Ethereum consensus, conditional on stated registration, inclusion, and slashing-evidence rules. The construction keeps ordinary BLS aggregation and needs no SNARK prover. Each same-message aggregate is a single 96-byte signature, and each validator publishes 592-688 bytes of reveal data per epoch. Each epoch key is bound to a seed derived from a checkpoint finalized before that epoch, so a committed key is opened under exactly one seed. We reduce unforgeability in the public-tag game to co-CDH' in the ROM and QROM, with explicit probability and resource costs. Transient quantum security requires hardness at the resulting budget; later checkpoint-derived seeds also require the stated public-environment condition.
Transient security requires forgery resistance for the whole interval in which an exposed key can affect the chain. Under Ethereum's attestation inclusion rules, that interval is nominally two epochs plus the reveal lead time under prompt processing. Historical slashing and delayed-fork acceptance need additional rules, which we state as preconditions. Published quantum attack costs inform the resource discussion. They do not establish a security lower bound for this construction.
We also provide a formal model and security analysis for the construction, and, of independent interest, a new analysis of BLS where the secret key is sampled similarly to the Dodis-Yampolskiy VRF (IACR PKC 2005) and the adversary is given a related group element as leakage.
Linear list size bounds for Reed-Solomon beyond the Johnson radius
Based on techniques discovered in the better.codes autoresearch project, we show that Reed-Solomon codes of rate $\rho$ and block length $n$ over a field of sufficiently large characteristic, have $C\cdot n$ list size bound when requiring fractional agreement $\alpha$ with a received word; where $C,\alpha$ are constants depending only on $\rho$ and $\alpha<\sqrt{\rho}$. This complements the recent breakthrough results [BCPZZ26,Jeronimo26] achieving $n^c$ list size bounds with agreement $\rho+\epsilon$ for any constant $\epsilon>0$ with an unspecified constant exponent $c$.
Quintus: Two-round Good-case Information Theoretic BFT for $n=5f+1$
We present Quintus, information-theoretic BFT protocols for tolerating $f < n/5$ Byzantine faults among $n$ parties. We present two protocols: The first protocol, Quintus-Fixed, is in a fixed view regime where views advance at a cadence $3\Delta$ time. This protocol incurs a good-case latency of $2\delta$ time where $\delta$ indicates actual network delay and message complexity of $O(n^2)$ in a view. The second protocol, Quintus-Responsive, is an optimistically responsive protocol with good-case latency of $2\delta$ time, $O(n^2)$ message complexity, and $2\Delta + 2\delta$ worst-case view latency where $\Delta$ denotes a pessimistic network delay parameter under synchrony.
Quantum Time-Lock Puzzles in the Quantum Random Oracle Model
A time-lock puzzle allows a sender to hide a message in a puzzle such that recovering the message requires substantially more sequential computation than the time required to generate the puzzle, even when parallel computation is allowed. Applications of time-lock puzzles include timed-release encryption, sealed-bid auctions, electronic voting, fair contract signing, coin flipping, and Byzantine consensus. However, time-lock puzzles are known to be impossible in the classical random oracle model.
To overcome the classical barrier, in this work we consider quantum time-lock puzzles, in which the puzzle itself is a quantum state. Our construction in the quantum random oracle model achieves generation in one oracle round, solving in at most $T$ oracle rounds, and security against polynomial-width quantum adversaries of depth $o(T)$ for every polynomially bounded delay $T$, resolving an open problem posed by Mahmoody, Moran, and Vadhan (2011).
Post-Quantum Cryptography from Quantum Stabilizer Decoding
Post-quantum cryptography currently rests on a small number of hardness assumptions, posing significant risks should any one of them be compromised. This vulnerability motivates the search for new and cryptographically versatile assumptions that make a convincing case for quantum hardness.
In this work, we argue that decoding random quantum stabilizer codes -- a quantum analog of the well-studied LPN problem -- is an excellent candidate. This task occupies a unique middle ground: it is inherently native to quantum computation, yet admits an equivalent formulation with purely classical input and output, as recently shown by Khesin et al. (STOC '26). We prove that the average-case hardness of quantum stabilizer decoding implies the core primitives of classical Cryptomania, including public-key encryption (PKE) and oblivious transfer (OT), as well as one-way functions. Our constructions are moreover practical: our PKE scheme achieves essentially the same efficiency as state-of-the-art LPN-based PKE, and our OT is round-optimal. We also provide substantial evidence that stabilizer decoding does not reduce to LPN, suggesting that the former problem constitutes a genuinely new post-quantum assumption.
Our primary technical contributions are twofold. First, we give a reduction from random quantum stabilizer decoding to an average-case problem closely resembling LPN, but which is equipped with additional symplectic algebraic structure. While this structure is essential to the quantum nature of the problem, it raises significant barriers to cryptographic security reductions. Second, we develop a new suit of scrambling techniques for such structured linear spaces, and use them to produce rigorous security proofs for all of our constructions.
SkrrtPIR: Doubly-Stateless Batch PIR from Single-Key RLWE Unpacking
Batch Private Information Retrieval (Batch PIR) allows a client to privately retrieve multiple entries from a public database while amortizing query costs. However, concretely efficient schemes typically rely on per-client server state, such as client-specific evaluation keys, which makes queries linkable across sessions and complicates deployment. In this work, we initiate the study of doubly-stateless Batch PIR, where the server stores no per-client state and the client maintains no database-dependent hint. For this model, we construct a communication-efficient scheme that substantially reduces communication compared with the natural baseline of adapting off-the-shelf Batch PIR schemes by sending fresh evaluation keys with each batch query. The core technical ingredient is a single-key RLWE unpacking procedure that replaces the traditional tree-based approach, which requires logarithmically many Galois keys, with a linear walk over a cyclic Galois subgroup requiring only a single Galois key.
Decentralized Proposer-as-a-Service (DPaaS): Improving Decentralization and Trustworthiness in Ethereum PBS
Proposer-Builder Separation (PBS) in Ethereum aims to improve decentralization and scalability by offloading block construction to specialized builders, but its current MEV-Boost implementation relies on trusted relays, introducing centralization as well as security and performance concerns. We propose Decentralized Proposer-as-a-Service (DPaaS) to eliminate relays while preserving compatibility with Ethereum’s consensus layer by distributing the combined proposer and relay roles across Proposer Entities (PEs) running in independent Trusted Execution Environments (TEEs). DPaaS presents itself to Ethereum as a single validator using threshold BLS signatures, while a new Byzantine broadcast protocol decentralizes the auctioneer role with censorship-resistance and availability-backed guarantees. Our evaluation, deployed across four independent cloud hosts and driven by real-world traces, shows that DPaaS achieves $\leq 6$ ms bid processing latency, $68.7$ ms latency from the end of auction to block proposal, and $3.3\%$ more MEV earnings – demonstrating that DPaaS can offer security, decentralization, and trustworthiness benefits while providing strong performance.
A Security-Aware PQC Benchmarking Framework on Dual-Core Xtensa Silicon
Deploying memory-heavy post-quantum cryptography (PQC) at the smart grid edge threatens real-time substation determinism, directly conflicting with the strict $\le 3 ms$ GOOSE tripping window of the IEC 61850 standard. To resolve this architectural tension, we propose a security-aware, hardware-in-the-loop benchmarking framework on the dual-core Xtensa LX7 (ESP32-S3) SoC running FreeRTOS. To prevent inter-core resource contention, the framework employs an asymmetric task-isolation design, pinning cryptographic operations to Core 1 while leaving Core 0 responsive to line-rate grid interrupts. Additionally, we define a programmatic heap-auditing methodology to model how heap_4.c maps key-state allocations across physical DRAM fragments while preserving the primary 128 KB contiguous system heap. Finally, we formulate an analytical latency model of the external Octal-SPI PSRAM interface, mathematically characterizing the CPU stall overhead ($C_{\text{stall}}$) induced when side-channel masking forces secret polynomial shares to spill over the external bus during non-sequential Cooley-Tukey NTT strides. This framework provides a rigorous methodology to characterize micro-architectural trade-offs, enabling utility engineers to plan post-quantum migration pathways without violating real-time grid constraints.
The Post-Quantum Cost of Garbled-Circuit Bitcoin Bridges
Recent Bitcoin bridge designs rely on verification of succinct proofs to process withdrawals. This requires off-chain garbled circuit evaluation of a succinct proof, the input labels for which must be encoded on chain in a manner compatible with malicious security. We assess the post-quantum vulnerability of these cryptographic components, and examine the costs of secure alternatives. Circuit sizes for post-quantum proving systems can be made smaller than the current pairing-based baseline, but at the cost of significantly higher proof sizes that incur greater cost and require multiple Bitcoin blocks to encode. We suggest avenues of future research to improve efficiency of proofs, circuit representations, and input encodings.
Differential-Neural Cryptanalysis of ChaCha and Related ARX Stream Ciphers
The paper presents the first-ever differential neural cryptanalysis of the Latin Dances family of Salsa, ChaCha, and Forró. First, we provide a systematic differential-neural study of the ARX stream cipher ChaCha. We train and compare six neural architectures, viz.: Gohr's residual network, DBitNet, an Inception network, an MLP-ResNet, an SE-ResNet, and a self-attention network on a 3-round reduced version of ChaCha. We train in both the classical single-pair setting and a multi-pair setting that combines up to sixteen ciphertext pairs through a log-odds rule. We extend the study for breadth to other ARX ciphers, Salsa, *ChaCha, and Forró. We provide the first-ever distinguisher for 4.5 rounds of Salsa with accuracy of 0.53 for one pair and 0.60 for 16 pairs. Also, for Forró the first-ever distinguisher for 1.25 rounds of Salsa with accuracy of 1 for single and multiple pairs. We also introduce a family of experimental round-1-XOR variants (\emph{XOR-1}) that isolate the contribution of the first round's diffusion to distinguishability. Finally, we investigate the trained 3-round ChaCha distinguisher with four explainability experiments and show that, although the output difference is its dominant feature, it is not a pure differential distinguisher: its decision is interpretable as a learned mixture of round-1 truncated differentials, five of which already account for $99\%$ of the high-confidence ciphertext pairs.
The Lattice Isomorphism Problem with Hints
The Lattice Isomorphism Problem (LIP) is a relatively new problem that has gained increasing attention in the field of lattice-based cryptography. It is the underlying hard problem of the Hawk signature scheme, which has been submitted to the second NIST call for post-quantum signatures. In this paper, we propose to study the security of LIP in the presence of partial information on the secret solution, which can be obtained through side-channel attacks or by design. We propose a new cryptanalysis approach for LIP that embeds it into a shortest vector problem (SVP) based on a different lattice than the one considered in the specifications of Hawk, allowing to integrate hints. We also introduce conversion techniques that transform hints expressed on arbitrary linear combinations of the secret key coefficients into hints on the target lattice, enabling the integration of a broader class of linear leakages on sensitive values. We implement our attack and predictions using the LeakyLWEEstimator tool (Crypto 2020) and obtain concrete security estimates for Hawk in the key-recovery setting. We also observe that Hawk signatures carry intrinsic information about the secret key and show that this can be exploited as a source of hints, yielding a refined key-recovery complexity, thereby eroding the original security estimates. For example, we estimate a security loss of around 11 bits for Hawk-1024. Finally, we apply our framework to side-channel analysis results on Hawk, solving an open problem raised in a recent analysis (TCHES 2024) and discuss further attack paths enabled by fault-injection techniques.
We believe that this new cryptanalysis approach for LIP and the integration of hints provide new insights towards a better understanding of its security.
Beyond Mosca’s Heuristic: Supported Is Not Protected in Post-Quantum Migration
Post-quantum (PQ) migration is usually tracked per asset, with Mosca’s inequality and a share of “migrated” systems. For a flow of sensitive data, the relevant questions are different: is every session that carries it keyed by a quantum-safe secret, what evidence supports that claim, and what can an assessor establish from outside? We propose an assessment method whose unit is the data path and whose verdicts are tied to evidence. Key lineage is an algebra on break dates: a derived key falls when all its inputs fall, and a key falls when any of its copies falls.
This covers TLS 1.3 resumption, key transport and keys wrapped several times. A verdict is a pair of strong-Kleene evaluations, one taking claims at face value and one admitting only claims that meet an evidence policy; the reachable pairs form four ordered labels. We characterize what an external probe can establish. A probe of the server decides a hop only if the server enforces PQ or cannot negotiate it; enforcement must be shown by a negative test paired with a positive control; a server that resumes sessions without a fresh key exchange
leaves the layer undecided; and behind a load balancer the confidence of a negative test follows a sampling bound only under an independence assumption that a default balancer violates.
We implement the probe and validate its inference rules on 22 configurations of five server stacks built on three TLS libraries, including confounders and a heterogeneous load balancer. The same nominal configuration yields different states across implementations, so declared configuration cannot replace runtime evidence. A protocol for an internet-scale enforcement study accompanies the paper