International Association
for Cryptologic Research

Multiparty fully homomorphic encryption (MPFHE) is a generalization of (multi-key) fully homomorphic encryption ((MK)FHE) that lives on the cusp between multiparty computation (MPC) and FHE, enabling a computation over encrypted data using multiple keys. However, contrary to MKFHE it seeks to reduce the noise inflation based on the number of parties by allowing the parties to first compute shared data in MPC before executing the computation in FHE. Generally, MPFHE protocols have required ad-hoc constructions and adaptations to already existing protocols. In this work we present a new framework that standardizes the approach of MPFHE to allow the use of a broad spectrum of MPC and FHE protocols, while eliminating the noise inflation based on the participating number of parties. This presents the first ever multiparty FHE protocol which allows an arbitrary number of participants. We then show a case study of this using the FINAL scheme and show that we reduce the required key material by 40-99.9% compared to the MKFHE FINAL scheme, FINALLY, 8-71% compared to the AKÖ scheme, and 65-70% compared to the Park-Rovira scheme. Moreover, we reduce the bootstrapping time for the AKÖ, Park-Rovira, and KMS schemes by 75-99.7%.

The Transfer of Ownership Protocol (TOOP) enables a secure transfer of assets from Bitcoin to other blockchains and back. This is achieved through a committee-based validation protocol that requires only 1-out-of-nhonest security. The protocol operates in distinct phases: the lock phase, where the initial setup and individual assets are locked on Bitcoin, and the unlocking with ownership transfer phase, where the asset is transferred to a possibly different legitimate owner. This protocol solves a limitation of all existing BitVM-like protocols that restricts the unlocking transfers to only addresses known and preregistered during lock and setup. Accordingly, our protocol avoids the financially costly, regulatory problematic, and congestion-prone front-and-reimburse paradigm. TOOP has been implemented for the first time in Cardinal, a protocol for wrapping Bitcoin Unspent Transaction Outputs (UTxOs) onto the Cardano blockchain, with Bitcoin Ordinals represented as Cardano Non-Fungible Tokens (NFTs).

The sponge is a popular construction of hash function design. It operates with a $b$-bit permutation on a $b$-bit state, that is split into a $c$-bit inner part and an $r$-bit outer part. However, the security bounds of the sponge are most often dominated by the capacity $c$: If the length of the digest is $n$ bits, the construction achieves $\min\{n/2,c/2\}$-bit collision resistance and $\min\{n,c/2\}$-bit second preimage resistance (and a slightly more complex but similar bound for preimage resistance). In certain settings, these bounds are too restrictive. For example, the recently announced Chinese call for a new generation of cryptographic algorithms expects hash functions with 1024-bit digests and 1024-bit preimage and second preimage resistance, rendering the classical sponge design basically unusable, except with an excessively large permutation. We present the SPONGE-DM construction to salvage the sponge in these settings. This construction differs from the sponge by evaluating the permutation during absorption in a Davies-Meyer mode. We also present SPONGE-EDM, that evaluates potentially round-reduced permutations during absorption in Encrypted Davies-Meyer mode, and SPONGE-EDM$^c$, that optimizes the amount of feed-forward data in this construction. We prove that these constructions generically achieve $\min\{n/2,c/2\}$-bit collision resistance as the sponge does, but they achieve $n$-bit preimage resistance and $\min\{n,c-\log_2(\alpha)\}$-bit second preimage resistance, where $\alpha$ is the maximum size of the first preimage in blocks. With such constructions, one could improve the security (resp., efficiency) without sacrificing the efficiency (resp., security) of hash-based signature schemes whose security relies solely on the (second) preimage resistance of the underlying hash functions. Also, one could use the $1600$-bit Keccak permutation with capacity $c=1088$ and rate $r=512$ to achieve $512$-bit collision resistance and $1024$-bit preimage and second preimage resistance, without making extra permutation calls. To encourage further cryptanalysis, we propose two concrete families of instances of SPONGE-EDM (expected to be weaker than SPONGE-DM), using SHA3 and Ascon. Moreover, we concretely demonstrate the security and performance advantages of these instances in the context of hashing and hash-based signing.

