International Association
for Cryptologic Research

The quantum random oracle model (QROM) has become the de-facto model to analyze post-quantum security of practical cryptographic schemes which use hash functions. The quantum random permutation model (QRPM), on the other hand, has not enjoyed a similar level of success for studying permutation-based schemes. A main reason is that it lacks the features offered by the former model to enable security proofs: namely, query-recording and reprogramming.

In this work, we present a new approach to simulate bidirectional-query random permutation oracles using Feistel constructions which unlock the above two features in the QRPM. We then show the potential of our framework by: • Analyzing the post-quantum security of a recent variant of the Fiat-Shamir transformation — called duplex-sponge Fiat-Shamir (Chiesa and Orrù, TCC 2025) — which is deployed in the wild. • Recovering a meaningful quantum query lower bound for the double-sided zero search problem — the hardness of which was conjectured by Unruh, but has resisted many attempts until very recently — via a simpler approach that generalizes the compressed oracle technique (Zhandry, Crypto 2019) to the QRPM.

All in all, our work demonstrates how the "Feistel toolkit" enables us to achieve reprogramming and query-recording for quantum random permutations, thereby effectively bridging the gap between the QROM and the QRPM in terms of analyzing real-world post-quantum cryptographic schemes and relevant quantum query complexity problems.

A blind signature scheme is an interactive protocol that enables a user to obtain a signature on a message without revealing any information about the message–signature pair to the signer. Despite more than 40 years of research, all existing constructions suffer from at least two of the following limitations.

1. The protocol is not round-optimal, requiring more than two messages to be exchanged during the signature phase.

2. There is only game-based security and/or lack of composability with global and observable setup (i.e., there is a need for trusted parameters or to program random oracles).

3. There is a need (unlike regular signatures) of demanding hardness assumptions, especially when targeting post-quantum security.

In this work, we bypass prior results by showing how to blindly sign a message, simultaneously overcoming all of the above three limitations. Specifically, we construct a (Global) Universally Composable (UC), two-round (optimal) blind signature protocol that relies only on one-way functions (optimal), without trusted parameters. The only deviation from the plain model is the need for a global non-programmable random oracle (NPRO). Nicely, our scheme can be instantiated from a variety of assumptions believed to be post-quantum secure (e.g., AES). A central technical component of our scheme is the construction of a novel commitment scheme that enjoys a special (mild) form of composability, which may be of independent interest. Finally, we argue that a concrete instantiation of our scheme has signature sizes and communication complexity suitable for practical applications.

Recently, the notion of dynamic zk-SNARKs was introduced. A dynamic zk-SNARK augments a standard zk-SNARK with an efficient update algorithm. Given a valid source statement-witness pair $(x,w)$ together with a verifying proof $p$, and a valid target statement-witness pair $(x',w')$, the update algorithm outputs a verifying proof $p'$ for $(x',w')$. Crucially, $p'$ is not recomputed from scratch; instead, the update algorithm takes time roughly proportional to the Hamming distance between $(x,w)$ and $(x',w')$, analogous to how dynamic data structures update the result of a computation after a small change.

In this paper, we initiate the study of designated-verifier dynamic zk-SNARKs: dynamic zk-SNARKs in which only a designated verifier, holding secret verification state, can be convinced by a proof. Following recent advances in designated-verifier zk-SNARKs---such as efficient post-quantum designated verifier SNARKs (CCS 2021) and designated verifier SNARKs with very small proofs (CRYPTO 2025)---we construct a designated-verifier dynamic zk-SNARK with $O(\log n)$ update time, constant proof size, and concrete efficiency. Our construction significantly outperforms Dynalog (both asymptotically and concretely), the only publicly verifiable dynamic zk-SNARK with polylogarithmic update time (Wang et al., 2024).

