International Association
for Cryptologic Research

Overhead costs associated with post quantum (PQ) algorithms, especially digital signatures, create a significant barrier to incorporation and adoption of post quantum cryptographic protocols in various settings. To counter this, the working group for the Messaging Layer Security (MLS) protocol under the Internet Engineering Task Force has proposed an approach where traditional and PQ sessions of the protocol are strategically combined in such a way as to amortize PQ-associated overhead, i.e., an Amortized Post Quantum (APQ) combiner. In this work, we implement and benchmark APQ using standardized NIST algorithms (ML-KEM and ML-DSA) integrated into OpenMLS with native Rust cryptographic libraries, presenting the first comprehensive performance evaluation of APQ to include PQ authenticity. Our evaluation encompasses execution run-time, message size, and memory consumption a cross various security levels and amortization ratios to compare and contrast MLS with traditional-only, APQ confidentiality-only, APQ confidentiality+authenticity, and an alternative hybrid ciphersuite. We demonstrate that APQ achieves exponential improvements in message size and memory efficiency as amortization traditional:PQ ratios decrease from 1:1 to 1:100, with optimal performance observed around 1:50 ratios. These findings establish APQ as a practical solution for deploying post quantum security in resource constrained settings.

Several works explored the use of discrete-logarithm-based zero-knowledge proof systems in order to prove the validity of Ring LWE ciphertexts and/or FHE ciphertexts. A technique suggested by del Pino {\it et al.} (PKC'19) notably enables proofs of $1$KB for the task of proving the validity of NewHope ciphertext using a variant of BulletProofs. A recent work of Libert (PKC'24) described a pairing-based adaptation of del Pino {\it et al.}'s approach with proofs of $3$ or $6$ group elements. While space-efficient, the latter solution is rather expensive in terms of proving time. In this work, we provide new NIZK arguments for the Ring-LWE-based public-key scheme proposed by Joye (CT-RSA'24), which is used in a variant of TFHE. The new schemes feature slightly longer proofs than in earlier pairing-based constructions with short proofs, but the prover is much faster. The number of exponentiations is reduced by a factor $\approx 7$ and the common reference string is compressed by a factor $\approx 9$ (and reduced to $1.5$MB for practically relevant parameters). We provide implementation results that confirm these estimations.

We introduce the Algebraic Isogeny Model (AIM): an algebraic model, akin to the Algebraic Group Model in the group setting, for isogenies and supersingular elliptic curves. This model is significantly more general than previous ones, such as the Algebraic Group Action Model: the AIM works with arbitrary isogenies over $\mathbb{F}_{p^2}$, rather than being limited to oriented ones, which gives considerably more power to the adversary. Within this model, we obtain three results. First, we show that any result in the AGAM can be lifted to the AIM, strengthening previous results against more powerful adversaries. Then, we prove that the SQIsign identification protocol is ID-sound: in turn, this implies that SQIsign is EUF-CMA secure in the Quantum Random Oracle Model, resolving (in the AIM) a long-standing open problem. Lastly, we establish the equivalence of the DLOG and CDH problems for all SIDH-derived key exchanges, such as M-SIDH, binSIDH, and terSIDH.

We study t-out-of-n threshold fully homomorphic encryption (ThFHE) in the synchronous setting, i.e., when the set of t decryptors is known at the outset of the decryption protocol. It has been observed in various works that the synchronous setting assumption enables to efficiently circumvent one of the major difficulties of ThFHE, namely hiding noise terms whose gigantic magnitude is incurred by the reconstruction coefficients of Shamir secret sharing. Yet, prior to this work, ThFHE in the synchronous setting had not even been properly defined. As a first contribution, we provide a clear syntax for ThFHE in the synchronous setting, as well as two security models: a weak model in which designating the set of decryptors is only viewed as an enabler of efficient decryption and it is fine for non-designated parties to be able to decrypt as long as there are sufficiently many of them; and a much stronger model where a set of decryptors which does not exactly match the designated set should not learn anything. Then, we show that the main existing schemes (Mouchet et al., Journal of Cryptology, 2023; Mouchet et al., ACM CCS, 2024) are insecure, even in the weak model, by describing efficient key-recovery attacks. Finally, we propose a simple and efficient construction which achieves security in the strong security model, by masking the partial decryption shares with pseudorandom functions.