In this paper, we propose a new block cipher primitive, based on ring-LWE, which allows key rotation with a possible security update. This makes it possible to double the security of the ciphertext with each key rotation. Our scheme could therefore be used for long-term secret storage, allowing the security of the ciphertext to be adapted to the attacker's computing power, without the need for decryption.

We propose an implementation of our cryptographic scheme and prove its security.

In ToSC 2025(1), Jia et al. proposed an SAT-aided automatic search tool for the S-box design. A part of the functionality of this tool is to search for implementations of an S-box with good area and gate-depth complexity. However, it is well-known that the gate depth complexity cannot precisely reflect the latency of an implementation. To overcome this problem, Rasoolzadeh introduced the concept of latency complexity, a more precise metric for the latency cost of implementing an S-box than the gate depth complexity in the real world. In this addendum, we adapt Jia et al.'s tool to prioritize latency as the primary metric and area as the secondary metric to search for good implementations for existing S-boxes. The results show that the combination of Jia et al.'s tool and Rasoolzadeh's latency complexity can lead to lower-latency S-box implementations. For S-boxes used in LBlock, Piccolo, SKINNY-64, RECTANGLE, PRESENT and TWINE, which are popular targets in this research line, we find new implementations with lower latency. We conducted synthesis comparisons of the area and latency under multiple standard libraries, where our results consistently outperformed in terms of latency. For example, for LBlock-S0, our solution reduces latency by around 50.0% ∼73.8% compared to previous implementations in TSMC 90nm library with the latency-optimized synthesis option.

The beyond unforgeability features formalize additional security properties for signature schemes. We develop a general framework of binding properties for signature schemes that encompasses existing beyond unforgeability features and reveals new notions. Furthermore, we give new results regarding various transforms: We show that the transform by Cremers et al. (SP'21) achieves all of our security notions and provide requirements such that this is also the case for the transform by Pornin and Stern (ACNS'05). Finally, we connect our framework to unforgeability notions.

This paper blends post-quantum cryptography (PQC) and zero trust architecture (ZTA) to secure the access for AI models, formalized through the abstract mathematical lens of category theory. In this work, latticebased PQC primitives are assigned ZTA components that include microsegmentation and context-aware authentication, leading to a visual compositional framework that describes cryptographic workflows as morphisms and trust policies as functors, showing how category theory allows for fine-grained policies and adaptive trust. This quantum-resistant algorithm viewing perspective offers an ease for protection against adversarial AI threats. The paper uses a concrete implementation to attest to the effectiveness of the theoretical contribution, rendering it a crypto-agile transition using categorical proofs for AI security .

In pairings-based cryptographic applications, final exponentiation with a large fixed exponent ensures distinct outputs for the Tate pairing and its derivatives. Despite notable advancements in optimizing elliptic curves with even embedding degrees, improvements for those with odd embedding degrees, particularly those divisible by \(3\), remain underexplored. This paper introduces three methods for applying cyclotomic cubing in final exponentiation and enhancing computational efficiency. The first allows for the execution of one cyclotomic cubing based on the final exponentiation structure. The second leverages some existing seeds structure to enable the use of cyclotomic cubing and extends this strategy to generate new seeds. The third allows generating sparse ternary representation seeds to apply cyclotomic cubing as an alternative to squaring. These optimizations improve performance by up to $19.3\%$ when computing the final exponentiation for the optimal Ate pairing on $BLS15$ and $BLS27$, the target elliptic curves of this study.

Following Gentry's seminal work (STOC 2009), Fully Homomorphic Encryption (FHE) has made significant advancements and can even evaluate functions in the bootstrapping process, called functional bootstrapping. Recently, Liu and Wang (ASIACRYPT 2023) proposed a new approach to functional bootstrapping, which bootstrapped ciphertexts in 7ms amortized time. Their methods packed the secret key of the TFHE cryptosystem into a ciphertext of the BFV cryptosystem, followed by performing functional bootstrapping of TFHE within BFV. However, while this yields high amortized efficiency, it faces high latency and computational complexity of $\mathcal{O}(\sqrt{t})$ ciphertext-ciphertext multiplications due to use of large BFV plaintext primes that serve as the TFHE ciphertext modulus, $t = 65537$, to maximize SIMD slots.

