Proof-of-stake blockchains require consensus protocols that support Dynamic Availability and Reconfiguration (which we call the DAR model). Here, Dynamic Availability means that the consensus protocol should remain live even if a large number of nodes temporarily crash, and Reconfiguration means it should be possible to change the set of operating nodes over time. State-of-the-art protocols inspired by the DAR model, such as Ethereum, Cardano's Ouroboros, or Snow White, require additional model features comprising external mechanisms or node capabilities that are difficult to justify, such as social consensus or the requirement that key evolution be performed even when nodes have crashed. The key result of this paper is the necessary and sufficient adversarial condition under which consensus can be achieved in the plain DAR model, without any extra features. We then introduce an additional feature to the model that is justified by proof-of-stake blockchain designs: honest nodes complete a sign-off procedure the moment they express intent to exit from the set of operating nodes. This additional feature reduces the power of the adversary relative to the plain DAR model and helps us obtain a bootstrapping gadget that is particularly simple and efficient in the common optimistic case of few reconfigurations and no double spending.

$\sharp\textsf{Pencil}$ is a domain-extended pseudorandom function by Bhaumik et al, accepted at CRYPTO 2026, claiming that it achieves close to $n$-bit security beyond the birthday bound. It is used as the key-derivation layer of the $\sharp\textsf{Pencil}$-CAU authenticated-encryption mode. We show that $\sharp\textsf{Pencil}$ has a birthday-bound collision attack: its front end $\textsf{Sharp}$ compresses the second half $N_2$ of the input through the $(n-8)$-bit value \[ J(N_2) = \operatorname{msb}_{n-8}\bigl({\mathsf{E}}_{K_1}(N_2 || \texttt{0x00})\bigr), \] after which the entire computation is a deterministic function of $(N_1,J)$. Thus, for any fixed $N_1$, distinct values $N_2,N_2'$ satisfying $J(N_2)=J(N_2')$ produce identical $\sharp\textsf{Pencil}$ outputs. Such collisions occur with probability $1-e^{-1}$ after $2^{(n-7)/2}$ queries, $2^{60.5}$ when $n=128$. This yields a PRF distinguisher with constant advantage, contradicting the security bound of Theorem 4. Since $2^{60.5}$ falls below the birthday bound $2^{n/2}$ that the construction was designed to pass, the beyond birthday-bound property does not hold. Given the derived key $K_1$, an explicit collision can be constructed in approximately $10^3$ inverse-cipher evaluations in expectation. The same collision breaks $\sharp\textsf{Pencil}$-CAU, as two nonce-respecting queries can reuse the key and the nonce of the inner GCM instance, yielding the difference of the two plaintexts. The first version of the paper does not have the defect: it left $J$ untruncated, which makes the map injective and invalidates the collisions above. Reverting to it is the remedy we suggest.

Anonymous credentials (ACs) let users prove identity claims with strong privacy guarantees, and national systems built on them $-$ EUDI and the Swiss e-ID $-$ go live soon. Due to these guarantees, however, AC systems cannot detect proof proxy attacks, where malicious users "lend" their identity by presenting their credentials on behalf of other users, exposing a fundamental gap between privacy and accountability. For instance, users could sell anonymous legal age proofs online and get away with it. This lack of accountability will act as an obstacle for AC adoption on grounds of "national safety", as exemplified by the recurring push towards chat control in the EU. Consequently, issuing authorities may well settle for less-than-ideal privacy guarantees of current solutions (e.g., batch issuance of one-show credentials). In this paper, we advocate the need for integrated accountability in ACs and introduce the cryptographic forensic trail (CFT). A CFT is a randomized encryption of a user's identity that they produce alongside each credential presentation; only when credential misuse, e.g., a proof proxy attack, is detected can the CFT be decrypted for accountability. The design of CFT is based on a legal process requiring probable cause for anonymity revocation. It enforces separation of powers between law enforcement, a judicial body, and a digital privacy advocate (NGO) using privacy-enhancing technologies. The protocol mimics checks and balances of a healthy democracy, in which neither law enforcement nor justice can track people as they will. Even if both branches colluded, the NGO can detect the misuse and block further use. We implement a prototype of CFT based on both hardware-compatible and zero-knowledge-friendly elliptic curves. Our evaluations show that CFT adds only $13-16\%$ computation overhead to credential shows on the user's end, indicating that deployment in smartphone wallets is within reach.

As a new lattice problem, we introduce $l$-Shortest Independent Vectors Problem ($l$-SIVP for short), where $l$ is a positive integer no greater than the rank of a lattice. In the case where $l=1$, $l$-SIVP means SVP, and in the case where $l$ is the rank of a lattice, $l$-SIVP means SIVP. We estimate upper bounds on the failure probabilities of the reductions from the subset sum problems to the $l$-SIVPs in terms of Ehrhart theory. Especially, in the case of $l=1$, our upper bound is tighter than the previous result given by Coster et al. We give some considerations for dominating terms of our upper bounds of failure probabilities when $l$ is general.

Signal is a secure messaging app offering end-to-end security for pairwise and group communications. It has tens of millions of users, and has heavily influenced the design of other secure messaging apps (including WhatsApp). Signal has been heavily analysed and, as a result, is rightly regarded as setting the "gold standard" for messaging apps by the scientific community. We present two practical attacks that break the integrity properties of Signal in its advertised threat model. Each attack arises from different features of Signal that are poorly documented and have eluded formal security analyses. The first attack, affecting Android and Desktop, arises from Signal's introduction of identities based on usernames (instead of phone numbers) in early 2022. We show that the protocol for resolving identities based on usernames and on phone numbers introduced a vulnerability that allows a malicious server to inject arbitrary messages into one-to-one conversations under specific circumstances. The injection causes a user-visible alert about a change of safety numbers, but if the users compare their safety numbers, they will be correct. The second attack is even more severe. It arises from Signal's Sealed Sender (SSS) feature, designed to allow sender identities to be hidden. We show that a combination of two errors in the SSS implementation in Android allows a malicious server to inject arbitrary messages into both one-to-one and group conversations. The errors relate to missing key checks and the loss of context when cryptographic processing is distributed across multiple software components. The attack is undetectable by users and can be mounted at any time, without any preconditions. As far as we can tell, the vulnerability has been present since the introduction of SSS in 2018. We disclosed both attacks to Signal. The vulnerabilities were promptly acknowledged and patched: the first vulnerability was fixed two days after disclosure, while the second one was patched after eight days. Beyond presenting these devastating attacks on Signal's end-to-end security guarantees, we discuss more broadly what can be learned about the challenges of deploying new security features in complex software projects.

A long-standing question in the blockchain community is which class of computations are efficiently expressible in cryptocurrencies with limited scripting languages, such as Bitcoin Script. Such languages expose a reduced trusted computing base, thereby being less prone to hacks and vulnerabilities, but have long been believed to support only limited classes of payments. In this work, we confute this long-standing belief by showing for the first time that arbitrary computations can be encoded in today's Bitcoin Script without introducing any language modification or additional security assumptions, such as trusted hardware, trusted parties, or committees with an honest majority. We present BitVM, a two-party protocol that realizes a generic virtual machine by combining cryptographic primitives and economic incentives. We conduct a formal analysis of BitVM, characterizing its functionality, system assumptions, and security properties. We further demonstrate the practicality of our approach by implementing a prototype and performing an experimental evaluation: in the optimistic case (i.e., when parties agree), our protocol requires just three on-chain transactions, whereas in the pessimistic case, the number of transactions grows logarithmically with the size of the virtual machine. We exemplify the deployment potential of BitVM by building a Bitcoin-sidechain bridge application. This work not only solves a long-standing theoretical problem, but it also promises a strong practical impact, enabling the development of complex applications in Bitcoin.

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.

The deployment of advanced cryptographic protocols such as zero-knowledge proofs (ZKPs) requires symmetric primitives optimized for fast verification inside proof systems. In frameworks based on Rank-1 Constraint Systems (R1CS), prover performance and proof size are dominated by the cost of arithmetization, specifically, by the number of nonlinear multiplication constraints. Traditional bit-oriented designs are typically inefficient under this metric. In this paper, we introduce Lumora, a family of arithmetization-oriented, permutation-based wide-block ciphers designed for efficient use inside zkSNARK circuits and for applications in post-quantum digital signatures. Each instance of Lumora follows a unified AES-like SPN structure defined over the binary extension field $\mathbb{F}_{2^n}$ for $n \in \{16,32,64\}$. The underlying permutation is instantiated as a block cipher via the Even-Mansour paradigm, which eliminates the R1CS constraint overhead of a separate key schedule, ensuring the prover's workload remains strictly focused on evaluating the public permutation. Finally, we provide a detailed security analysis of the Lumora family, together with implementation results and a comparison within the FAEST-EM-256 framework.

Video conferencing software, including Zoom, Microsoft Teams, and Cisco Webex, use human-driven key verification ceremonies to protect end-to-end encrypted meetings against a potentially malicious service provider. The client software shows each participant a code that they must compare; if the codes match, the call is considered secure. Prior security analyses assumed authenticated out-of-band channels for the comparison, but this is generally unrealistic. The codes are short-lived, so the ``in-band'' channel being verified is, itself, the most natural one to use. We seek to understand the implications of this common practice, asking whether it can be secure and under what conditions. To this end, we formalize the notion of a Human-to-Human Group Key Agreement protocol, modeling an authenticated group key exchange between people, rather than their cryptographic keys. We identify that the security of these protocols relies on the pre-existing capacity of people to consistently recognize one another, avoiding any global identification scheme or trusted external infrastructure. We present a construction, prove it secure in our model, derive concrete bounds, and discuss non-examples demonstrating the definition's subtlety. Our results highlight the approach's usability issues and reliance on unforgeability of human-authenticated video streams---an assumption additionally challenged by recent advances in deepfakes.

Private information retrieval (PIR) is a fundamental cryptographic primitive that allows a client to retrieve an entry of a database from a server without revealing which entry was retrieved. PIR security is traditionally defined with a distinguishing game that ensures the clients' access patterns are kept private from a semi-honest server. Verifiable PIR (VPIR) adds another game-based property that holds against a malicious server: the server is bound to a particular database and cannot cause a client to retrieve a database entry that is inconsistent with this database. Recent work by Alon and Beimel [ITC 2025] deviated from the traditional game-based PIR definitions and contributed a definition of standalone simulation-based security for multi-server PIR. Their techniques, however, do not readily extend to single-server VPIR and do not consider concurrent protocol composition when PIR is used as a building block within a larger application. In this work, we further the study of simulation-based VPIR security. We are the first to formalize a universally composable (UC) definition of VPIR in the single-server setting by giving an ideal VPIR functionality. We motivate the need for UC security by showing how game-based VPIR properties fail under sequential and concurrent protocol composition. We also demonstrate the generality of our UC VPIR functionality by providing two realizations based on a trivial PIR and VeriSimplePIR [de Castro and Lee, USENIX Security 2024]. Additionally, we introduce a new kind of VPIR, called Updatable VPIR (UVPIR), which guarantees to clients that (1) database updates are authorized by permissioned clients and (2) responses to their queries are consistent with a specific version of the PIR database. We show that UVPIR can be constructed in a black-box manner on top of any VPIR protocol.

Finding the largest pair of consecutive $B$-smooth integers for a fixed value of $B$, also called a $B$-smooth twin, is computationally challenging. It has only been provably done for $B \leq 100$ and heuristically for $100 < B \leq 113$. We improve this by detailing a new algorithm to find such smooth twins. The core idea is to solve the shortest vector problem (SVP) in a well-constructed lattice. Using a heuristic about smooth numbers in short intervals, we give an estimate of the size of the largest smooth twin for a given $B$. We are able to significantly increase $B$ and notably report the heuristically largest twin with $B = 751$, which has $196$ bits. By slightly modifying the lattice, we are able to find even larger twins, but the resulting smoothness bound will not always be optimal. This notably includes a $213$-bit twin with $B = 997$, which is the largest twin found in this work.

We present InsPIRe that is the first private information retrieval (PIR) construction simultaneously obtaining both high-throughput and low query communication while using silent preprocessing (meaning no offline communication). Prior PIR schemes with both high-throughput and low query communication required substantial offline communication of either downloading a database hint that is 10-100x larger than the communication cost of a single query (such as SimplePIR and DoublePIR [Henzinger et al., USENIX Security 2023]) or streaming the entire database (such as Piano [Zhou et al., S&P 2024]). In contrast, recent works such as YPIR [Menon and Wu, USENIX Security 2024] avoid offline communication at the cost of increasing the query size by 1.8-2x, up to 1-2 MB per query. Our new PIR protocol, InsPIRe, obtains the best of both worlds by obtaining high-throughput and low communication without requiring any offline communication. Compared to YPIR, InsPIRe requires 5x smaller cryptographic keys, requires up to 50% less online query communication while obtaining up to 25% higher throughput. We show that InsPIRe enables improvements across a wide range of applications and database shapes including the InterPlanetary File System and private device enrollment. At the core of InsPIRe, we develop a novel ring packing algorithm, InspiRING, for transforming LWE ciphertexts into RLWE ciphertexts. InspiRING is more amenable to the silent preprocessing setting that allows moving the majority of the necessary operations to offline preprocessing. InspiRING only requires two key-switching matrices whereas prior approaches needed logarithmic key-switching matrices. We also show that InspiRING has smaller noise growth and faster packing times than prior works in the setting when the total key-switching material sizes must be small. To further reduce communication costs in the PIR protocol, InsPIRe performs the second level of PIR using homomorphic polynomial evaluation, which only requires one additional ciphertext from the client.

An anonymous credential allows a user to prove that she is authorized in an anonymous and unlinkable fashion. A rate-limited token is an anonymous credential that can only be used a limited number of times in any particular context; this means that even though we do not know which users are gaining access to a resource, there is a limit to how many resources one user may consume. Such tokens are becoming an increasingly attractive way to balance privacy with authorized access. Although a general architecture for how to obtain rate-limited tokens from digital signatures, pseudorandom functions (PRFs), and non-interactive zero-knowledge proofs (NIZKs) has been known for over twenty years, efficiently instantiating it with post-quantum-secure signatures and proofs has, until now, remained an open problem. In this work, we present the first lattice-based construction of rate-limited tokens and tackle the practical challenges associated with using lattice-based building blocks in this setting. A central difficulty lies in the absence of lattice-based PRFs that support efficient NIZK proofs of correct evaluation. We show that, in the random oracle model, a weak PRF—where adversaries are restricted to querying random inputs—suffices. We further present a weak PRF construction that both admits efficient NIZK proofs and remains secure—even when adversaries have partial control over the randomness—and extend this guarantee more generally to key-homomorphic PRFs. Another contribution, which is of independent interest, is the first lattice-based construction of partially binding commitments, a primitive introduced by Goel et al. (Eurocrypt 2022) that was previously known only under discrete-log assumptions. We give a practical construction that enables succinct disjunctive proofs via a variant of the self-stacking compiler of Goel et al. Along the way, we develop a new technique for batching CNF proofs of $\Sigma$-protocols, which allows one to efficiently prove that a value is the output of a PRF on one of a set of inputs. As a direct application, this yields logarithmic-size lattice-based ring signatures based on Fiat–Shamir-with-Aborts $\Sigma$-protocols (Lyubashevsky, Eurocrypt 2012). Finally, we observe for the first time that the anonymous counting tokens of Benhamouda, Raykova, and Seth (Asiacrypt 2023) can be obtained from anonymous rate-limited tokens. This yields a construction whose communication complexity is independent of the number of tokens that need to be issued.

How few participants are needed before general secret-sharing schemes can outperform linear ones under a fixed security notion? Under statistical security, we show that the answer is five participants; under perfect security, the corresponding threshold remains unknown. It is known that the \(157\) connected access structures on five participants split into \(140\) Shannon-exact cases and seventeen exceptional cases. For the former, linear schemes attain the Shannon polymatroid region; for each of the latter, the exact linear contribution region is the all-pairs one-common-information region and is strictly smaller than the Shannon region. We investigate the statistical contribution regions of these seventeen exceptional structures. For fifteen of them, we construct a partial scheme whose contribution vector lies outside the exact linear region; Jafari--Khazaei's partial-to-statistical transfer then gives a statistically secure family with the same asymptotic vector. One dual pair remains open. For \(\Gamma_{30}\), we further show that the maximum information ratio under statistical security lies in \([14/9,1.6502)\), improving both previously established bounds; moreover, \(1.6502<5/3\), where \(5/3\) is the optimum for linear schemes.

