Modern blockchains increasingly rely on parallel execution to improve throughput. We show several industry and academic transaction fee mechanisms (TFMs) struggle to simultaneously account for execution parallelism while remaining performant and fair. First, if parallelism affects fees, adversarial protocol manipulations that offset possible benefits to throughput by introducing fake transactions become rational: users can insert functionally useless parallel transactions solely to reduce fees, and schedulers can create useless sequential transactions to increase revenue. Execution contingency, a core feature of expressive programming languages, both exacerbates the aforementioned threats and introduces new ones: (1) users may overpay for unused resources, and (2) scheduler revenue is harmed when reserved scheduling slots go unused due to contingency. We introduce a framework for this challenging setting, and prove an impossibility, highlighting an inherent tension: both parallelism and contingency involve a trade-off between minimizing risks for users and schedulers, as favoring one comes at the expense of the other. To complete the picture, we introduce a fee mechanisms and prove that they achieve the boundaries of this trade-off. Our results provide rigorous foundations for evaluating designs advanced by notable blockchains, such as Sui and Monad.

Digital library lending is a critical resource for access to information. Currently prevalent models of digital lending, however, involve opaque licensing schemes that entail serious drawbacks to reader privacy and freedom of expression. In popular modern library apps, publishers and hidden intermediaries control a wealth of informa- tion about readers and reading habits, at a scale and level of detail that would be essentially impossible in physical library lending. To understand digital lending needs in practice, our work begins with a series of interviews with library professionals (𝑁= 11). We present thematic findings on their concerns with existing systems, including privacy, surveillance, preservation, and lack of library control over resources. Many of the concerns raised are inherently unproblematic in the context of physical library lending—leading us to our central technical question: Can digital lending achieve privacy and transparency at least as strong as physical library lending? Based on our qualitative findings, we provide the first rigorous modeling of security, privacy, and transparency requirements in digital library lending. As existing systems fall short of the strong guarantees we model, we propose a new system design, LendLocked, based on cryptography and trusted hardware, and prove it achieves these guarantees in the random oracle model. We micro-benchmark our design’s key cryptographic functionalities, s

Constant time programming patterns is the primary defense against timing attacks on cryptographic implementations, yet what "constant time" means varies across academia and industry. This work systematizes constant time models and their evolution, identifies a recurring gap between what models protect and what specifications assume, and distills an offensive methodology for discovering timing vulnerabilities that originate outside the cryptographic primitive boundary. Applying this methodology, we locate a specification-level vulnerability related to private key loading, and confirm the leak in both OpenSSL and BoringSSL. Counterintuitively, BoringSSL's per-observation signal is several orders of magnitude stronger than OpenSSL's, despite an explicitly stricter threat model.

Hybrid post-quantum migration is entering deployed handshake designs, but hybrid KEM security protects only one shared-secret input. It does not by itself say whether handshake, application, exporter, or resumption material remains pseudorandom after branch reveals, stage-key reveals, selective corruptions, or late corruptions. We characterize these staged claims through branch-formula freshness: each stage receives a monotone formula over branch exposure, authentication freshness, transcript binding, KDF ancestry, and explicit non-reveal atoms. Secrecy follows by replacing a surviving branch contribution and then using a labelled HKDF/PRF-style target-hiding argument along a fresh KDF cut; agreement follows separately from authentication binding and injective transcript representation. We also give selector-local accounting, where a fixed admissible witness selector determines which surviving branches and KDF cuts are charged. For scoped TLS 1.3 ECDHE--ML-KEM 1-RTT, we identify the branch-replacement, HKDF-path, and binding assumptions that imply concrete preservation bounds for handshake, application, exporter, and resumption targets.

The zero-difference attack on AES, introduced by Bardeh and Rijmen in [ToSC 2022(2):43--62], exploits some structural properties -referred to as related differentials- in the AES MDS matrix. Daemen and Rijmen earlier demonstrated that these related differentials appear not only in the AES MixColumns matrix but in all $4\times 4$ circulant MDS matrices [CCDS 2009(1):47--69]. In the same paper, they also showed an example of $4\times 4$ Hadamard MDS matrices for which there exists no related differentials. Combining both results, we can say for example that some $4\times 4$ Hadamard MDS matrices are more ``secure" than any $4\times 4$ circulant MDS matrices. Recently, Jha et al. investigated whether it is possible to characterize $4\times 4$ Hadamard MDS matrices for which we can find no related differentials in [ IACR Commun. Cryptol. 2(1): 37 (2025)]. As a result, they gave a systematic method to construct such ``secure" matrices with respect to their parameters. In this paper, we investigate the same problem for all $2\times 2$ and $3\times 3$ matrices to understand the cryptographic resilience of MDS matrices both theoretically and practically. As a result, we obtain the following results: - There are no related differentials for any $2\times 2$ MDS matrices. - There exist related differentials for all $3\times 3$ circulant MDS matrices. - There exist related differentials for all $3\times 3$ involutory MDS matrices when the finite field has even size. - We characterize all $3\times 3$ MDS matrices for which there exist no related differentials when the size of the finite field is even. In this way, we fill a gap for the cryptographic resilience problem of MDS matrices over finite fields.

This paper presents improved attacks and proofs for the key committing security of EtE-HCTR2, a robust authenticated encryption scheme constructed from HCTR2 and the Encode-then-Encipher (EtE) framework, in light of the ongoing standardization effort of cryptographic accordions by NIST. We improve attacks on the instantiations with two common encodings, where zeros are either appended or prepended to the message, namely EtE_A-HCTR2 and EtE_P-HCTR2. Compared with the state-of-the-art attack by Chen et al. in ToSC 2023(4), our EtE_A-HCTR2 attack reduces the complexity from $O(2^{\tau/2})$ to $O(2^{\max\{\tau/3, \tau-n\}})$ for an $n$-bit block cipher and $\tau$-bit zero padding, which degrades EtE_A-HCTR2's security below the birthday bound. Meanwhile, our EtE_P-HCTR2 attack reduces the complexity from $O(2^{\min \{n/2, \tau\}})$ to $O(2^{\tau/2})$, which is tight with our new security proof. We verify these computationally-bounded attacks by experimentally generating concrete vectors for both EtE_A-HCTR2 with $\tau=96$ and EtE_P-HCTR2 with $\tau=64$, each instantiated with $n=128$, in less than 15 minutes. We consider yet another padding scheme that appends zeros to the first message block, namely EtE_S-HCTR2, and prove that it has a tight committing security bound of $O(2^{\tau/2})$ by avoiding the issue in EtE_A-HCTR2.

Following the cryptographic security analyses of proof-of-work (PoW) blockchain protocols, a line of research has focused on their economic robustness. The two core questions asked are: How resilient is the system to rational attacks, and how profitable it is for miners to execute it. However, to our knowledge, no work to date has attempted to address them considering the full complexity of the blockchain protocol, including difficulty readjustment, which is needed to handle dynamic participation, price fluctuations, and the impact of risk. In this work, we provide a fine-grained game-theoretic analysis for Nakamoto-style PoW blockchains, which takes into account both incentives of parties to deviate and complications introduced by difficulty readjustment. Our results employ the Rational Protocol Design framework of Garay et al. [FOCS’13] and extend recent works on the economic robustness of the Bitcoin backbone protocol to the variable difficulty setting. Notably, our fine-grained specification of miners’ utility incorporates variable difficulty adjustment alongside factors like the average cost of mining and the depreciation factor, which, despite being common in economics, are typically either abstracted as exogenous parameters or ignored in the blockchain literature. We showcase the expressivity and usefulness of our formulation of utilities by using it to provide estimates and trends for such factors across several real-world cryptocurrencies.

The study of digital signatures with tight reductions has attracted considerable attention over the past two decades, as such schemes inherit essentially the same quantitative hardness as the underlying computational problem. In the context of lattice-based cryptography, the GPV approach (Gentry, Peikert, and Vaikuntanathan, STOC ’08) admits a simple tight reduction from the SIS problem, but relies on preimage sampling via trapdoors, which often leads to complex and brittle implementations. By contrast, tight proofs for trapdoor-free constructions, following the Fiat–Shamir paradigm, necessarily rely on decisional assumptions, most notably the decisional LWE assumption. From the perspective of concrete security, however, reliance on a search assumption is preferable, as known search-to-decision reductions for LWE provide only weak quantitative guarantees. This paper presents the first efficient lattice-based signature scheme with a tight reduction to a search assumption (namely, the hardness of the search LWE problem) that does not require any trapdoor in the scheme itself (but merely uses, instead, a trapdoor in the proof). Our construction follows the Fiat-Shamir paradigm and can be viewed as a lattice analogue of Chevallier–Mames signatures (CRYPTO ’05). Establishing security in the lattice setting, however, requires overcoming significant technical obstacles: in particular, our proof develops several new techniques to cope with the inherently weak soundness guarantees of lattice-based interactive proofs.

This paper presents the first blind signature scheme in a pairing-free group with the following properties: (1) the signing protocol consists of only three moves; (2) the proof of one-more unforgeability relies solely on the Decisional Diffie-Hellman (DDH) assumption in the Random Oracle Model (ROM); and (3) the construction makes only black-box use of the underlying group. This resolves a major open problem in the area, as all prior pairing-free blind signatures either additionally relied on the Algebraic Group Model (AGM) or required at least four moves. Moreover, a recent lower bound by Dietz et al. (ePrint, '26) shows that three moves are optimal for such constructions. Both the communication complexity and the signature size in our scheme consist of a constant number of group elements. Our construction in fact achieves strong one-more unforgeability (which was not known for any of the recent AGM-free constructions requiring four moves), and we also present a partially blind variant. Furthermore, blindness is statistical (in the ROM). Our approach is based on a new construction paradigm that combines a conventional (yet, by itself, not fully secure) blind signature scheme (specifically, the blind Okamoto-Schnorr scheme) with a carefully crafted algebraic MAC.

Shuffle differential privacy (shuffle DP) offers an attractive distributed alternative to standard differential privacy. It uses a secure shuffler to permute users' randomized encodings, providing individual data privacy without a central trusted entity. A key challenge, however, is to achieve both generality and client efficiency. Under information-theoretic shuffle-DP guarantees, protocols that nearly match central-model utility are restricted to statistical tasks such as summation and histograms. In contrast, in the computational setting, additive randomized encodings (ARE), introduced by Halevi et al. (CRYPTO 2023), yield a generic compiler that achieves central-model utility for arbitrary mechanisms. However, their construction incurs prohibitive worst-case computation and communication costs for clients, making it impractical for resource-constrained devices such as mobile phones, IoT sensors, and web browsers. In this work, we present a client-efficient one-round compiler from central DP to non-robust computational shuffle DP. To achieve this, we first construct a new balanced ARE scheme, where all the clients almost equally share the computational burden in the protocol. For a mechanism $M$ over $n$ clients, this reduces the worst-case per-client computation from $O(|M|)$ in prior work to $O(|M|/n)$, where $|M|$ denotes the circuit complexity of the mechanism. The key technical ingredient is a new permute-XOR ARE primitive that enables wire splicing across independently generated garbled subcircuits. Secondly we design a more efficient ARE-to-shuffle compiler, whose client bandwidth scales with the sparsity and cross-partition structure parameter of the ARE encoding - a quantity that is always sublinear in $n$. This is an improvement over Halevi et al. (CRYPTO 2023) where each client bandwidth is $\Omega(n)$. At a high level, the first contribution improves client computation while the second improves client bandwidth. We provide an implementation of our generic compiler for differentially private tasks including selection, distinct elements, and linear contextual bandits. We obtain shuffle protocols that match the utility of their central-model counterparts with reasonable client overhead. We evaluate our method across a range of practical settings, and observe substantial gains over the compiler of Halevi et al., with per-client computational and bandwidth speedups increasing linearly in the number of clients.

In the private simultaneous message (PSM) setting, $k$ players obtain inputs $x_i\in\{0,1\}^n$ and then independently send messages to a referee, who should learn $f(x_1,...,x_k)$ but no other information about $(x_1,...,x_k)$. The PSM setting was introduced as a minimal model for secure multiparty computation. In the quantum setting, PSM has been related to non-local quantum computation (NLQC), and has several connections to the complexity of Boolean functions. The communication and correlation cost of implementing private simultaneous message passing may be much larger than the cost without privacy, and the cost of privacy in this setting remains poorly understood. Here, we give new upper and lower bounds on the PSM model, in both the quantum and classical settings. Concretely, we prove two lower bounds: 1) Nečiporuk's measure lower bounds the entanglement required for $k$-player quantum PSM with perfect correctness. This can be evaluated to give quadratic lower bounds for some explicit functions. 2) The rank of the communication matrix of $f(x_1,x_2)$ lower bounds 2-player quantum PSM with perfect privacy but imperfect correctness. This implies a previously unknown lower bound on classical PSM with imperfect correctness. When allowing both quantum communication and shared entanglement, these two bounds are the first lower bounds on quantum PSM that make use of the privacy condition. Regarding upper bounds, we show: 1) Letting $s$ be the size of a quantum circuit computing $f$, $d_f$ be the circuit depth, $k$ the number of players, $n$ the number of bits received by each player, and $\epsilon$ the correctness parameter of the PSM protocol, we obtain the upper bound $\mathsf{PSM}_k^*(f) \leq (kn +s) \cdot \log^{O( d_f)}(s/\epsilon)$. 2) The square of the Fourier 1 norm of $f$, $\Vert \hat{f}\Vert_1^2$, upper bounds the classical PSM complexity, $\mathsf{PSM}(f)\leq O(\Vert \hat{f} \Vert^2_1)$. In proving the first upper bound, we also generalize existing $T$-depth based techniques for NLQC from $2$ to $k\geq 2$ parties, and consider cases where the Clifford layers are restricted to having small light cones. These generalizations may be of independent interest.

A private information retrieval (PIR) protocol enables a client to retrieve a bit from an $N$ bit database replicated among $k$ servers in such a way that each server learns no information about the retrieved bit. Modern PIR protocols with information-theoretic privacy (Efremenko, SICOMP, 2012; Dvir and Gopi, STOC, 2015; Ghasemi et al., STOC, 25) are based on matching vectors over a composite number $m$. To construct a PIR protocol from the matching vectors, these protocols use a decoding polynomial, a sparse polynomial that returns a non-zero value on 1 and returns zero on a certain set implied by the matching vectors. Beimel et al. (CCC, 2012) abstracted the properties required by the transformation computed by the decoding polynomial, defining the notion of share conversion. In such a conversion, a set of parties is given shares of a secret in one secret-sharing scheme, and each party locally computes a new share (without any communication) such that the new shares are shares in a second secret-sharing scheme of a related secret. Beimel et al. showed that share conversion can replace the decoding polynomial in the PIR protocol of Efremenko and constructed a share conversion from the ring $\mathbb{Z}_6$ to the field $\mathbb{F}_{2^2}$. This share conversion cannot be computed by a decoding polynomial, as decoding polynomials convert shares from a ring $\mathbb{Z}_m$ to a finite field of characteristic $p$ such that $p$ does not divide $m$. Alon et al. (TCC, 2025) simplified and generalized the PIR protocols of Dvir and Gopi and Ghasemi et al., using share conversion; however, in this protocol, the share conversion is from a ring $\mathbb{Z}_m$ to a finite field of characteristic $p$ such that $p$ does not divide $m$. In this paper, we study the power of share conversions. Our main result proves that if there is a $k$-party share conversion from a ring $\mathbb{Z}_m$ to a finite field of characteristic $p$ such that $p$ does not divide $m$, then there is a $k$ sparse decoding polynomial from a ring $\mathbb{Z}_m$ to a finite field of characteristic $p$. This result implies that using share conversion in the protocol of Alon et al. can only improve the communication complexity by a constant factor. In addition, we show that if there is a $k$-party share conversion from a ring $\mathbb{Z}_m$ to a finite field, where $m$ is a product of $r$ distinct primes, then $k\geq r+1$, i.e., the number of servers in the resulting PIR protocols using the appropriate matching vectors is at least $r+1$. A similar result was recently proved by Ghasemi and Kopparty (ITCS 26); our lower bound also applies to the case in which the characteristic of the field divides $m$.