In this work, we adapt their techniques to achieve lower latency functional bootstrapping by relaxing the requirement for prime BFV plaintext modulus to prime powers, $t = p^r$. We first introduce an improved linear transformation stage, multiplying Laurent Polynomial packed secret key and ciphertexts, $a_{ij}$ and $sk_j$, evaluating a $\mathbb{Z}_{p^r}$ linear map. With this, we reduce the number of operations needed to evaluate the linear phase of bootstrapping. Finally, we generalize their functional bootstrapping procedure from plaintext space $\mathbb{Z}_t$ to $\mathbb{Z}_{p^r}$ via leveraging the digit extraction algorithm, achieving a theoretical complexity of $\mathcal{O}(r^2\sqrt{p})$ ciphertext-ciphertext multiplications. Additionally, we enable a multi-valued bootstrapping scheme that permits the evaluation of multiple functions over a shared input. To the best of our knowledge, this is the first demonstration of such a method for TFHE ciphertexts that relies predominantly on BFV-based techniques.

In our experiments, we achieve overall runtimes as low as 49.873s, representing latency reductions of at least $26\times$, while noting a $19\times$ slowdown in amortized performance.

Fully homomorphic encryption (FHE) is an appealing and promising solution for privacy-preserving transformer inference to protect users' privacy. However, the huge computational overhead makes it unrealistic to apply FHE in real-world transformers for large language models (LLM). Current FHE-based approaches to secure transformer inference face significant performance challenges, with total latency exceeding 5 hours for 32-input batches. The feedforward block, comprising a large-scale matrix multiplication followed by a GELU evaluation, is widely recognized as one of the most computationally intensive components in privacy-preserving transformer inference. In the state-of-the-art system NEXUS, evaluating the feedforward block incurs a total latency of 5,378 seconds, processing up to 32 inputs per batch. We aim to reduce the latency and propose LEAF, a low-latency evaluation architecture for the feedforward block. LEAF introduces a novel combination of fast matrix multiplication and an asymptotically efficient algorithm for computing non-polynomial activations. When evaluated on the BERT-base model, LEAF reduces total latency to 53.4 seconds, offering a $100\times$ speedup over the state-of-the-art method in the same environment. Our implementations are available.

Symmetric primitives used in multi-party computation, fully homomorphic encryption, and zero-knowledge proofs are often defined over Finite Field $\mathbb{F}_{q}$ with $q=2^t$ or an odd prime $p$. Integral attack is one of the most effective methods against such primitives due to the common use of low-degree non-linear layers. This in turn highlights the importance of a deeper understanding of degree growth. For ciphers defined over $\mathbb{F}_{2^t}$, numerous works have explored the growth of the algebraic degree. However, these methods cannot be directly applied to $\mathbb{F}_{p}$. At CRYPTO 2020, Beyne et al. extended the integral cryptanalysis to $\mathbb{F}_{p}$ by comparing degree with $s(p-1)$ when using $p^s$ data. However, given that the precise degree evaluation remains fundamentally challenging and often computationally infeasible, one may lose better integral distinguishers.

In this paper, we present the first automatic search model over $\mathbb{F}_{p}$ based on the exact coefficient $\mathcal{A}$ of the monomial $\prod_{w=1}^{s}x_w^{p-1}$ contained in the algebraic representation. This model is constructed following the Computation-Traceback-Determine framework, where $\mathcal{A}$ is represented by several sums of multinomial coefficients under specific conditions. The existence of integral properties is then transformed into a determination of whether these sums can consistently equal $0\bmod{p}$. This determination is facilitated by four newly developed propositions based on Lucas Theorem. To demonstrate the effectiveness of our framework, we apply it to all variants of GMiMC. As a result, we achieve the best integral distinguishers for GMiMC-erf/-crf using large primes when they are used as block ciphers. For GMiMC-nyb/-mrf using 32/64-bit primes, our integral distinguishers cover more rounds than all other attacks. Meanwhile, all distinguishers we identified are no worse than those trivial ones predicted only considering the maximal degree. This shows the necessity of considering exact coefficients when searching for integral distinguishers over $\mathbb{F}_p$. Our framework is further employed to assess the security of two HADES designs: HadesMiMC and Poseidon2$^\pi$. The results reveal that the full rounds at the beginning and end of HADES provide sufficient resistance against integral cryptanalysis.