The Hamming Quasi-Cyclic (HQC) cryptosystem, recently selected by NIST for standardization, uses a concatenation of Reed-Muller (RM) and Reed-Solomon (RS) codes to ensure correct decryption. This work optimizes the underlying code and decoder with the goal of reducing ciphertext and public-key sizes. First, we propose a two-level generalized concatenated code (GCC), exploiting the observation that the inner RM code contains a repetition subcode. The repetition layer incurs a smaller inner failure probability and, therefore, admits a higher code rate than the RS code. Second, we develop a reliability-based decoding framework for the outer code. The inner decoder provides a reliability measure whose distribution, jointly with the decoding outcome, is bounded analytically. These bounds allow deriving conservative DFR guarantees for two erasure-assignment strategies (threshold-based and partition-based). Combining both contributions, we observe that public-key and ciphertext sizes can be reduced by up to 4.34%.

Common information (CI) is useful in entropy-based lower bounds for secret sharing. We study CI for group-characterizable (GC) random variables. Building on the sufficient condition of Kaboli--Khazaei--Parviz, we prove an exact pair criterion: two coset random variables $X_H$ and $X_K$ have common information if and only if the subgroups $H$ and $K$ permute, that is, $HK=KH$. Consequently, a GC tuple is $1$-CI exactly when every pair of subgroups in the meet closure of its labels permutes, whereas it is recursively CI exactly when every pair in the generated subgroup sublattice permutes. This also gives a finite algorithm for deciding recursive CI, and we exhibit a GC tuple over $S_3\times S_3$ that is $1$-CI but not $2$-CI. Since normal subgroups satisfy the recursive criterion, homomorphic random variables are recursively CI. For the twelve-participant disjoint Fano--non-Fano access structure, the Shannon lower-bound method with all separate $1$-CI extensions still gives maximum and average optima equal to one. Two depth-two recursive CI extensions instead give the lower bounds $43/41$ and $54089/51756\approx1.04508$ for the maximum and average information ratios of perfect homomorphic schemes. The same bounds hold for Abelian schemes; the exact mixed-linear and linear values are already known.

MEV and censorship, fuelled by public mempool visibility, remain existential threats to Ethereum and have recently started to spread to its layer-two ecosystem. Encrypted mempools promise to conceal transaction content until ordering is final. While this sounds appealing, their viability rests on cryptographic, economic, and deployment trade-offs. This paper systematises the evolution of threshold-encrypted mempools, from early schemes such as Shutter and Ferveo to the most recent research, and analyses how successive iterations have resolved bottlenecks like committee communication overhead, lack of pending transaction privacy, and position-dependent encryption. We highlight a convergence along four design axes, namely batched decryption to mitigate latency, silent setup to eliminate the complexity of distributed key generation, epochless encryption to remove position dependency, and collision-free encoding to prevent slot-collision censorship. We further survey the active Ethereum deployment debate, including EIP-8105 and the LUCID headliner submission, and map the requirements raised there onto the cryptographic corpus. We conclude by exposing a critical limitation common to all current proposals: blind ordering and binary decryption together suppress not only the toxic part of MEV that motivated encrypted mempools, but also the same-block auction mechanisms that return value to users and sustain geographic decentralisation of the network.

Consider the problem of merging inside a garbled circuit (GC) two arrays of $w$-bit elements, yielding a single length-$n$ array. This garbled merge problem is core to garbled random access memory (GRAM), a technique that enables efficient garbling of general-purpose programs. We present a novel symmetric-key-based garbled merge that achieves a garbling size of $(w + 1) \cdot n \cdot \lambda$ bits, providing both asymptotic and concrete improvements over the state of the art. By applying our garbled merge, we obtain a symmetric-key GRAM of size $O(n \lg^3 n \cdot \lambda) \cdot \omega(1)$ for a word RAM program that manipulates words of size $\Theta(\lg n)$ bits and halts within $n$ steps, improving over the previous best result (Heath et al., CRYPTO'23) by an $O(\lg \lg n)$ factor. This communication cost was previously only achieved under the public-key-style DDH assumption (Gu et al., CRYPTO'25). We implement our construction, and our evaluation shows that our garbled merge reduces the communication cost over the DDH-based merge by about $3\times$.

Two-server Private Information Retrieval achieves arbitrarily small polynomial communication, but relies on a strong non-collusion assumption that is difficult to justify in practice. We introduce a new variant of two-server PIR in which one server acts as a standard \emph{compute} server, while the other is a restricted \emph{retrieval-only} server. The latter stores a public encoding of the database and merely serves requested symbols or blocks of this encoding, without performing any PIR-specific computation. We argue that such a retrieval-only server can be instantiated using existing static-content or repository-hosting services, thereby grounding the non-collusion assumption in realistic architectural and deployment constraints. Assuming Learning Parity with Noise (LPN) over the ternary field with inverse-polynomial noise rate, we construct RC-PIR with arbitrarily small polynomial communication and polynomial storage. Leveraging this construction, we derive the following unexpected applications for every constant \(k\): \begin{enumerate} \item \(k\)-server PIR with arbitrarily small polynomial communication and privacy against any coalition of \(k-1\) servers. \item \(k\)-server robust PIR with arbitrarily small polynomial communication that simultaneously achieves correctness and privacy with respect to an arbitrary monotone access structure \(\mathcal{A}\). Namely, correctness is guaranteed whenever the set of online servers \(S\) satisfies \(S \in \mathcal{A}\), while privacy holds against every coalition \(S \notin \mathcal{A}\). \item A \(k\)-party secure computation protocol for size-\(n\) truth tables also known as lookup tables, with arbitrarily small polynomial communication and passive security against any coalition of \(k-1\) parties. This result extends to active security either in the honest-majority setting, or without an honest majority assuming collision-resistant hash functions. \end{enumerate} None of these results were previously known under the LPN assumption. Along the way, we uncover new relationships between different complexity measures of PIR.

Universal hashing gives a pairwise guarantee: for two distinct messages, the probability of any fixed keyed-hash output difference is at most $\varepsilon$. Summing over the $\binom q2$ query pairs gives the familiar multi-query upper bound $\binom q2\varepsilon$, but this union bound does not show that one transcript can realize quadratically many useful pairwise events. We study when a single algebraically structured query set can do so by arranging many substantially different key conditions whose solution sets spread across the key space. Catching gives a simple chosen-offset baseline, while action-invariant grouping provides both a general analysis tool and an attack-search methodology based on message transformations, key relabelings, relative actions, and solution-set overlap. For POLYVAL, and for $\operatorname{NH}[w]$ when even $w\geq4$, we obtain zero-offset constructions in which every query uses output offset zero and balanced partial sets already achieve $\Theta(q^2\varepsilon)$ growth up to absolute constant factors. Thus the quadratic phenomenon can be intrinsic to keyed-hash algebra rather than caused by chosen output offsets. We then show that the same key-space coverage principle survives inside complete accordion modes. HCTR2 gives expected-list recovery of its derived POLYVAL subkey: the true subkey is always included and the candidate list has expected size $2$ in the ideal-permutation model. In ddd-AES the consequence is stronger than distinguishability: with $2^{65}$ fixed-tweak chosen plaintexts of length $384$ bits, exactly one observable cross-pair is the internal POLYVAL catch and it deterministically determines the full $128$-bit POLYVAL key $L$.

Subgroup membership testing serves as a crucial countermeasure against small subgroup attacks, thereby ensuring the security of pairing-based cryptographic protocols. Despite its vital importance, the expensive computational requirements for membership testing on specific pairing-friendly curves pose a non-negligible challenge. In this paper, we revisit the $\mathbb{G}_2$ membership testing algorithms on KSS16 curves and propose a novel approach specifically designed for the families constructed by the KSS method (Kachisa-Schaefer-Scott method). Moreover, we generalize several previous methods for $\mathbb{G}_2$ membership testing, rendering them applicable to more generic pairing-friendly curves. Specifically, we implement an efficient $\mathbb{G}_2$ membership testing on three well-known curves KSS16-329, KSS16-330, and KSS16-766 for verification. The experimental results illustrate that our new method achieves improvements of $24.0\%$, $33.3\%$, and $29.2\%$ in terms of clock cycles compared to the state-of-the-art, respectively.

Quantum public-key encryption (QPKE) is an important direction for secure communication in the presence of quantum adversaries. In this paper, we analyze the four-state QPKE scheme of Liu et al. and show that its ciphertext structure leaks information about computational-basis plaintexts. We present a ciphertext-leakage attack in which an adversary, without knowing the private key, measures the quantum ciphertext component and combines the result with the exposed classical correction bit to recover the plaintext. To overcome this limitation, we propose $\mathsf{sQPKE}$, a simple quantum public-key encryption scheme. The $\mathsf{sQPKE}$scheme uses only elementary operations such as XOR, parity computation, CNOT, Hadamard, Pauli-$Y$ gates, and computational-basis measurements. We prove correctness, analyze security against ciphertext-leakage, eavesdropping, and distinguishing attacks, and validate the attack and proposed construction through Qiskit implementation and resource estimation.

We present LUNA+, a refinement of the LUNA designated-verifier lattice-based ZK-SNARG that achieves significantly improved concrete succinctness. While the original LUNA scheme achieves quasi-optimal asymptotic proof length ($O(\lambda)$), its practical parameters are constrained by its statistical privacy analysis. This analysis, founded on a Leftover Hash Lemma with Leakage (LHLL), necessitates the use of polynomially large, but still significant "smudging" noise to guarantee statistical uniformity. This noise inflation directly propagates to larger lattice dimension and modulus parameters and, consequently, larger proof and CRS sizes. Our core contribution is a new privacy analysis that replaces this statistical foundation with a computational one. We demonstrate that the circuit privacy of LUNA's re-randomization procedure can be securely based on the computational hardness of the Matrix Hint-Module Learning With Errors (MH-MLWE) problem. This computational approach avoids the need for large statistical noise and enables a key optimization: we decouple the secret re-randomization noise from the fresh masking noise. We then formalize and solve an optimization problem to find the minimal noise parameters that satisfy both correctness and the MH-MLWE security reduction. In the process, we also introduce a new problem called Coset Error Knapsack MH-MLWE in which the MLWE error is sampled from a coset of a lattice, which we show is as hard as the standard MH-MLWE problem, and may be of independent interest. This new analysis results in substantial concrete efficiency gains. For a 128-bit security level and an R1CS instance of size $2^{16}$, LUNA+ reduces the proof size by $\approx 25\%$ (from 5.60 KB to 4.22 KB) and the compressed CRS size by $\approx 73\%$ (from 2.06 GB to 0.54 GB) compared to the original LUNA. These succinctness improvements are also accompanied by performance gains, including up to a $\approx 1.73\times$ speedup in setup, a $\approx 1.53\times$ speedup in addition and a $1.44\times$ speedup in decryption for the implementation parameters.

We present the first ciphertext-only distinguishing attack on 5-round AES and a key-recovery attack on 6-round AES for all key sizes under ASCII-encoded English-language plaintext distributions, as well as additional ciphertext-only results under uniform ASCII distributions. Our attacks are enabled by a new analytical framework for estimating truncated differential probabilities in 5-round AES, a problem that remains largely unresolved beyond restricted configurations. Existing approaches, relying on statistical sampling, integral cryptanalysis, or differential distribution tables of super S-boxes, are primarily limited to settings with a single active diagonal in the plaintext and a single passive inverse diagonal in the ciphertext. Our method extends this line of work by providing analytical estimates over a substantially broader range of configurations. We construct this framework by combining precise computations of MDS-level transition probabilities with a systematic enumeration of truncated differential characteristic classes. By organizing characteristics into equivalence classes defined by diagonal propagation patterns, we enable structured aggregation of probability contributions. This approach captures configurations with a single active diagonal in the plaintext and arbitrary passive inverse diagonals in the ciphertext, as well as the complementary setting involving multiple active diagonals in the plaintext and a single passive inverse diagonal in the ciphertext. Our results are validated through independent derivations, consistency checks against prior work, and computer-aided enumeration. More broadly, the framework offers a systematic approach to truncated differential analysis of AES and potentially other AES-like SPN ciphers.

We revisit the notion of PViO [Jain-Jin, FOCS’22] – an indistinguishability obfuscation (iO) scheme for Turing machines with unbounded input length that guarantees security for pairs of machines whose equivalence can be proven in Cook’s Theory PV. Known constructions of PViO require subexponentially-hard iO for circuits. We give the first construction based on polynomially-hard iO and other standard assumptions. We further show how to replace iO with EFiO – an efficiently falsifiable variant, thus obtaining a construction based on efficiently falsifiable assumptions. Central to our result is a new twist to the celebrated punctured programming technique [Sahai-Waters, STOC’14], where one can program an obfuscated probabilistic function on its entire input domain in one shot instead of an input-by-input manner. Our key ingredient is the notion of function secret sharing [Boyle-Gilboa-Ishai, EUROCRYPT’15]. We further show the versatility of our technique by removing the use of complexity-leveraging in two applications of iO: unleveled fully homomorphic encryption, and adaptively-sound succinct non-interactive arguments for “trapdoor” languages.

The study of memory-hard functions (MHFs) has so far focused mainly on provable guarantees on the expected minimum cumulative memory complexity (CMC) required per \emph{evaluation} when amortized over multiple instances. Such results, however, say nothing about whether the passwords in a compromised password bank remain \emph{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 widely accepted security model when inputs have low entropy or are correlated, and requires the adversarial effort to scale linearly with the number of instances broken. To prove these results, we 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 combine the two resulting frameworks to bound the number of guesses of adversaries with a given \emph{maximum} CMC (over the random oracle and adversary coins) in terms of the pebbling complexity of the graph underlying the iMHF. Combined with known lower bounds on the pebbling complexity of Catena's underlying graph, we obtain concrete unrecoverability bounds for Catena, showing in particular that adversarial advantage diminishes exponentially with the number of instances recovered, with the per-instance advantage growing linearly in the maximum CMC of the adversary.

MAYO is a signature scheme based on the Unbalanced Oil and Vinegar (UOV) construction and a third round candidate in the NIST standardization process for additional post-quantum signature schemes. We present a memory-optimized pure- C implementation of MAYO signature verification that reduces RAM consumption by 97–99% compared to the reference implementation provided by the PQM4 project [KPR+] at the cost of increasing runtime by 50–200% and while maintaining code size. This reduction finally enables verifying MAYO signatures on smart cards and small microcontrollers with only a few kilobytes of RAM. We achieve it through three coupled design choices: a) we expand the public key vector-by-vector on the fly rather than all at once at the start; b) we reorder the calculation of the matrix product SPS so that each vector of P is used exactly once, which avoids repeated expansions; and c) we add precomputed multiples of each P-vector directly onto the result instead of accumulating P-vectors before multiplication. We provide results using the PQM4 framework for all parameter sets listed in the specification and supported by PQM4 on our platform, including three main parameter sets MAYO{1,2,3}. This enables direct comparison with other post-quantum digital signature schemes. Further parameter sets not supported by PQM4, including the fourth main parameter set MAYO5, are measured on our own framework, which supports key and signature generation on the host. Our results for non-standard MAYO parameter sets offer insights into the performance and scalability of the proposed approach that may inform ongoing standardization efforts.