Incremental preprocessing in private information retrieval (PIR) schemes refers to handle insertions, modifications, and deletions to the database without requiring complete preprocessing after each update. This broadens the applicability of PIR in practical scenarios. However, two major issues remain: the concept of incremental preprocessing for the single-server PIR is still not established, and the row-level update strategy (iSimplePIR (Row-level)) introduces excessive unnecessary overhead. This paper aims to efficiently extend incremental preprocessing to the single-server setting. To our knowledge, we are the first to propose the formal definition of single-server incremental PIR. Besides, we construct an entry-level incremental scheme (iSimplePIR (Entry-level)) based on SimplePIR (USENIX ’23). iSimplePIR (Entry-level) supports real-time updates of individual entries, as well as optimization of communication for scenarios with certain update cycles by incorporating a row aggregation mechanism. For a 1\% column-major update in a 1GB database, iSimplePIR (Entry-level) achieves a 224$\times$ reduction in preprocessing computation overhead and a 4.2$\times$ reduction in both communication and monetary costs compared to iSimplePIR (Row-level). When applied to password breach detection with completely random entry updates, iSimplePIR (Entry-level) reduces preprocessing time by 86$\times$. Our technique can be applied to reduce the preprocessing cost of any protocol in the SimplePIR family, such as DoublePIR, authenticated PIR (based on the LWE assumption), VeriSimplePIR, and YPIR.

Unbalanced private computation on set intersection (uPCSI) enables two parties to securely compute fine-grained functions over $X\cap Y$, where $|Y|\ll |X|$. Existing works proposed a uPCSI framework based on fully homomorphic encryption (FHE)-based private set intersection (PSI) protocols. However, their solutions face efficiency limitations, as they introduce an additional comparison procedure with a complexity of $\mathcal{O}(|Y|\log|X|)$.

In this paper, we present a lightweight uPCSI framework with semi-honest security. First, we propose a permuted multi-query private membership test (pmqPMT) protocol and its labeled variant from the FHE-based PSI, thereby avoiding the costly comparison procedure. Upon our pmqPMT, we propose an optimized uPCSI framework for computing arbitrary functions over the intersection, along with several specific optimizations for better efficiency. Besides, our framework can be extended to support more comprehensive labeled uPCSI requirements, covering both single-labeled and double-labeled cases. Compared to the state-of-the-art uPCSI protocols, we achieve over a $4.7\times$ online speedup and reduce communication costs by 15% on average.

Single Sign-On (SSO) protocols allow an identity provider to authenticate users and report the outcome by issuing identity attestations. Recent attacks show that breaching the identity provider infrastructure enables adversaries to issue arbitrary identity attestations and impersonate users. Survivable SSO protocols limit the risks of similar intrusions, but they have only been defined for password-based authentication, inheriting their limitations against powerful attacks such as credential phishing. While phishing-resistant passwordless authentication protocols have been standardized, they are not designed to guarantee intrusion tolerance. We initiate the research for Survivable Passwordless SSO (SPS) and propose a modular approach which includes the novel definition of Survivable Passwordless Challenge-response (SPC) protocols for authentication as a sub-routine of SSO. We give the first frameworks and game-based security definitions both for SPC and SPS which capture both novel attack classes, such as session injection attacks in a decentralized setting, and existing but not yet formalized attack classes, such as detection of cloned authenticators. The design of the models includes novel strategies to capture proactive security in survivable protocols within security definitions and to compose authentication and SSO through a modular approach. Our strategies and models may also be applied with minor modifications to non-survivable protocols, possibly providing a novel approach to assess the security of existing SSO protocols.