At the current state of the art, algebraic attacks are the most efficient method for finding preimages and collisions for arithmetization-oriented hash functions, such as the closely related primitives Poseidon/Poseidon2 and Neptune. In this paper, we revisit Gröbner basis (GB) attacks that exploit subspace trails to linearize some partial rounds, considering both sponge and compression modes.

Starting from Poseidon's original security evaluation, we identified some inaccuracies in the model description that may lead to misestimated round requirements. Consequently, we reevaluate and improve the proposed attack strategy. We find that depending on the concrete instantiation, the original security analysis of Poseidon under- or overestimates the number of rounds needed for security. Moreover, we demonstrate that GB attacks leveraging subspace trails can outperform basic GB attacks for Poseidon/Poseidon2 and Neptune.

We propose a variant of the previous attack strategy that exploits a crucial difference between Poseidon/Poseidon2 and Neptune: while Poseidon's inverse round functions have a high degree, Neptune's inverse external rounds maintain the same degree as the forward rounds. Using this new model, we demonstrate that Neptune's security in compression mode cannot be reduced to its security against the Constrained-Input-Constrained-Output (CICO) problem. To the best of our knowledge, this is the first time a concrete example has been provided where finding preimages is easier than solving the corresponding CICO problem.

Our results emphasize the importance of considering the mode of operation in security analysis while confirming the overall security of Poseidon/Poseidon2 and Neptune against the presented algebraic attacks.

$\textsf{GCM}$ and $\textsf{CCM}$ are block cipher (BC) based authenticated encryption modes. In multi-user (mu) security, a total number of BC invocations by all users $\sigma$ and the maximum number of BC invocations per user $\sigma_\mathsf{u}$ are crucial factors. For $\textsf{GCM}$, the tight mu-security bound has been identified as $\frac{\sigma_\mathsf{u} \sigma}{2^n} + \frac{u p + u^2}{2^k}$, where $k$ and $n$ are respectively the key and block sizes, $u$ is the number of users, $p$ is the number of offline queries.In contrast, the $\mathsf{CCM}$'s mu-security bound is still unclear. Two bounds of $\frac{u \sigma_\mathsf{u}^2}{2^n} + \frac{u p + u^2}{2^k}$ and $\frac{\sigma^2}{2^n} + \frac{u p + u \sigma}{2^k}$ have been derived by Luykx~et~al.~(Asiacrypt~2017) and Zhang~et~al.~(CCS~2024), respectively, but both are not tight and worse than the $\textsf{GCM}$'s bound. Moreover, methods to enhance mu security without disruptive changes in the scheme have been considered for $\textsf{GCM}$, namely nonce randomization ($\textsf{NR}$) to improve offline security and nonce-based key derivation ($\textsf{KD}$) to improve online security, but their applicability to $\textsf{CCM}$ has never been discussed. In this paper, we prove an improved mu-security bound of $\textsf{CCM}$, which is tight, and reaches the $\textsf{GCM}$'s bound. We then prove that $\textsf{NR}$ and $\textsf{KD}$ applied to $\textsf{CCM}$ result in the same bounds for the case to $\textsf{GCM}$. An important takeaway is that $\textsf{CCM}$ is now proved to be as secure as $\textsf{GCM}$. Moreover, we argue that $\textsf{NR}$ and $\textsf{KD}$ can be insufficient for some applications with massive data, and propose a new enhancement method called nonce-based and tag-based key derivation ($\textsf{NTKD}$) that is applied to $\textsf{GCM}$ and $\textsf{CCM}$. We prove that the resulting schemes meet such real-world needs.