CSIDH (Commutative Supersingular Isogeny Diffie--Hellman) is a class-group-based key-exchange protocol operated on supersingular elliptic curves, which, at the time of its proposal, exhibited several attractive selling points such as non-interactivity. Unfortunately, CSIDH is vulnerable to the sub-exponentiation attack--Kuperberg's algorithm, thereby requiring large parameters to ensure security. A recent work based on oriented elliptic curves with large discriminants, proposed by Houben, allows for a significantly small base field (around 255 bits). We name this protocol CSIDH-LDO. However, the practicality of CSIDH-LDO is currently hindered by the necessity of performing multiple group actions and its huge public-key size. In this paper, we address these bottlenecks by presenting highly optimized constant-time implementations alongside an effective public-key compression framework for CSIDH-LDO. We combine algorithmic improvements, specifically scalar multiplication by differential addition chains and isogeny computation on the twisted Edwards model, with \textit{limb-slicing} to exploit parallelism via Intel's AVX-512 instructions. To resolve the architectural mismatch when mapping $r \in \{7, 13\}$ group actions to 8-lane SIMD registers, we evaluate two parallel scheduling strategies. While a dummy-based approach allows us to leverage efficient $\mathbb{F}_{p^2}$-arithmetic, our dummy-free strategy systematically exploits internal parallelism to fully saturate the 512-bit vectors without redundant computations. Benchmarks on an Intel Tiger Lake processor demonstrate our parallel implementations achieve speedups of up to 3.40$\times$ (AVX-512F) and 7.30$\times$ (AVX-512IFMA) over an optimized x64 assembly baseline. Furthermore, we establish a formal framework for public-key compression tailored for CSIDH-LDO. Specifically, we propose two efficient techniques that achieve a compact public key representation of approximately $(r+2)\log_2(p)$ bits, thereby significantly reducing communication bandwidth. To the best of our knowledge, this work is the first to demonstrate the efficacy of SIMD parallelization combined with optimized compression for isogeny-based protocols derived from orientations of large discriminants.

Recent works have highlighted the risk of deterministic memory encryption, as used for example in AMD SEV. In the so-called ciphertext side-channel attack, an adversary leaks sensitive information, such as cryptographic keys, from an encrypted VM by observing changes in the encrypted contents of the memory. To date, countermeasures have been quite restricted in scope and have not addressed the root cause. Alternatively, some studies suggest adding freshness to memory encryption. However, this approach is considered impractical due to the performance overhead introduced by fetching such freshness values for every single memory access. In this work, we propose an efficient approach for eliminating most of the overhead of fetching the aforementioned freshness. Our core idea is to repurpose the ECC memory area to efficiently store random nonces or counters. We propose a range of implementations with varying trade-offs between security guarantees and performance overhead, and demonstrate that we can achieve a solid baseline security even with small random nonces. By leaving a portion of ECC memory unused, we show that it is possible to efficiently integrate protection mechanisms such as memory integrity and memory tagging, while limiting the overall performance overhead to approximately 2%.

Private Function Evaluation (PFE) facilitates the secure computation of private functions on private inputs in an oblivious manner, ensuring that both the function and the inputs remain confidential throughout the entire computational process. PFE has garnered significant attention due to its critical applications in various domains, such as privacy-preserving healthcare systems and privacy-preserving credit checks, where safeguarding the confidentiality of the function itself is of paramount importance. However, despite its broad applicability, existing PFE schemes often exhibit inefficiencies, even in relatively straightforward scenarios such as the evaluation of lookup tables. To mitigate these limitations, we propose a novel variant of PFE, termed Preprocessed Private Function Evaluation (PPFE), which leverages preprocessing techniques to significantly enhance the efficiency of online computations. Within this framework, we introduce a specialized construction tailored specifically for lookup table operations, achieving sublinear complexity during the online computation phase. The efficacy of the proposed approach is demonstrated through experimental evaluations. For a lookup table of size $2^{24}$, the online computation time required to process a single query is about 3 milliseconds, representing a performance improvement of more than an order of magnitude compared to existing results. Furthermore, the proposed scheme exhibits strong scalability, effectively handling thousands of adaptive queries within the same framework.

Proof-of-work (PoW) remains a fundamental mechanism for achieving decentralized consensus, most commonly instantiated using cryptographic hash functions. In such constructions, mining takes the form of an unstructured search problem over a large input space, where miners repeatedly evaluate candidate solutions until a valid one is found. While this design has proven effective in practice, it admits a quadratic quantum speedup via Grover’s algorithm, raising concerns about the long-term security of hash-based mining. Motivated by this limitation, we investigate the use of code-based cryptographic problems as an al- ternative foundation for proof-of-work. In particular, we focus on the syndrome decoding problem and examine its classical and quantum com- plexity based on current state-of-the-art information-set decoding (ISD) algorithms and their quantum variants, comparing the resulting quantum advantage with that of hash-based and lattice-based constructions. Building on this analysis, we propose a proof-of-work construction based on the Syndrome Decoding Problem (SDP) with a structured profile constraint, which enables controlled variation of solution density and difficulty. Under the standard random-instance heuristic, we derive ex- pressions for the expected number of solutions and the probability of successful mining, providing a principled basis for parameter selection.

We give a structural cryptanalysis of GRAFHEN, a proposed group-based fully homomorphic encryption scheme whose public rewriting rules hide a group representation used for decryption. Under the designers' isomorphism hypothesis, the compatible representations in a finite target $T$ form one free $\mathrm{Aut}(T)$-orbit. Thus every representative induces the same zero predicate. For a fixed publication, the published key-class expression is the expected trial count of uniform verified sampling rather than a lower bound on reconstruction work. More generally, a homomorphism $\psi$ gives the correct zero predicate exactly when $\ker\psi\cap\Gamma\subseteq\Lambda$, where $\Gamma$ is the ciphertext set of the presented group and $\Lambda$ its zero-ciphertext subgroup. After reconstruction, we give a finite-sample distinguishing bound for independent zero queries and an independent challenge. It requires neither uniform sampling nor generation of the full zero subgroup. For matched query and challenge distributions, the target alone puts the advantage above $1/2$ after $14$ queries at degree $7$ and $26$ at degree $11$. Our attack, HEnbane, combines automorphism-reduced search over complete group elements with algebraic forcing from short public consequences. At the level of a generic algorithmic schema, an uncapped whole-element branching fallback makes reconstruction complete for every finite effectively enumerable target with enumerable element-orbit representatives. The released software instantiates this schema for its supported symmetric-group targets and the fixed target $\mathrm{PSL}_2(343)$. The two-seed force chains used by all supplied instances are a fast path rather than a completeness assumption. It decrypts all five released symmetric challenges, with a slowest ten-run mean of $25.4$ seconds. It also solves the author-supplied $\mathrm{SL}_2(343)$ challenge for the revised parameters by reconstructing in the $\mathrm{PSL}_2(343)$ quotient and recovering the ten central lift signs over $\mathbb F_2$, averaging $37.7$ seconds end to end without exact-order hints.

In this paper, we investigate the nonexistence of $N$-ary sequences with ideal arithmetic correlation. We prove that there exist no ternary, quaternary, or $6$-ary sequences with ideal arithmetic autocorrelation when the connection integer is an odd prime power $p^{t}$ and $\textup{ord}_{p^{t}}(N)=\phi(p^{t})/4$, where $\phi$ denotes Euler's totient function. Furthermore, when the connection integer is an odd prime $p$ and $\textup{ord}_{p}(N)=\phi(p)/6$, no such ternary, quaternary, or $6$-ary sequences exist for ideal arithmetic correlation. This includes in particular the case $p\equiv7(\textup{mod}12)$, for which $\textup{ord}_{p}(N)=\phi(p)/6$ and we further show that no $N$-ary sequence with ideal arithmetic correlation exists for any prime $N>2$. These results provide further evidence that ideal arithmetic correlation is highly restrictive in the $N$-ary setting.

Selfish mining undermines incentive compatibility of proof-of-work blockchains, letting a miner earn disproportionate rewards at a hashrate lower than the majority threshold. A decade of work has asked whether a strategy is profitable, however, far less is understood about when it becomes profitable. Timing is critical since selfish mining operates at a loss before it turns a profit, typically requiring tens of weeks to break even in the classic case. In this paper, we present a holistic study of the time-to-profitability (TTP) of existing selfish mining strategies structured around four contributions. First, in the single-attacker setting, we characterize TTP across the full strategy space and find that TTP-minimizing and profit-maximizing strategies frequently diverge, making attack horizon a critical metric. In particular, under realistic fee dynamics, the use of incentive transactions to recruit honest-but-rational miners enable incentivized strategies to reach profitability up to $15\times$ faster than classic selfish mining at the same hash rate. Second, we explore TTP for the first time in the multi-attacker setting, showing that the difference in strategies between opposing attackers has a dramatic impact on joint-profitability lag. Third, we generalize intermittent selfish mining by exploring temporal composition over the full strategy space and show that its purported benefits are largely overstated. That is, alternating strategies rarely outperform the best static strategy in terms of either TTP or long-term profits. Finally, and building off our earlier findings, we explore adaptive, state-conditioned strategy selection at the difficulty adjustment period (DAP) level. We compare a general-purpose LLM agent against a fixed decision-tree selector, both implementing the same selection criteria. We find that both selectors reliably identify profit-maximizing strategies from observed network conditions, at a low operating cost, lowering the expertise barrier to exploiting adaptive selfish mining.

This work composes SHA-2 and SHA-3 into a unified hardware architecture, bringing them together as a single, efficient cryptographic ensemble. This need is driven in particular by Post-Quantum Cryptography (PQC), where different standardized schemes rely on either SHA-2 or SHA-3/SHAKE primitives. Rather than enforcing strict round-level unification, the proposed design applies selective sharing across the most area-critical components, including a shared 25x64-bit register bank, shared round-constant storage, and unified padding and control logic while maintaining full compliance with FIPS 180-4 and FIPS 202. In addition, a duet execution mode exploits the otherwise underutilized upper half of the 64-bit datapath to process two independent SHA-224/256 streams in parallel, benefiting Merkle-tree-based constructions in hash-based PQC. The design is implemented and synthesized on an Artix-7 FPGA, occupying 5,873 LUTs and 2,310 FFs. Experimental results show that SHARMONY achieves a throughput of 1,959 Mbps for SHA-256, representing improvements of 100-152% over the SHA-256 engines of SLotH, Sphincslet, OpenTitan, and Caliptra. At the same time, SHARMONY reduces LUT utilization by an average of 40% and FF utilization by an average of 55% compared to combined designs constructed from separate SHA-2 and SHA-3 implementations.

Lattice-based cryptography offers a promising direction for transitioning Bitcoin toward post-quantum security, serving as a secure replacement for currently deployed discrete logarithm signatures. The primary advantages of lattice-based signature schemes include the compact combined size of signatures and public keys (e.g., in some cases below 1.6 KB), the robustness of underlying security assumptions, and an algebraic structure that, while not yet yielding practical constructions, holds potential for advanced functionality such as threshold and multi-signatures, compared to hash-based constructions. In this paper, we present a self-contained review of three lattice-based signature schemes, with Bitcoin's post-quantum transition as the motivating application: Dilithium, Falcon, and Hawk. The latter was recently withdrawn from NIST standardization following a key-recovery attack; we retain it because its design paradigm remains of independent interest. For each protocol, we detail the high-level intuition, the necessary technical preliminaries, low-level mechanics, performance, and security analysis. We then assess the deployment aspects relevant to Bitcoin: the on-chain footprint, determined by the combined public-key and signature size and compared against hash-based alternatives; the target security level for outputs that may remain unspent for decades; implementation constraints, such as Falcon's floating-point signing; and wallet key derivation. No prior exposure to lattice-based cryptography is assumed: all the required background is developed within the document.

Anonymity infrastructures such as mix networks, anonymous storage, and privacy-preserving replication rely on public re-randomization: any party holding only public information can transform a ciphertext into a fresh-looking encryption of the same plaintext, hiding the linkage between the two. Classical ElGamal-based solutions are broken by quantum adversaries, while existing lattice-based alternatives carry very large ciphertexts with unanalyzed noise growth, rely on heavyweight homomorphic-encryption stacks with approximate (rounded) decryption, or lack a precise analysis of how many re-randomizations are safe. We address this gap with a practical Ring Learning with Errors (Ring-LWE) public-key encryption scheme supporting public re-randomization without ciphertext growth. Our construction is Lyubashevsky–Peikert–Regev / Fan–Vercauteren (LPR/BFV)-style encryption over $R=\mathbb{Z}[x]/(x^n+1)$ with $n=4096$, engineered around a two-limb Chinese Remainder Theorem (CRT) modulus $q=t\cdot q_2$ with 32-bit primes. Embedding plaintext as $\Delta M = q_2 M$ makes the message vanish modulo $q_2$, so the $q_2$-limb carries only the decryption noise, enabling exact message recovery without rounding. We prove correctness with explicit decryption-failure bounds that remain valid under repeated re-randomization, via an aggregation lemma showing that arbitrarily many re-randomizations affect decryption only through a single aggregated randomness triple. We also prove that two-limb ciphertexts are pseudorandom (indistinguishable from uniform, IND\$) under Decision Ring-LWE over the combined modulus $q=tq_2$; security against chosen-plaintext attack (IND-CPA) and re-randomization unlinkability follow. A constant-time Rust implementation encrypts in 0.80 ms, re-randomizes in 0.51 ms, and decrypts in 0.21 ms per 64 KiB ciphertext carrying 15.5 KiB of payload on a fixed-frequency 3.8 GHz CPU—on par with a modulus-matched Microsoft SEAL baseline—and passes timing-leakage tests. Empirical noise simulations validate the analysis.

In multi-epoch deployments, private set union~(PSU) operates in an adaptive-input loop: after observing the union at epoch $t$, the receiver may choose its next input for epoch $t+1$. Liu et al.~(EUROCRYPT 2026) formalized this multi-epoch adaptive-input setting for updatable private set intersection and provided an instantiation, but their framework does not extend to PSU. Meanwhile, existing PSU protocols are analyzed only in the single-shot setting. We present the first semi-honest, adaptive-input-secure updatable PSU protocol supporting two-sided add/delete updates in the multi-epoch adaptive-input setting of Liu et al. Our construction is built around a new primitive, the updatable oblivious key-value store (uOKVS). Its defining rule, distributional erasure, requires each refresh to be distributed identically to a fresh static encoding of the current key set, rather than merely indistinguishably. We realize uOKVS by combining the Band-OKVS of Bienstock et al. with a PRF under a persistent key. The resulting refresh reuses a cached factorization, so its per-epoch encoding cost scales linearly rather than quadratically in the band width $w$. Building on this layer, we obtain a multi-epoch PSU protocol whose leakage is limited to set and update cardinalities, even against adaptive-input adversaries. We implement the protocol and benchmark it in a single-threaded setting. At $n = 2^{20}$ with per-epoch updates $\Delta = 55$ over $10$ epochs, the online per-epoch wall-clock time is $1.41$ s on LAN, yielding a $30.9\times$--$98.9\times$ speedup over prior static PSU protocols re-executed from scratch at each epoch.

Offline payments present an opportunity for central bank digital currency to address the lack of digital financial inclusion plaguing existing digital payment solutions. However, the design of secure offline payments is a complex undertaking; for example, the lack of connectivity during the payments renders double spending attacks trivial. While the identification of double spenders and penal sanctions may curb attacks by individuals, they may not be sufficient against concerted efforts by states or well-funded institutions. It is hence important to also rely on preventive measures that reduce the scale of such attacks. An example of such a measure is secure elements. These however are limited in compute and storage, making the design of solutions that offer comparable privacy guarantees to those of physical cash challenging. We address this with a protocol that offloads most of the payment computation to the user’s mobile device and restricts the computation on the secure element to deleting spent tokens, and generating a signature with a computation equivalent to that of ECDSA. We claim that the use of mobile devices or enhanced smart card-based devices are required for secure consumer-to-consumer payments. To further harden the protocol, we enable the efficient identification of double spenders on the off-chance an attacker successfully double spends. Finally, we prove its security in the ideal/real world paradigm, and evaluate its performance to demonstrate its practicality.

In this short note, we show that two identity-based encryption schemes, introduced by Joye and Zhao et al., which appear different, are essentially the same scheme. The only difference between them is that one prioritizes speed (Zhao et al.), while the other prioritizes bandwidth (Joye). We also show how to speed-up Joye's scheme at the cost of adding at most one integer to the public key, thereby achieving a better encryption complexity, while having the same bandwidth requirements.