Fully Homomorphic Encryption (FHE) enables computations to be performed directly on encrypted data, without ever requiring decryption. This capability is particularly crucial for privacy-preserving outsourced computation in sensitive fields such as healthcare and finance. While FHE ensures data confidentiality under the honest-but-curious adversarial model, achieving full malicious security, encompassing both integrity and privacy, requires an additional layer of verifiability.

To address this, a growing body of research has explored combining FHE with techniques from verifiable computation, leading to the notion of verifiable FHE (vFHE). However, the integration of these two paradigms often results in substantial computational overhead, making existing approaches largely impractical for real-world deployment.

In this work, rather than targeting general-purpose verifiable FHE, we design a novel and practical verifiable homomorphic encryption scheme tailored for an important and widely used operation: matrix–vector multiplication. We provide an open-source implementation and our experimental results demonstrate that the proposed scheme achieves high efficiency, making it ready for practical adoption.

Masking is a principal countermeasure against side-channel attacks, yet its practical application is often hindered by its high randomness cost. While randomness reuse is a common efficiency strategy, securely managing the resulting algebraic dependencies without significant overhead has been a central challenge. Previous approaches have either resorted to injecting costly extra randomness to ensure compositional security in hardware, or remained confined to theoretical proposals with impractical latency costs. Critically, a systematic methodology to resolve randomness dependencies and achieve provable security at a practical cost has been lacking. This paper addresses the challenge by introducing the Unique Randomness Guard (URG) property as a foundational principle for secure masked circuit design. Building upon this property, we formally establish conditions under which the randomness in a circuit remains uniform and independent throughout its computation. Based on these results, we construct a general framework that provides a systematic methodology for randomness reuse, defined through a set of formally verified rules for both parallel and serial compositions. The security of these rules is guaranteed by the URG-based theoretical results, ensuring constructions that are first-order secure under the robust probing model. We also present a first-order masked implementation of the AES. To the best of our knowledge, this hardware implementation is the first to be proven first-order secure in the robust probing model while using only the randomness required for input encoding, all while maintaining a competitive hardware area. This work ultimately validate that randomness reuse can be fully realized without compromising rigorous verifiability, establishing a new framework that directly addresses the central challenge of randomness cost in masked implementations.