In 2022, Antonov showed that SHA-256 does not satisfy some secure property that SPHINCS$^+$ needs, and a fogery attack based on this observation reduces the concrete classical security by approximately 40 bits of security. This illustrates a more general concern: the provable security of some hash-based signature schemes can be compromised when implemented with certain real-world hash functions, and motivates the need to design new functions with rigorous, provable security guarantees. Besides, it has been shown that from W-OTS to W-OTS$^+$, the security requirement for the hash function's collision resistance can be relaxed to second-preimage resistance (SPR), which means that it is possible to use some functions with SPR property to instantiate the underlying function family $\mathcal{F}_n$ in W-OTS$^+$, and obtain a provably secure W-OTS$^+$. In this paper, we use multivariate quadratic functions (MQ functions) to instantiate $\mathcal{F}_n$ in W-OTS$^+$, which yields the first provably secure W-OTS$^+.$ To prove its security, we need to derive the SPR property of MQ functions. The key is to show the $\mathbf{NP}$-hardness of finding second preimages. Furthermore, we prove the multi-function, multi-target one-wayness (MM-OW) and the multi-function, multi-target second-preimage resistance (MM-SPR) of MQ functions, which implies the provable security of MQ-based W-OTS$^+$ in the multi-user setting, on the condition that the number of users is $O(n^{1-\epsilon})$ for some $\epsilon\in (0,1)$, where $n$ is the security parameter.

We revisit the security analysis of the permutation-based deterministic random bit generator~(DRBG) discussed by Coretti et al. at CRYPTO 2019. Specifically, we prove that their construction, based on the sponge construction, and hence called Sponge-DRBG in this paper, is secure up to $O\left(\min \left\{2^{\frac{c}{2}}, 2^{\frac{\lambda}{2}}\right\}\right)$ queries in the seedless robustness model, where $\lambda$ is the required min-entropy and $c$ is the sponge capacity. This significantly improves the provable security bound from the existing $O\left(\min \left\{2^{\frac{c}{3}}, 2^{\frac{\lambda}{2}}\right\}\right)$ to the birthday bound. We also show that our bound is tight by giving matching attacks.

As the Multi-Extraction game-based reduction proposed by Chung et al. at Asiacrypt 2024 is not applicable to Sponge-DRBG in a straightforward manner, we further refine and generalize the proof technique so that it can be applied to a broader class of DRBGs to improve their provable security. We also propose a new permutation-based DRBG, dubbed POSDRBG, with almost the optimal output rate $1$, outperforming the output rate $\frac{r}{n}$ of Sponge-DRBG, where $n$ is the output size of the underlying permutation and $r=n-c$. We prove that POSDRBG is tightly secure up to $O\left(\min \left\{2^{\frac{c}{2}}, 2^{\frac{\lambda}{2}}\right\}\right)$ queries. Thus, to the best of our knowledge, POSDRBG is the first permutation-based DRBG that achieves the optimal output rate of 1, while maintaining the same level of provable security as Sponge-DRBG in the seedless robustness model.

Poseidon and Poseidon2 are cryptographic hash functions designed for efficient zero-knowledge proof protocols and have been widely adopted in Ethereum applications. To encourage security research, the Ethereum Foundation announced a bounty program in November 2024 for breaking the Poseidon challenges, i.e. solving the CICO (Constrained Input, Constrained Output) problems for round-reduced Poseidon constructions. In this paper, we explain how to apply the Graeffe transform to univariate polynomial solving, enabling efficient interpolation attacks against Poseidon. We will provide an open-source code and details our approach for solving several challenges valued at $20000 in total. Compared to existing attacks, we improves 2^{13} and 2^{4.5} times in wall time and memory usage, respectively. For all challenges we solved, the cost of memory access turns out to be an essential barrier, which makes the security margin much larger than expected. We actually prove that the memory access cost for FFT grows as the 4/3-power of the input size, up to a logarithmic factor. This indicates the commonly used pseudo linear estimate may be overly conservative. This is very different from multivariate equation solving whose main bottleneck is linear algebra over finite fields. Thus, it might be preferable to choose parameters such that the best known attack is interpolation, as it presents more inherent hardness.

Public-coin protocols are cryptographic protocols in which all messages sent by a specific party (typically the receiver or verifier) consist solely of random bits. These protocols have been extensively studied $\textit{in the classical setting}$ due to their advantageous properties in several scenarios, such as the parallel repetition of interactive arguments, and the design of secure multi-party computation with low round complexity, among others. Curiously, $\textit{post-quantum}$ constructions of public-coin protocols remain limited, particularly when optimization is sought in additional factors like round complexity or hardness assumptions.