This paper analyzes the bilinear embedding of matrix algebras into commutative cyclotomic rings. We apply the Cohn-Umans method. This establishes that single-multiplication bilinear monomial embeddings require a ring degree of $\widetilde{\Omega}(N^3)$. We circumvent this bound by routing Strassen tensor rank decompositions through orthogonal Chinese Remainder Theorem ideals. This reduces the asymptotic complexity to $\widetilde{\Omega}(N^{\log_2 7})$. We optimize the coprime tensor decomposition. Embedding the inner tensor into the maximal real subfield satisfies the Lempel-Weinberger parity constraint. This guarantees the existence of a Self-Dual Normal Basis, reducing the required basis generators to a single element and mathematically halving the homomorphic trace depth. Canonical integer polynomial lifts ensure uniform norm bounds. Type I Optimal Normal Bases bound the trace dual expansions to an $O(1)$ constant. By invoking Kronecker's theorem, we prove that the polynomial power basis minimizes the canonical expansion for the non-evaluated tensor components. A towered evaluation over composite degrees controls noise propagation. This decouples key-switching errors into a logarithmic bound. We generalize the embedding to Galois rings via Hensel's and Nakayama's lemmas to support high-precision integer arithmetic. Furthermore, we extend the architecture to boundless matrices exceeding the fixed ring capacity via a multi-ciphertext block-Strassen decomposition. By deferring the homomorphic trace operator to post-Strassen recombination, we completely eliminate homomorphic basis-switching, achieving an asymptotic complexity of $O(N^{\log_2 7 - 1/\rho})$ multiplications and $\widetilde{O}(N^{2 - 2/(\rho \log_2 7)})$ automorphisms for matrices of arbitrary dimension. Empirical benchmarks over the BGV scheme validate the approach. A multi-threaded towered trace evaluates $32 \times 32$ matrices in $141.3$ milliseconds at a security level of $\lambda=148$ using one ciphertext-ciphertext multiplication. We achieve a speedup factor of $2.49$ over multi-threaded baselines.

Efficient polynomial multiplication and matrix-vector operations are fundamental to computational algebra and modern cryptography. In lattice-based post-quantum cryptography (PQC), schemes utilizing Number Theoretic Transform (NTT)-unfriendly rings require highly optimized subquadratic multiplication algorithms. In this paper, we establish a rigorous mathematical framework for generalized $k$-way split polynomial multiplication and Toeplitz Matrix-Vector Product (TMVP) algorithms over arbitrary fields. First, we construct generalized $k$-way Schoolbook and Karatsuba multiplication algorithms, deriving exact closed-form recurrence relations and arithmetic complexities for any integer $k$. Second, we introduce a novel $k$-way TMVP algorithm utilizing optimal evaluation points and matrix row-reversal techniques. We mathematically prove that this generalized formulation strictly achieves the theoretical interpolation lower bound, requiring exactly $2k-1$ subproblems and yielding a subquadratic asymptotic complexity of $O(n^{\log_k(2k-1)})$. Furthermore, we determine the optimal consecutive application sequence of $k$-way Karatsuba and Schoolbook algorithms for any input size $n$, proving that the peak efficiency is driven entirely by the prime factorization of $n$. Finally, we establish exact algebraic crossover thresholds, demonstrating that our generalized TMVP formulas and optimal algorithmic sequences significantly outperform state-of-the-art unequal $k$-way splits and classical combinations in the literature, providing minimum arithmetic operation counts for $k \in \{5, 6, 8, 12\}$ and inputs of power-of-two and power-of-three dimensions.