We introduce the Huffman-Merkle Tree (HMT), an authenticated data structure (ADS) optimized for dynamic workloads where some items may be more frequently accessed than others, and access frequencies change over time. An ADS allows proving item membership against a short commitment to a large mutable state, with applications including verifiable storage, Internet transparency services, and blockchains. Optimizing ADS performance under continuously changing access frequencies has not been fully addressed before, neither in theory nor in practice. HMT tackles access skew via tiering: "hot" items are stored according to a Huffman coding layout where frequently accessed items are closer to the root and thus contribute less to overall costs, while a binary Merkle Tree (MT) is used for cold and new elements to lower their update overhead. To efficiently handle dynamic workloads, we incrementally apply and batch layout changes, track access frequencies via count-min sketch, use a tier promotion cache, and consider various tier migration policies. We implement HMT and compare it on real-world data against Ethereum's Merkle Patricia Trie (MPT) ADS and its proposed replacement, the Unified Binary Tree (UBT). Our evaluation considers two metrics: the amount of hashing per ADS update and access-weighted membership-proof size. The latter metric captures both the cost of accessing each item and its access frequency. We find that the best HMT policy uses about 2.4x and 0.34x less average hash operations than MPT and UBT respectively, while featuring proofs shorter by 0.18x than MPT and 0.55x than UBT.

Modern consensus protocols often aspire to be responsive---that is, to confirm transactions in time proportional to the actual network delays as opposed to a (typically much larger) worst-case bound on network delays. Responsiveness can yield substantial practical improvements in both protocol latency and throughput. In blockchain settings, however, block proposers commonly have economic incentives (most notably MEV) to delay their blocks, a phenomenon repeatedly observed in practice, e.g., in the block production supply chains for Ethereum and Solana. Such incentives clash with responsiveness in existing protocol designs. This paper develops a rigorous framework for designing incentive-compatible responsive consensus protocols. We first consider the canonical case of single-leader protocols and establish feasibility results characterizing the conditions on the distribution of network latency under which responsiveness can be incentivized through a suitable reward function. We further quantify the amount of stake required from the leader to deter dishonest delays. We then show strong positive results for protocols with multiple leaders, demonstrating that the multi-leader approach is fundamentally superior to single-leader designs for resolving the tension between responsiveness and incentive-compatibility: by forcing leaders to compete for rewards, much of the burden otherwise placed on the incentive mechanism is alleviated. Notably, this results in simpler reward mechanisms with no stake requirements that also remain feasible in parameter regimes which are provably impossible under a single leader.

In this paper, we demonstrate a way to generalize learning with errors (LWE) to the family of so-called modular-maximal cyclic groups which are non-commuting. Since the group $\mathbb{M}_{2^t}$ has two cycles of maximal multiplicative order, we use this fact to construct an accurate criterion for restoring the message bit with overwhelming probability. Furthermore, we implement the original idea by O. Regev in the considered group to gain benefits from the non-commutativity of $\mathbb{M}_{2^t}$. Also we prove that using this approach we can achieve a level of security comparable to the original idea.

Oblivious map (OMAP) is a fundamental primitive for encrypted databases, yet existing designs largely adhere to a uniform worst-case principle: every record incurs nearly the same time to retrieve, regardless of how often it is queried. Real-world workloads, however, are typically highly skewed, with a small hot set accounting for most requests. We argue that such skewness should be leveraged as a first-class design signal for oblivious retrieval, rather than treated solely as leakage to conceal. We present TieredOMap, the first skewness-aware framework for OMAP, opening up a new design space for improving OMAP efficiency. TieredOMap separates hot and cold records into separate and independent OMAPs to enable more efficient access to hot records without weakening the security guarantees of standard OMAPs. Moreover, its design naturally supports further performance gains under a small, explicit relaxation of security. To make TieredOMap more practical, we also develop a complete mechanism to support dynamic workloads with evolving hot sets. Overall, our results show that oblivious accesses to records need not be governed solely by uniform worst-case behavior, and that skewness-aware structure represents a promising new direction orthogonal to existing OMAP design principles.

Post-Quantum Cryptography (PQC) and Quantum Key Distribution (QKD) are both contenders for securing communication against quantum adversaries, but are at different stages of maturity. For hedging security risks, hybridization is the default approach. Unlike previous research on classical–post-quantum hybrids, we propose a QKD-PQC hybrid for Authenticated Key Exchange (AKE). To minimize the attack surface, we completely remove the requirement for digital signature schemes and propose a Hybrid Authenticated Key Exchange (HAKE) that combines Post-Quantum (PQ) AKE and QKD key agreement, leveraging Key Encapsulation Mechanisms (KEMs) for both key exchange and authentication. Our fully modular security analysis, based on the recent multi-input Key Derivation Function (KDF) framework by Backendal et al. (Eurocrypt 2025), establishes AKE security in the CK01 model and yields a conditional information-theoretic security guarantee when the QKD component is uncompromised; a property not achieved by prior hybrid protocols. We demonstrate the protocol’s practical feasibility with benchmarks using ML-KEM, FrodoKEM, and Classic McEliece.

Heterogeneous computing platforms increasingly rely on high-throughput data paths spanning CPUs and accelerators, yet most high-speed software ciphers are optimized primarily for CPU-centric execution models. We present AICE, an arithmetic-oriented stream cipher over \(\mathbb{Z}/2^{16}\mathbb{Z}\) with a 37-word (592-bit) internal state, a nonlinear feedback combining modular addition, multiplication, bitwise OR, and rotation, a 370-round initialization with post-initialization key feed-forward, and periodic blank updates. We analyze AICE under several cryptanalytic models, including differential trail screening, linear approximation over the abelian group \(\mathbb{Z}/2^{16}\mathbb{Z}\), guess-and-determine state recovery, and exact SMT-based cube evaluation, and find that all observable structural phenomena remain confined to reduced-round settings far below the full initialization. On the AI Cores of Huawei Ascend accelerators, AICE reaches a single-core peak throughput of $114.13$ Gbps on the Ascend 950 and $55.36$ Gbps on the Ascend 910B4, and scales to $1.59$ Tbps on $32$ Ascend 910B4 cores, roughly $54\times$ the throughput of AES-CTR and $107\times$ that of SM4-CTR on the same $32$-core configuration; on the ARM Kunpeng 920 it remains in the same throughput class as hardware instruction accelerated AES-CTR.