We introduce the concept of $\textit{almost-total puzzles}$, a novel cryptographic primitive characterized by two key properties: (i) hardness against any efficient adversary, and (ii) an "almost-total" guarantee of the existence of solutions, even when the puzzle generator is malicious. We demonstrate that this primitive can be derived from one-way functions in public-coin, requiring only two rounds. By leveraging this primitive, we obtain a family of new $\textit{public-coin}$ results in both the classical and post-quantum settings, based on the $\textit{minimal assumption} $ of (post-quantum) one-way functions, including:

- five-round post-quantum extractable commitments and witness-indistinguishable arguments of knowledge, where the (knowledge) extractors achieve the $\textit{coherently expected quantum-polynomial-time}$ ($\mathsf{EQPT}_c$) simulation proposed by Lombardi, Ma, and Spooner [FOCS'22];

- five-round classical extractable commitments that $\textit{do not suffer from over extraction}$;

- five-round classical delayed-input strong witness-indistinguishable arguments of knowledge, and delayed-input witness-hiding arguments of knowledge;

- the five-round post-quantum analogue of the last item, but with the difference that (1) the input can be delayed until the third round, and (2) post-quantum arguments of knowledge are again defined w.r.t. $\mathsf{EQPT}_c$-simulation;

- $O(\log^* \lambda)$-round post-quantum non-malleable commitments.

Threshold linearly homomorphic encryption (ThLHE) is a useful cryptographic tool for secure computation in multi-party settings, with applications in electronic voting, secure multiparty computation (MPC), and beyond. Although ThLHE offers significant advantages such as low communication overhead, its adoption in modern systems is hindered by a critical dilemma between efficiency and utility. Precisely, existing ThLHE schemes either suffer from high decryption complexity—typically $\mathcal{O}(N^2\log N)$ or worse for $N$ parties—or impose extra restrictions on the message space or participant set, limiting their practicality in large-scale and dynamic settings.

In this work, we resolve this efficiency-utility dilemma for ThLHE by introducing a novel primitive termed message-space adapter (MeSA). By developing a lattice-based MeSA for exponential ElGamal (Exp-ElGamal), we mitigate the small-message restriction of Exp-ElGamal while preserving its efficient threshold decryption. This leads to the design of the first ThLHE scheme that achieves quasi-linear decryption complexity without restrictions on the message space or participant set. We implement a prototype of this new ThLHE scheme and validate the quasi-linear growth of its running time with respect to $N$.

Beyond resolving this dilemma, we further extend the applications of our new ThLHE scheme. Specifically, we apply it to construct the first multi-party fully homomorphic encryption scheme with quasi-linear computation complexity and constant communication complexity, while supporting arbitrary threshold and dynamic participant set. This demonstrates the extra benefits of our ThLHE scheme with broader applicability.

We analyze the post-quantum security of succinct interactive arguments constructed from interactive oracle proofs (IOPs) and vector commitment schemes. Specifically, we prove that an interactive variant of the \emph{BCS transformation} is secure in the standard model against quantum adversaries when the vector commitment scheme is collapse binding.

Prior work established the post-quantum security of Kilian's succinct interactive argument, a special case of the BCS transformation for one-message IOPs (i.e., PCPs). That analysis is inherently limited to one message because the reduction, like all prior quantum rewinding reductions, aims to extract classical information (a PCP string) from the quantum argument adversary. Our reduction overcomes this limitation by instead extracting a \emph{quantum algorithm} that implements an IOP adversary; representing such an adversary classically may in general require exponential complexity.

Along the way we define \emph{collapse position binding}, which we propose as the \DoQuote{correct} definition of collapse binding for vector commitment schemes, eliminating shortcomings of prior definitions.

As an application of our results, we obtain post-quantum secure succinct arguments, in the standard model (no oracles), with the \emph{best asymptotic complexity known}.

Logup argument (in it's modern GKR version, as described in eprint:2023/1284 paper) is a logarithmic derivative-based unindexed lookup argument. An indexed lookup argument can be constructed from unindexed one using standard trick. In this short informal note, we explain a different way of obtaining indexed lookup from logup, which does not commit any additional arrays of the size of the indexing array. That makes it particularly amenable for lookups in small tables (giving, to our knowledge, a first argument with this property).

Additionally, this argument is not subject to numerator overflow issue that requires additional mitigation described in eprint:2024/2067.

Improvements to SPARK / Lasso protocols are also discussed.