Grinding is a technique which introduces a proof of work into the Fiat-Shamir transform: by constraining the challenge to satisfy a $w$-bit condition, forging a proof requires about $2^w/\varepsilon$ evaluations of the hash function instead of $1/\varepsilon$, where $\varepsilon$ is the soundness error of the underlying protocol. This allows one to select reduced parameters, yielding shorter proofs and signatures. Grinding is used in FAEST, MQOM and SDitH, the three MPC-in-the-Head schemes selected for the third round of the NIST additional post-quantum signature standardization process, where it is instantiated with Keccak. In this short paper, we investigate grinding schemes in which the proof of work is expressed in terms of block cipher computations, specifically AES, which is significantly faster than Keccak on modern CPUs, is already a building block of these schemes, and underlies the very definition of the NIST security categories. We formalize the notion of grinding scheme together with a protocol-agnostic security notion, we propose a construction performing two cipher calls per iteration, and we prove, in the ideal cipher and random oracle models, that an adversary making $Q_E$ cipher queries breaks it with probability at most $\frac{4}{3} \cdot \varepsilon\, Q_E / 2^w$, up to negligible terms. We further generalize the scheme to use more cipher calls per iteration, which makes the constant $\frac43$ tend to $1$.

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, 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 are defined on non-negligible sets such as computability, or global properties, such as algorithmic indistinguishability. We resolve this by shifting from defining local satisfaction as 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 \emph{non-negligible sets} as possible worlds, rather than the propositional S5 fragment with \emph{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, together with a first-order calculus, $\mathsf{BC}^+$, whose sole modal operator is the overwhelming-truth bracket $[\,\cdot\,]$. The calculus is sound and, on its fragment, derives exactly the theorems of first-order S4 with persistence; computational completeness holds on the fragment; cut elimination holds propositionally, while at first order every cut is confined to an optimal Barcan shape. 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.

The cost of quantum cryptanalysis is dominated by the quantum circuit of the target cipher. Estimating the quantum attack cost of a cipher thus requires building that circuit and measuring its qubit count, Toffoli count, and Toffoli depth. This is manual work that needs expert knowledge and must be redone for each cipher and each cost target. Large language models handle ordinary programming well, but their use in constructing quantum circuits for ciphers is still limited. In this work, we collect quantum circuit optimization techniques that apply across many ciphers. We write these techniques into a guideline for a general-purpose LLM. Given this guideline and a single target cipher, the model produces two circuits. One minimizes the qubit count, and the other minimizes the Toffoli depth. Each circuit is verified against the test vectors of the cipher before its resources are estimated. Using this approach, we implement quantum circuits of CRAFT, MANTIS, QARMA, mCrypton, EPCBC, and Pyjamask for which quantum circuit implementations have not previously been reported. We further apply the same approach to ciphers with existing implementations. Without access to prior results, the generated circuits reach resource counts comparable to manually optimized ones.

The design, proposal, and analysis of cryptographic primitives (schemes and protocols) is one of the primary research fields in cryptology. To advance this research field, in this paper, we systematically introduce the research motivations for proposing new constructions (for a primitive) in public-key cryptography. We found that all research motivations aim to produce more benefits for certain users, including practicality, security, and functionalities, although some of the benefits may not be obvious or may only hold conditionally. We have categorized the approaches for exploring more benefits into 3 ways, 6 types, 17 areas, and 40 research strategies. Each research strategy is presented as ``From less-beneficial (in the first construction) To more-beneficial (in the second construction)". This SoK paper aims to provide valuable insights into the driving forces behind advancements in public-key cryptography, facilitating future research efforts in this field.

Levin and Pedersen proposed at Asiacrypt2025 a new verifiable random function (VRF) based on a CGL-analogue hash function constructed from radical isogenies. Their construction applies the same secret radical-CGL walk to a public starting curve and a message-dependent curve, and uses an R1CS proof relation to show that the two walks use the same secret key. We present a two-stage attack on this construction. The first stage concerns the unspecified representation of the public key. The reported key size indicates that the public curve is stored as a \(j\)-invariant, whereas both the specified radical-CGL computation use two coefficients to represent a curve. By exploiting this form we can produce two different VRF outputs under the same public key and message, breaking the unique provability. Hence, the output of the radical-CGL computation must follow the specification. In the second stage, we exploit these coefficients to recover the VRF secret key. With \(1536\) queries, our implementation recovers the complete \(256\)-bit secret in 30 minutes, thereby breaking residual pseudorandomness. Interestingly, we also observe that the using public key alone without queries can sometimes reveal one or two bits of the secret walk. Besides, we extend Lai's observation to obtain a one-query attack on the group-action-based VRF proposed in the same paper with advantage closed to 1/2. Together, these constitute three attacks on their work.

Oblivious algorithms allow a space-constrained client program to securely outsource storage to an untrusted server. Any program can be compiled to an oblivious form via Oblivious RAM (ORAM), but this is asymptotically and concretely expensive. Recent work (Appan et al., CCS'24) proposed a weakening of ORAM called Oblivious Single Access Machine (OSAM), which offers asymptotically-improved oblivious compilation for many programs, including those that manipulate graph data structures. While of theoretical interest, OSAM graph algorithms were worse than generic ORAM, even for large graphs (tested on graphs of size up to $2^{25}$). This work improves the concrete costs of OSAM-based oblivious algorithms. In short, the original work on OSAM proposed algorithms for manipulating objects with pointers to other objects, but their management of pointers involves non-trivial and concretely-expensive algorithms. Our work greatly simplifies and improves the efficiency of OSAM-based pointer handling by co-designing (1) pointer-friendly modifications to the underlying Path ORAM algorithm and (2) new algorithms for managing pointers and building graphs from pointers. Our work provides generic and easy-to-use oblivious tools with concretely better performance than state-of-the-art generic tools. Natural graph algorithms can now be automatically compiled to an oblivious form while enjoying up to a $4$x improvement in performance as compared to generic Path ORAM (and at least $8$x as compared to the original OSAM).

We perform the first formal security analysis of the cryptographic core of Olvid, an end-to-end encrypted messaging app notably used by French government officials, including ministers. Despite its deployment in sensitive contexts and its role in critical communications infrastructure, Olvid's cryptographic security has received little independent analysis. To address this gap, we develop detailed models of Olvid's authenticated key exchange and continuous key agreement protocols. We formally verify that our protocol models achieve security properties such as mutual authentication, session-key secrecy, forward secrecy, and replay protection, under an active Dolev-Yao network adversary model that can compromise parties. While we constructively prove that the protocol design meets core security guarantees, our analysis also reveals that, contrary to its claims, the protocol does not meet strong modern security properties that are met by other state-of-the-art secure-messaging protocols, such as Signal. For example, we show in our formal analysis that Olvid is not secure in modern security models such as eCK. Along the way, we uncover a potential timing leakage, and discuss Olvid's anonymity claims.

The Unbalanced Oil and Vinegar (UOV) scheme was proposed by Kipnis et al. in 1999 as a multivariate signature scheme. Owing to its small signature size and its resistance to various attacks over more than two decades, UOV has become one of the leading candidates in multivariate public key cryptography. In 2025, Ran proposed a novel algebraic key recovery attack exploiting the algebraic structure of UOV, which reduced the security of several parameter sets of UOV and its variants submitted to the second round of the NIST PQC standardization process for additional signatures. This attack was improved by Jin et al., and Furue and Ikematsu, forming a line of attacks that has significantly advanced the cryptanalysis of UOV. However, Ran's attack is applicable only when $v<2m$, where $v$ denotes the number of vinegar variables and $m$ the number of public polynomials. In fact, when $v\ge 2m$, an additional kernel element of the ideal generated by the public polynomials appears, preventing the attack from recovering the oil subspace. A similar issue arises in the improvements by Jin et al., and Furue and Ikematsu. In this paper, we propose a method that overcomes this issue, extending the applicability of this line of attacks to the case where such an additional kernel element appears. Applying our method to SNOVA via the lifting technique of Nakamura et al., we show that the claimed security levels of some parameter sets of SNOVA in the second round of NIST PQC standardization process for additional signatures are reduced. In particular, for the parameter set $(v,o,q,l)=(37,17,16,2)$ of NIST security level I, although Ran's attack is not applicable, our method reduces the estimated security to $2^{103}$ gate operations, which matches the complexity of the attack by Bros et al. in 2026.

Quasi-Cyclic Moderate-Density Parity-Check (QC-MDPC) codes are a family of error correcting codes admitting parity-check matrices composed of sparse circulant blocks. QC-MDPC codes have been used for the design of BIKE, one of the finalists in the NIST competition for the standardization of post-quantum cryptography. Decoding of QC-MDPC codes with cryptographically relevant parameters is intrinsically bound to fail, resulting in a decoding failure rate (DFR) that is nonzero. To achieve INDistinguishability under Adaptively Chosen Ciphertext Attacks (IND-CCA2), the DFR must not exceed $2^{-\lambda}$, with $\lambda$ being the security parameter. QC-MDPC codes are customarily decoded with a Bit Flipping (BF) algorithm. Especially at very low DFR values, error patterns having a large intersection with near-codewords (which are vectors corresponding to columns of the parity-check matrix, up to some shift) are the main cause of decoding failures. In this paper, we show how a BF decoder can be tweaked to exploit the knowledge about near-codewords. Since error vectors that cause decoding failures are likely making the decoder converge to the closest near-codeword (i.e., to the near-codeword with the largest amount of overlapping positions with the error vector), we exploit such a harmful but predictable behavior: we let the decoder recognize, and consequently correct, syndromes of near-codewords. This modification comes with a very mild computational overhead and can be applied to any BF decoder. As a concrete application, we focus on BIKE parameters for NIST security category 1. We show that a recently proposed BF variant called $\textsf{BF}\text{-}\textsf{Max}$ outperforms significantly the two decoders used by BIKE within the NIST competition, achieving a significantly lower DFR with a comparable computational complexity.

The good-case latency of a consensus protocol measures the latency from block proposal by a consensus leader to decision, in the case in which the leader is correct. It is arguably the efficiency metric most pertinent for discussing the practical latency performance of consensus protocols. Well understood in the context of the authenticated setting, with PBFT [Castro 99], Tendermint [Buchman 16] & Simplex [Chan, Pass 23] achieving the optimal good-case latency of 3 rounds, significant gaps remain in the unauthenticated setting. We present Forget-IT, an unauthenticated consensus protocol with optimal good-case latency of 3 rounds. Furthermore, our protocol only requires constant persistent storage, and has $O(n^2)$ message complexity per view.

Function secret sharing (FSS) has become a core primitive in privacy‑preserving computation. However, each FSS invocation requires a fresh pair of function keys, typically produced by a trusted dealer—a dependency that expands the system's trust boundary and hinders practical deployment. Existing dealerless protocols eliminate this dependency, but incur substantial communication and a number of interaction rounds that grows linearly with the input bit‑width, making key generation a major bottleneck. This paper presents KORD, a protocol–hardware co‑design that dramatically reduces the cost of dealerless FSS key generation. At its core is a pair of chips that establish a common root of trust through mutual attestation and, within it, reconstruct FSS keys—eliminating the need for a dealer. This root of trust further forms a security boundary within which KORD restructures the generation protocol, collapsing the interaction of prior dealerless protocols into a single round, independent of GGM depth. A cross‑key scheduling scheme then interleaves independent GGM‑tree traversals, sustaining high computational throughput. KORD reduces key‑generation communication per operation by $7{,}633$–$70{,}274\times$ over the state‑of‑the‑art distributed FSS protocol. On a ZCU102 FPGA, cross‑key interleaving lifts AES lane utilization from $8.3\%$ to a board‑measured $99.0\%$, for $11.60$ million $32$-bit DPF keys per second at $187.5\,\text{MHz}$ on a $21.5\,\text{K}$ LUT engine ($12.38\,\text{M}$ at the separately validated $200\,\text{MHz}$ operating point). On private ResNet‑18 inference, key generation's share of end‑to‑end time falls to $10.1\%$, from $82.6\%$ under a trusted dealer and over $96\%$ under the dealerless baseline.

Background: The migration to post-quantum cryptography confronts resource-constrained Internet of Things (IoT) devices with a material performance cost. CRYSTALS-Dilithium, standardised as the Module-Lattice-Based Digital Signature Algorithm (ML-DSA) in FIPS 204, fixes the Keccak-based SHAKE functions as its only symmetric primitives, and profiling on embedded platforms identifies hashing as the largest single contributor to the scheme’s software cost. This review synthesises the performance evidence for ML-DSA on constrained platforms, classifies the optimisation strategies pursued in the literature, and tests whether any published work substitutes a standardised lightweight extendable-output function for SHAKE within the scheme. Methods: Following Kitchenham’s guidelines and the PRISMA 2020 statement, we searched IEEE Xplore, the ACM Digital Library, Scopus, and SpringerLink for peer-reviewed studies published from January 2020 onwards, complemented by backward and forward snowballing and by targeted update searches through July 2026. A protocol was prepared in advance of the search. From 115 database records and 22 records identified through other methods, 40 primary studies met the inclusion criteria. Results: On the ARM Cortex-M4, optimised software implementations of Dilithium3 require 10,667 kilocycles on average for signing and 2,321 kilocycles for verification; on the Cortex-M7, Dilithium-2 verification averages 1,429 kilocycles (6.6ms at 216MHz), with signing spanning 1,835 to 16,440 kilocycles due to rejection sampling. Optimisation efforts fall into four categories: hardware acceleration, platform-specific software optimisation, protocol-level adaptation, and optimisation of the incumbent Keccak primitive itself. Architecture-specific Keccak optimisation reduces hashing’s share of Dilithium’s runtime on the Cortex-M4 by only 2.46 to 5.03 percentage points, indicating that the bottleneck largely survives direct attack. Replacing Keccak with Ascon inside the sibling scheme Kyber yields a 24 to 25% cycle reduction and a 2 to 8% memory reduction on the Cortex-M4. No peer-reviewed study applies this substitution to ML-DSA. Conclusions: With FIPS 204 and NIST SP 800-232 both final, the cost of ML-DSA’s primitive choice on constrained platforms is a well-posed and unanswered question on both sides. We specify a per-call-site Dilithium–Ascon evaluation, including its security constraints and non conformance status, as the priority direction for software-only optimisation of post-quantum signatures on IoT devices. Keywords: post-quantum cryptography; ML-DSA; CRYSTALS-Dilithium; Ascon; lightweight cryptography; Internet of Things; systematic literature review

Distributed Oblivious RAM (DORAM) is a promising building block for privacy-preserving cloud databases and outsourced storage systems. However, existing two-server designs often rely on slow linear scans or heavy cryptographic primitives, making them struggle to balance efficiency and bandwidth, and thus hindering their practical deployment. We present DuetORAM, a two-server DORAM that achieves constant-round access with $O(\log N)$ communication while avoiding these computational bottlenecks. Our key idea is a replicated-to-shared block encoding that allows servers to keep identical ciphertexts for efficient PIR-based retrieval, while locally interpreting them as secret shares to enable oblivious eviction via a lightweight shuffle. We further design a secret-shared shuffle with an offline-online decomposition that shifts most bandwidth-intensive work to a preprocessing phase, significantly reducing online communication. We implement a prototype of DuetORAM and evaluate it under diverse network conditions. Our results show that DuetORAM outperforms both the state-of-the-art two-server scheme DUORAM (reducing retrieval latency by up to 170$\times$ in LAN settings), and three-server design S$^3$ORAM (reducing retrieval latency by 1.7$\times$ in LAN and accelerating eviction by 7$\times$ in LAN and 5$\times$ in WAN, respectively).

Privacy-preserving computation over real numbers typically employs either floating-point or fixed-point arithmetic. While fixed-point methods are highly efficient, they struggle to handle wide dynamic ranges. Conversely, floating-point methods support a much larger numerical scope but incur overheads more than a hundred times higher than their fixed-point counterparts. In this paper, we propose DYNAFIX, a dynamic fixed-point computation scheme that strikes a balance between floating-point and fixed-point arithmetic. Compared to traditional fixed-point approaches, our scheme supports an arbitrary numerical range; compared to floating-point computation, it maintains performance comparable to fixed-point execution. Experimental results demonstrate that our method achieves a $24.1\times$ speedup over the state-of-the-art when evaluating high-precision functions, such as the exponential function.

Classical selection criteria for cryptographic S-boxes—nonlinearity $\mathrm{NL}$, differential uniformity $\delta$, boomerang uniformity $\beta_{\mathrm{B}}$, algebraic degree $\deg$—are invariants of affine equivalence. That property is exactly what blinds them to a class of side-channel weaknesses. The correlation-power-analysis (CPA) template distinguisher is governed by the Hamming-weight functional, and Hamming weight is not affine-invariant; it does not descend to the affine-equivalence quotient on which the classical criteria live. Two S-boxes with identical $(\mathrm{NL},\delta,\beta_{\mathrm{B}},\deg)$ can therefore leak differently under template CPA. We make this precise for the key-dependent family $S^{\mathcal{G}}(x)=A\,\iota(x)\oplus c$, with $\iota$ the multiplicative inverse in $\mathrm{GF}(2^8)$ and $(A,c)\in\mathrm{GL}(8,\mathbb{F}_2)\times\mathbb{F}_2^8$ drawn from a byte stream $\mathcal{G}$. A structural proposition fixes the four invariants at $(112,4,6,7)$ across the entire family; they carry no information about $\mathcal{G}$. We introduce the Hamming-weight template correlation $\rho_{\mathrm{HW}}(\cdot,S_{\mathrm{AES}})$, identify it as the population statistic controlling the AES-template CPA distinguisher, and show that it resolves the fiber the classical invariants collapse. As a stress test we instantiate $\mathcal{G}$ with three sources of contrasting regularity—a system CSPRNG, a discretised logistic map, and a $\sin(1/x)$/xxHash hybrid—and sample $3\times10^{5}$ S-boxes from a single master seed. The classical invariants are identical everywhere, as predicted. The metric is not. The logistic source widens the $\rho_{\mathrm{HW}}$ distribution against $S_{\mathrm{AES}}$ by $12$–$13\%$ ($\sigma_\ell=0.0704$ vs. $0.0626/0.0623$; Levene $p<10^{-180}$). The widening vanishes against a uniform-random reference permutation (Levene $p>0.13$), survives an exact Q1.31 fixed-point reimplementation at $3.1\%$, and does not appear for a tent-map control. Propagated through the Mangard–Oswald–Popp trace-budget model and checked against a $2.16\times10^{5}$-attack Monte-Carlo CPA simulation, it yields a $29\%$ relative excess in AES-template success rate at $\mathrm{SNR}=10$, $N=10^3$ (empirical ratio $1.29$, analytic $1.26$). By every standard effect-size measure the widening is small (Cohen's $d=0.128$ on $|\rho_{\mathrm{HW}}|$, Cohen's $h=0.130$ on the attackable fraction); its significance is detectability, not magnitude. The contribution is a measurement axis, not a weak generator: a metric that flags template-CPA leakage where $\mathrm{NL}=112$, $\delta=4$ report perfect scores.

Blockchains aim to provide open access and censorship resistance, but centralization of block production in blockchains like Ethereum undermines these goals. Inclusion List (IL) protocols mitigate this by requiring block proposers to include transactions selected by an IL committee to enforce the inclusion of transactions that appear to have been censored. However, protecting the confidentiality of individual committee members’ contributions is essential to prevent retaliation and ensure robust censorship resistance. We propose a lightweight, privacy-preserving inclusion list protocol that allows committees to collectively construct transaction lists while hiding individual contributions and ensuring plausible deniability. Our approach builds on multiparty computation (MPC) techniques to achieve strong privacy without relying on heavyweight cryptography or anonymous broadcast channels. We implement two variants of our protocol design: an optimistic version providing malicious security with abort (latency $\sim 4.0$s) for speed, and a robust variant (latency $\sim 124.7$s) for guaranteed output delivery in the presence of a Byzantine threshold of $t < n/3$ malicious parties.

P vs NP problem is the most important unresolved problem in the field of computational complexity. Its impact has penetrated into all aspects of algorithm design, especially in the field of cryptography. The security of cryptographic algorithms based on short keys depends on whether P is equal to NP. In fact, the security requirements for cryptographic keys are much stricter than those for P$\neq$NP, the security of the key must ensure not only a sufficiently high computational complexity to crack it, but also consider the security of each bit of the key, while fully avoiding the effectiveness of various attack methods. In this paper, we innovatively propose a new encoding mechanism and develop a novel block symmetric encryption algorithm, which be named Eagle, whose encryption and decryption can be completed in linear time. The key consists of 6 variables, for the attacker, in the case when only the plaintext-ciphertext correspondence is known, the problem of cracking the key is equivalent to solving a system of equations about six unknown variables. We prove that the computational complexity of verifying two variables should not be lower than the computational complexity of verifying any intermediate unknown variable whose number of possible values is exponentially to the length of the key, thus proving that the computational complexity of verifying two variables can't be polynomial. Due to the computational complexity satisfying the condition of ``complexity of cracking the key = complexity of solving six variables $\geq$ complexity of solving two variables $\geq$ complexity of verifying two variables", thus the computational complexity of cracking the key can't be polynomial, So the decryption is a one-way function, and according to ``the existence of one-way function means P$\neq$NP", thus solving the unsolved problem of P vs NP. In addition, this paper delves into the underlying mathematical laws of this new encoding mechanism, and develops a right multiplication operation to binary. Based on this right multiplication operation, we further constructed a nonlinear operation and designed another block symmetric encryption algorithm, which be named $Eagle^{*}$. The key of $Eagle^{*}$ is composed of three independent variables. Given any plaintext ciphertext correspondences, the problem of verifying any two variables in the key is equivalent to solving a system of quintic equations. Based on the conclusion that there are no algebraic solutions to quintic equations, we assert that there is no fast algorithm to verify any two variables, and thus the computational complexity of cracking the key is equal to the computational complexity of completely exhausting the three variables. In addition, we conducted an in-depth analysis that without cracking the key, it is not possible to directly decrypt new ciphertext by simply collecting a large number of ciphertext plaintext correspondences. Due to the fact that ciphertext consists of two parts, one part is a completely randomly generated random number, while the other small part is calculated using plaintext, algorithms, and random numbers, and its distribution is also completely random, thus $Eagle^{*}$ is resistant to all forms of linear and differential attacks.

Secure and anonymous messaging has many compelling use-cases and is becoming increasingly popular. In this paper, we consider it in the context of delay-and-disruption-prone networks, which are characterized by handicapped network access, disrupted operation, censorship, and intermittent network outages. With such settings in mind, we define and design a Private Identity-Based Bulletin Board (PIB^3) scheme, which allows users to anonymously post and retrieve messages to and from a distributed database, and supports communication between users without pre-established setup or pre-exchanged keys. Anyone can encrypt a message for an identity and public epoch, such that only the party with the decryption key for that identity can identify, retrieve, and decrypt the message. Against one corrupted non-colluding PIB^3 server, the server learns neither the recipient identity nor the retrieved record indices beyond the leakage explicitly modeled by the scheme: the public epoch, the database size, and the number of retrievals made by the receiver. If retrieval-count privacy is required, retrievals can be padded to a fixed bound. The multi-server construction extends this guarantee to larger server sets, and gives coalition privacy whenever the underlying multi-server PIR scheme is private against the corresponding coalition. Contributions of this work are: (1) formally defining functionality and security requirements for PIB^3-s, (2) defining and constructing a Hierarchical Identity-based Encryption (HIBE) scheme with searchable ciphertexts, which serves as a building block for the proposed PIB^3 scheme and may be of independent interest, (3) designing an efficient PIB^3 scheme that can be realized with $n\geq 2$ servers based on the HIBE scheme with searchable ciphertexts combined with additional primitives, and (4) implementing a functional PIB^3 prototype which demonstrates practicality of the entire concept and allows us to assess its performance empirically.

We study auctions where two positions are sold to unit-demand bidders with private heterogeneous order preferences: some are specialists who value only the first position, while others are generalists indifferent between the two. First, we consider a first-price rule which allocates the first and second items to the highest and second-highest bidders, respectively. We show that no strategy profile ex-post implements the efficient allocation at every type profile, irrespective of payments, and provide a distribution-free equilibrium welfare guarantee of 1/2. To augment this result, we prove that for deterministic one-round auctions and discrete bids, the efficient allocation requires each bidder to communicate at least one bit more than its bid's binary representation. We next ask what the same bit accomplishes in winner-pays-bid formats where bidders can also specify specific item preferences. In particular, we show that this strengthens our distribution-free equilibrium welfare guarantee to 1-1/e. Finally, we discuss the applicability to priority service, blockchain transaction ordering, and cloud compute and artificial intelligence (AI) marketplaces.

The post-quantum signature scheme Falcon (FN-DSA), currently being standardized by NIST as FIPS 206 (Initial Public Draft submitted August 2025, final standard expected 2026-2027), relies on a discrete Gaussian sampler whose critical bottleneck is the function fpr_expm_p63, computing $\lfloor \exp(-x) \cdot 2^{63} \rfloor$ for $x \in [0, \ln 2)$. While the reference implementation already employs a degree-12 fixed-point polynomial (FACCT), no segmented approximation has been studied for this specific function, nor has empirical timing security been published on ARM Cortex-M3 (emulated or physical). This paper presents a systematic study of piecewise polynomial approximation applied to fpr_expm_p63, combining the Remez exchange algorithm (computed with 50 decimal digits of precision via mpmath), fixed-point arithmetic, and Horner evaluation. Two configurations are implemented and evaluated: a 32-segment degree-6 approximation at scale $2^{62}$ targeting x86-64, and a 16-segment degree-3 approximation at scale $2^{31}$ (256-byte LUT) targeting ARM Cortex-M3 IoT devices without hardware floating-point unit (FPU). Against the authentic FACCT reference from Falcon's fpr.c, ported verbatim to ARM Cortex-M3 (emulated via QEMU user-mode with arm-linux-gnueabi -mfloat-abi=soft), our implementation achieves a $1.28\times$ median speedup across 30 independent runs (range $1.24\times$ to $1.33\times$), measured with a rigorous anti-noise protocol combining batch measurement, aggressive warm-up, ref/opt interleaving, and percentile filtering (P5-P95). DUDECT timing leakage tests confirm that both the FACCT reference (t-score $\in [0.05, 2.51]$) and our implementation (t-score $\in [1.99, 5.24]$) remain within statistical safety thresholds in the vast majority of runs (FACCT: 30/30; optimized: 27/30). Static instruction-level analysis via objdump disassembly provides deterministic constant-time evidence: zero data-dependent conditional branches, zero FPU instructions, and zero soft-float calls, yielding a branchless fixed-point Horner core; however, the full constant-time claim is limited to the tested compilation target and memory model. To the best of our knowledge, this constitutes the first comparative study of segmented versus global polynomial approximation for fpr_expm_p63 in the FN-DSA context, and the first empirical DUDECT measurement of this function on emulated ARM Cortex-M3 against the authentic FACCT reference. Physical hardware validation on STM32F103 is identified as future work.

Distributed monotone-policy encryption (DPE) lets each user sample and publish its own key, after which anyone can encrypt to a list of published keys under a monotone access policy that determines which coalitions can decrypt. Silent threshold encryption is the $t$-out-of-$N$ special case. What makes the primitive non-trivial is compactness, where the ciphertext stays sublinear in the policy description. Every post-quantum DPE scheme so far settles for selective security, fixing the challenge policy and the corrupted positions before setup, and complexity leveraging cannot close the gap without giving up compactness. The one DPE scheme known in the stronger static model, where the policy and the placement of malicious keys are chosen adaptively, relies on witness encryption (Devadas-Jain-Waters-Wu, Asiacrypt'25). We give the first statically secure DPE schemes from falsifiable lattice assumptions. For DNF policies, ciphertexts are of size $\mathsf{poly}(\lambda, \log N)$, independent of the number and widths of the clauses, and public keys, secret keys, and partial decryptions are of size $\mathsf{poly}(\lambda)$. For $t$-out-of-$N$ threshold policies, ciphertext of size $\tau^6 \cdot \mathsf{poly}(\lambda)$ for $\tau = \min(t^2, N - t)$, improving to $\tau^2 \cdot \mathsf{poly}(\lambda)$ given a common reference string. We prove security under decomposed LWE, and the improved threshold parameters under succinct LWE, in the random oracle model. Our constructions generalize the equivocal encryption framework of Goyal-Yadugiri to policies. We define equivocal DPE, which simulates public keys and partial decryptions and withholds the equivocation trapdoor while releasing the public coins that accompany a ciphertext, and compiles to static DPE with no loss in parameters.

Fully Homomorphic Encryption (FHE) has emerged as one of the key technologies for privacy-preserving computation, enabling arbitrary computation directly on encrypted data. Vectorized FHE schemes, such as Brakerski/Fan--Vercauteren (BFV), Brakerski--Gentry--Vaikuntanathan (BGV), and Cheon--Kim--Kim--Song (CKKS), are typically used in applications dealing with large datasets, for example, confidential database queries and private ML inference. These FHE schemes are based on the computational hardness of Ring Learning with Errors (RLWE) and share a common algebraic foundation: arithmetic over high-dimensional polynomial rings with coefficient moduli spanning hundreds or thousands of bits, far exceeding the native arithmetic capabilities of modern processors. This article surveys the evolution of large-integer arithmetic in RLWE-based FHE libraries, with a focus on the Residue Number System (RNS) techniques used in practically all modern implementations. We give a formal treatment of the two fundamental RNS building blocks --- basis extension and scaling --- that require information about the magnitude of a large value and are therefore incompatible with a purely residue-wise view of arithmetic. We contrast the two principal algorithmic approaches to these operations: the integer-only approach of Bajard, Eynard, Hasan, and Zucca (BEHZ), which tolerates approximation overflows and corrects them with auxiliary redundant moduli, and the floating-point approach of Halevi, Polyakov, and Shoup (HPS). We then show how these primitives compose into the higher-level RNS procedures used across all vectorized RLWE schemes and review how their adoption reshaped the architecture and performance of libraries such as HElib, SEAL, PALISADE/OpenFHE, HEAAN, and Lattigo. We give particular attention to the scaling error inherent in the original Full RNS variant of CKKS, and to the more recent techniques --- reduced-error scaling, composite scaling, and grafting --- that eliminate it or restore flexible, high-precision rescaling from within the residue representation. We also cover GPU-accelerated implementations and close by discussing a renewed, and so far exploratory, interest in positional (non-RNS) representations, raising the question of how such approaches might compare with the Full RNS variants that dominate FHE implementations today.

Recent advances in quantum hardware, including Google's Willow processor, have substantially narrowed the timeline to cryptographically relevant quantum computers. In the blockchain setting, where addresses and key derivation standards such as BIP32, BIP44, and SLIP-10 are the dominant infrastructure for wallet management, a quantum computer running Shor's algorithm can recover any elliptic-curve private key from the corresponding public key, threatening every wallet in production today. Migrating to post-quantum signature schemes requires changing the public key format and forcing address migration across all participating networks, a significant problem for blockchain communities. We present an orthogonal approach: keep the existing address format entirely unchanged and instead replace the classical signing step with a NIZK proof of knowledge of the seed underlying the existing address, where security against quantum adversaries reduces to the conjectured quantum hardness of the underlying hash functions and the soundness of the NIZK against quantum adversaries, requiring no address migration or key registration. We build on the observation of Baldimtsi et al. that EdDSA's deterministic seed-to-key mapping makes the seed a valid zero-knowledge witness for the public key, and extend their single-level result to the full hierarchical deterministic wallet setting. Starting from BIP32-Ed25519, we replace the classical signing step with a NIZK proof certifying knowledge of the root seed and the full derivation chain, and prove EUF-CMA security for the resulting scheme; post-quantum security is conjectured to hold since all underlying primitives depend only on the hardness of hash functions and the soundness of the NIZK against quantum adversaries. The existing schemes each derive their quantum-safe witness as an incidental artifact of a curve-specific key format, and none provides a single derivation standard that works uniformly across curves. We therefore introduce QBIP32, a new key derivation scheme based on a keyed function HASH768 (instantiated with KMAC256) that produces the signing scalar, an explicit quantum-safe witness, and the chain code in a single call. QBIP32 is defined for any elliptic curve group of prime order with a fixed generator, requiring no structural change to the derivation or proof system across curves: the same construction covers secp256k1, Ed25519, and any future curve used in blockchain infrastructure. This universality stands in contrast to the BIP32-Ed25519 approach, which relies on the Ed25519 extended key format and has no analogue for other curves. We then address the efficiency problem: a monolithic proof of the full derivation chain has cost growing linearly with derivation depth. Our main contribution is ZKPoSP (Zero-Knowledge Proof of Seed Provenance), a signature scheme conjectured secure against quantum adversaries that splits the proof into a derivation proof generated once per key pair and a signing proof generated once per message, reducing per-message proving cost to a constant independent of derivation depth. We further characterise exactly when the derivation proof itself can be shortened to cover only the last step of the derivation rather than the full chain from the root seed, and identify the existence of a private value that is bound to the seed by a one-way function and not recoverable from the public key as the precise criterion. This criterion is met by hardened keys but not by non-hardened keys, a structural distinction common to all schemes: BIP32 secp256k1, SLIP-10/Ed25519, BIP32-Ed25519, and QBIP32 all admit a last-step derivation proof for hardened keys, while non-hardened keys require a proof reaching back to the last hardened ancestor. We exploit this for BIP44 paths to prove only one hardened step plus the non-hardened suffix in a single proof, allowing the root seed to be removed from the proving device once the anchor node is generated, while remaining in secure long-term storage. Before Q-day, separating the derivation and signing proofs already reduces per-transaction cost to a constant independent of derivation depth. After Q-day, once networks reject all non-post-quantum signatures, the leaf scalar can be moved to the public statement, removing all elliptic-curve scalar multiplications from the proof circuit and reducing derivation proving time substantially. We implement all constructions in Rust using RISC Zero as the NIZK backend, instantiate HASH768 with KMAC256, and report benchmarks for monolithic proofs, ZKPoSP across full BIP44 paths, and the post-Q-day variant. Signing proving time is constant at approximately 12-13 seconds and verification time is constant at approximately 9-10 ms across all variants and depths.

Updatable vector commitments let users store and authenticate values contained within an evolving data vector. Existing work on updatable vector commitments studies how clients can store only the values and authentication proofs relevant to them, and can refresh stale opening proofs, with the help of an online maintainer that keeps the current vector and proof state. This work studies the complementary problem: how to decentralize the maintainer, in order to distribute the cost and availability requirements. We formalize this problem as extendable distributed vector commitments (EDVC). A public control plane, such as consensus or a trusted party, determines batches of updates and extensions of stored vector. Maintainers accept and apply a batch only after validating it against the current authenticated state. The resulting state is stored across many maintainer nodes, each of which holds a publicly assigned coded data fragment and updates it non-interactively. A stale client can obtain the current state, and a fresh authenticated opening, from the current maintainers (without replaying the updates history). We construct the first EDVC protocol, called Borg, from two components: a sparse vector commitment, and a coded storage layer that can be updated by linear operations. This construction applies when all active positions lie within a known growing prefix of the vector. We then construct a coded storage layer with the operations needed for this setting, including single-position openings, aligned range openings, public updates, adding new nodes, repairing failed nodes, and moving storage responsibilities between nodes. This is then used to flexibly distribute the data alongside a sparse Merkle tree for authentication. Our construction is particularly simple when the maintained data is an append-only public log (e.g., a blockchain’s block archive, or certificate transparency logs). In this setting, distributed updates to the data and its authentication structure can be made just by broadcasting the new log entries, with no coordination across maintainer nodes. We empirically evaluate maintainers’ cost for various workflows, showing that nodes can process hundreds of thousands of updates per second. We also show that node addition, repair of lost local state, and changes to the proof-serving threshold can all be supported efficiently.

A verifiable shuffle proves that output ciphertexts are a rerandomized permutation of the inputs without revealing the permutation or rerandomization factors. It is a core primitive in mix-nets for electronic voting and blockchain-based anonymization, where each mix server publishes an auditable proof. Existing deployed schemes typically have proof size $O(N)$ or $O(\sqrt{N})$ in the number of ciphertexts $N$, making shuffle proofs a major bandwidth cost. We present a logarithmic-size verifiable shuffle for ElGamal ciphertexts. The logarithmic term in our proof size is one third of that in the previously known logarithmic construction for the same shuffle relation by Hoffmann et al. (CCS 2019). Our protocol is public coin, non-interactive via the Fiat--Shamir transform, and relies on an updatable structured reference string that can be generated once in a powers-of-tau ceremony and reused across applications. We implement the protocol in Rust and provide, to our knowledge, the first benchmarks for a logarithmic-size ElGamal shuffle. At \(N=2^{20}\), the proof is 2.6 KiB. In a four-server mix-net election, the four shuffle proofs occupy approximately 10.6 KiB in total, excluding ballot-validity and decryption proofs.

We present UFOs, a multivariate public-key signature scheme in the Unbalanced Oil and Vinegar (UOV) family. The scheme replaces generic quadratic polynomials with a structured subclass based on Frobenius-type quadratic forms, yielding a compressed public-key representation while retaining the efficient UOV signing procedure. We describe the key-generation, signing, and verification algorithms, and we detail the derivation of the public system from a compact secret description. We discuss security in the standard multivariate setting, including direct algebraic attacks and key-recovery approaches, and we formalize the underlying computational problems induced by the proposed structure. Finally, we report implementation results quantifying the costs of key generation, signing, and verification, as well as the resulting public-key and signature sizes.

Field trace evaluation has emerged as a powerful tool in fully homomorphic encryption, with broad applications ranging from bootstrapping algorithms to privacy-preserving protocols. Recent advances have significantly reduced its noise growth by combining tower-based evaluation strategies with rescaling operations. However, existing analyses rely on uniform noise bounds that fail to capture the actual noise behavior across different coefficients, leading to substantial gaps between theoretical estimates and empirical observations. In this work, we present a refined algebraic analysis of trace evaluation over power-of-two cyclotomics that uncovers structured cancellation effects among noise coefficients induced by subsequent linear operators, in particular the trace mappings of subextensions. We show that, except for the constant term, the variance of each output noise coefficient depends on the 2-adic valuation of its index, yielding bounds that improve upon prior uniform estimates by a factor of $O(\log n)$ both for non-constant coefficients and after a subsequent plaintext-ciphertext multiplication, where $n$ is the ring degree. We further extend our analysis to two typical algorithmic applications of trace evaluation. For ciphertext packing, we derive a non-recursive formulation that admits a cleaner structure and slightly tighter noise estimates. For coefficient extraction, our coefficient-wise analysis improves upon prior uniform variance bounds by factors ranging from $\Theta(n)$ to $\Theta(n^2)$ for non-constant coefficients and by a factor of $O(n)$ after post-multiplication. Experimental results confirm that the observed noise variances follow the coefficient-wise pattern predicted by our analysis and demonstrate pronounced improvements over existing estimates, providing effective guidance for parameter selection and system configuration in practice.

Designated Verifier Signatures (DVS) are an important variant of digital signatures that ensure only a specified verifier can validate a signature, while preserving non-transferability. With the advent of quantum computing, several quantum DVS schemes have been proposed to achieve quantum security. In this paper, we revisit the quantum DVS protocol of Xin et al. [Quantum Information Processing, 2022] and provide a structural cryptanalysis of its design. We show that the scheme admits an existential forgery under a chosen-message attack: given a valid quantum signature on one message, an adversary can efficiently transform it into a valid signature on another message without knowledge of the signer’s private key. To address this weakness, we propose a minimal countermeasure based on QKD-derived keys and quantum one-time pad encryption.

The VOX signature scheme is a multivariate signature scheme which was submitted to the Round 1 Additional Digital Signature Schemes NIST process. VOX relies on the Hat Plus perturbation and the Quotient-Ring transform (QR). We formalize a dimension criterion enabling the direct attack to be used as a key recovery attack against UOV schemes. This enables a practical cryptanalysis of the Round 1 VOX parameters. Next, we show that some of the alternative parameters proposed for VOX after attacks on the Round 1 submission are still vulnerable. More precisely, these parameters were chosen to defeat an attack of Furue and Ikematsu in the field extension defined by the QR parameter. We observe that one may use a smaller field extension of any degree dividing the QR parameter, in which case the attacks apply again. These attacks are relevant for a subset of the parameter sets proposed for VOX: I, Ic, III, IIIa, V, Vb. In particular, we apply the subfield framework to our previous dimension criterion for the direct attack. We estimate the cost of our attack on these parameter sets and find costs of at most 2^67 gates, and significantly lower in most cases. In practice on a commercial laptop, our attack requires 0.3s, 1.35s, 0.56s for parameter sets I, III, V for VOX, and 56.7s, 6.11s for the alternative parameter sets IIIa, Vb. Our analysis also improves the cryptanalysis of some alternative parameters proposed by Guo and Ding, and of the ``Minus'' variant of VOX.

Universal hash functions (UHFs) are basic building blocks in cryptography, making the topic of designing secure, fast UHFs of longstanding interest. This paper presents an exploration of the design space for multivariate UHFs, that is UHFs that involve the evaluation of a multivariate polynomial over a finite field. We focus on two-level designs, wherein a lower-level hash function produces intermediate values that are consumed by a higher-level one, and where both hash functions are based on either univariate or multivariate polynomials. This approach allows designs to benefit from the desirable features of both components and thereby strike new trade-offs between key size, security level, and amenability to optimization techniques. We extend the recent UHF code generation and benchmarking framework of Degabriele et al. (IEEE S&P 2024) to accommodate our multivariate designs (and also to support binary field arithmetic). We then use the framework to study the performance of a large collection of new two-level designs. This is done by first conducting a statistical factor analysis to determine which design features (and combinations of those features) most influence performance, and then using it to identify particular combinations of lower-level and higher-level hash functions offering particularly good performance/security trade-offs. We present new designs for both binary and prime fields, at two different security levels (corresponding to roughly 128 and 256 bits of security). Our best designs have performance that significantly outperforms state-of-the-art UHFs in the research literature and as deployed in mainstream cryptography libraries by up to 25%, resulting in 0.3 cycles/byte for 128-bit binary fields. We expect further gains from optimizations such as vectorization, as our benchmarks rely purely on auto-generated code from the extended framework, while state-of-the-art implementations typically use hand-optimized implementation strategies. We conclude with a brief inquiry into the performance implications of employing our best UHF design in the AEAD and Accordion mode designs currently under consideration for standardization by NIST.

Federated Learning (FL) is an advancement in Machine Learning motivated by the need to preserve the privacy of the data used to train models. While it effectively addresses this issue, the multi-participant paradigm on which it is based introduces several challenges. Among these are the risks that participating entities may behave dishonestly and fail to perform their tasks correctly. This misbehavior, in turn, also threatens privacy, because an undetected deviation in training or aggregation can silently undermine the confidentiality guarantees that FL was designed to provide. This motivates mechanisms that provide checkable evidence that released checkpoints are consistent with a declared learning specification and an auditable execution trace. In this SoK, we model federated learning as an append-only transcript of submissions, admissions, aggregation, and finalization events, and formalize verifiability as a collection of integrity claims issued by clients and the aggregator, and checked by different verifier classes. We derive a taxonomy of recurring client-side and aggregator-side claims and use it to analyze representative verifiable FL (VFL) systems spanning Zero-Knowledge Proofs (ZKP) and Trusted Execution Environment (TEE) technologies. Our analysis suggests that, while verifiable aggregation is comparatively mature, data verifiability appears feasible but still sparsely adopted in practice, and verifiable training remain costly and rarely scale to modern models.

In 2021, Masson, Sanso, and Zhang introduced the Bandersnatch curve associated to the BLS12-381 pairing-friendly curve, an elliptic curve designed for zero-knowledge proofs requiring circuits with a curve arithmetic. This type of curve is useful for privacy-preserving protocols, and more generally for succinct validity proof using pairing-based SNARKs. An embedded curve is defined over a field whose order is the group order of its associated curve. In this way, the pairing-friendly curve is used to express a zero-knowledge proof (such as a SNARK) of a statement taking place on the embedded curve. Contrary to the previous embedded curves (such as CØCØ, JubJub), Bandersnatch was built with the complex multiplication (CM) method, in order to ensure a very small discriminant (-8, whose magnitude is small), and thus efficient scalar multiplication thanks to the GLV technique. The algorithm provided by Masson, Sanso, and Zhang for searching this type of curves requires computation of Hilbert class polynomials, making the search of curve slow. It was not known whether Bandersnatch was an exceptional curve or whether comparable curves exist, of larger discriminants. This paper highlights the technicalities of the CM method already in use in the 90s to generate curve parameters of chosen order. This old technique allows revisiting the curve search of Bandersnatch, providing a dramatic speed-up improvement. This paper presents two algorithms: one to generate embedded elliptic curves of SNARK-friendly elliptic curves, with a variable discriminant; a second to generate families (parameterized by polynomials) with a fixed discriminant. When the (negative) discriminant is -3 modulo 4, it is possible to obtain a prime-order curve, and form a cycle. To illustrate this, we apply the technique first to generate more embedded curves like Bandersnatch with BLS12-381, such as a curve of discriminant -6673027, defining a plain twist-secure cycle. We also comment on the scarcity of Bandersnatch-like CM curves, and recall that with this generic algorithm, it is only a question of core-hours to find them. Second, we show the link between a paper of Ben Smith in 2015 and the work of Dai, Lin, Zhao, and Zhou in 2023, obtaining prime-order parameterized families of embedded curves of fixed discriminant, such as -3 for BLS and KSS18 curves. With KSS16 curves, the discriminant -4 is also possible (the curve has an even order). The technique can work with any KSS, Scott--Guillevic, Gasnier--Guillevic, or other fixed-discriminant parameterized family of pairing-friendly curves. This paper provides a more general point of view on embedded curves such as Bandersnatch, putting into perspective the works of Masson, Sanso, and Zhang, and Sanso and El Housni. The Python/SageMath scripts are available at https://gitlab.inria.fr/zk-curves/cm-embedded-curves/.

At CRYPTO 2019, A. Gohr introduced Neural Differential Cryptanalysis and used deep learning to improve the state of the art in cryptanalysis of 11-round SPECK32. As of February 2025, Gohr’s article has been cited 238 times on Google Scholar. The variety of targeted cryptographic primitives, techniques, settings, and evaluation methodologies that appear in these follow-up works provides a basis for a careful survey, which we provide in this paper. More specifically, we propose a taxonomy of these 238 publications and systematically review the 71 papers focusing on neural differential distinguishers, pointing out promising directions and recent advances in explainability and key-recovery attacks. We then highlight future challenges in the field, particularly the need for improved comparability of neural distinguishers and advancements in scaling. This holistic survey helps researchers and engineers to identify the leading neural differential attacks, compare their performance, and highlight the outstanding open problems in AI-assisted cryptanalysis.

We present the first passive side-channel distinguisher on LESSv2.0, a second-round candidate in NIST’s call for additional post-quantum digital signature schemes. We target the Gaussian elimination at the core of LESS and and present a method to exploit algorithmic leakage arising from the manipulation of sparse versus dense columns. We show that this leakage, while trivially available in non-constant-time implementations, also persists in constant-time implementations and can be exploited using a distinguisher. Concretely, the proposed attack relies only on distinguishing zero-valued computations from random ones that are repeatedly evaluated during the computation, leading to a large attack surface and making the attack robust to noise. Through simulation, we experimentally show that the required number of observed signatures lies between 300 and 2357 depending on the parameter set. This relatively large number is due to the targeted information being inherently noisy, leading to a correlation-based key recovery attack, even with noiseless leakage. Furthermore, we discuss three common countermeasures: first-order masking, shuffling and blinding. Finally, we validate our approach on implementations with and without masking by showing the presence of leakage on a physical target.

Private histogram computation is a fundamental building block for many data analytics tasks, enabling frequency analysis without revealing individual inputs. Existing protocols achieving robustness against malicious clients and servers typically require three servers with limited adversarial tolerance, restricting practicality. In this work, we present Paras, the first two-server protocol for private histogram computation that achieves robustness against collusion between a malicious server and arbitrarily many malicious clients. Paras builds upon distributed point function-based approaches and introduces novel consistency checks leveraging vector oblivious linear evaluation (VOLE) to enforce both input correctness and output integrity. To realize these checks, we design two new cryptographic primitives: (1) aBV, an authenticated bit verification protocol that ensures VOLE committed shares correspond to valid bits, and (2) adIPA, an authenticated double inner product argument that enables secure consistency checks across two different VOLE sessions. These primitives may be of independent interest for other secure computation tasks. We show that Paras is highly efficient and scalable: clients incur minimal cost independent of domain size, while servers achieve low per-client runtime, communication, and storage even at scale. For example, with 8192 clients over a domain of 128 inputs, each server requires only 14 ms runtime and 24 KB communication per client.

Aggarwal, Dadush, Regev, and Stephens-Davidowitz (ADRS; STOC 2015) sample $2^{n/2}$ discrete Gaussians at an arbitrary parameter in $2^{n+o(n)}$ time, and above smoothing in $2^{n/2+o(n)}$ time. They ask whether the latter bound suffices for one sample at an arbitrary parameter. We answer this question affirmatively: for every rank-$n$ lattice $L\subseteq\R^n$ specified by a rational basis and every rational $s^2>0$, we produce one sample from $D_{L,s}$ within statistical distance $\exp(-\Omega(n^3))$ in expected $2^{n/2+o(n)}$ time and $2^{n/2+o(n)}$ space on every execution. The algorithm samples from random superlattices that are smooth at the required scale with constant probability and outputs the first point in $L$; a Gaussian-mass comparison shows that the $2^{n/2}$ samples produced by one ADRS call contain a point of $L$ with inverse-polynomial probability. The factor $2^{n/2}$ is tight in this Gaussian-mass comparison. For every fixed rational $\alpha<1.4697$, the same comparison gives a sub-$2^n$ algorithm for exact CVP on targets satisfying $\dist(y,L)\le\alpha\lambda_1(L)$, without a uniqueness assumption, and an exact-SVP algorithm in $2^{0.7315n+o(n)}$ time.

Video provenance is an important problem on the modern internet. In response, the Coalition for Content Provenance and Authenticity (C2PA) has developed a standard for verifying video and image provenance where cameras sign captured videos with an on-device secret key. Since videos are generally edited and resized before be- ing posted, the C2PA signature from a camera cannot be used as is to verify provenance of published videos. Prior work has developed zero-knowledge techniques for verifying provenance of edited im- ages and videos. In this work, we develop new efficient techniques for producing such zero-knowledge proofs. First, we show how to represent common video edits as matrix multiplications in a form that is particularly friendly for zero-knowledge provers and enables a number of optimizations. Second, we develop a SNARK-friendly video representation, which we call sfvr, that reduces prover work for video editing. Third, we design new efficient methods for incor- porating signed data into a SNARK proof. To evaluate our designs, we built an end-to-end system for proving edits to a signed video. In our end-to-end system, we optimize the NeutronNova folding scheme for high-arity folding. To scale the size of our Neutron- Nova proofs, we implement a “Read-Write Streaming” version of NeutronNova to take advantage of high-performance storage and parallel computing resources. Our system achieves competitive performance and scale relative to prior work.

We present randomized algorithms for the shortest vector problem (SVP). For the $n$-dimensional lattice $\mathcal L$, our algorithms solve SVP in time $2^{0.6039n+o(n)}$ classically and $2^{0.5411n+o(n)}$ quantumly and space $2^{0.5n+o(n)}$, improving the previous best algorithm running in $2^{n+o(n)}$ time and space of Aggarwal, Dadush, Regev, and Stephens-Davidowitz [STOC'15]. Our algorithms heavily use the property of the Hessian of the periodic Gaussian function at the half shortest vector: For a shortest vector $v \in \mathcal L$, the Hessian at $v/2$ has the eigenvector close to $v$, which can be used to recover $v$ using the (preprocessing) bounded distance decoding algorithm. Given the periodicity modulo $\mathcal L$, the candidate midpoints are indexed by the parity classes in $\mathcal L/2\mathcal L$. Our algorithm searches for the class of a shortest vector by estimating the corresponding Hessians using discrete Gaussian samples. We optimize the algorithm using random sublattice cosets and various sampling technique, achieving the final complexity. The optimization techniques may be of independent interest.

Payment Channel Hub (PCH) improves blockchain scalability by enabling off-chain transactions via an untrusted intermediary known as the tumbler. However, existing PCHs either fail to guarantee the unlinkability privacy or rely on inefficient non-interactive zero-knowledge (NIZK) proofs. Recently, Ge et al. proposed Accio, a privacy-preserving PCH that eliminates the need for NIZK proofs. Nevertheless, Accio only supports unidirectional channels which results in high on-chain costs and routing inefficiencies. In this paper, we present Baker, the first bidirectional payment channel hub that operates without NIZK proofs and guarantees unlinkability. Unlike prior PCH solutions that maintain channel balance using a single state, Baker introduces a novel design in which each non-tumbler user maintains two separate pockets to record the channel balance. To ensure payment atomicity, Baker further designs a novel cryptographic primitive named Aggregatable Adaptor Signature (AAS) to enable atomic signature exchanges and signature aggregation. We implement Baker and empirically demonstrate its advantages over state-of-the-art protocols. Compared to BlindHub, which relies on NIZK proofs for privacy, Baker reduces off-chain communication overhead to 0.0036%. Moreover, the off-chain computation overhead of Baker is 7% of that of BlindHub and 40% of TBPChannel. Relative to Accio, Baker incurs only 80% of its on-chain cost and enjoys a 25% higher average transaction success rate.

Witness encryption (WE) allows one party to encrypt a message under an arbitrary satisfiable circuit, so that anyone holding a satisfying input can decrypt. Efficient WE enables numerous modern applications, such as identity-based and attribute-based encryption. Recent candidates for efficient WE base their security on rank properties of structured ciphertext matrices, which encode the validity of a given witness. This shrinks ciphertext sizes considerably compared to previous constructions, but rests on heuristic arguments rather than security reductions. We describe two attacks against two such constructions, namely the affine determinant program (ADP) construction from 2020 and its arithmetic extension, the AADP, from 2026. The first attack observes that for sparse circuits, the natural regime for both schemes, commutators formed from the public ciphertext matrices have unexpectedly low rank. Elementary linear algebra on these matrices then recovers the encrypted message directly from the public ciphertext, without knowledge of any witness, and hence breaks the security of both schemes. The second attack linearizes the nearly-skew-symmetric (NSS) variant of the ADP construction, recovering the encryption randomness and the message. To our knowledge, ours are the first attacks against these WE candidates, and we verify both in practice.

HAWK is a lattice signature scheme that is currently a third-round candidate in NIST's post-quantum signature competition. We give an unconditional, deterministic polynomial-time reduction from HAWK-$n$ key recovery over $K_n=\mathbb{Q}(\zeta_{2^\ell})$ to $\mathrm{poly}(n)$ calls to an exact Shortest Vector Problem (SVP) oracle in dimension $n/2+1$, where $n=2^{\ell-1}$ is the ring degree. The reduction uses a nontrivial automorphism of the key lattice, supplied by the Galois involution $\tau:\zeta\mapsto-\zeta$ and recoverable as a shortest vector of a public rank-$n$ lattice isometric, up to scaling, to $\mathbb{Z}^{n/2+1}\oplus\sqrt{2}\,\mathbb{Z}^{n/2-1}$. Ducas's block reduction on this near-hypercubic class finds the automorphism, and the descent of van Gent and Pulles recovers the key from it. In the gate-count model, the attack lowers the key-recovery cost of HAWK-512 from $2^{150}$ to $2^{108}$ and of HAWK-1024 from $2^{288}$ to $2^{182}$. We demonstrate this with a practical implementation that recovers a HAWK-256 secret key end-to-end in a few hours on a single server. The construction does not transfer to Falcon. Conductors $m\in\{p^k,2p^k\}$ ($p$ an odd prime), i.e.\ the $m>4$ with cyclic $(\mathbb{Z}/m)^\times$, evade the attack.

General-purpose secure multiparty computation (MPC) remains bottlenecked in large part by a lack of efficient techniques for handling memory access. We demonstrate a remarkably simple and efficient 2PC instantiation of random access memory (RAM), based on distributed point functions (DPFs, Gilboa and Ishai, Eurocrypt'14). Our semi-honest 2PC protocol can be achieved from oblivious transfer (OT) and a black-box pseudorandom generator (PRG). For a memory storing large enough data words, our 2PC RAM incurs constant communication overhead per access. Like prior works using DPFs to achieve memory access, our work incurs linear computation per access, but per-access communication is lean. Our 2PC RAM is built on top of an obliviousness-friendly model of computation called the single access machine model (SAM, Appan et al., CCS'24). In the SAM model, each memory slot can be read at most once. We present a simple 2PC SAM protocol, where each single-access memory operation incurs at most $O(w + \lambda \lg n)$ bits of communication, where $w$ is the word size, $n$ is the number of memory words, and $\lambda$ is a security parameter. Of this cost, only $2w + 2\lg n$ bits are incurred in the online phase. There are now many oblivious algorithms that compile directly to SAM more efficiently than via a compilation to RAM, and our 2PC SAM can instantiate these algorithms. As one example, we can use our 2PC SAM to implement privacy-preserving graph traversal (DFS or BFS) over a secret-shared size-$n$ graph while revealing nothing beyond the runtime of the SAM program. Our construction achieves online communication $O(n \lg n)$ bits, asymptotically matching the number of bits touched in a corresponding cleartext graph traversal.

Coin flipping in the presence of a dishonest majority is a fundamental cryptographic primitive whose requirements lack a clean characterization. Recent work (Bonneau et al., Eurocrypt 2025) showed a lower bound that fair dishonest-majority coin-flipping implies delay functions. However, until now known upper bounds exhibited a significant gap: All existing protocols rely on assumptions that we do not know how to instantiate in the plain model. In this work, we close this gap. Specifically, we show that fair $n$-party coin flipping in the presence of up to $n-1$ malicious corruptions follows from the minimal assumption of delay functions. This completes the equivalence between delay functions and fair dishonest-majority coin-flipping protocols.

A basic property of lattice-based homomorphic encryption schemes is that ciphertexts carry an inherent noise that accumulates as computation advances. The key-switching procedure of these schemes allows the homomorphic re-encryption of a ciphertext under a new secret key, but it is a major source of noise growth. Several strategies have been proposed to reduce the amount of noise introduced by key-switching in the CKKS scheme. In this work, we generalize the RNS-based decomposition technique to an arbitrary number of input polynomials and secret keys. Performing multiple relinearizations and rotations in batch enables one to hoist the modulus lowering and decomposition steps of key-switching, respectively, which restricts noise growth and avoids redundant computation. We prove the security and correctness of all the proposed algorithms, and derive explicit noise bounds for them. Practical examples illustrate the impact of these optimizations on applications like private deep neural network inference. In addition, we provide—to the best of our knowledge—the first noise analysis of the double-hoisted BSGS matrix-vector multiplication algorithm of Bossuat et al. 2021, which is a building block of state-of-the-art CKKS bootstrapping circuits. Our analysis additionally reveals an optimization concerning the automorphism applications during its giant steps.

In October 2024, the National Institute of Standards and Technology announced the second round candidates of its standardization effort for additional post-quantum signatures. One of these candidates is CROSS, a code-based scheme relying on the restricted syndrome decoding problem. In this work, we present the first hardware design of CROSS, delineating efficient implementation strategies for the critical components of the cryptographic scheme. Our architecture parallelizes rejection sampling in two dimensions, enabling to simultaneously generate multiple vectors, as well as multiple entries of these vectors. We implement hardware friendly modular reduction circuits requiring only shifts and additions to obtain a DSP-free design, and carefully schedule operations enabling to hide them behind more computationally intensive tasks. Depending on the chosen security level, our design generates a key pair in 8 to 148 µs, signs a message in 338 µs to 4.62 ms, and verifies a signature in 303 µs to 3.27 ms on a Xilinx Artix-7 device. We show that our design is among the fastest and smallest when compared with other on-ramp candidates, namely LESS, MEDS, MAYO, Raccoon and SDitH, and comparable to current standard-selected ML-DSA, FN-DSA, and SLH-DSA in terms of efficiency.

A party may participate in multiple threshold cryptosystems. For example, it may serve on multiple overlapping threshold committees in a proof-of-stake blockchain or a distributed oracle network, or act as a client of multiple cryptocurrency wallet services built on threshold cryptography. With conventional distributed key generation (DKG), each threshold system independently generates its key shares, imposing significant key-management overhead on such a repeating party. In contrast, modern key-management practice favors deriving all cryptographic material deterministically from a single master key, raising a fundamental question: Can DKG be reconciled with key derivation while preserving security and compatibility with legacy threshold systems? We present Anchor-DKG, a new DKG protocol that allows up to $t^{\mathsf{rec}}$ (the reconstruction threshold) parties to deterministically fix their secret key shares while retaining standard security guarantees. Anchor-DKG supports concurrent executions with overlapping participants across multiple DKG instances and remains fully compatible with legacy threshold schemes, including ECDSA, BLS, Schnorr, and ElGamal. At the core of Anchor DKG lies a new technique: fixed-point distributed polynomial sampling (FpDpS). FpDpS allows parties to jointly sample a random $(t^{\mathsf{rec}}-1)$-degree polynomial $f$ such that $f(i) = s_i$ at designated points $i$, where each $s_i$ can be a private input, e.g., a key derived from a master secret. The final secret key remains $f(0)$, ensuring compatibility with existing discrete-log-based threshold systems. We provide an efficient construction of Anchor DKG under standard cryptographic assumptions, which, compared to classical constructions such as Gennaro et al. (J.Cryptol. 2007), only incurs one more point-to-point round and marginal computation. Experimental results show that, for a network size of $n=128$, our protocol incurs a per-party computation cost of $1.59$ s, compared to $1.36$ s for GJKR.

We revisit the post-quantum security of Password-Authenticated Key Ex- change (PAKE) from Key Encapsulation Mechanisms (KEM), focusing on (O)CAKE. Despite extensive study, these protocols still lack a security proof against quantum adversaries. We pinpoint exactly why by identifying the precise remaining obstacle. Most game-hopping arguments extend to the quantum setting via standard QROM techniques. The difficulty lies with ideal ciphers: adaptive programming and query recording are well understood classically, but no analogous tools exist for ideal ciphers in quantum superposition. To isolate the issue, we formalize programming for PAKE via a programming simulator, which captures adaptive programming on a family of permutations from an arbitrary distribution. We prove this notion is both necessary and sufficient for a proof. For necessity, we present a meta-reduction showing that any reduction-based proof for (O)CAKE must use programming in exactly this sense. We exhibit a class of KEMs – including practical schemes such as Kyber/ML-KEM – for which any successful reduction must either program or directly break the KEM challenge. The existence of this class implies that no fully generic KEM-based PAKE proof can avoid programming. For sufficiency, we show that this is the only remaining barrier: assuming the existence of our simulator and using known QROM tools, we give a complete post-quantum security proof for OCAKE. Together, our results explain why generic KEM-based PAKEs have so far resisted quantum security proofs and pinpoint the open problem whose resolution would complete the proof.

We investigate a multi-prime multi-power generalization of the RSA cryptosystem for arbitrary moduli $n>1$, which under reasonable cryptographic assumptions works correctly for almost all messages $m<n$. Based on a new sharpening of Carmichael's theorem, tailored to regular integers modulo $n$, we prove that this generalization is correct precisely for messages represented by regular integers modulo $n$, thereby generalizing the original RSA correctness theorem. As in the original RSA scheme, decryption can be accelerated by Chinese remaindering, yielding a corresponding generalization of CRT-RSA.

Pseudorandom error-correcting codes (PRCs), a novel cryptographic primitive recently proposed at CRYPTO 2024, are primarily applied in undetectable watermarking schemes for large generative models. However, the security of PRCs has not yet been systematically analyzed. To fill this gap, we present the first cryptanalysis of PRCs. Specifically, focusing on LDPC-PRC, the only known practical instantiation of PRCs, we propose three novel attacks that challenge its undetectability and robustness. To rigorously demonstrate the practical threat, we analyze the concrete attack complexity under realistic parameters and validate the attack effectiveness on both real-world large language models and generative image models, including DeepSeek and Stable Diffusion. Our analysis shows that the claimed security guarantees of LDPC-PRC are undermined across all practically feasible regimes. For example, our attacks can detect the presence of a watermark with overwhelming probability at a cost of $2^{22}$ operations. Beyond attacks, we further propose three defenses: parameter recommendation, implementation suggestion, and a revised key generation function. However, PRC-based watermarking schemes still fail to achieve 128-bit security due to inherent constraints of large generative models, such as the maximum output length of large language models. Overall, our work clarifies the concrete security limits of PRCs in real-world watermarking applications.

Boolean polynomial multiplication is the primary computational bottleneck of the Hamming Quasi-Cyclic (HQC) key encapsulation mechanism. In this paper, we reframe the Frobenius Additive FFT (FAFFT) in ring-theoretic terms, via quotient-ring homomorphisms and the Chinese Remainder Theorem. This perspective shows that a complete decomposition into evaluation points is unnecessary for multiplication, and naturally yields the Strided FAFFT (SFAFFT), which operates over smaller finite fields with fewer butterfly stages and admits a much sparser CRT modulus for the non-power-of-two degrees in HQC. Our SFAFFT implementations outperform all previous FAFFT-based multiplications on every tested platform (x86 AVX2, GFNI, Apple M1, ARM Cortex-A72, and Cortex-M4), and set new overall speed records for HQC in nearly all settings except plain AVX2, where Toom-Cook-Karatsuba remains faster for the two smaller parameter sets.

Let $E=\mathbb Q(\zeta_m)$ be a power-of-two cyclotomic field, with maximal totally real subfield $K=\mathbb Q(\zeta_m+\zeta_m^{-1})$. In previous work, Chevignard et al. (Eurocrypt'25) gave a reduction from module-LIP for rank-two module lattices over $\mathcal O_E$ to the norm-reduced Principal Ideal Problem (nrdPIP) in a quaternion algebra. We derive two consequences of this reduction. First, we obtain a polynomial time reduction from rank-$2$ module-LIP over $\mathcal O_E$ to rank-$3$ module-LIP over $\mathcal O_K$. Note that rank-$2$ modules over $\mathcal O_E$ are naturally seen as rank-$4$ modules over $\mathcal O_K$, so this is indeed an improvement. Our second result is specific to the module $\mathcal O_E^2$, underlying the Hawk signature scheme. In this setting, we also obtain a reduction to a rank-$3$ module-LIP instance over $\mathcal O_K$, but we can additionally show that these modules have a simple geometric shape: they are isomorphic to $\mathbb Z^{m/2+1} \perp \sqrt{2}\, \mathbb Z^{m/4-1}$. We then adapt Ducas' result (ePrint'23) to this setting. Putting everything together we obtain an algorithm breaking Hawk's key recovery by making polynomially many exact-SVP calls in lattices of dimension at most $3m/8+1$. This improves upon the previous analysis from Ducas (ePrint'23) which required exact-SVP calls in lattices of dimension at most $m/2+1$.

We study pseudorandomness arising from quartic Dirichlet characters and obtain results that connect analytic and cryptographic perspectives. From an analytic perspective, and following the framework of Mauduit and Sárközy, we define a Boolean function $\psi_\pi$ from the quartic character $\chi_\pi$ modulo a Gaussian prime $\pi$ and analyze sequence $E_{p-1}=(\psi_\pi(1),\ldots,\psi_\pi(p-1))$ for $p=\pi\bar\pi \equiv 1 \bmod{4}$. Using classical character-sum bounds (Pólya-Vinogradov and refinements of Mauduit-Sárközy and Oon), we show that $E_{p-1}$ satisfies $W(E_{p-1}) =O(\sqrt{p}\log p)$ and $C_{\mu}(E_{p-1}) \leq 2^{\frac{\mu}{2}+1} \mu \sqrt{p}\log p,$ which imply strong pseudorandomness for small $\mu$. From the cryptographic side, we resolve an open question posed by Damgård by proving that quartic characters yield the secure pseudorandom generators and weak pseudorandom functions (wPRFs). Adapting similar techniques of Corrigan-Gibbs and Wu, we have shown that distinguishing quartic wPRF implies solving quadratic residuosity, via a chain of polynomial-time reductions. Our results show that under the Quadratic Residuosity Assumption, the quartic character also yields cryptographically secure wPRFs whose one-wayness was assumed in the construction of $\mathsf{Quartapus}$ signature scheme by Brier et al. and the post-quantum secure signature scheme $\mathsf{PorcRoast}_{4}$ by Beullens et al. that are more efficient and secure than legacy schemes based on the Legendre character.

Lattice-based succinct arguments allow to prove bounded-norm satisfiability of relations, such as $f(\vec{s}) = \vec{t} \bmod q$ and $\|\vec{s}\|\leq \beta$, over specific cyclotomic rings $\mathcal{O}_\mathcal{K}$, with proof size polylogarithmic in the witness size. However, state-of-the-art protocols require either 1) a super-polynomial size modulus $q$ due to a soundness gap in the security argument, or 2) a verifier which runs in time linear in the witness size. Furthermore, construction techniques often rely on specific choices of $\mathcal{K}$ which are not mutually compatible. In this work, we exhibit a diverse toolkit for constructing efficient lattice-based succinct arguments: (i) We identify new subtractive sets for general cyclotomic fields $\mathcal{K}$ and their maximal real subfields $\mathcal{K}^+$, which are useful as challenge sets, e.g. in arguments for exact norm bounds. (ii) We construct modular, verifier-succinct reductions of knowledge for the bounded-norm satisfiability of structured-linear/inner-product relations, without any soundness gap, under the vanishing SIS assumption, over any $\mathcal{K}$ which admits polynomial-size subtractive sets. (iii) We propose a framework to use twisted trace maps, i.e. maps of the form $\tau(z) = \frac{1}{N} \cdot \mathsf{Trace}_{\mathcal{K}/\mathbb{Q}}( \alpha \cdot z )$, to embed $\mathbb{Z}$-inner-products as $\mathcal{R}$-inner-products for some structured subrings $\mathcal{R} \subseteq \mathcal{O}_\mathcal{K}$ whenever the conductor has a square-free odd part. (iv) We present a simple extension of our reductions of knowledge for proving the consistency between the coefficient embedding and the Chinese Remainder Transform (CRT) encoding of $\vec{s}$ over any cyclotomic field $\mathcal{K}$ with a smooth conductor, based on a succinct decomposition of the CRT map into automorphisms, and a new, simple succinct argument for proving automorphism relations. Combining all techniques, we obtain, for example, verifier-succinct arguments for proving that $\vec{s}$ satisfying $f(\vec{s}) = \vec{t} \bmod q$ has binary coefficients, without soundness gap and with polynomial-size modulus $q$.

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. The most efficient variant of our signature schemes features a signing which is $1.4\times$ to $1.6\times$ faster than the most recent implementaion of SQIsign, whereas verification ranges from $1.2\times$ slower to $1.01\times$ faster depending on the security level. The sizes of public key and signature are comparable to existing schemes.

Identity-based key encapsulation remains attractive for managed systems, but practical post-quantum instantiations must balance compact ciphertexts, low decryption-failure rate (DFR), high-throughput and protection-friendly private-key extraction, and meaningful concrete security reductions. Existing NTRU-based IBE schemes satisfy these requirements only partially: compact DLP-style constructions lack a satisfactory reduction and have high failure rates, while LATTE's higher-rank structure and correctness treatment come with larger private keys, larger ciphertexts, and additional encapsulation/decapsulation work. These lines also use moduli and transform roots distinct from those of standardized PQC schemes, complicating deployment in implementations already built around standardized arithmetic. We introduce `ANSA-IBKEM`, a practical single-level identity-based KEM that retains the compact DLP-style identity relation while redesigning the trapdoor, extraction, correctness, and implementation layers around standardized post-quantum arithmetic. The construction combines annular NTRU trapdoors, Hybrid-Sampling extraction, a BCH-based message layer, and ciphertext compression over the ML-DSA modulus $q=8380417$. At the selected compressed points $(d_u,d_v)=(21,4)$ and $(23,5)$, the resulting ciphertext sizes are $3200\,\mathrm{B}$ and $7168\,\mathrm{B}$, with BCH-tail DFR estimates below $2^{-164}$ and $2^{-248}$ after applying one-sided $95\%$ upper bounds to the measured nonzero-error rates. We present a layered random-oracle-model security reduction for `ANSA-IBKEM` with an explicit concrete advantage bound and separate accounting for birthday-style collision terms. The proof accounts for the transform layer with explicit HHK-style losses in the identity-based setting, passes from exact extraction to ideal conditional extraction using Rényi divergence, and reduces to a programmed single-user encryption experiment connected to annular-NTRU/RLWE-style assumptions. This route separates transform losses, extraction-distribution losses, correctness terms, message-space terms, collision terms, and lattice-assumption terms, and it gives a proof template for DLP-style lattice IBKEMs. We also give a method for deep arithmetic reuse, with full low-level ML-DSA arithmetic reuse on the $N=1024$ line.

Constructing a multivariate signature scheme that is both trapdoor-free and provably secure in the standard model has been a long-standing challenge. In this paper, we present MQ-based W-OTS$^+$, the first multivariate one-time signature scheme to achieve these properties, and prove its \emph{existential unforgeability under chosen-message attack} via reductions to the \emph{MQ one-wayness (MQOW) assumption}. Our analysis focuses on the three properties that the MQ function family must satisfy within the W-OTS$^+$ framework: \emph{one-wayness} (OW), \emph{second-preimage resistance} (SPR), and \emph{undetectability} (UD). For SPR, we give a tight reduction from SPR to its OW. For UD, we provide a tighter reduction from UD to its OW, reducing the security loss from the previous bound of $O(\epsilon^{-4})$ to $O(\epsilon^{-2})$ over arbitrary finite fields. MQ-based W-OTS$^+$ consolidates the three assumptions required by W-OTS$^+$ (OW, SPR, and UD) into one standard multivariate assumption (MQOW). This shows that we can leverage some desirable properties of the MQ function family to construct a multivariate one-time signature in the standard model, instead of relying on trapdoors or zero-knowledge proofs.

Large language model (LLM) is increasingly deployed as a remote service, where users rely on third-party servers to perform computation. However, such settings introduce critical integrity concerns, as an untrusted server may deviate from the prescribed computation, skip expensive operations, or return incorrect results, while users lack practical approaches to verify execution correctness. Ensuring the correctness of LLM inference under untrusted execution remains a fundamental challenge. Zero-knowledge proofs (ZKPs) provide a principled approach verifying computation correctness, but applying them to LLM inference remains challenging. Modern LLMs involve a large number of non-linear operations and require modeling real-valued computation in finite fields, introducing substantial computational and memory overhead and potential loss of numerical precision. Moreover, the large scale of LLMs makes end-to-end verification difficult to scale, limiting the practicality of existing approaches. This paper presents OpenLLM, an efficient and modular system for verifiable LLM inference. Our key idea is to decompose large-scale LLM inference into a set of reusable atomic operators, each equipped with efficient ZKP protocols, enabling scalable verification at the operator level. Based on this abstraction, we design succinct non-interactive zero-knowledge proof constructions for representative non-linear functions, which can be composed into end-to-end inference pipelines independent of model architectures. We further evaluate OpenLLM across operator-level performance, end-to-end inference, layer-wise scaling, larger models, and approximation accuracy. The results show that OpenLLM achieves smaller proof sizes, lower verification cost, and improved numerical fidelity while scaling from individual operators to full-model inference. Compared with state-of-the-art interactive protocols, OpenLLM eliminates communication overhead through a fully non-interactive design while maintaining competitive efficiency. Building on this operator-level efficiency, it further enables a scalable and modular framework for end-to-end verifiable LLM inference, outperforming prior end-to-end approaches.

Relying solely on encryption for privacy-preserving computations is prone to leakage-abuse/access-pattern attacks. TEEs, while cost-effective, are also vulnerable to side-channel attacks. Oblivious primitives, such as oblivious memory (ORAM) and data structures (ODS), are effective building blocks to mitigate these risks by concealing memory access patterns and side-channel information. Applications range from private contact discovery (Signal) to anonymous key transparency, encrypted email search, encrypted/oblivious databases, anonymous communication (Sparta/SP'25), private federated learning, LLM privacy (Compass/OSDI'25), and broader confidential computing efforts. Tree-based ORAMs (EnigMap (USENIX'23), GraphOS (PVLDB'23), Oblix (SP'18)) offer low latency but limited parallelism. Partition-based solutions like Snoopy (SOSP'21) shard data across subORAMs (which build oblivious hashtables on incoming requests, then linearly scan them), achieving high throughput by trading off latency, theoretically enabling linear scalability. In practice, Snoopy’s performance hinges on how quickly each subORAM can build the oblivious hashtable and complete its linear scan before exceeding latency targets, constraining server utilization and throughput. While supporting a TB-scale dataset with Snoopy is theoretically feasible, we estimate it would require 1000+ servers. In this work, we reconcile the fractured landscape between low-latency and high-throughput ORAM designs. We introduce SONIC: the first parallel/concurrent doubly-oblivious tree-based ORAM for TEEs. SONIC achieves 156K-3.3M req/s with a single server, tackling the core challenges of all tree-ORAM constructions: overcoming the sequential eviction bottleneck, enabling efficient batch evictions, and providing lock-free access/reshuffle/stash operations. SONIC achieves throughput 29-104$\times$ higher than EnigMap, and 158-560$\times$ higher than GraphOS, with lower latency. In the distributed, high-throughput setting, our SONIC-powered OMAP PMChain can replace Snoopy's subORAM, supporting higher throughput and $64\times$ larger datasets using the same hardware (reducing Snoopy's server requirements).