The concrete efficiency of our construction enables, for the first time, an efficient implementation of a dynamic proof of index: Given a digest $d$ of an arbitrary set and a digest $d'$ of its sorted index (e.g., binary search tree), we produce a SNARK proof certifying the consistency of $d$ and $d'$. More importantly, this proof can be updated in sublinear time when the underlying set changes---for example, when an element is modified or inserted, potentially altering the sorted order. We demonstrate applications of designated-verifier dynamic proofs of index to verifiable dynamic database outsourcing, where a client outsources a database and later maintains verifiable indices for efficient query answering, even under arbitrary database updates.

In the formal verification of complexity-theoretic properties of cryptography, researchers have traditionally attempted to capture ``overwhelming truth'' (satisfaction with all but negligible probability) via satisfaction on individual traces of probabilistic execution. However, this approach introduces significant complexity when quantification is present: satisfaction of existential quantification over traces often produces witnesses---such as nonce-guessing oracles---that witnesses that, without further constraints, may not correspond to meaningful global objects like PPT algorithms respecting causal structure. This discrepancy creates significant obstacles when attempting to combine trace properties, such as reachability, with properties that hold globally, such as algorithmic indistinguishability.

We resolve this by shifting from local satisfaction on individual traces to a semantics based on ever-decreasing non-negligible sets. We demonstrate that the logical key to this unification lies in first-order modal logic S4 with non-negligible sets as possible worlds, rather than the propositional S5 fragment with traces as possible worlds suggested in previous investigations by the Squirrel Prover team. By introducing a PPT computational first-order S4 Kripke semantics and adopting Fitting's embedding for trace properties, we provide a unified quantified treatment of overwhelming truth for trace properties and indistinguishability that admits cut-elimination and remains sound and complete---resolving an open question in the literature.

We show that Fitting's embedding naturally accommodates the higher-order quantification used in the Squirrel prover by interpreting function types as sorts in a many-sorted first-order logic; this reduces the need for the specialized $\texttt{const}$ predicate and its associated structural restrictions. Finally, using our findings, we present a hybrid semantics for CryptoVampire that eliminates the need for bounded Skolemization.

In this paper, we examine the One-time signature scheme using run-length encoding, as proposed by Steinwandt et al., under the scenario where an adversary is allowed to obtain signatures on two messages before attempting to forge a signature on a third message. Our analysis follows the line of security discussion presented by Groot Bruinderink et al. in their paper “Oops, I Did It Again – Security of One-Time Signatures under Two-Message Attacks.” By considering various attack models and different strategies, we estimate both the attack complexity and the probability of forging a signature. Our results indicate that the signature scheme performs well under a two-message attack, making it an interesting candidate for a few-time signature scheme. Few-time signature schemes such as HORS are a fundamental building block of stateless hash-based signature schemes.

While existing Proof-of-Work (PoW) based blockchain protocols have demonstrated innovative potential, they face inherent limitations regarding scalability, efficiency, and decentralization. The compact block propagation method, though effective in reducing network bandwidth and propagation delay in ideal environments, suffers from performance degradation due to mempool inconsistencies among nodes. This paper proposes a novel block propagation and consensus protocol that mitigates the blockchain's dependency on mempool synchronization. The proposed approach redefines the PoW process to shorten the time to consensus despite increased block sizes. Specifically, it includes a compressed transaction input ID list within the compact block to induce nodes to immediately begin mining without full verification. The full verification of transactions adopts a 'delayed verification' method, performed in parallel with the mining operation. This study enables the processing of more transactions quickly while maintaining the decentralization and security of Bitcoin (e.g., achieving approximately 66.7 TPS with 10MB blocks).