We study error correction in a computationally bounded world, where errors are introduced by an arbitrary polynomial-time adversarial channel. Recent works construct seeded codes in this model, where the encoding and decoding procedure share a public random seed. They achieve significantly better tradeoffs between rate and error tolerance than what is possible information theoretically for unique decoding, essentially matching the parameters of the best known efficiently list-decodable codes. Over the binary alphabet, however, this is still well short of the optimal Shannon capacity with rate $R \approx 1 - H_2(p)$ for a $p < 1/4$ fraction of errors. Even heuristic constructions meeting this target were not previously known. We make progress towards this goal. - $\textbf{Secret-Key Codes.}$ We first study secret-key codes, where the encoder and decoder share a secret key hidden from the adversarial channel. Lipton (STACS '94) constructed one-time secure secret-key codes achieving Shannon capacity in this setting, but it was unknown whether one can get CPA (resp. CCA) security where the adversary may query an encoding oracle (resp. also a decoding oracle). We construct CCA-secure secret-key codes achieving Shannon capacity via pseudorandom codes (PRCs). - $\textbf{Seeded Codes (Heuristic).}$ We can heuristically upgrade the resulting secret-key codes to seeded codes by publishing an obfuscation of the encoding/decoding procedures with a hard-coded secret key as a seed. Security holds in the ideal obfuscation model. - $\textbf{Public-key Codes.}$ We also consider public-key codes, where the decoder has a secret key and the encoder has the corresponding public key. We construct such CPA-secure public-key codes achieving Shannon capacity with unique decoding for $p < 1/4$ errors, and list decoding all the way to $p < 1/2$ errors, assuming PRCs and the subexponential security of standard crypto assumptions (e.g., LWE or DDH or QR or DCR). We also show how to get CCA security in the random oracle model. Our secret-key and public-key codes meeting Shannon capacity are also simultaneously pseudorandom codes.

Pseudorandom codes (PRCs) are error-correcting codes whose codewords are computationally indistinguishable from uniform random strings, a primitive motivated by the need to robustly watermark generative AI models. While recent breakthroughs have established the feasibility of PRCs, critical challenges remain regarding the diversity of their underlying cryptographic assumptions and their security against active adversaries. This work advances the study of PRCs on two complementary fronts: structural diversity and advanced security. On the structural side, we propose a novel PRC template that departs from the prior one based on sparse parity-check trapdoors. We introduce a new LPN-type assumption, formalized as Dense-Planted LPN, which postulates $(\mathbf{M}\mathbf{T}, \ \mathbf{M}\mathbf{T}\mathbf{s}+\mathbf{e})\ \approx_c\ (\mathbf{M}\mathbf{T}, \ \mathbf{u})$, where $\mathbf{T}$ is a random dense matrix and $\mathbf{M}$ is sampled from a distribution containing a planted structure. This hidden structure enables a completely new decoding mechanism based on a local-window search rather than global parity checks. Notably, this template provides a viable path toward constructing PRCs from assumptions beyond code-based ones, including Learning with Errors (LWE) assumptions. On the security side, we construct the first public-key PRC secure against pre-challenge chosen-codeword attacks (CCA1) in the standard model. In realistic watermarking deployments where detectors are exposed as public services, CCA security is essential. However, prior CCA-secure PRCs were only achievable in the random oracle model. By formally introducing and instantiating a robust tag-based equivocal bit commitment scheme combined with robust hinting PRGs, we demonstrate that CCA1 security can be achieved in the standard model without sacrificing decoding robustness.

Pseudorandom codes (PRCs), recently proposed by Christ and Gunn (CRYPTO'24), are encryption schemes that have pseudorandom ciphertexts and a decryption algorithm which is resilient against a bounded number of Hamming errors. This notion provides a significant strengthening over standard PKE and has exciting applications in, e.g., watermarking LLMs. The recent work of Alrabiah et al. (STOC'25) initiated the study of CCA-secure public-key PRCs, where the adversary is additionally given access to a decoding oracle. In terms of realizations, they provide one that can be proven secure in the random oracle model. Constructing CCA-secure public-key PRCs in the standard model remained an open problem. In this work, we resolve this problem and provide the first construction of CCA-secure public-key PRCs in the standard model. Our construction achieves a constant rate and can decode from a constant fraction of adversarial errors. In fact, our construction is a general blueprint that can be instantiated from a broad range of standard cryptographic assumptions. As an additional contribution, we construct a strong adaptively robust public-key pseudorandom code with conjectured sub-exponential security based on a new family of assumptions we call Noisy McEliece. In a nutshell, these assumptions mask a scrambled generator matrix from an efficiently decodable inner-code family with sparse Bernoulli noise; this additional error is meant to obscure the algebraic structure targeted by known attacks and thereby permits candidate instantiations from broader classes of codes.

Masking stands as one of the most effective countermeasures against side-channel attacks. While a number of recent works have investigated first-order masking schemes that eliminate the need for fresh randomness, most existing solutions trade off this randomness reduction against increased latency or area overhead. This paper targets the simultaneous achievement of low latency and zero fresh randomness. To this end, we make the following contributions. First, we identify a security flaw in the round-based design proposed by Askeland et al.\ at CARDIS 2022, which builds upon the Changing of the Guards (COTG) technique. Second, we propose a revised construction that rectifies this vulnerability without incurring any additional randomness or latency penalty. Finally, by integrating the Time Sharing Masking (TSM) S-box introduced at CHES 2025, we present a first-order masked AES implementation with a latency of 20 clock cycles that requires no fresh randomness.

This work proposes StakeNote, a distributed ledger protocol that combines Proof-of-Stake (PoS) with privacy and anonymity preserving payments. The protocol combines Ouroboros Praos, a provably secure PoS protocol, with CryptoNote, a privacy-preserving payment system based on ring signatures which has been widely used in practice. We prove that StakeNote inherits the security guarantees of Ouroboros Praos and the privacy guarantees of CryptoNote and we demonstrate its practicality via a proof of concept implementation, where block creation requires less than 25 ms and eligibility proofs are approx. 3 KB for anonymity sets of size 16. Finally, we discuss heuristic enhancements that potentially increase privacy and enable dynamic participation.

In KEM-based TLS 1.3 key establishment, the client generates a fresh KEM key pair for each connection, placing key generation on the handshake critical path. For NTRU+, a KEM based on the NTRU problem selected in the Korean Post-Quantum Cryptography (KpqC) competition, the dominant cost in this path is the polynomial inversion needed to compute the public key. Although NTRU+ uses an NTT-friendly ring and performs this inversion in the NTT domain, the routine still decomposes into many base inversions, each requiring a modular inversion computed by exponentiation. To accelerate polynomial inversion in the NTT domain, we collect the modular inversions arising from base inversions into a single stage. This makes it possible to apply Montgomery's trick, reducing the number of modular inversions to one at the cost of sequential product and recovery chains. These chains limit instruction-level parallelism (ILP). To address this dependency bottleneck, we apply hierarchical batching to these exposed denominator inversions, splitting the inputs into $k$ groups to expose independent product chains and recursively batching the resulting $k$ group-product inversions. This preserves the arithmetic cost of Montgomery's trick while improving ILP, thereby reducing cycle counts. We evaluate hierarchical batch inversion across all NTRU+ parameter sets in both C and AVX2. For NTRU+$864$, the parameter set with the largest gains, compared with non-batched polynomial inversion, it reduces polynomial inversion latency by 48.91% in C and 59.57% in AVX2. For key generation, the corresponding speedups are 18.91% in C and 9.34% in AVX2.

Blockchain consensus protocols, also known as BFT state-machine replication, enable a system of $n$ players to decide an ever-growing chain of blocks. We consider partial synchrony: after an unknown time GST, messages sent by honest players are delivered within an unknown actual delay $\delta$, and a known bound $\Delta$ satisfies $\delta \leq \Delta$. This setting imposes $t<n/3$ corruptions. We study leader-based consensus, a class with the smallest known latency metrics when sufficiently many designated leaders behave honestly. We consider the mainstream metric of {expected latency in the view-based sense:} for a transaction known to all honest players having entered a post-GST iteration, this is the expected time until that transaction appears in a decided block, under independent random leaders. We introduce Hamster, a rotating-leader consensus protocol, which reduces this expected latency to $\Delta+4\delta$, down from the previous $1.5\Delta+3.5\delta$ bound achieved by Simplex (Chan-Pass, TCC'23) for the same view-based metric. Hamster also brings this latency further down to $\Delta+3.5\delta$ for adversaries that do not get publicly caught equivocating. The main technical novelty is a certificate of exclusivity for a block $B$. It is shown by the next leader as evidence that players can safely vote for a child of $B$. A certificate of exclusivity is an interpolation between a quorum certificate and a timeout certificate, in that it is formed from a mix of votes for a unique block $B$ and complaint votes, proving that $B$ is the only non-dummy block that can still obtain a decision certificate for that iteration. The other novelty of Hamster is the use of {overlapping iterations: after a process has supported a newer proposal, the protocol may still allow it to support a safe proposal of an earlier iteration}. This overlap is what allows old honest proposals to be decided in time despite players advancing iterations faster. We also analyze another metric, called the {pessimistic block proposal time}, which is the time during which a bad leader can delay the proposal of a transaction in a block which will be decided. Hamster achieves a pessimistic block proposal time of $2\Delta+2\delta$, refined to $2\Delta+\delta$ for leaders not caught equivocating, down from $3\Delta+\delta$ for Simplex.

Emerging attacks and applications have motivated the development of transforms that turn a given AE scheme into a committing AE (cAE) one. We give a new transform called UCX with the following attributes: It does not require the starting scheme to be tag based, works for schemes in the broad AE5 framework rather than the limited AE1 one, and preserves both UNAE (Unique Nonce AE) and MRAE (Misuse Resistant AE) security. No prior transform is ``universal'' in the sense of having the combination of all these properties. The use of UCX in place of prior, limited transforms reduces the risk of error and failure in the real world, where choices may be made by application developers and hidden in software libraries. The committing security of UCX is shown in the ideal-cipher model, and its AE5-security in the standard model. To design UCX, we introduce and build a new primitive, that we call a Tweakable Committing Concealer, and that may be of independent interest.

The block cipher (BC) mode for realizing a variable-input-length strong tweakable pseudorandom permutation (VIL-STPRP), also known as the accordion mode, is a rapidly growing research field driven by NIST's standardization project, which considers AES as a primitive. Widely used VIL-STPRP modes, such as HCTR2, have birthday-bound security and provide only 64-bit security with AES. To provide higher security, NIST is considering two directions: to develop new modes with beyond-birthday-bound (BBB) security and to use Rijndael-256-256 with HCTR2. This paper pursues the first direction while maintaining compatibility with HCTR2. In particular, we provide two solutions to achieve BBB security for two different approaches: (i) general cases without any conditions on the tweak and (ii) under the condition that the same tweak is not repeated too often as adopted in bbb-ddd-AES recently presented at Eurocrypt 2025. For the first approach, we propose a new mode, CHCTR, that iterates HCTR2 with two independent keys, which achieves $2n/3$-bit security in the multi-user (mu) setting and satisfies NIST's requirements. For the second approach, we prove mu security of HCTR2, which allows us to apply the tweak-based key derivation (TwKD) to HCTR2 in a provable manner. When the number of BC calls processed by a single tweak is upper-bounded by $2^{n/3}$, HCTR2-TwKD achieves $2n/3$-bit mu security. By benchmarking optimized software implementations, we show that CHCTR with AES-256 outperforms HCTR2 with Rijndael-256-256, in all the twelve processor models examined. Similarly, HCTR2-TwKD outperforms bbb-ddd-AES in general cases, and it is even comparable to bbb-ddd-AES rigorously optimized for tweak-repeating use cases using precomputation.

The eSIM specification enables remote SIM provisioning without the need to hand out a physical SIM card. Instead of a physical SIM card, the subscriber downloads a SIM profile, which contains a subscriber's identity and authentication key material, to their embedded UICC, a discrete, embedded chip in the user's phone. This provisioning process is specified in the remote SIM provisioning (RSP) protocol and is secured through contemporary public-key cryptography. However, the potential advent of general-purpose quantum computers threatens the security of RSP. This paper provides a quantum threat analysis of the RSP protocol, considering both Harvest Now, Decrypt Later attacks and active quantum attacks. To alleviate this threat, this paper introduces PQC-RSP, a post quantum secure version of the RSP protocol. The main challenge we address is the introduction of key encapsulation mechanisms (KEMs) into the RSP protocol, both in a PQC-only and hybrid version, and the security implications of this modification. We prove the security of PQC-RSP and review the performance overhead introduced through the usage of post quantum cryptography.

Achieving (at least) a worst-case correctness error is essential for an underlying public-key encryption (PKE) scheme to which the Fujisaki-Okamoto (FO) transformation is applied. There are three average-case to worst-case (ACWC) transformations—denoted as $\mathsf{ACWC}_{0}$, $\mathsf{ACWC}_{1}$ (PKC 2023), and $\mathsf{ACWC}_{2}$ (TIFS 2023)-which generically convert a PKE scheme with an average-case correctness error into one with a worst-case correctness error. However, in these ACWC transformations the $\gamma$-spreadness, a critical factor in determining explicit rejection ($\mathsf{FO}^{\perp}$) or implicit rejection ($\mathsf{FO}^{\not\perp}$), has not been established with rigorous proofs. Existing analyses of $\gamma$-spreadness lack rigorous proofs, include analytical flaws, or fail to achieve the tightest possible bounds. In this work, we reprove the $\gamma$-spreadness of ACWC-transformed PKE schemes by leveraging two key facts: the random oracle is chosen at random and the encoding mechanism used in the ACWC framework is message-hiding. Our new proofs are applied to the previous NTRU-based PKE schemes, called $\mathsf{NTRU}\mbox{-}\mathsf{C}$, $\mathsf{NTRU}\mbox{-}\mathsf{B}$, and $\mathsf{NTRU+}$, giving the corrected $\gamma$-spreadness for those PKE schemes with concrete parameters.

Byzantine atomic broadcast (ABC) is at the heart of permissioned blockchains and various multi-party computation protocols. We resolve a long-standing open problem in ABC, presenting the first information-theoretic (IT) and signature-free asynchronous ABC protocol that achieves optimal $O(n^2)$ messages and $O(1)$ expected time. Our ABC protocol adopts a new design, relying on a reduction from---perhaps surprisingly---a somewhat neglected primitive called multivalued Byzantine agreement (MBA).

We initiate the study of arithmetic private information retrieval (APIR) schemes, in which the database is a vector of field elements and the scheme makes a black-box use of the field. We obtain the following results. 1. Our main result is a negative one: We show that no single-server APIR scheme can achieve non-trivial download cost smaller than $n$ field elements. We observe that recent proposals for code-based PIR (Holzbaur et al., ISIT'20; Verma and Hollanti, ISIT'24) are arithmetic, and show how to break them within a few minutes on a standard workstation for all suggested parameters. 2. We complement the above by positive results in alternative models. Concretely, we show that with either two servers or a single server with secret-key preprocessing, it is possible to construct computationally secure APIR schemes based on well-studied coding assumptions. This is achieved by arithmetizing the distributed-point-function-based PIR of Boyle et al.(CCS'16), and by observing that the recent construction of secret-key single-server PIR by Chen et al.(STOC'26) also arithmetizes. 3. Finally, we characterize the existence of information-theoretic two-server APIR schemes in linear-algebraic terms, and show that communication of $O(n^{1/3})$ can be achieved in this setting based on the original approach of Chor et al.(FOCS'95). The optimality of this result remains an interesting open question.

This document provides a machine-checked Isabelle/HOL formalisation of the modular-arithmetic core of the Neon NTT paper of Becker, Hwang, Kannwischer, Yang, and Yang. We develop parametric theories of Barrett and Montgomery reduction and multiplication; the equivalence of Barrett and Montgomery arithmetic; the doubling- and rounding-Montgomery variants; and correctness and bounds theorems for Neon assembly kernels, against a hand-written model of the word arithmetic underlying the relevant Neon instructions. The development is a directed auto-formalisation: definitions, theorem statements, and proofs were produced by Claude Opus 4.7 and 4.8 using AutoCorrode's LLM-Isabelle integration layers. The human author set the architecture, chose abstractions and proof strategies, often nudged the model toward shorter or cleaner proofs, and controlled which output entered the development. This document is auto-generated from the Isabelle sources through Isabelle’s document preparation system, eliminating drift between prose and formal artifact.

Depth-robust directed acyclic graphs (DAGs) are an important combinatorial primitive in cryptography, with applications to memory-hard functions, proofs of space, and proofs of sequential work. These applications require node depth-robustness, yet constructing sparse graphs with strong concrete guarantees remains a longstanding challenge. By contrast, edge depth-robust graphs are easier to construct explicitly and achieve better parameters, motivating the problem of efficiently transforming edge-depth-robust graphs into node-depth-robust graphs. We give a new and substantially more efficient transformation from edge-depth-robust graphs to node-depth-robust graphs. We give a new and substantially more efficient transformation from edge-depth-robust graphs to node-depth-robust graphs. Prior work of Blocki and Cinkoske (ITCS 2021) gave a general transformation by replacing each node with an ST-robust graph, resulting in extraordinarily large overhead and relying on non-explicit components. In contrast, our transformation replaces each node with a single superconcentrator rather than an ST-robust graph, yielding an explicit construction whenever the input graph is explicit, with dramatically improved concrete efficiency. Formally, given an $(e,d)$-edge-depth-robust graph $G$ with $N$ nodes and $m$ edges, our transformation generates a graph $G'=Transform(G_N)$ with $N' = O(m)$ nodes, constant indegree, and $(e/3,\, 2d-1)$-node depth-robustness. We also show that the transformation preserves fractional depth-robustness. Moreover, when $m=\omega(N)$, we show that our transformation can amplify depth --- overcoming a key limitation of prior work. In particular, for any parameter $d'$, we can obtain a constant-indegree graph $G'$ with $N' = O(m+d'N)$ nodes and $(e/3,\, (d-e)d')$-node depth-robustness, yielding asymptotically tighter results in the important setting where $m = \omega(N)$ and $e \geq d$ by setting $d' \sim m/N$. As an application, We provide a novel analysis of Schnitger's edge-depth-robust graph construction (FOCS 1983). We show that the graph $G_n$, which has $N=2^{n+1}-1$ nodes and $m \leq n2^{n}$ edges, is $(e,2d-1)$-edge-depth robust for all $e + d \leq 2^n$. Applying our transformation yields an explicit DAG on $N'$ nodes with maximum indegree $2$ and depth-robustness parameters $e = \Omega(N'/\log N')$ and $d = \Omega(N')$, matching the best known asymptotic trade-offs—even compared with non-explicit constructions—while improving the best previously known concrete ed-product lower bound by a multiplicative factor of 6.6.

Niederreiter-style post quantum cryptosystems based on QC-MDPC codes, such as BIKE, have shown promising efficiency figures and enjoy a straightforward reduction to conjectured-hard problems in coding theory. The longstanding issue in their design is having a closed form Decoding Failure Rate (DFR) analysis of the iterative decoder employed by their decryption primitive, as decoding failures leak information on the private key. State of the art models either provide loose bounds, or do not consider the decoding algorithm employed in practice, using the behavior of a simpler one as a proxy. In this work, we provide a closed-form estimate of the DFR for the practically employed three-iterations parallel decoder, applied to QC-MDPC codes. This result constitutes the first closed form DFR model targeting both the same code family and the same decoder employed in the cryptosystem. Leveraging our estimation technique, we design the parameters for a QC-MDPC based Niederreiter encryption scheme, obtaining a $2\times$ improvement in public key and ciphertext size w.r.t. the previous best cryptosystem design with DFR closed-form bounds, LEDAcrypt-KEM. Furthermore, we show that our new parameters yield up to $30$% smaller public key size and $2.2\times$ to $4.4\times$ smaller ciphertexts w.r.t. HQC, the code based key encapsulation method selected by the US NIST for standardization, and achieve up to $3\times$ speedup with respect to BIKE in ephemeral and long-term key usage.

We introduce WayFinder, a framework for generalizing the Delfs-Galbraith and SuperSolver algorithms for the supersingular isogeny problem. Our framework extends the search for elliptic curves with an orientation by an order containing $\mathbb{Z}[\ell \sqrt{-p}]$ to more general orders, and we derive a cost model for such generalisations. Our cost model not only works in a more general context, but also provides more accurate predictions when applied to SuperSolver. We instantiate WayFinder for orders containing $\mathbb{Z}[\ell_1\sqrt{-\ell_2p}]$ where $\ell_i$ are $1$ or primes such that the modular curve $X_0(\ell_2)$ has genus $0$. We then introduce a low-storage algorithm for computing an isogeny between two oriented supersingular elliptic curves, even when the curves are oriented by distinct orders. Together, these provide an algorithm that improves on the state of the art for solving the isogeny problem, and a cost model with potential applications to parameter selection in isogeny-based cryptography.

European Digital Identity (EUDI) Wallet aims to provide end users with a way to get attested credentials from issuers, and present them to different relying parties. An important property mentioned in the regulatory frameworks is the possibility to revoke a previously issued credential. While it is possible to issue a short-lived credential, in some cases it may be inconvenient, and a separate revocation service which allows to revoke a credential at any time may be necessary. In this work, we propose a full end-to-end description of a generic credential revocation system, which technically relies on a single server and secure transmission channels between parties. We prove security of the proposed revocation functionality in the universal composability model, and estimate its efficiency based on a proof-of-concept implementation.

We study frequency estimation in the shuffle model of differential privacy under poisoning attacks, where corrupted users may deviate from the local randomizer to inject crafted in-domain messages. Existing shuffle-model protocols face a core tension: achieving low estimation error relies on flexible multi-message noise generation, which can amplify poisoning influence once messages are anonymized by shuffling. To address this tension, we propose a symmetric binomial-sum noise distribution (i.e., $\mathrm{Bin}(n/2,p) + \mathrm{Bin}(n/2,1-p)$), which preserves high accuracy while limiting the impact of crafted in-domain messages. We realize this distribution via preprocessing-guided noise generation, which routes a balanced collection of mode flags through the shuffler so that each user receives a randomly assigned mode flag that fixes their noise-sampling behavior prior to shuffling. For binary estimation, our protocol requires a single Bernoulli trial per user and at most $2$ messages per user ($1.5$ on average), while bounding the worst-case poisoning influence of a single corrupted user by $O(1/n)$. We extend the protocol to histograms, including large domains via hashing, and provide formal privacy, accuracy, and robustness guarantees. Experiments on real datasets show that our protocols remain resilient under poisoning and reduce MAE by up to nearly $2\times$ over the strongest baseline at comparable per-user communication on small-domain workloads, and stay on par with it on large domains.

Key encapsulation mechanism (KEM) is an often used primitive in communication, closely related to public key encryption (PKE). Dual-receiver encryption (DRE) is another primitive closely related to PKE that allows a sender to encrypt a message to two different receivers. Most applications of DRE need the soundness property which guarantees that both receivers decrypt any ciphertext to the same message. Addition ally, IND-CPA security is often not enough and therefore schemes should satisfy a stronger notion like IND-CCA2. Meanwhile, an alternative to IND-CCA2 for KEMs is the IND-SB-CPA security notion which was proven to be strong enough to realize secure channels while in theory enabling the construction of more efficient schemes. Most IND-CCA2 security proofs rely on the FO transformation, which is only secure in the ROM, and the standard model DREs and KEMs are far from efficient. We fill this gap by providing a sound DRE and a KEM satisfying IND-CCA2 and IND-SB-CPA security respectively. Both schemes are based on RLWE, proven secure in the standard model, and have key sizes of 150 KB and ciphertext sizes of 100 KB, improving upon previous results by a factor of 10x to 100x.

Permissionless consensus enables parties to perform Byzantine agreement without any a priori knowledge about who is participating, except for an upper bound on the number of participants running the protocol (no PKI, etc.). Since Nakamoto’s Bitcoin paper, it has been widely believed that permissionless consensus is feasible provided the (Byzantine) adversary only controls a fraction of the collective computational power. However, all known protocols, including Nakamoto’s, rely on idealized assumptions (or ad hoc instantiations). Is permissionless consensus possible without such assumptions? Surprising little progress had been made towards solving this open question until the recent result by Ball et al. (Crypto 2024), which showed how to achieve permissionless consensus from proofs of work (PoWs) based on fine-grained complexity assumptions in a setting where a randomness beacon is available to all parties running the protocol. Their work left open whether it is possible to remove the beacon assumption; this question is the focus of our work, which we resolve via a new consensus protocol construction that relies on a novel class of distributed samplers and a common random string (that does not need to be structured or sampled precisely at the onset of the protocol execution). To prove our protocol secure, we revisit the concept of distributed samplers and adapt it to a setting where multiple sampler executions need to be simultaneously secure. To address this challenge we introduce the primitive we call d-wise independent distributed samplers and put forward constructions for such samplers based on DDH and LWE. We then present our consensus protocol via a modular design that utilizes a new moderately hard cryptographic primitive we call multi-verifier signatures of work, a sort of “time-based signature” we construct by composing distributed samplers and (fine-grained complexity-based) PoWs, and which may be of independent interest.

Secure multiparty computation (MPC) allows distrusted parties to jointly evaluate a common function while keeping their inputs private. In this work, we focus on improving the communication complexity of information-theoretic asynchronous MPC with optimal resilience ($t < n/3$). The current state-of-the-art work in this setting by Goyal, Liu-Zhang, and Song [Crypto’24] achieves amortized linear communication per gate with $\Omega(n^{14})$ elements additive overhead. In comparison, the best-known result in the synchronous setting by Goyal, Song, and Zhu [Crypto’20] achieves the amortized linear communication per gate with only $\mathcal{O}(n^{6})$ elements additive overhead, revealing a significant gap that we aim to close. This work closes this gap and goes further. We present the first statistically secure asynchronous MPC protocol achieving amortized linear communication per gate with only $\mathcal{O}(n^{5})$ elements additive overhead assuming a functionality for Agreement on Common Set (ACS). With the best-known instantiation for ACS, we obtain an asynchronous MPC protocol in the plain model with additive overhead $\mathcal{O}((\kappa+n)n^4\log\kappa)$ elements in expectation, where $\kappa$ is the security parameter. In the setting of statistical security with optimal resilience, this even surpasses the best synchronous result when $n\geq\sqrt{\kappa\log\kappa}$. Technically, our contributions include (i) a new protocol for generating Beaver triples with linear communication per triple and $\mathcal{O}(n^3)$ elements additive overhead assuming functionalities for generating random degree-$t$ Shamir sharings and ACS, and (ii) a new protocol for generating random degree-$t$ Shamir sharings with linear communication per sharing and $\mathcal{O}(n^{5})$ elements additive overhead assuming a functionality for ACS.

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

A Private Information Retrieval (PIR) scheme allows a client to retrieve data from a database hosted on a remote server without revealing which location is being accessed. In Doubly-Efficient PIR (DEPIR), the server preprocesses the database offline into a data structure that enables it to answer any client query in sublinear time with respect to the database size $N$. The breakthrough work of Lin-Mook-Wichs (STOC’23) presented the first DEPIR construction from the Ring-LWE assumption. This remains essentially the only known construction to date, and realizing DEPIR from alternative foundations, particularly from plain LWE, has remained elusive. In this work, we present a simple LWE-based construction of DEPIR in the CRS model. Our construction is inspired by SimplePIR (USENIX’23) and leverages the matrix–vector multiplication preprocessing of Williams (SODA’07). While our construction is only barely doubly-efficient, with server computation of $o(N / \log{N})$, it was previously unknown whether even such modest sublinear efficiency could be achieved from unstructured, plain LWE.

Classically testing for the presence of anti-commuting operators on a quantum device is a critical tool underpinning recent progress in classical verification of quantum computation. While such tests can be based on cryptographic assumptions, known constructions rely on highly structured assumptions, e.g. trapdoor claw-free functions. In this work, we seek to explain this state of affairs by constructing strong cryptography from (certain forms of) classical tests of anti-commutation. In particular, we formulate the notion of a test of non-commutation (ToNC), an interactive protocol between a quantum prover and classical verifier in which the prover's final-round response is obtained by measuring one of two binary observables 𝑃₀, 𝑃₁ depending on the verifier's challenge bit 𝑐. We prove that, for a broad range of parameters, ToNC implies classical-communication key agreement (KA), and ToNC combined with one-way functions implies oblivious transfer (OT). Along the way, we develop tools for and provide the first known results on hardness amplification for post-quantum KA and OT, where communication is classical but adversaries may be quantum. In particular, we prove the following results of independent interest. - Post-quantum hard-core measure theorem: For any efficiently sampleable high-min-entropy distribution 𝐷 over pairs (𝑥,𝑏) such that quantum circuits have advantage at most 𝛿 in predicting 𝑏 from 𝑥, there exists a sub-distribution 𝑀≼𝐷 of density 1-𝛿 on which 𝑏 is nearly optimally quantum-hard to predict. - Post-quantum interactive XOR lemma: Given any classically-interactive protocol, if quantum adversaries have advantage at most 𝛿 in guessing a private challenger bit 𝑏, then two sequential repetitions reduce the advantage for predicting the XOR of the challenger bits 𝑏₁⊕𝑏₂ to at most 𝛿² + negl(𝜆).

In addition to anonymity and traceability, which are the primary security properties of group signatures, non‑frameability is also defined (Bellare-Shi-Zhang, CT-RSA 2005). This property guarantees that even an adversary colluding with all authorities (the opener and the issuer) cannot produce a signature that frames an honest user, and it is regarded as a security notion that protects users. In this short note, we introduce a new perspective on non-frameability, namely that it can also protect the authorities, and we examine its significance in the context of anonymous auctions, a well‑known application of group signatures. We show that non-frameability serves as an effective countermeasure against situations in which a winning bidder falsely claims not to have placed a bid and accuses the organizer of forgery.

Federated fine-tuning of Large Language Models via Low Rank Adaptation (LoRA) faces a critical privacy-efficiency trade-off: low-rank factors can leak sensitive data, yet standard secure aggregation is restricted to linear operations. Existing solutions for aggregating matrix products (e.g., $\mathbf{B}_i \mathbf{A}_i$) either sacrifice exactness, depend on a trusted third party, or incur prohibitive costs at scale. We present SecLoRA, the first decentralized framework achieving exact aggregation of LoRA updates with linear communication complexity. The core of SecLoRA is a novel cryptographic primitive: Pairwise Composable Multi-Client Functional Encryption (PC-DMCFE). Unlike traditional functional encryption, which treats ciphertext recombination as an attack, the dual-encryption architecture of PC-DMCFE ($\mathsf{Enc}_A, \mathsf{Enc}_B$) is intentionally designed to harness this property. It allows any ciphertexts $\mathsf{ct}_A$ and $\mathsf{ct}_B$ to be arbitrarily paired and evaluated via a functional key to reveal their inner product. This unique property enables secure and decentralized aggregation of matrix products without losing LoRA's linear communication advantages. Furthermore, SecLoRA ensures round-isolated decryption to prevent temporal leakage without extra interaction. Evaluation shows that SecLoRA is practical for cross-silo deployments.

Quantum cryptography is a rapidly developing area which leverages quantum information to accomplish classically impossible tasks. In many of these protocols, quantum states are used as long-term cryptographic keys, relying on the quantum no-cloning theorem to ensure that the keys cannot be copied by an adversary. Unfortunately, quantum state tend to decohere, and hence, persistent quantum memory is and will remain one of the most valuable and challenging resources for quantum computers. As such, it will be important to minimize the extent to which our protocols use persistent quantum memory. In this work, we consider the case of one-shot signatures (OSS), and more general quantum signing tokens, important uncloneable primitives where quantum signing keys allow for signing a single message but not two. Very recently, the first OSS scheme was constructed unconditionally in a classical oracle model as well as in the standard model under cryptographic assumptions (Shmueli and Zhandry, CRYPTO 2025). We observe that the quantum memory required for these protocols is a large polynomial (in the security parameter). The main contribution of this work is to significantly decrease the quantum secret key size, in some cases achieving the asymptotically optimal size. One of our schemes guarantees perfect correctness and the other one admits a parallel signing algorithm for long messages. We also achieve strong signature incompressibility, which implies a public-key quantum fire scheme (Çakan, Goyal and Shmueli, QCrypt 2025) with perfect correctness. During the course of this work, we develop novel techniques for proving the security of cryptosystems using coset states, one of the main tools used in uncloneable cryptography.

A polynomial commitment scheme (PCS) enables a prover to succinctly commit to a large polynomial and later generate evaluation proofs that can be efficiently verified. In recent years, PCSs have emerged as a central focus of succinct non-interactive argument (SNARG) design. We present TensorSwitch, a hash-based PCS for multilinear polynomials that improves the state-of-the-art in two fundamental bottlenecks: prover time and proof size. We frame our results as an interactive oracle PCS, which can be compiled into a cryptographic PCS using standard techniques. The protocol uses any linear code with rate $\rho$, list-decoding and correlated agreement up to $\delta$, and encoding time $\tau \cdot \ell$, where $\ell$ is the block length. For a size $n$ polynomial, security parameter $\lambda$, and sufficiently large field, it has the following efficiency measures, up to lower order terms: - Commitment time: $(\tau/\rho^{2} + \tau/\rho + 3) \cdot n$ field multiplications. - Opening time: $6 n$ field multiplications. - Query complexity: $\frac{1}{-\log(1-\delta^{2})} \cdot \lambda$. - Verification time: $O(\lambda \log n)$. Moreover, the evaluation proof only contains $O(\log \log n)$ oracles of total size $(\lambda n)^{0.5 + o(1)}$. With a Reed-Solomon code of rate $1/2$, the query complexity is $2.41 \lambda$ and commitment time is dominated by $(6 \log n + 3) \cdot n$ field multiplications. With an RAA code of rate $1/4$ and distance $0.19$, the query complexity is $19 \lambda$ and the commitment time is $42 n$ field additions and $3 n$ field multiplications. For both instantiations, the opening time is dominated by $6 n$ field multiplications.

Succinct non-interactive arguments of knowledge (SNARKs) enable the verification of complex computations via short proofs. Recursive proof composition allows long-running or distributed computations to be verified incrementally, but existing approaches exhibit a fundamental trade-off. Folding-based schemes achieve highly efficient recursion but require provers to maintain and communicate large private state, while stateless approaches such as full SNARK recursion and atomic accumulation incur higher prover costs due to the need to produce and verify a full SNARK proof at each step. We introduce holography accumulation, a framework for stateless recursive proving for SNARKs based on the lincheck or checkable subspace arguments. These SNARKs admit a natural decomposition of verification into witness-dependent checks and public polynomial evaluations encoding the computation. We show that the latter, which we call holographic checks, can be accumulated efficiently across recursive steps. To formalize this idea, we introduce generalized bilinear forms (GBF), a linear-algebraic abstraction capturing the holographic verification procedures of several modern SNARKs. Using this abstraction, we construct generic PCD schemes compatible with both univariate and multivariate polynomial commitment schemes, and present an efficient decider that collapses the accumulated checks to a single polynomial evaluation.

A significant number of works have considered the problem of multi-party computation over dynamic committees in synchronous networks, including YOSO MPC [Crypto'21], Fluid MPC [Crypto'21], SCALES MPC [TCC'22] and Layered MPC [Crypto'23]. However, prior works assume that every party has access to an ideal synchronous broadcast channel towards the next committee. While this assumption is partly justified due to the seminal work of Garay [WDAG'94] stating that deterministic broadcast with dynamic committees is impossible, it is open whether there are randomized solutions. We answer this question in the affirmative, by providing a complete characterization of broadcast with dynamic committees. We use the formalization introduced in the Layered MPC setting and achieve the following results for layered broadcast: - A statistically secure protocol tolerating $t<n/3$ corruptions with no setup. - A computationally secure protocol tolerating $t<n/2$ corruptions, assuming only a bulletin-board PKI for signatures. - A matching impossibility result showing that broadcast is impossible for $t \geq n/2$ corruptions. Using our broadcast, we achieve the following polynomial-time results: - YOSO MPC protocols without broadcast (statistical for $t<n/3$ without setup; and computational for $t<n/2$ assuming a plain PKI for signatures). - Assuming plain PKIs for signatures and public-key encryption, a Layered MPC protocol without broadcast for $t<n/2$. - Assuming homomorphic commitments, a Layered MPC without broadcast for $(t+1)^2 \le n$. To achieve this, we introduce a secure-message-transmission protocol for $(t+1)^2 \le n$ which has linear communication in $\ell$ and polynomial communication in $n$ when transmitting a message across $\ell$ layers. This result is of independent interest.

This paper presents Heli, a system that lets a pair of servers collect aggregate statistics about private client-held data without learning anything more about any individual client's data. Like prior systems, Heli protects client privacy against a malicious server, protects correctness against misbehaving clients, and supports common statistical functions: average, variance, and more. Heli's innovation is that only one of the servers (the "heavy server") needs to do per-run work proportional to the number of clients; the other server (the "light server") does work sublinear in the number of clients, after a one-time setup phase. As a result, a computationally limited party, such as a low-budget non-profit, could potentially serve as the second server for a Heli deployment with millions of clients. Heli relies on a new cryptographic primitive, aggregation-only encryption, that allows computing certain restricted functions on many clients' encrypted data. In a deployment with ten million clients, in which the servers privately compute the sum of 32 client-held 1-bit integers, Heli's heavy server does 84,000 core-s of work and the light server does 8 core-ms of work. Compared with prior work, the heavy server does 34$\times$ more computation, but the light server does 150,000$\times$ less.

We construct preimage sampleable function families on $q$-ary lattices [Gentry–Peikert–Vaikuntanathan, STOC'08] for which preimage sampling reduces to sampling uniform points of unitriangular lattices from simple polytopes: affine linear transforms on the $\ell_1$ and $\ell_\infty$ balls, and a scaled intersection thereof. We build the necessary samplers by adapting an algorithm of [Kannan–Vempala, STOC'97] and improving its analysis. This sampling requires only uniform bits and affine linear transforms on the uniform distribution on $[0,1]$. The collision resistance of these families relies on the short integer solutions problem [Ajtai, STOC'96] in various $\ell_p$ norms. Considering the Lee metric as the $\ell_1$ norm in $q$-ary lattices, we answer an open question to construct such families for the Lee metric [Hörmann–van Woerden, CRYPTO'24]. We also answer an open question of [Plançon--Prest, PKC'21] by sampling from polytopes with inradius smaller by a factor almost square root in the lattice rank. We provide a generic framework for constructing preimage sampleable function families from polytopes with sufficient conditions for realising it. While our parameters are worse than prior discrete Gaussian based constructions, such distributions are challenging from a physical security perspective.

Group-action-based Sigma protocols have proven to be truly flexible for the design of advanced cryptosystems. When they are compiled via the Fiat-Shamir transform, the resulting NIZKPs can be efficiently optimized using standard techniques within the fixed-weight framework. Unfortunately, the same techniques are not as effective when they are combined with straight-line extractable NIZKPs (e.g. Fischlin, CRYPTO '05), a key building block in the design of complex protocols. This work introduces the GAO (Group Action Oriented) transform, a new generic compiler that produces straight-line extractable NIZKPs from Sigma protocols while significantly simplifying the analysis of the fixed-weight framework. The GAO transform is then optimized in two different ways. First, by defining a collision predicate that results to be even more effective combined with GAO than with the Fischlin transform, for which was originally introduced (Kondi and shelat, ASIACRYPT '22). Second, adopting a technique, which we call Stretch-and-Compress (SC), that enables trading a smaller number of expensive operations for a larger number of inexpensive ones, which surprisingly leads to a reduction of both the computational complexity and the proof size. Our final transform, obtained from GAO applying the two optimizations, is called SC-Coll-GAO. The practical advantages of the SC-Coll-GAO transform are theoretically motivated and concretely tested on the Sigma protocol underlying the Fiat-Shamir digital signature LESS, a code-based candidate that recently advanced to the second round of the NIST standardization process specifically purposed for post-quantum signatures. Remarkably, when compared to the Fiat-Shamir LESS baseline, SC-Coll-GAO incurs a computational cost increase by 50-60%, while signature sizes grow by only 10-20%.

While passive probing attacks and active fault attacks have been studied for multiple decades, research has only started to consider combined attacks that use both probes and faults relatively recently. During this period, polynomial masking became a promising, provably secure countermeasure to protect cryptographic computations against such combined attacks. Unlike other countermeasures, such as duplicated additive masking, polynomial masking can be implemented using a linear number of shares, as shown by Berndt et al. at CRYPTO '23. Based upon this fact, Arnold et al. noted at CHES '24 that polynomial masking is particularly well-suited for parallel computation. This characteristic is especially effective in scenarios involving multiple circuits with identical structures, such as the 16 SBoxes in AES. Just recently, Faust et al. showed at CHES '25 that one can also incorporate the technique of packed secret sharing into these masking schemes, given that the state-of-the-art polynomial masking scheme is secure against combined attacks. In this work, we present provably secure advancements regarding this state-of-the-art scheme in both computational and randomness efficiency, reducing the randomness complexity by up to 50% and the computational complexity even more by going from a quadratic term to a linear one for many parameters. Moreover, we present the first implementation of a polynomial masking scheme against combined attacks along with an extensive experimental evaluation for a wide range of parameters and configurations as well as a statistical leakage detection to evaluate the security of the implementation on an Arm Cortex-M processor. Our implementation is publicly available to encourage further research in practical combined resilience.

Fully Homomorphic Encryption (FHE) is a powerful primitive which allows a computationally weak client to outsource computation to a powerful server while maintaining privacy. However, FHE typically suffers from high ciphertext expansion, meaning that the amount of data the client has to send to the server increases by many orders of magnitude after it is encrypted. To solve this problem, the approach known as transciphering consists in combining symmetric encryption with FHE. The most common choice of cipher in this context is the AES, which has been used as a benchmark for transciphering. However, although FHE is typically post-quantum secure, existing transciphering protocols only use AES-128, failing thus to offer security against quantum adversaries. In this work, we construct transciphering protocols based on standard ciphers that offer post-quantum security. For this, we propose algorithms to efficiently evaluate the ChaCha cipher with FHE. We notice that ChaCha is a well-established cipher which even has a standardized version in TLS offering 256 bits of security against classic attackers, thus, 128 bits of security in the quantum world. We show that our solutions have both better latency and throughput than the state-of-the-art transciphering protocol based on AES. Namely, compared with an extended (128-bit PQ secure) version of Hippogryph (Belaïd et al., IACR CiC 2025), in single-core experiments, our running times are up to 11.7 times faster while our throughput is more than 50 times higher.

We present $\mathsf{Protoss}$, a new balanced PAKE protocol with optimal communication efficiency. Messages are only 160 bits long and the computational complexity is lower than all previous approaches. Our protocol is proven secure in the random oracle model and features a security proof in a strong security model with multiple parties and multiple sessions, while allowing for generous attack queries including multiple $\mathsf{Test}$-queries. Moreover, the proof is in the practically relevant single-bit model (that is harder to achieve than the multiple-bit model) and tightly reduces to the Strong Square Diffie-Hellman assumption (SSQRDH). This allows for very efficient, theoretically-sound instantiations and tight compositions with symmetric primitives.

End-to-end deep-learning side-channel attacks on public-key implementations have recently become possible even for million-sample traces. However, existing methods require large computational resources and extract only partial key shares, which means that dedicated post-processing is required to turn detected leakage into demonstrations of successful key recovery attacks. We present an end-to-end sequence-to-sequence prediction approach to recover complete 256-bit key shares from single raw traces on the SCAAML ECC datasets recently studied by Bursztein et al (TCHES 2024). Our solution combines aggressive trace compression for dimensionality reduction with a 1-D U-Net trained using Connectionist Temporal Classification loss. The key idea is to decouple detecting leakage from mapping each leakage site to the correct part of the secret: the network outputs an annotated map of the trace marking likely leakage sites, and a greedy decoder reconstructs the ordered key bits from that map. Using synthetic tasks, we show that this division of labor circumvents a fundamental problem that causes neural network architectures and training methods commonly used in side-channel analysis to struggle with massive multi-target or misaligned extraction tasks. As a result, we are able to train a single extractor that achieves high accuracy on all four SCAAML ECC datasets in a single training run that takes minutes on a single GPU. The resulting extractors are robust, essentially maintaining their performance under large misalignment (we empirically tested rotations up to \(61\%\) of trace length), while degrading gracefully under a variety of trace corruptions, and even time reversal. They transfer across key shares and datasets with little degradation and no retraining. The U-Net outputs also yield prediction maps that localize leakage along the trace prior to decoding.

Cryptographic accumulators based on groups of unknown order (GUO) provide constant-size set membership proofs. For security purposes, existing works require first encoding set elements via division-intractable (DI) hash functions, typically instantiated as random oracles that destroy any algebraic structure. This confines GUO-based accumulators to a purely set-membership role, making them "incompatible" with various existing cryptographic proof techniques over committed integers in the same groups as the GUO, such as constant-size proofs of exponentiation and modular exponent relations. We introduce the notion of morphic accumulators, which replaces the DI hash with a discrete logarithm encoding $H_g(x) = g^x$, mapping set elements to a group before accumulation. We prove, under a variant of the subset product assumption in the generic group model, that this encoding is inherently division intractable, achieving the same security guarantee as random-oracle DI hashes, while simultaneously being a group homomorphism: accumulated elements retain their group-algebraic relationships. This resolves a fundamental tension between compact representation and algebraic structure: the accumulator serves simultaneously as a binding commitment to a set and as a substrate for homomorphic computation over its elements. Morphic accumulators yield asymptotically optimal constructions across multiple domains: range proofs with $O(n)$ prover time, $O(1)$ proof size, $O(1)$ verification with transparent setups (the first scheme to simultaneously achieve these optimal bounds); polynomial commitments with $O(n)$ prover and $O(1)$ proof size, resolving the cubic bottleneck in prior constant-proof-size GUO-based schemes; and the first linkable ring signatures with $O(1)$ signature size, transparent setup, $O(n)$ offline signing and $O(1)$ online signing.

Bitcoin bridges, protocols that lock BTC on Bitcoin and represent it on a secondary system, underpin much of Bitcoin's application layer, yet remain poorly secured. Deployed bridges rely on federated custody with honest-majority assumptions, while BitVM2, the state of the art in trust-minimized bridging, incurs worst-case dispute costs of approximately \$16,000, requiring large operator bonds and deposits that restrict participation to well-capitalized parties. We present BitVM3-BRIDGE, a trust-minimized bridge architecture from Bitcoin to (i) chains with finality certificates, such as Ethereum, and (ii) Bitcoin rollups. Our main contribution is an end-to-end bridge construction that makes trust-minimized Bitcoin bridging practical at scale. The bridge is powered by BitVM3-CORE, a modular abstraction for permissionless off-chain computation on Bitcoin using garbled circuits. In BitVM3-CORE, a challenger evaluates a garbled circuit entirely off-chain and obtains a fraud-proof witness if and only if the operator's claim is incorrect. This paradigm reduces total on-chain costs to approximately \$9, with the challenge transaction itself costing just \$0.20. This nearly 1000× cost reduction enables smaller bonds, broader operator participation, and smaller deposit sizes. Beyond the bridge itself, we make two additional contributions. First, we formalize BitVM3-CORE as a sound and complete on-chain proof system under standard cryptographic assumptions. Prior GC-based proposals typically provide either informal security arguments or construction-specific formalizations; by contrast, our framework captures existing constructions within a uniform model and gives a generic treatment based on axiomatized security and functional assumptions. Second, we introduce an on-chain Bitcoin light client secure in the variable-difficulty setting, enabling permissionless chain introspection on Bitcoin and thereby the rollup variant of BitVM3-BRIDGE.

The (Multi-)Scalar multiplication is a crucial operation in numerous FHE-related applications, and its performance has a significant impact on their overall efficiency. This paper presents SMOOTHIE: (Multi-)Scalar Multiplication Optimisations On TFHE, introducing new techniques to improve the performance of single- and multi-scalar multiplications in TFHE. We show that the bucket/Pippenger method, rooted in the elliptic curve field, can be successfully adapted to TFHE when combined with new optimisations that address their inherent differences. We propose a new negation with offset technique that eliminates direct carry propagation after ciphertext negation. Additionally, we introduce a bucket merging technique for the bucket aggregation step, which exploits TFHE properties to reduce bootstrap operations. Specifically, in the multi-scalar multiplication case, we implement a bucket doubling method that eliminates the need for precomputation on each input ciphertext. Our implementation is integrated in the TFHE-rs library and achieves up to $\times2.05$ speedup for single-scalar multiplication compared to the current state-of-the-art, with multi-scalar multiplication improvements up to $\times6.43$, depending on the vector sizes.

Two post-quantum upgrades to TLS 1.3 are being standardized in parallel: a hybrid key exchange (already deployed) that runs an elliptic-curve Diffie-Hellman exchange alongside ML-KEM, and a standalone mode that uses ML-KEM on its own. The Internet-Draft draft-usama-tls-risks-of-mlkem points out that the machine-checked symbolic proofs of TLS 1.3 rely on the commutativity of Diffie-Hellman, which ML-KEM does not share: a key encapsulation mechanism is asymmetric, one endpoint generating a key pair and the other encapsulating against it. The existing proofs therefore no longer apply, a new one is needed, and the draft argues that hybrids should be preferred. We supply that proof. We extend the reftls ProVerif models with a faithful, non-commutative KEM and analyze classical (EC)DHE, standalone ML-KEM, and the hybrid together, as unbounded concurrent sessions against a single active attacker free to break any cryptographic component. The central result is a sharp and tight contrast in robustness: standalone ML-KEM is a single point of failure, secure only while ML-KEM itself is unbroken, whereas the hybrid stays secure as long as either of its components survives: an attacker must break both, in one session, to learn anything. This single point of failure reaches authentication as well as confidentiality: with the sole key-exchange secret exposed and no secret pre-shared key salting the key schedule, the server Finished message becomes forgeable, so a client can complete a handshake that no server completed, while the hybrid stays safe unless both components break. The three modes also interoperate without ever confusing one another's keys, so migrating from (EC)DHE to a hybrid is a strict improvement. Two further experiments address the draft's remaining concerns: reusing an ML-KEM key forfeits the forward secrecy that an ephemeral key preserves, and a principal acting as both initiator and responder exposes no role-confusion attack arising from the asymmetry. At the symbolic level, and under stated assumptions, the analysis substantiates the draft's case for preferring hybrid key exchange.

We present a post-quantum commitment scheme based on kernel-tagged punctured Richelot isogeny walks on superspecial genus-2 Jacobians. The puncturing rule skips every step landing in the product locus, detected by I10 = 0, so honest executions remain in the Jacobian locus and avoid the entry point of known product-locus attacks. Each opening is encoded as a deterministic non-backtracking walk together with a kernel tag recording its action on a small public auxiliary torsion basis. The tag is verified as part of the opening and is kept explicit throughout the security analysis. In particular, scalar-related collisions force equality of the ordered kernel sequence and hence equality of the tag, so any nontrivial binding attack yields a short non-scalar endomorphism. Using spectral bounds for the Richelot graph, we show that puncturing preserves rapid mixing for logarithmic walk lengths, which yields statistical hiding for the tagged punctured scheme. We therefore reduce binding to the Short Richelot Endomorphism Problem (SREP), relate SREP to the One-Endomorphism Problem and, under a standard KLPT2 -style heuristic, to the endomorphism-ring problem. A SageMath prototype based on (2, 2)-Kummer isogenies indicates practical performance at standard security levels.

The evaluation of both arithmetic and logic operations on machine words (e.g., 64-bit registers) in homomorphic settings is an attractive problem due to its close alignment with real-world programming models. Existing FHE schemes require *iterative* bootstrapping operations with the iteration number scaling with the machine word bit-width $n$. Prior approaches incur either quadratic cost for multiplication (DM/CGGI), linear cost for logic operations (REFHE [Eurocrypt'26] and Kim [TCHES'26]), or logarithmic cost for multiplication (CPL [Eurocrypt'26]). We mitigate this inherent barrier by amortizing $O(n)$ iterations across $O(n)$ ciphertexts for scenarios with sufficient machine words. We introduce a triangle encoding such that in its conversion to boolean mode, each iteration on a combined ciphertext processes multiple ciphertexts, resulting in an amortized constant cost per ciphertext. Additionally, the triangle encoding supports leveled arithmetic, and its refreshing requires only two CKKS bootstrapping operations. We reuse discrete CKKS as our boolean mode, which supports lightweight conversion to the triangle encoding. We also introduce a method to induce SIMD structure for the triangle encoding from the RLWE ring. Even when we bootstrap after each multiplication, we show a 1.7$\times$ to 2$\times$ higher throughput compared with the state-of-the-art CPL scheme. We further estimate 15$\times$ and 491$\times$ higher throughput for multiplication and bitwise operations, respectively, compared with the REFHE scheme. We make our OpenFHE-based prototype open source for ease of reference.

This work presents the first full-round attacks on ChiLow-32 and ChiLow-40, two tweakable low-latency block ciphers presented at Eurocrypt 2025. We first describe a straightforward Meet-in-the-Middle attack on full ChiLow-32 with multiple known plaintext-ciphertext pairs. To improve this attack, we carefully reduce the number of guesses required by (1) tracing differences in order to remove linear key dependencies and (2) moving from key guesses to state guesses. Using a novel method that is based on the propagation of differences and linear masks, we are able to map out the state dependencies for computing the difference at the matching point. This results in an attack on ChiLow-32 with time complexity $2^{120.34}$ using $160$ known plaintext-ciphertext pairs, and an attack with time complexity $2^{102.09}$ using $64$ chosen ciphertexts. Using these techniques, and an additional trick to better balance the complexities of the meet-in-the-middle branches, we propose an attack on ChiLow-40 with time complexity $2^{122.32}$ and $2^8$ chosen plaintexts. All of our attacks are within ChiLow's security model, and are currently the best and only known key recovery attacks on full-round ChiLow-32 and ChiLow-40.

The unbalanced oil and vinegar signature scheme (UOV) was proposed by Kipnis et al. in 1999 as a multivariate-based scheme. UOV is regarded as one of the most promising candidates for post-quantum cryptography owing to its short signatures and fast performance. Recently, Ran proposed a new key recovery attack on UOV over a field of even characteristic, reducing the security of its proposed parameters. Furthermore, Jin et al. generalized Ran’s attack to schemes over a field of arbitrary characteristic by exploiting the structure of the symmetric algebra. In this work, we propose a new framework for recovering the secret subspace of UOV over a finite field $\mathbb{F}_{p^e}$ by generalizing these preceding results. First, we show that a key recovery against UOV can be successfully performed using the XL algorithm by exploiting the structure of the $p$-truncated polynomial ring $R^{(p)}=\mathbb{F}_{p^e}[x_1,\dots,x_n]/ \langle x_1^p,\dots,x_n^p\rangle$. This result simplifies the description of the attacks proposed by Jin et al. by formulating them in terms of the polynomial ring, independent of the structure of the symmetric algebra. Second, we generalize this result to the polynomial rings of more general forms, namely, the $p^\ell$-truncated polynomial rings $R^{(p^\ell)}$ for any $1 \le \ell \le e$. This result is due to our description in terms of the polynomial ring and can relax the constraints on the solving degree of the XL algorithm using $R^{(p^\ell)}$ by taking a larger $\ell$. Finally, we consider performing the reconciliation and intersection attacks using the $p^\ell$-truncated polynomial rings against UOV. In particular, we consider the intersection attack using this framework, which has not been addressed in previous analyses. Based on our complexity estimation, we confirm that the optimal complexity of the reconciliation attack using the proposed framework is consistent with that of the symmetric-algebra attack by Jin et al. We further show that the intersection attack using the proposed framework outperforms the reconciliation attack against the proposed parameters of UOV and reduces the security of multiple parameters compared to their claimed security levels.

The Feistel (Luby-Rackoff) structure underlies numerous block-cipher and mode-of-operation designs, whose security is traditionally assessed via indistinguishability. For low-round Feistel constructions, a variety of classical and quantum distinguishing attacks are known. In this work, we show that such distinguishing attacks can be systematically upgraded to full plaintext recovery with essentially the same query complexity. We establish classical recovery attacks on the $2$-round Feistel under CPA and the $3$-round Feistel under CCA using only three queries, and introduce quantum-assisted forward/backward extension techniques based on Simon’s algorithm that yield recovery attacks on the $3$-round Feistel under qCPA and the $4$-round Feistel under qCCA. We further prove that the attacks extend to the Unified Feistel-Lai-Massey (UFLM) framework and therefore apply to a broad class of two-branch constructions. As a consequence, we obtain plaintext-recovery attacks on $4/5/6$-round Feistel-FK and on several practical enciphering schemes, including AEZ-core, FMix, OleF, double-decker, and docked-double-decker. Overall, our results reveal a fundamental connection between distinguishing and full plaintext recovery in low-round two-branch Feistel-type designs, in both classical and quantum settings.

Two techniques have recently emerged in the construction of Succinct Non-Interactive Arguments of Knowledge (SNARKs) that yield extremely fast provers; The use of multilinear (instead of univariate) polynomial commitment schemes (PCS) and the construction of practical SNARKs from error-correcting codes. Recently, BaseFold (Crypto 2024) introduced a family of SNARKs that combine these two techniques, thereby achieving a better trade-off between prover time and verifier costs than prior work. Despite its impressive overall efficiency, BaseFold suffered from larger proof sizes than its univariate counterparts, due to unproven claims about linear codes, which were not relevant in the univariate setting. This work closes this gap by proving a new fact about linear codes -- that if $\pi_L, \pi_R$ are two vectors in $\mathbb{F}^{n}$ and if $\pi_L + r \pi_R$ is close to a codeword in $C$, then $\pi_L, \pi_R$ and $(\pi_L + r \pi_R)$ all agree with codewords at positions in the same set $S \subset [n]$, except with negligible probability over $r \leftarrow \mathbb{F}$. Our result holds as long as $|S| > ((1 - \Delta_C + \epsilon)^{1/3} + \eta) n$, for $\epsilon, \eta \in [0,1]$ and with failure probability smaller than $\frac{3}{\epsilon\eta |\mathbb{F}|}$, where $\Delta_C$ is the minimum distance of the code. Importantly, our results extend to any finite field and any linear code, and lead to a $2 \times$ reduction in proof size compared to state-of-the-art field-agnostic, hash-based SNARKs.

Unbiased, unpredictable, and publicly verifiable randomness is essential for a wide range of blockchain-based Web3 applications. Verifiable Random Functions (VRFs) naturally satisfy these requirements. For practical deployment, however, a VRF scheme must support efficient key generation and allow multiple evaluations across different blockchain rounds. In this work, we present a post-quantum secure, key-updatable VRF construction built from symmetric cryptographic primitives, including hash functions and pseudorandom generators (PRGs). The core of our design is a quantum-secure Extended Merkle Signature Scheme (XMSS) structured over multiple layers. We reorganize the XMSS framework in a systematic way to integrate it seamlessly into our VRF construction. Compared to existing approaches, our scheme offers improved key generation efficiency while enabling multiple evaluations from a single secret–verification key pair.

We initiate the study of basing the hardness of hinted ISIS problems (i.e. with trapdoor information, or ‘hints’) on the previously conjectured space-time hardness of lattice problems without hints. We present two main results. 1. If there exists an efficient algorithm for hinted ISIS that outputs solutions a constant factor longer than the hints, then there exists a single-exponential time and polynomial memory zero-centred spherical Gaussian sampler solving hinted SIS with norm a constant factor shorter than the hints. 2. Assume the existence of a chain of algorithms for hinted ISIS each taking as input Gaussian hints whose norms decrease by a constant factor at each step in the chain, then there exists a single-exponential time and polynomial memory algorithm for SIS with norm a quasilinear factor from optimal. The existence of such hinted ISIS solvers implies single-exponential time and polynomial memory algorithms for worst-case lattice problems, contradicting a conjecture by Lombardi and Vaikuntanathan (CRYPTO’20) and all known algorithms. This suggests that hinted ISIS is hard. Apart from advancing our understanding of hinted lattice problems, an immediate consequence is that signing the same message twice in GPV-style [Gentry–Peikert–Vaikuntanathan, STOC’08] schemes (without salting or derandomisation) likely does not compromise unforgeability. Also, cryptanalytic attempts on the One-More-ISIS problem [Agrawal–Kirshanova–Stehlé-Yadav, CCS’22] likely will need to overcome the conjectured space-time hardness of lattices.

Private information retrieval (PIR) allows to privately read a chosen bit from an $N$-bit database $x$ with $o(N)$ bits of communication. Lin, Mook, and Wichs (STOC 2023) showed that by preprocessing $x$ into an encoded database $\hat x$, it suffices to access only $polylog(N)$ bits of $\hat x$ per query. This requires $|\hat x|\ge N\cdot polylog(N)$, and even larger server circuit size. We consider an alternative preprocessing model (Boyle et al. and Canetti et al., TCC 2017), where the encoding $\hat x$ depends on a client's short secret key. In this secret-key PIR (sk-PIR) model we construct a protocol with $O(N^\epsilon)$ communication, for any constant $\epsilon>0$, from the Learning Parity with Noise assumption in a parameter regime not known to imply public-key encryption. This is evidence against public-key encryption being necessary for sk-PIR. Under a new conjecture related to the hardness of learning a hidden linear subspace of $\mathbb{F}_2^n$ with noise, we construct sk-PIR with similar communication and encoding size $|\hat x|=(1+\epsilon)\cdot N$ in which the server is implemented by a Boolean circuit of size $(4+\epsilon)\cdot N$. This is close to optimal, and the first candidate single-server PIR scheme with linear circuit complexity.

Blockchain mempool transparency fuels Maximal Extractable Value (MEV), where attackers can front-run, back-run, and reorder transactions as soon as they appear. Encrypted mempools aim to delay the release of information until block commitment, yet nearly all existing designs rely on a trusted decryption committee. This creates two structural problems. First, committee members hold decryption material by design, so a colluding threshold can reconstruct the decryption key and learn transactions before block commitment. Second, once such a committee becomes malicious, honest parties have no easy in-protocol way to recover: restoring privacy for future epochs requires an external intervention such as a hard fork that replaces the committee and rotates the long-lived cryptographic material. In this work, we ask whether encrypted mempools can instead use proof-of-work to realize an open and recoverable decryption committee. We then introduce DecryptChain, a permissionless proof-of-work encrypted mempool in which decryption authority is not assigned to persistent identities or long-lived key shares. Instead, decryption is continuously re-contested through public computational work. Even if an adversary successfully breaches one epoch, it gains no reusable secret for future epochs; honest parties can always re-enter and recover the decryption process by contributing sufficient work. DecryptChain decouples block production from decryption, enabling it to operate as a Layer-2 timely decryption service on any underlying blockchain while preserving eventual decryption for committed on-chain encrypted transactions.

The communication complexity of unconditionally Secure Multi-Party Computation (MPC) protocols has been studied by a series of works in the honest-majority setting. For evaluating an arbitrary Boolean circuit, the state-of-the-art MPC protocol by Goyal et al. (Crypto 2021 and Crypto 2022) achieves the total communication cost of $O(\log n)$ bits per gate, where $n$ is the number of parties. In this work, we present the first unconditional MPC protocol for any Boolean circuit with communication of $O(1)$ bits per gate. We first construct an unconditionally secure protocol in the presence of semi-honest adversaries, and then strengthen it to guarantee security against malicious adversaries with the same communication efficiency.

In their seminal work, Goldreich, Goldwasser, and Micali [CRYPTO 1984] constructed a pseudorandom function (PRF) using a black-box access to a pseudorandom generator (PRG). When combined with Levin's domain extension technique, the GGM construction invokes the PRG $\omega(\log n)$ times, where $n$ denotes the input length to the PRG. To this day, no black-box construction achieving fewer calls is known. Recently, Beimel, Malkin, and Mazor [CRYPTO 2024] showed that for a certain family of constructions, which they termed \emph{tree constructions}, the GGM construction is optimal. However, the basic challenge of whether a PRF can be built with just \emph{one invocation} of the PRG still remains open. In this work, we consider fully black-box constructions of PRFs from PRGs, where both the construction and the reduction are required to be black-box, and the number of interactions the reduction makes with the adversary is independent of the number of oracle calls the adversary makes to its underlying function within each interaction. Our main result shows that no such construction can have $o(n/\log n)$ and $o(\mathsf{in}/\log\mathsf{in})$ \emph{non-adaptive} calls to the PRG, where $\mathsf{in}$ is the input length of the PRF. This impossibility holds even for weak PRFs with one-bit output, where the adversary is restricted to making i.i.d. uniformly random queries. In addition, we prove a lower bound for weak PRFs with sufficiently long outputs that holds even when the construction is allowed to make adaptive queries to the PRG.

We propose the first blind signature scheme that simultaneously achieves the following properties: - It uses a pairing-free group and random oracles in a black-box manner; - It provably achieves concurrent security based on standard assumptions (DDH) without the algebraic group model (AGM); - It requires only three moves. Moreover, the public key, signature, and communication of our scheme all consist of only a constant number of group/field elements. Prior to our work, black-box, three-move pairing-free schemes were only known in the AGM. A recent line of work proposed and optimized schemes without the AGM, but they all require at least four moves.

CMoSS facilitates modular specifications, design and analysis of cryptographic protocols. Modular design and analysis is achieved by supporting provably-secure compositions of protocols; typically, a protocol uses a blackbox subprotocol, and is proven secure when composed with any subprotocol meeting the blackbox specifications. For modularity of specifications, CMoSS extends the approach of the MoSS framework: protocol specifications are defined modularly, by a set of independent predicates (games) for each model (assumption) and requirement (goal). CMoSS makes it feasible to rigorously specify, develop and analyze realistic applied cryptographic protocols, supporting real-time concurrency and involving different attacker capabilities, delays, faults and synchronization challenges. CMoSS specifications provide a precise formalization of the informal specifications used by practitioners, facilitating provable security for practical protocols.

A recent breakthrough [Hirahara and Nanashima, STOC’2024] established that if $\mathsf{NP} \not \subseteq \mathsf{ioP/poly}$, the existence of zero-knowledge (ZK) with negligible errors for $\mathsf{NP}$ implies the existence of one-way functions (OWFs). This work obtains a characterization of one-way functions from the worst-case complexity of zero-knowledge in the high-error regime. Assuming $\mathsf{NP} \not \subseteq \mathsf{ioP/poly}$, we show that any non-trivial, constant-round public-coin ZK argument for NP implies the existence of OWFs, and therefore also (standard) four-message zero-knowledge arguments for $\mathsf{NP}$. Here, we call a ZK argument non-trivial if the sum of its completeness, soundness and zero-knowledge errors is bounded away from 1. As a special case, we also prove that non-trivial non-interactive ZK (NIZK) arguments for $\mathsf{NP}$ imply the existence of OWFs. Using known amplification techniques, this also provides an unconditional transformation from weak to standard NIZK proofs for all meaningful error parameters. Prior work [Chakraborty, Hulett and Khurana, CRYPTO’2025] was limited to NIZKs with constant zero-knowledge error $\varepsilon_{\mathsf{zk}}$ and soundness error $\varepsilon_{\mathsf{s}}$ satisfying $\varepsilon_{\mathsf{zk}} + \sqrt{\varepsilon_{\mathsf{s}}} < 1$.

Asynchronous multiparty computation (AMPC) requires an input agreement phase where all participants have a consistent view of the set of private inputs. While the input agreement problem can be precisely addressed by a Byzantine fault-tolerant consensus known as Asynchronous Common Subset (ACS), existing ACS constructions with potential post-quantum security have a large $\widetilde{\mathcal{O}}(n^3)$ communication complexity for a network of $n$ nodes. This poses a bottleneck for AMPC in the same setting. In contrast, ACS has optimal constructions with quadratic communication complexity based on bilinear map assumptions. In this paper, we bridge this gap by introducing a nearly optimal ACS, which, assuming a common coin oracle, relies on the blackbox use of collision-resistant hash functions. It exhibits $\widetilde{\mathcal{O}}(n^2)$ communication complexity, expected constant round complexity, and security against adaptive adversaries who can corrupt up to $n/3$ nodes and perform “after-the-fact-removal” attacks. At the core of our new ACS is the first nearly optimal hash-based asynchronous Multi-valued Validated Byzantine Agreement (MVBA). To reduce cubic communication while avoiding heavy cryptographic tools, we introduce a new design paradigm with several novel components. This paradigm also enables an information-theoretic MVBA construction, whose communication complexity is higher than its hash-based counterpart but still quadratic. We give standard treatment of those using the conventional property based definitions. We also define and analyze our MVBA and components within the UC-framework, facilitating their modular use in broader applications, particularly in AMPC.

While FHE enables computation on encrypted data, protecting the program itself remains a theoretical and practical challenge, often forcing practitioners to choose between exposing proprietary logic or suffering impractical performance penalties. This paper introduces HEGIDE, an oblivious processor based on the (discrete) Cheon-Kim-Kim-Song (CKKS) scheme that bridges the gap between theoretical Private Function Evaluation (PFE) and its practical realization. Central to our contribution is OSReM (Oblivious Shift Register Memory), a novel memory architecture that circumvents the linear complexity of standard FHE-RAM writes. By treating memory as a shift register, OSReM enables low-latency, constant-time writes without the need for expensive full-memory bootstrapping. HEGIDE leverages a MIMD (Multiple Instruction, Multiple Data) design, utilizing CKKS packing to evaluate distinct program threads in parallel, thus maximizing throughput. While the processor architecture natively supports arbitrary word sizes and instructions, we provide a compiler that manages memory scheduling to abstract the complexity of the shift-register design. We provide a proof-of-concept full implementation of HEGIDE using the OpenFHE library. Experimental results demonstrate the efficiency of our approach, achieving an amortized cycle time of just 6.4 ms for a 16-bit processor - two orders of magnitude faster in throughput than comparable approaches - offering a viable path for the secure execution of proprietary algorithms on encrypted data.

The Learning with Errors (LWE) problem is a fundamental hardness assumption underlying most fully homomorphic encryption (FHE) schemes. Given the close relationship between the Learning with Rounding (LWR) and LWE problems, several cryptographic constructions have also been developed based on LWR. In particular, LWR-based schemes often benefit from simpler and more efficient implementations, as they eliminate the need for explicit Gaussian error sampling. Despite these advantages, relatively few FHE constructions in the literature are based on the LWR assumption. At AsiaCCS 2025, Goyal and Gangopadhyay proposed a multi-key FHE (MKFHE) scheme based on LWR that adopts a public-key extension mechanism rather than the conventional ciphertext-extension paradigm. The authors also identified the development of a ring-based analogue as an open future direction. In this work, we present two Ring-LWR-based MKFHE constructions that can be viewed as ring analogues of the LWR-based MKFHE scheme of Goyal and Gangopadhyay. To the best of our knowledge, these are the first MKFHE schemes based on the Ring-LWR assumption. Compared with existing Ring-LWE-based multi-key constructions, our schemes achieve improved compactness in terms of storage and communication costs. We provide concrete parameterizations supporting circuits of varying multiplicative depths and present a proof-of-concept implementation to validate our claims.

The problem of computing an isogeny of large prime degree from a supersingular elliptic curve of unknown endomorphism ring is assumed to be hard both for classical as well as quantum computers. In this work, we first build a two-round identification protocol whose security reduces to this problem. The challenge consists of a random large prime $q$ and the prover simply replies with an efficient representation of an isogeny of degree $q$ from its public key. Using the hash-and-sign paradigm, we then derive a signature scheme with a very simple and flexible signing procedure and prove its security in the standard model. Our optimized C implementation of the signature scheme shows that signing is roughly $1.8\times$ faster than all SQIsign variants, whereas verification is $1.4\times$ times slower. The sizes of the public key and signature are comparable to existing schemes. Latest version: PRISM with a pinch of salt: Simple, Efficient and Strongly Unforgeable Signatures from Isogenies, from the same authors, is an extended and updated version of the present article. It is available at https://eprint.iacr.org/2026/443.

The recent study has demonstrated that neural networks can serve as a navigator for an automatic search model for integral cryptanalysis with a reduction in computational complexity. However, the inherent drawbacks of using a deep learning model such as large datasets and limited interpretability are the major obstacles in cryptanalysis. In this paper, we introduce another simple data-driven approach using the linear algebraic concept to characterize key-independent balance properties as the kernel of a matrix with empirical parity data. We stack the ciphertext parities obtained under many independent keys into the parity matrix and prove that every mask satisfying the matrix multiplication as zero corresponds exactly to a balance property. Candidates of the balance mask from the test are additionally evaluated by the spurious mask test. We demonstrate the practicality and generality of the kernel methodology on seven lightweight block ciphers spanning SPN with SKINNY, Midori, PRESENT, LED and ARX with SPECK, SIMON, SIMECK. Across these cases, our method recovers known distinguishers and reveals additional non-trivial linear combinations missed by conventional analyses. We additionally position the kernel method relative to other similar methodologies. Our results show that the kernel method provides a rigorous and cipher-agnostic alternative to neural feature exploration and complements division property-based search techniques.

We show that the data deduplication scheme [IEEE Trans. Cloud Comput., 11(1), 156-167, 2023] is flawed due to some inconsistent computations. The scheme tries to propose a hybrid encryption and authentication mechanism based on RSA cryptosystem and pairing cryptosystem, but it has confused the different group operations. In the data sharing phase, the cloud service provider cannot determine which stored tag matches the temporary tag, and fails to return the stored data to the requester. To fix, it should explicitly specify which is randomized by modular exponentiation with an RSA modulus, and which is randomized by point multiplication over the underlying elliptic curve.

In high-volume online services—such as privacy-preserving CAPTCHA bypass or metered paywalls—service providers must filter malicious traffic without compromising user privacy. Anonymous tokens with private metadata (ATPM) address this by embedding a hidden bit into a user's token; for example, indicating whether the user is suspected of being a bot. However, existing ATPM constructions are limited by high communication complexity, requiring a fresh interaction with the issuer for every single token. Furthermore, they lack support for fine-grained policy requirements, preventing service providers from verifying user attributes (such as age or subscription status) without stripping away anonymity. In this work, we bridge this gap by introducing SMA2RT (Secret-Metadata Attribute-based Anonymous Rate-limited Tokens). For the first time in the hidden-metadata context, our construction supports selective attribute disclosure, thereby bridging the gap between the anonymous credentials and anonymous tokens literatures. Our construction leverages signatures on equivalence classes (SEQ) to achieve an "issue once, spend N times" capability. This allows a user to interact with the issuer only once to obtain a master credential and subsequently derive up to N unlinkable, valid tokens locally, without further online communication. This significantly reduces server load and network latency, making the scheme practical for real-time web applications. Each derived token preserves the issuer's hidden metadata bit and supports selective disclosure of the user's attributes.

We expand the well developed toolbox between quaternionic ideals and supersingular elliptic curves into its higher dimensional version, namely (Hermitian) modules and maximal supersingular principally polarized abelian varieties. One of our main result is an efficient algorithm to compute an unpolarized isomorphism $A \simeq E_0^g$ given the abstract module representation of $A$. This algorithm relies on a subroutine that solves the Principal Ideal Problem in matrix rings over quaternion orders, combined with a higher dimensional generalisation of the Clapotis algorithm. To illustrate the flexibility of our framework, we also use it to reduce the degree of the output of the KLPT$^2$ algorithm, from $O(p^{25})$ to $O(p^{15.5})$.

The devastating attacks against SIDH (Supersingular Isogeny Diffie-Hellman) have popularised the practical use of isogenies of dimension $2$ and above in cryptography. Though this effort was primarily focused on dimension 2, $4$-dimensional isogenies, have been used in several isogeny-based cryptographic constructions including SQIsignHD, SQIPrime, (qt-)Pegasis and MIKE. These isogenies are also interesting for number theoretic applications related to higher dimensional isogeny graphs. In 2024, a work by Pierrick Dartois introduced algorithms to compute efficiently chains of $2$-isogenies with Mumford's level $2$ theta coordinates in all dimensions, focusing on cryptographic applications in dimension $4$. In this paper, we improve Dartois' results by providing a simpler and faster method to compute generic isogenies in any dimension, and new computation and evaluation algorithms adapted to gluing isogenies from a product of four elliptic curves, with techniques that generalise a previous work by Max Duparc in dimension $2$. Unlike previous algorithms by Dartois, the algorithms we propose are both easy to implement and naturally constant time. We apply our results to propose the first constant time C implementation of a $4$-dimensional chain of $2$-isogenies, adapted to the qt-Pegasis algorithm and running in less than $25$ ms for a $500$ bit prime. With our new gluing evaluation method, we are able to work fully over $\mathbb{F}_p$ instead of $\mathbb{F}_{p^2}$, allowing further efficiency gains. Indeed, our new formulae accelerate the proof of concept SageMath implementation of qt-Pegasis by up to 19 % for a $500$ bit prime.

Consensus protocols in the partially synchronous setting face a fundamental trade-off: achieving optimal Byzantine fault tolerance requires a good-case latency of at least three rounds, while committing in fewer than three rounds generally entails reduced resilience. Even optimistic protocols such as SBFT (DSN'19), FaB (TDSC'06), and Kudzu (DISC'25) achieve an optimistic good-case latency of two rounds under favorable conditions, but only at the cost of reduced fault tolerance. In this work, we introduce Hydrangea, a partially synchronous state machine replication protocol that combines low latency with improved fault resilience. Let $f$ denote the maximum number of tolerated Byzantine faults, $c$ the maximum number of tolerated crash faults, and $k \ge 0$ a tunable parameter. For a system of $n = 3f + 2c + k + 1$ parties, Hydrangea achieves an optimistic good-case latency of two rounds when the total number of faulty parties (Byzantine or crash) is at most $p = \lfloor \frac{c + k}{2} \rfloor$. In more adversarial settings, with up to $f$ Byzantine faults and $c$ crash faults, it guarantees a good-case latency of three rounds. We further prove a matching lower bound: no protocol can achieve a two-round optimistic commit under this fault model if $p > \lfloor \frac{c + k + 2}{2} \rfloor$. Our experimental evaluation on geo-distributed deployments demonstrates that Hydrangea consistently achieves substantially lower latency than state-of-the-art protocols in both Byzantine-only and Byzantine–crash fault models, while also delivering modest improvements in throughput.

We continue the study of fast functions, computable by linear-size circuits, that share useful properties of random functions. Motivated by cryptographic applications, we generalize and improve on previous results in this area, obtaining the following results: - For any constant $t$, we construct a fast $t$-wise independent hash function with algebraic degree $\log_2 t$ (over $\mathbb F_2$), simultaneously optimizing both asymptotic circuit size and degree. - We simplify and improve a recent construction (ITCS 2026) of a family of fast codes with fast duals, both meeting the Gilbert-Varshamov bound. Unlike the previous construction, our construction has negligible failure probability, can accommodate general fields and rates, supports a systematic encoding, and admits fast universal encoders. - We strengthen the above to support stronger random-like properties, such as optimal combinatorial list-decoding. This is achieved by constructing, for any constant $t$, a family of fast linear functions that map any $t$ linearly independent inputs to uniform and statistically independent outputs. Prior to our work, this was only known for $t=1$. We demonstrate the usefulness of the above results to cryptography. This includes the first nontrivial protocols for perfectly secure multiparty computation whose circuit complexity scales linearly with the number of parties, as well as protocols for computing encrypted matrix-vector products with optimal asymptotic circuit complexity.

Decentralized governance plays a critical role in blockchain communities, allowing stakeholders to shape the evolution of platforms such as Cardano, Gitcoin, Aragon, and MakerDAO through distributed voting on proposed projects in order to support the most beneficial of them. In this context, numerous voting protocols for decentralized decision-making have been developed, enabling secure and verifiable voting on individual projects (proposals). However, these protocols are not designed to support more advanced models such as quadratic voting (QV), where the voting power, defined as the square root of a voter’s stake, must be distributed among the selected by voter projects. Simply executing multiple instances of a single-choice voting scheme in parallel is insufficient, as it can not enforce correct voting power splitting. To address this, we propose an efficient blockchain-based voting protocol that supports liquid democracy under the QV model, while ensuring voter privacy, fairness and verifiability of the voting results. In our scheme, voters can delegate their votes to trusted representatives (delegates), while having the ability to distribute their voting power across selected projects. We model our protocol in the Universal Composability framework and formally prove its UC-security under the Decisional Diffie–Hellman (DDH) assumption. To evaluate the performance of our protocol, we developed a prototype implementation and conducted performance testing. The results show that the size and processing time of a delegate’s ballot scale linearly with the number of projects, while a voter’s ballot scales linearly with both the number of projects and the number of available delegation options. In a representative setting with 64 voters, 128 delegates and 128 projects, the overall traffic amounts to approximately 2.7 MB per voted project, confirming the practicality of our protocol for modern blockchain-based governance systems.

The Merkle-Damgård construction (in its strengthened form as used in SHA-256 and SHA-512, the untruncated members of SHA-2) is not classically indifferentiable from a Variable-Input-Length (VIL) random oracle because of the length-extension attack. Nevertheless, Dodis, Ristenpart, and Shrimpton showed that Merkle-Damgård is publicly indifferentiable, a weaker notion that still justifies replacing a VIL random oracle by Merkle-Damgård in many security proofs when all inputs to a random oracle are public (e.g., Fiat-Shamir and full-domain-hash signatures). In this paper, we show that this replacement fails in the post-quantum setting: (Strengthened) Merkle-Damgård is not publicly indifferentiable from a VIL random oracle against quantum distinguishers with superposition access to the underlying primitive (while construction queries remain classical), even if the compression function is ideally random. We first formalize post-quantum public indifferentiability so that the corresponding composition theorem extends to the quantum random oracle model. We also introduce a post-quantum version of sequential indifferentiability, an even weaker notion. We then prove that (strengthened) Merkle-Damgård satisfies neither notion by showing that an explicit quantum distinguisher achieves non-negligible advantage against any efficient simulator, using Zhandry's compressed-oracle technique. We thus obtain an explicit, conjecture-free separation between an indifferentiability-style notion in the classical setting and its post-quantum analogue.

In 2020 and 2024 respectively, NIST released a Special Publication (SP 800-208) and a Federal Information Processing Standard (FIPS 205) specifying hash-based signature schemes with natural quantum resistance thanks to their symmetric foundation. The former recommends the stateful hash-based signature schemes LMS and XMSS, whereas the latter standardizes their stateless counterpart SPHINCS+. While in principle all three constructions can be instantiated with any secure cryptographic hash function, the concrete instances recommended by NIST are currently limited to either the SHA-2 or the SHA-3 family. Building on the maturity of these standardized families is of course a sensible choice. Yet, we argue that neither is particularly well suited for this purpose, especially once physical security matters. As an alternative we suggest pSquare-hash, an arithmetization-oriented family of lightweight tweakable hash functions. We demonstrate that such dedicated tweakable constructions ideally suit the instantiation and security requirements of hash-based signature schemes, potentially leading to efficiency advantages over standard concatenation-based approaches through either a reduction of the permutation size or the number of calls. With respect to physical security, the presence of the tweak enables a clean separation between inputs that need to be protected against leakage/faults and those that are insensitive. The arithmetization-oriented nature and choice of prime enable the effective utilization of masking schemes with superior passive and active attack resistance (e.g., prime-field and/or inner-product masking) and keep the design suitable for zero-knowledge applications. We compare higher-order masked software (Cortex-M4) and hardware (NanGate 15 nm) implementations of pSquare-hash to equivalent SHA-2, SHA-3, SKINNY-Hash, Ascon-Hash and Poseidon2 instances and exhibit favorable characteristics whenever masking is applied.

In this work, we introduce a more efficient post-quantum oblivious PRF (OPRF) design, called LeOPaRd. Our proposal is round-optimal and supports verifiability and partial obliviousness, all of which are important for practical applications. The main technical novelty of our work is a new method for computing samples of MLWE (Module Learning With Errors) in a two-party setting. To do this, we introduce a new family of (interactive) lattice problems, called MLWE-PRF with re-use (MLWE-PRF-RU). Here, the adversary is given a mix of MLWE and PRF samples where each PRF error is dependent on an adversarially-chosen matrix and the MLWE error. We rigorously study the hardness of MLWE-PRF-RU and provide a reduction from the standard MLWE to MLWE-PRF-RU, establishing a strong security foundation. We believe MLWE-PRF-RU problem family and the intermediate security reductions we introduce along the way can be of independent interest for other interactive protocols. LeOPaRd exploits this MLWE-PRF-RU assumption to realize a lattice-based OPRF design without relying on heavy machinery such as noise flooding and fully homomorphic encryption used in earlier works. LeOPaRd can feature around 138 KB total communication, compared to 300+ KB in earlier works, while also achieving about 2x reduction in online communication compared to the prior state-of-the-art result. We also identify gaps in some existing constructions and models, and propose appropriate fixes.

Modern cryptography relies on the intractability of computational problems. We present an approach to building cryptography from a new source of hardness: \emph{proving mathematical theorems}. Our main result is a construction of succinct non-interactive arguments (SNARGs) for NP under a new, but natural, assumption on the hardness of proving lower bounds in proof complexity. Specifically, our assumption states that it is impossible to prove, within a weak bounded arithmetic theory, the correctness of certifying hard tautologies against Extended Frege. This assumption is inspired by an informal mathematical challenge proposed by Razborov [Ann. Math. '15], and can be viewed as a generalization of an unconditional unprovability result due to Krajíček and Pudlák [J. Symb. Log. '89]. Our construction is a simple variant of the SNARG construction of Jin, Kalai, Lombardi, and Vaikuntanathan [STOC '24]. While the soundness of their construction was proven only for a subclass of NP, we prove its soundness for all of NP under our assumption. At the heart of our result is the observation that cryptographic reasoning is simple in a formal sense: the security proof of most cryptographic primitives can be formalized in a weak theory. In particular, we show how to formalize the scheme of Jin et al. in Jeřábek's theory $\mathsf{APC}_1$ [J. Symb. Log. '07], a weak theory of bounded arithmetic.

Message Authentication in the Short Authenticated String model (SAS-MA) allows Alice and Bob to establish a secure channel without trust in any third party, as long as they can exchange short authenticated strings, e.g. 20 bits. In a recent paper, Gu et al. [17] showed a SAS-MA scheme based on Verifiable Random Functions (VRF), which can utilize the ephemeral keys sent in the X3DH Authenticated Key Exchange (AKE), allowing for extending X3DH to SAS-MA with minimal round complexity and no changes to X3DH key distribution. X3DH is used in many messaging apps, including WhatsApp and Signal, and a SAS-MA extension of X3DH would allow app users to authenticate their connections without trust in PKI or the app’s Key Distribution Center (KDC), as long as they can exchange short authenticated strings (SAS), using out of band authenticated channels. However, a major motivation behind using X3DH as an AKE is its deniability property, i.e. that an X3DH transcript cannot serve as a proof that either Alice or Bob established a secure connection with each other. The VRF-based SAS-MA extension of X3DH of [17] violates deniability, essentially because a VRF is a signature. We show an alternative SAS-MA scheme which offers the same ease of integration with X3DH as the VRF-based SAS-MA of [17], but it (almost) maintains the deniability of X3DH. The proposal is based on a private VRF (PVRF), which allows only ‘designated-verifier’ verification of correctness. We show a low-cost PVRF variant of ECVRF, and we show that X3DH extended by our PVRF-based SAS-MA adds human-centric no-trust-in-KDC authentication to X3DH while preserving the deniability properties of X3DH.

Censorship has always existed, serving both to prevent harms and to inflict them by chilling speech, suppressing organizing, and withholding inconvenient facts and ideas; most technical work aims to prevent all forms of censorship --- the "good", the "bad", and everything in between. We study the complementary, rarely explored goal of making any censorship attempt transparent. We formalize censorship-evident publishing systems (CEPS), protocols that force both overt and covert takedowns to yield transferable evidence. We also provide a CEPS instantiation with Streisand, a proof-of-concept deployment that combines a blockchain-backed timestamp oracle, private information retrieval (PIR)-based anonymous queries to prevent extraction attempts from being conspicuous, and probabilistic Merkle-witness retrieval to produce compact censorship proofs. We present performance evaluations on a 1.3 GiB Enron-derived dataset with regex-based PII redaction to model realistic censorship, and demonstrate that a background daemon can detect heavy censorship after a small number of post-censorship queries, making Streisand an effective auditing mechanism rather than interactive file retrieval. We also discuss design trade-offs (proof size vs. computation, PIR sufficiency vs. necessity), scalability limits, and how CEPS complements existing transparency practices, with Streisand as a starting point for CEPS deployments.

This paper presents a new method for approximating the correlations of differential-linear distinguishers. From the perspective of Beyne's geometric approach, the differential-linear correlation is a corresponding coordinate of the \textit{correlation vector} associated with the ciphertext multiset, which can be obtained by using the correlation matrix of the \textit{2-wise form} of the cipher. The composite nature of the correlation matrix leads to a round-based approach to approximate the correlation vector. This simple approximation is remarkably precise, yielding the most accurate estimation for differential-linear correlations in \ascon thus far and the first DL distinguishers for 6-round \ascon-128a initialization. For \present, we present 17-round DL distinguishers, 4 rounds longer than the current record. To apply the round-based approach to ciphers with the large Chi ($\chi$) function as nonlinear functions, we derive theorems to handle the correlation propagation for $\chi$ and its 2-wise form. Strong DL distinguishers for up to 6 rounds of \subterranean and \koala-$p$ are provided, 2 rounds longer than the previous differential and linear distinguishers. Furthermore, the round-based approximation idea is also extended to the higher-order differential-linear distinguishers. We give the first second-order DL distinguisher for 6-round \ascon-128 initialization and the first second-order DL distinguishers for up to 7 rounds of \subterranean and \koala-$p$.

This paper presents high-performance Advanced Vector Extensions 512 (AVX-512) implementations of two Korean standard cryptographic algorithms: the Lightweight Secure Hash (LSH) hash function and Lightweight Encryption Algorithm-Galois/Counter Mode (LEA-GCM) authenticated encryption. For LSH, we apply three optimization strategies: single-message processing using AVX-512 512-bit vector registers, dual-message parallel processing through register interleaving, and multi-core parallelization using a dynamic queue-based pthread thread pool. For LEA-GCM, we propose an end-to-end optimization that replaces scalar Counter mode (CTR) encryption with 16-block AVX-512 parallel processing and Streaming SIMD Extensions (SSE)-based Galois Hash (GHASH) authentication with VPCLMULQDQ-based 4-block parallel processing. Performance evaluation on an Intel Core i7-1165G7 (Tiger Lake) processor shows that LSH-256 achieves an average 1.16× throughput improvement and LSH-512 achieves an average 1.61× improvement over the Korea Internet and Security Agency (KISA) AVX2 reference implementation. Dual-message interleaving achieves an average superlinear speedup of 2.28× driven by instruction-level parallelism (ILP), and the 8-core thread pool delivers speedups of 3.50× to 5.12×. The optimized LEA-GCM implementation achieves a 3.26× throughput improvement over the KISA SSE-based reference and a 12.1× improvement over the pure software implementation for 4096-byte inputs, with correctness verified against KISA official test vectors.

Electronic voting systems inherently encompass a structural tension among ballot secrecy, verifiability, and coercion resistance. Voters must be able to verify whether their votes have been included; however, if such verification information can serve as evidence presentable to a third party, it becomes a basis for post-election intimidation. Existing studies have focused primarily on performance evaluation or data separation, and have not comprehensively addressed the structural tension between verifiability and coercion resistance. This study defines this tension as the verification paradox and designs and implements an electronic voting prototype on a three-organization consortium based on Hyperledger Fabric 2.5, combining a 2-of-3 endorsement policy, nullifier-based anonymity, Exponential ElGamal homomorphic tallying, zero-knowledge proof (ZKP)-based ballot validity verification, panic password-based deniable verification, and Private Data Collection (PDC)-based coerced vote separation. Quantitative evaluation results confirm a server latency overhead of +0.9% for ElGamal relative to the AES performance baseline, statistical indistinguishability between normal and panic responses (p > 0.05), and a peak throughput of approximately 40.7 TPS (with an error rate of 0%) under 1,000 concurrent voters. This study demonstrates that permissioned blockchains can provide practical mitigation of the verification paradox through implementation and quantitative evaluation.

The Korean Cryptographic Module Validation Program (KCMVP) is a national certification system that verifies the security and conformity of cryptographic modules deployed in government and public institutions. The current process typically takes about one and a half years, during which frequent supplement requests and the resulting retesting cycles substantially raise costs and delay schedules. To address this, we propose an AI-based pre-certification framework that combines rule-based deterministic detection (L1), RAG-based guideline-evidence retrieval (L2), and LLM-based final decision (L3) into a funnel-shaped pipeline that progressively reduces false positives. L1 applies more than 170 YAML inspection rules across four pattern types (missing, regex, semantic, ast) to perform deterministic detection. L2 retrieves and attaches KCMVP guideline evidence to each violation through multi-stage RAG search, and L3 employs Gemini 2.5 Flash-Lite to make context-aware decisions on false-positive candidates. In an initial evaluation on 128 Ground Truth cases derived from the KISA LEA code, the system detected all 128 cases, achieving 100% recall, while L3 correctly removed 9 of 46 FP candidates (19.6%) without inducing any false negatives (FN), confirming the stepwise refinement effect of the funnel structure. A blind verification on a certified commercial cryptographic module (~14.5 KLOC) yielded a low detection frequency of 0.58 cases per 1,000 lines of code, supporting the system’s practicality in real environments.

The advancement of quantum computing threatens public-key cryptographic algorithms used in TLS connections, such as RSA and ECDHE. The Harvest Now, Decrypt Later (HNDL) attack exposes long-term confidential data to risk even before quantum computers are practically realized, yet a systematic methodology for immediately quantifying the quantum vulnerability of individual TLS connections remains absent. This paper proposes a layered risk scoring model that quantifies the quantum threat exposure of TLS connections on a 0–100 scale. The model decomposes risk into five independent layers—TLS protocol exposure (L1), legacy public-key vulnerability (L2a), AES-128 Grover weakening (L2b), PQC Level-1 vulnerability (L2c), and certificate expiration urgency (L3)—and incorporates an HNDL global multiplier M that reflects the confidentiality retention period of transmitted data. Applied to 502 real-world TLS sessions across four industry sectors with M = 1.50, the domestic average risk score (16.0) is approximately 34% higher than the global average (11.9), with domestic legacy key exchange usage at 77.4% versus 53.5% globally and PQC adoption at 22.6% versus 46.5%. These results quantitatively confirm the elevated quantum risk of domestic network infrastructure, underscoring the urgency of PQC transition.

The “Harvest Now, Decrypt Later (HNDL)” attack—which intercepts and stores encrypted communications before quantum computers become practical and decrypts them afterward—poses a long-term threat to TLS communication channels. Following the completion of NIST PQC standardization, organizations must pursue a phased migration of their TLS layers; however, existing approaches are limited by late detection of configuration errors, absence of cryptographic asset tracking, and insufficient automated response. This paper proposes an 11-Step DevSecOps pipeline grounded in Policy as Code. The pipeline automatically validates and deploys a 3-Stage TLS migration—Classical ECC (Stage 1), Hybrid PQC (Stage 2), and Advanced Hybrid PQC (Stage 3)—through 11 steps per execution, integrating OQS-Nginx custom builds, security scanning, CBOM Diff, and matrix CI regression detection. In our evaluation against six PQC toolchain pitfalls, standard SCA/SAST/SBOM pre-detected 0/6, whereas custom builds pre-prevented 5/6 and matrix CI detected 6/6 at runtime. In an evaluation of LLM-based code migration across 80 trials (55 responses received), even with static AST validation applied, 24 failures due to signature/argument hallucination (43.6% of response trials) were only caught at runtime, quantitatively confirming that semantic execution validation is an essential component of multi-layered defense.

A recent paper by Calderini et al. investigates the use of a CCZ transformation to mask the quadratic central map in a multivariate scheme, providing an instance leading to a system of degree four. A following paper by Caminata et al. presents two methods to reduce the masked system back to a quadratic system. In this work we further study the method based on the quadratic relations between input and output of the masked function, generalizing it and applying to any CCZ transformation (of any quadratic map). Moreover, we study how the existence of these quadratic relations can be used to study whether a function can be CCZ equivalent to a quadratic map and, more generally, to study whether two functions can be CCZ equivalent. In fact, this analysis gives us necessary conditions that can be checked also in relatively large dimensions. Particularly, we completely analyse the cases of vectorial Boolean functions with 1 and 2 output bits.