In many unbalanced private set intersection (uPSI) applications of the client-server setting, the server needs to perform uPSI with multiple clients. Cong \textit{et al.} (ACM CCS'21) proposed a state-of-the-art (SOTA) uPSI protocol based on fully homomorphic encryption (FHE), achieving malicious security by employing an oblivious pseudorandom function (OPRF) in the pre-processing phase. However, re-executing existing uPSI protocols with each client imposes significant computational overhead for the server. In this paper, we present JAGUAR, a maliciously secure and efficient uPSI protocol designed for this setting. JAGUAR reduces online computation through a Divide-and-Combine optimization, requiring only $\mathcal{O}(\sqrt{|X|})$ homomorphic multiplications. Furthermore, it employs a novel fixed VOLE-based OPRF that enables reusable and lightweight pre-processing across multiple clients. Experimental results demonstrate that JAGUAR achieves up to $2.7\times$ improvement in online runtime compared to the SOTA protocol in LAN. In multi-client scenarios, JAGUAR further outperforms existing protocols by a wide margin in terms of scalability and overall performance.

In this work, we present a new lightweight two-party Private Set Intersection (PSI) paradigm in both the semi-honest and malicious models. It requires only a small number of base Oblivious Transfers (OTs), along with a single Oblivious Key-Value Store (OKVS) encoding and a number of decodings equal to the sender input size. All computations (except for the base OTs) can be implemented using efficient hash and bitwise operations. Furthermore, we extend the proposed PSI protocol to circuit PSI and, subsequently, to several PSI variants, including PSI-cardinality, PSI-sum, and Private Join and Compute (PJC). All proposed protocols are evaluated under both LAN and WAN settings, with performance compared against existing works. Experimental results demonstrate that the proposed PSI achieves about $1.5 \times$ faster runtime than the most efficient Vector Oblivious Linear Evaluation (VOLE)-based PSI, while maintaining consistently lower communication overhead under identical settings. For circuit PSI, it is up to $3.6\times$ faster and reduces communication by a factor of $1.5$ compared to VOLE-based circuit PSI constructions. In the cases of PSI-cardinality and PSI-sum, they achieve speedups of up to $12.2\times$ and $10\times$, respectively, while incurring only moderate communication overhead. For PJC, the proposed protocol outperforms prior work by $731\times$ in runtime and achieves a $3.2\times$ reduction in communication, maintaining high efficiency even under a low-bandwidth condition. The performance under the unbalanced setting is also evaluated, showing that our PSI achieves at most two orders of magnitude improvement in the LAN setting compared with existing unbalanced PSI protocols, and gradually gains superiority under the WAN setting as the receiver set size increases.

Elliptic curve-based cryptographic systems have established themselves as fundamental components of modern cryptography, providing both efficiency and security guarantees. In this paper, we propose EHDSA (Elliptic Curve Homomorphic Digital Signature Algorithm), which addresses the privacy limitations inherent in classical ECDSA by introducing a novel isomorphism $\phi$ from the elliptic curve group $E(\mathbb{F}_p)$ to the integer ring $\mathbb{Z}_n$. Our approach utilizes a secret parameter $t \in \mathbb{Z}_n^*$ to define a scalar mapping that effectively obfuscates ephemeral public key components while maintaining the algebraic and homomorphic properties essential for signature verification. This transformation provides enhanced unlinkability and signature indistinguishability while preserving the computational efficiency of ECDSA. We provide formal security proofs under standard cryptographic assumptions, demonstrate correctness, and analyze computational complexity, showing that EHDSA achieves security levels equivalent to ECDSA with minimal computational overhead.

Attribute-based signatures (ABS) provide fine-grained control over who can generate digital signatures and have many real-world applications. This paper presents a pair of fast ABS schemes: one for Key-Policy ABS (KP-ABS) and another for Signature-Policy ABS (SP-ABS). Both schemes support expressive policies using Monotone Span Programs (MSP), and offer practical features such as large universe, arbitrary attributes, and adaptive security. Most notably, we provide the first implementation of MSP-based ABS schemes and demonstrate that our schemes achieve the best-known asymptotic and concrete performance in this domain. Asymptotically, key generation, signing and verification time scale linearly with the number of attributes; verification requires only two pairing operations. In concrete terms, for 100 attributes, our KP-ABS scheme performs key generation, signing, and verification in 0.16s, 0.10s, and 0.13s, respectively; our SP-ABS scheme achieves times of 0.082s, 0.26s, and 0.21s for the same operations.

At Asiacrypt'25, Lapiha and Prest proposed a lattice-based IND-CCA threshold key-encapsulation mechanism (TKEM) obtained from a threshold identity-based encryption (TIBE) and a signature scheme. Their construction relies on a variant of the Boneh-Canetti-Halevi-Katz (BCHK) transform, instantiated with a lattice-based TIBE. However it suffers from large ciphertexts at 540 KiB for $\kappa = 128$ bits of security.

We present substantial improvements to their TIBE, resulting in the first concretely efficient lattice-based IND-CCA TKEM, with ciphertexts just under 30 KiB for a threshold $T = 32$, $Q = 2^{45}$ queries, and the same $\kappa$.

Our design simplifies the original framework by leveraging the power of random oracles already present in their construction. We further enhance efficiency by adopting approximate computations where appropriate and by replacing module-NTRU trapdoors with NTRU trapdoors, achieving a remarkable eighteenfold reduction in ciphertext size. Finally, leveraging recent developments in secret sharing, we ensure the verifiability of key-extraction shares even in the presence of malicious parties.

Password-Authenticated Public Key Encryption (PAPKE) enables secure encryption using only a shared, human-memorable password—eliminating the need for trusted intermediaries or pre-established infrastructure. It allows a sender to encrypt a message for a recipient, using the recipient's password-authenticated public key and a shared password, while provably resisting man-in-the-middle and offline dictionary attacks. PAPKE's support for reusable password-authenticated public keys makes it especially suitable for asynchronous, PKI-free communication scenarios.

An important open problem is to construct PAPKE schemes that are secure against quantum adversaries, as existing instantiations rely on Diffie-Hellman assumptions. The PAPKE-IC construction (ACNS 2019) is generic and admits integration with post-quantum PKE schemes. However, the scheme assumes an Ideal Cipher (IC) over the public key domain, which is large for most post-quantum PKE schemes. While an IC is typically instantiated using a block cipher, standard block ciphers operate over much smaller domains (e.g., 128 or 256 bits). Alternatively, one can use an 8-round Feistel network, which achieves indifferentiability from an ideal cipher, or domain extenders. The latter are inefficient at the domain sizes required, making the efficient and secure instantiation of the IC in PAPKE-IC, in combination with post-quantum PKE, particularly challenging.

In this paper, we propose PAPKE-HIC, a UC-secure PAPKE scheme built from a PKE scheme and a Half-Ideal Cipher (HIC, introduced at EUROCRYPT 2023), which circumvents the challenges of instantiating ideal ciphers over large domains. We provide a detailed security proof of PAPKE-HIC and establish precise requirements for the underlying PKE: strong robustness, one-wayness, ciphertext anonymity, and pseudo-uniformity of public keys. Our analysis identifies a gap in the original PAPKE-IC security proof, motivating the introduction of a novel property, which we denote Decryption Robustness (DROB-CCA). Although DROB-CCA is implied by strong robustness (SROB-CCA), the reduction is not tight and incurs a quadratic security loss. We analyze which PKE schemes directly satisfy DROB-CCA, and conclude by presenting concrete instantiations of PAPKE-HIC. To our knowledge, this is the first practical, post-quantum instantiation of the PAPKE primitive.

Subversion-resilient Authenticated key-exchange (AKE) aims to achieve the guarantees of secure AKE even in the presence of an adversary that has tampered with parts of the protocol's implementation. One way to achieve subversion-resilient AKE is the use of Reverse Firewalls (RFs), an untrusted third-party that can restore security. Recent work [18] highlights the challenges of designing RFs for practical secure channel-establishment.

This paper extends existing RF-based subversion-resilient AKE at three levels: security definitions, constructions, and the use of formal verification. First, we introduce a useful relaxation of the notion of security in subversion-resilient AKE with RFs: the goal is no longer to prevent all exfiltration, but rather to restore to the AKE protocol a property lost upon subversion. We focus specifically on authenticating and (key-)securing RFs. We also discuss subversion-resilience against a spectrum of compromises, designing a flexible framework in which protocols are proved secure with respect to adversaries that can tamper with some components of the implementation, but perhaps not others.

Our ultimate goal is to achieve post-quantum secure subversion-resilient key-exchange. Far from being trivial, this requires the introduction of a malleable-yet-secure notion of key encapsulation, which we dub re-randomizable Key Encapsulation Mechanism. We carefully formalize this new primitive and instantiate it first based on a classical Diffie-Hellman KEM and one based on Kyber.

Finally, we lay the foundations for the formal verification of RF based protocols, by formally proving our protocol with the CryptoVerif prover, in addition to computational-security proofs in usual Bellare-Rogaway methodology.

The study of memory-hard functions (MHFs) so far has mainly focused on providing provable guarantees on the expected minimum cumulative memory complexity (CMC) required per evaluation when amortized over multiple instances. Such results, however, do not provide any guarantees for the security of compromised password banks in the sense of passwords remaining unrecoverable. Indeed, a construction can be memory-hard while still leaking information about its input. We provide the first formal treatment of the unrecoverability of graph-based data-independent MHFs (iMHFs) in the multi-instance setting. Multi-instance security is the accepted security model when inputs have low-entropy or are correlated, and require the adversarial effort to linearly scale with the number of instances broken.

To prove these results, we appropriately extend the ex-post-facto pebbling technique of Alwen and Serbinenko (STOC'15) and the unguessability reductions of Farshim and Tessaro (EUROCRYPT'21). We then use the resulting compatible frameworks to bound the number of guesses of adversaries with a given CMC in terms of the pebbling complexity of the graph underlying the iMHF. Combined with known lower bounds for the pebbling complexities of their graphs, we obtain, as corollaries, concrete unrecoverability bounds for the Argon2i, Catena, and Balloon hashing, showing in particular that the advantage indeed scales linearly with the number of instances and the cumulative memory complexity of the attacker.

In this paper, we present some research on quantum complexity measurements for applying Grover's search algorithm to recover the key of a stream cipher, Atom. As a foundational step, we propose a novel and complete quantum gate-level design of Atom. We incorporate a quantum lookup table to implement the key filtering with a specific decimal counter value during the keystream generation phase, which is absent in the only known previous work on the quantum attack against Atom. Based on the proposed design, we present an algorithm based on Grover's search to recover the key of Atom. Considering the limited qubit capacity of the IBM Qiskit simulator, the proposed search algorithm, with a round-reduced initialization phase, is simulated for 3-qubit key recovery with a probability greater than 0.9. We provide resource estimations for the proposed quantum algorithms. We also perform optimizations on the resources required by the proposed Grover oracle and present a benchmark for Grover's search algorithm on Atom. The research findings in this paper claim that Atom satisfies NIST Level 1 security.

In this work, we initiate the study of aborting hash functions, i.e., hash functions that may abort on a non-negligible fraction of inputs. We introduce the aborting random oracle model (aROM), an idealized framework that extends the standard random oracle model (ROM) to account for aborts. Within this model, we derive bounds for various security notions and establish generic indifferentiability results demonstrating how to construct aborting random oracles from standard ones. Consequently, the derived bounds ultimately hold in the standard ROM. In this way, the aROM and its associated bounds provide a convenient and easy-to-use framework for analyzing cryptographic constructions that rely on potentially aborting hash functions.

To illustrate the utility of our framework, we apply our techniques to two settings: (1) the analysis of SNARK-friendly incomparable hypercube encodings, a core primitive in hash-based signature schemes, and (2) the analysis of grinding in Fiat–Shamir-based non-interactive arguments. Through our generic indifferentiability results, we can easily translate these analyses into concrete security bounds in the standard (non-aborting) random oracle model.

Central bank digital currencies (CBDCs) and other related digital asset platforms have the potential to revolutionize the financial world. While these platforms have been deployed in test environments by virtually all large financial institutions, including central banks, there are still several limitations of these systems that prevent widespread adoption. These include (i) privacy, (ii) security against quantum adversaries, and (iii) auditability. In this work, we undertake (to our knowledge) the first formal study of these systems.

While there have been many digital asset platforms implemented, we do not know of any formal model for a fundamentally UTXO-based digital asset platform/CBDC. Our first contribution is a formal modeling of a UTXO-based private digital asset system that meets our requirements listed above. This model is loosely based upon the open source software that we found came the closest to meeting our requirements, Hyperledger Zeto. In the course of our formal modeling, we found a critical security bug in Zeto which we responsibly disclosed to the Zeto maintainers and has since been fixed. We then provide an efficient construction of such a system, which we call Qurrency. Qurrency is an efficient UTXO-based privacy-preserving token system that includes an auditing mechanism and is secure against "harvest now, decrypt later" attacks, which is critically important for several central banks, including the Bank of Brazil. We implemented our construction to show that it is practically efficient and can be used on any EVM-based blockchain system with ease.