Post-quantum migration must balance two risks: future quantum breaks of classical cryptography and residual uncertainty in newly standardized post-quantum cryptography (PQC). Hybrid Key Encapsulation Mechanisms (KEMs) hedge by combining a classical and a PQC component. Prior work shows that optimized combiners may omit large public inputs from the final key-derivation step, but only if the derived key remains bound to the ciphertext transcript and, in multi-target settings, to the intended recipient; otherwise ciphertext manipulation and cross-recipient amortization at the KDF layer can increase an adversary’s concrete advantage. In practice, these requirements are often conflated, leading either to unsafe secret-only schedules or to unnecessary hashing of large transcripts. We distill practitioner-facing, interface-level guidance by separating ciphertext-to-secret binding from multi-target security, and by adopting ciphertext second-preimage resistance (C2PRI) as a checkable criterion under deployed encodings.

We apply this perspective to X-Wing, a hybrid combining ML-KEM with an X25519-based DH-to-KEM under consideration as an IETF Internet-Draft. Under the deployed raw-output interface, we show how distinct classical ciphertexts can yield the same shared secret, motivating hashing of the classical ciphertext in the outer KDF and clarifying when recipient public-key context is needed in multi-target deployments. We also show that similar issues arise for other widely deployed elliptic-curve Diffie–Hellman (ECDH) APIs, including P-256, when they export only partial point information. Finally, we summarize when ciphertext hashing can be omitted, including canonical prime-order abstractions such as Ristretto255 and designs that internalize transcript context via per-component hashing, as in HPKE Diffie–Hellman-based KEM (DHKEM) profiles.

Neural network model extraction attacks pose a serious threat to the intellectual property of deep learning models. While most prior work focuses on Fully Connected Networks (FCNs), effective extraction of Convolutional Neural Networks (CNNs) remains underexplored, particularly in the hard-label setting. In this work, we propose the first systematic method for the recovery of complete CNN parameters in such conditions. By reformulating convolutional layers as sparse Block Toeplitz with Toeplitz Blocks (BTTB) matrices, we extend the model extraction attack method from FCNs to CNNs. The proposed method supports both one- and two-dimensional CNNs, handling scenarios with multiple kernels, multi-channel structures, and average pooling. To enhance computational efficiency and scalability, a kernel-centric clustering algorithm is proposed to exploit kernel parameter sharing, and a Singular Value Decomposition (SVD)-based acceleration strategy is adopted to address the computational cost of large sample sets. Moreover, we perform experiments to demonstrate that our method accurately and efficiently extracts CNN parameters, including multi-channel, multi-kernel and average-pooling layers, with a worst-case relative error of $2^{-17.75}$ and up to $2^{9.26}$ speedup, and recover large models LeNet-5 within practical runtime.

Efficiently masking multiplications in software is a long standing and extensively studied problem. A variety of gadgets have been proposed to perform these multiplications, each offering different trade-offs between efficiency and security. However, almost all existing solutions rely on arithmetic masking, in which multiplications cannot be naturally protected. In this work, we introduce two novel gadgets, named A2S and S2A, that enable conversions between arithmetic masking and Shamir’s Secret Sharing (SSS)-based masking. With this approach, multiplications can be performed naturally and securely in a sharewise manner. We prove that our gadgets achieve SNI security, which provides security guarantees and straightforward composability. Moreover, we demonstrate that composing them with multiplication yields PINI security. We then provide a detailed complexity analysis and discuss the contexts where our gadgets are most relevant.

As a case study, we apply them to the MQOM post-quantum signature scheme, a candidate in the second round of the NIST additional post-quantum digital signature standardization process. When computing the sensitive multiplications in MQOM, for masking order t = 1, our approach reduces the number of multiplications, additions, and randomness requirements by 31%, 71%, and 60%, respectively, compared to the state of the art, while incurring only small additional memory overhead. We further show that these gains not only hold but actually increase as the masking order grows. Our results demonstrate that arithmetic-to-SSS conversions provide an effective and scalable path toward efficient masked implementations, making them particularly attractive for postquantum cryptography.

We demonstrate a general and efficient technique to Hensel-lift a solution to a system of ($p$‑adically analytic) equations which may be given implicitly in the form of an efficient evaluation algorithm. Contrary to textbook Hensel lifting, we do not require the equations to be represented explicitly; indeed, our main application uses the method for a system of equations that can be exponentially larger than its representation as an arithmetic circuit: we show how to compute traces of elliptic-curve endomorphisms over a finite field $\mathbb{F}_q$ by constructing an (approximate) lift to $\mathbb{Z}_q$. Our examples include endomorphisms represented as a chain of Vélu, √élu, modular, or radical isogenies, as well as HD‑embedded endomorphisms. The resulting trace-computation algorithm outperforms the state of the art both asymptotically and concretely.

Position verification schemes are interactive protocols where entities prove their physical location to others; this enables interactive proofs for statements of the form "I am at a location L." Although secure position verification cannot be achieved with classical protocols (even with computational assumptions), they are feasible with quantum protocols. In this paper we introduce the notion of zero-knowledge position verification, which generalizes position verification in two ways: 1. enabling entities to prove more sophisticated statements about their locations at different times (for example, "I was NOT near location L at noon yesterday"). 2. maintaining privacy for any other detail about their true location besides the statement they are proving. We construct zero-knowledge position verification from standard position verification and post-quantum one-way functions. The central tool in our construction is a primitive we call position commitments, which allow entities to privately commit to their physical position in a particular moment, which is then revealed at some later time.

The primary goal of Anamorphic encryption ($\mathsf{AE}$), introduced at Eurocrypt 2022, is to enable private communication even in highly adversarial settings, such as when an adversarial $\textit {dictator}$ "legally" confiscates a user's secret keys (compromising the receiver's privacy) and/or coerces users into sending specific messages (compromising the sender's privacy). To achieve this, $\mathsf{AE}$ embeds hidden additional messages within seemingly innocuous ciphertexts where the sender and receiver comply with the dictator's demands and, in doing so, $\mathsf{AE}$ uncovers novel structural properties of encryption mechanisms. One methodology that extends the capability of a ciphertext is to embed the hidden anamorphic message in the randomness used in encryption. However, not all schemes reveal this randomness as part of the decryption process! Here, we unveil a conceptually simple yet general new methodology that achieves $\mathsf{AE}$. It is based on the concept of $\textit {Trapdoor-Aided Randomness Recovery}$ by which one can generate special key pairs $(\mathsf{pk},\mathsf{sk})$ that are still indistinguishable from honestly generated key pairs but possess an associated trapdoor $\mathsf{td}$ that first allows for randomness extraction from a ciphertext (and nothing more). Secondly, importantly and differently from prior proposals, the new trapdoor should be different from and computationally independent of "the decryption trapdoor key." Primarily, this new methodology allows for a generic construction of $\textit{public-key}~\mathsf{AE}$ which is a notion introduced at Crypto 24, where, to date, the only known public-key anamorphism relied on a specific CCA encryption scheme. Note that public-key $\mathsf{AE}$ eliminates the need for a preliminary private interaction between the receiver and the sender, thus greatly extending the applicability of anamorphism. In addition to obtaining public-key anamorphism, the new methodology, in turn, generically allows for extended anamorphic properties: Specifically and significantly, the methodology allows protections against a dictator that may ask for the randomness employed by the sender.

We then show concrete instantiations of the above methodology based on known lattice-based schemes. Specifically, due to the new methodology, we give efficient anamorphic versions of the Dual Regev scheme and the Lindner-Peikert scheme. Technically, we first define a new problem, called $\textit{randomness finding}~(\mathsf{RFinding})$, which requires that even if the adversary obtains the receiver's secret key, then, while it can decrypt, it cannot fully recover the randomness from the ciphertext. Secondly, we reduce the standard LWE assumptions to the hardness of $\mathsf{RFinding}$ for both schemes. Notably, in both schemes we achieve public-key anamorphism utilizing the "trapdoor techniques for lattices" introduced by Micciancio and Peikert at Eurocrypt 2012.

We present the first formally verified implementation of a hash-based signature scheme that is linked to a machine-checked proof of security. Specifically, we provide reference implementations of XMSS and XMSS$^{\textrm{MT}}$ written in Jasmin, targeting the AMD64 architecture. Beyond the implementations, we provide formal EasyCrypt specifications of XMSS and XMSS$^{\textrm{MT}}$, transcribed from RFC~8391, and prove that our implementations adhere to these specifications. Furthermore, for XMSS, we give a machine-checked proof that our specification of RFC~8391 refines the abstract specification proven secure in EasyCrypt by Barbosa, Dupressoir, Grégoire, Hülsing, Meijers and Strub [CRYPTO'23]. In particular, we prove the security of our specification via a reduction, demonstrating that breaking our specification contradicts the [CRYPTO'23] result for our instantiation. Consequently, our implementation is not only functionally correct, but also adheres to a specification that is proven secure. The core technical challenge in our work resides in bridging low-level implementations of TreeHash algorithms with high-level functional specifications used in the pre-existing formalization.

Homomorphic Signatures (HS) enable the authentication of data that has been processed by an untrusted party, allowing a verifier to check the correctness of a computation without access to the original signed inputs. Since their introduction, HS have evolved from algebraically restricted linear schemes to expressive non-linear and Fully Homomorphic Signature (FHS) constructions, spanning diverse cryptographic assumptions and security models.

This paper presents a Systematization of Knowledge (SoK) on homomorphic signatures. We organize existing schemes along key dimensions including functional expressiveness, underlying cryptographic primitives, security notions (selective vs. adaptive, single-key vs. multi-key), and privacy guarantees such as context hiding. This unified perspective highlights a fundamental shift from algebraic constructions toward proof-based and post-quantum designs, as well as the growing importance of Multi-Key Homomorphic Signatures (MKHS) for decentralized settings. We conclude by identifying open problems and emerging directions that must be addressed to bridge the gap between theoretical HS constructions and practical verifiable computation.

We show how to improve rank-metric solvers when certain side information (hints) about the secret is available. Concretely, we adapt the kernel search algorithm for MinRank and the GRS algorithm for the Rank Syndrome Decoding problem when some entries in the rank decomposition of the error matrix are known. This setting is motivated by side-channel leakage and cryptographic applications: Mirath and RYDE, two signature candidates in the NIST post-quantum competition, rely on these problems and employ secret keys in this decomposed form. As a main technical ingredient, we give an optimal procedure for guessing a subspace containing the row space of a systematic matrix given only partial knowledge of its entries. Further, we describe a profiling side-channel attack on the reference implementation of Mirath to demonstrate the plausibility of obtaining such hints.

Masking is the standard defense against power-based side-channel analysis (SCA) for cryptographic software, in which sensitive variables are split into independent shares. Although prior work often attributes leakage to microarchitectural effects, architectural interactions alone can already introduce subtle leaks that remain poorly understood. In this work, we propose ISALeak, a target-agnostic framework for analyzing full masked implementations to precisely identify and attribute the root causes of side-channel leakage at the instruction-set (ISA) level. ISALeak complements statistical tests such as TVLA by not only detecting leakage, but also localizing and explaining its source. We evaluate our approach on masked AES and masked Ascon across multiple compiler versions and optimizations. Using power measurements from ASIC (PicoRV32) and FPGA (Ibex) RISC-V cores, we show that 20-40% of the leaks detected by TVLA for masked AES originate from architectural register interactions. For masked Ascon, 17-23% of the observed leakage likewise stems from ISA-level effects and consistently manifests in physical power traces.

Threshold ECDSA has been an active research topic in recent years, driven by its wide-ranging applications, particularly in blockchain domains. Existing constructions of threshold ECDSA generally fall into two categories: those based on threshold linearly homomorphic encryption (TLHE) and those leveraging the Multiplicative-to-Additive (MtA) paradigm. The TLHE-based approach (e.g., WMC24 in NDSS'24) achieves constant communication per party but incurs an expensive online phase and requires a broadcast channel. In contrast, the MtA-based approach (e.g., DKLs24 in S\&P'24) offers an optimal online phase and avoids the use of a broadcast channel. However, it has the drawback of requiring linear (i.e., $O(n)$) communication per party when $n$ parties are involved.

In this work, we propose an MtA-based threshold ECDSA scheme with constant amortized communication. At the core of our approach is the use of packed secret sharing, which enables the same MtA operations to generate $\ell = \epsilon n$ signatures. With a constant $\epsilon$, the communication complexity per signature is amortized to a constant in dishonest-majority settings. Furthermore, we extend this packing technique to design a robust threshold ECDSA with constant communication under honest-majority settings, which ensures the delivery of valid signatures as long as a sufficient number of parties are honest. In contrast, the state-of-the-art robust MtA-based construction (TX25 in S\&P’25) requires linear communication per party. We implement our packed constructions using both CL-based and OT-based MtA protocols. Benchmark results show that our amortized efficiency surpasses that of DKLs24. Moreover, our robust scheme outperforms TX25 and has significantly better online efficiency with comparable overall complexity to WMC24.

Arithmetic correlations represent the extension of classical correlations into the with-carry setting and serve as a critical performance criterion for pseudorandom sequences constructed via feedback with carry shift registers. The arithemetic correlation values should be as small as possible for application perspective. This paper establishes a sufficient condition for $N$-ary sequences to have ideal arithmetic correlation. Based on this characterization, it is demonstrated that $N$-ary $\ell$-sequences with a prime connection integer $p$ satisfying $p\equiv1(\textup{mod}\:N)$ exhibit ideal arithmetic correlation. Furthermore, under the condition $N^{p-1}\not\equiv1(\textup{mod}\:p^{2})$, this result is extended to the case where the connection integer is a prime power. Additionally, an upper bound is established for the arithmetic crosscorrelation of binary sequences derived from Fermat quotients with coprime periods.

This paper shows that the Merkle-Damgard construction is not public indifferentiable from a Variable-Input-Length (VIL) random oracle in the post-quantum setting. Classically, Merkle-Damgard is not indifferentiable from a VIL random oracle due to the length extension attack. Yet, it satisfies public indifferentiability, a weakened but practically powerful notion introduced by Dodis, Ristenpart, and Shrimpton. This classical result guarantees that Merkle-Damgard can safely replace VIL random oracles in many cryptosystems such as Fiat-Shamir and Full Domain Hash (FDH) signatures, as long as inputs to random oracles are public, while preserving the validity of security proofs. In this work, we show that this ``free replacement'' of a VIL random oracle by Merkle-Damgard does not hold in the post‑quantum setting. We first formalize post‑quantum public indifferentiability in a way that the composition theorem lifts to the QROM-based proofs for classical cryptosystems, and also define a post-quantum version of sequential indifferentiability, which is even weaker than public indifferentiability. We then show that Merkle-Damgard is neither post‑quantum public indifferentiable nor post-quantum sequentially indifferentiable from a VIL random oracle. Specifically, we construct an explicit quantum distinguisher and prove that its advantage is non-negligible against any efficient simulators for either notion, utilizing Zhandry's compressed‑oracle technique. To the best of our knowledge, this is the first conjecture-free example showing that a construction can satisfy a classical indifferentiability-style security notion yet fail to satisfy the corresponding post-quantum notion.

This paper presents a formal framework for decentralized identity (DID), which achieves both minimal disclosure and session unlinkability under public verifiability. We instantiate this framework as PrivDID. In PrivDID, a user can prove a predicate about a committed attribute via a single ring signature, thereby hiding in an anonymity set dynamically selected from the public ledger. PrivDID builds on Pedersen commitments and binary-range encodings, and is proven secure in the random oracle model. It is fully W3C-compliant and requires no trusted setup. Implementation shows practical efficiency in storage, communication, and computation, confirming real-world feasibility.