Many recent constructions of probabilistic proofs achieve fast proving times but have high space complexity (much higher than that of the computation being proved). Empirically this arises due to the fact that error-correcting codes, a key ingredient of such constructions, suffer from limiting time-space tradeoffs. It remained open, however, whether such time-space tradeoffs exist for proofs themselves. We establish time-space tradeoffs for probabilistically checkable proofs (PCPs) as well as for their multi-round extension, interactive oracle proofs (IOPs), with straightline knowledge soundness. Our results hold for machine computations that have sequential input access, the same model for which similar tradeoffs hold for error-correcting codes. We complement this result by describing an IOP for R1CS that avoids the tradeoff but requires random access to the R1CS witness. Our techniques build on and extend results for codes of Cook and Moshkovitz (CCC~2024). A key difficulty that we encounter in establishing our tradeoff is that distance of the code plays a key role in prior results, while for probabilistic proofs there is no natural notion of distance. Nevertheless, we show that, assuming the existence of collision-resistant hash functions, we can establish time-space tradeoffs by carefully relating a small-space machine's information flow to the proof system's properties.

Coin-tossing protocols allow mutually distrustful parties to generate trusted randomness. While strong fairness is impossible against a corrupted majority, Chung et al. (2018) introduced cooperative-strategy-proof (CSP) fairness for multi-party coin tossing, under the assumption that each party gets utility only when the outcome matches its public preference. CSP-fairness ensures that no PPT adversary can increase the expected joint utility of the corrupted parties through deviation. Since then, a line of work (Wu et al., 2022; Thyagarajan et al., 2024; Zhang and Wu, 2025) has explored the landscape of CSP-fair coin tossing and shown that CSP-fairness can be achieved even against a corrupted majority. In this work, we study CSP-fair multi-sided coin tossing against up to $n-1$ corruptions when parties may have arbitrary utilities over the possible outcomes. Perhaps surprisingly, we show that CSP-fairness against any semi-malicious adversary corrupting up to $n-1$ parties is achievable for every full-row-rank utility matrix. More generally, we introduce an abort-safe opening order condition on the utility matrix that suffices for resilience against $n-1$ corruptions. Our construction uses a public random walk whose state dynamically determines the distribution of the eventual outcome. The parties jointly generate randomness deciding each walk step using commit-and-reveal. When a party aborts, the protocol adjusts the transition distribution of the walk based on the parties' utilities. These adjustments, together with a carefully chosen opening order, prevent profitable deviations. We also identify conditions on the utility matrix under which CSP-fair coin tossing is impossible. For three parties, our positive and negative results together give a complete characterization of the utility matrices for which CSP-fairness against two corruptions is achievable.

Inner-product functional encryption (IPFE) allows the holder of a functional key for a vector $y$ to learn $\langle x,y\rangle$ from an encryption of $x$, and nothing more. Keys, however, accumulate: a coalition holding sufficiently many independent keys recovers the plaintext. We model each institution by the span $W_i\leq\F_q^n$ of its authorized key vectors and show that a coalition $I$ determines the plaintext exactly modulo $(\sum_{i\in I}W_i)^\perp$; for a uniform plaintext it learns exactly $\dim\sum_{i\in I}W_i$ field symbols. The resulting leakage function is a representable and entropic polymatroid. We then study authorization spaces of dimension $r$ whose pairwise intersections have dimension at most $h$. We prove that some coalition of size $c\geq2$ always learns at least $\min\{n,2r-h+c-2\}$ dimensions, and we give a Vandermonde-type construction in which every coalition of size $c$ learns exactly this amount, for all $c$ simultaneously. Hence the largest achievable reconstruction threshold is $n-2r+h+2$, which gives an exact tradeoff between functional diversity and collusion resistance. The optimal configuration is a sunflower, an equidistant subspace code and a generalized arc; its orthogonal complements form a generalized dual arc, and for $r=1$ it reduces to Reed--Solomon secret sharing.

Fully Homomorphic Encryption (FHE) enables one to implement low-round and low-communication complexity Multi-Party Computation (MPC) which is secure in the static malicious corruption model. By expanding on an idea presented in the full version of the FHE-based MPC protocol of Smart (IMA, 2023), we show how to completely remove the need for Zero-Knowledge Proofs-of-Knowledge in that protocol. This simplification makes the final security proof of the MPC protocol much simpler, and more modular. The new protocol makes use of an FHE scheme with an encrypted PRF functionality, and in addition to our main result we formalize the security of such encrypted PRFs and prove the construction of Deo et al. (CCS 2025) secure in this model.

We show an attack on a lattice-based blind signature proposed in Crypto'20. Formally it is a linear hash function based framework with a lattice-based instantiation. We first notice a bug in their security proof of blindness, which is overlooked these years. Then, we develop an attack under the honest key and the honest-but-curious signer setting against the blindness notion of the schemes by exploiting the coorelations between the leaves of the tree. We also discuss how to repair the scheme.

We present the first new infinite family of APN functions obtained by applying the switching construction to a known family since the introduction of the Budaghyan-Carlet-Leander family in 2009. Our construction is also the first example of an infinite APN family obtained via the switching construction from an infinite family of non-power functions. More generally, we study families of APN functions that can be obtained from the Budaghyan-Helleseth-Kaleyski family by the addition of carefully selected perturbation terms. We perturb the known family by combinations of Frobenius conjugates of the relative norm and obtain four constructions, naturally arranged into two switching pairs. One of these families is EA-equivalent to the Li-Zhou-Li-Qu family, for which our construction yields a new univariate representation. Switching it by a norm-derived Boolean term produces a second family that we prove to be APN in every dimension where the base family is defined, and we show that this family is CCZ-inequivalent to all previously known constructions. Furthermore, we investigate two other infinite families that can be switched to one another, conjecture that they are APN for infinitely many dimensions, and obtain conditions that can be used to characterize their APN-ness. The new infinite APN family and the two conjectured APN families generalize previously known sporadic APN instances in dimension 10.

Lattice agreement is a relaxed version of the standard consensus problem: correct processes need not decide the same value, but their decisions must be ``comparable''. Namely, every process proposes a value from a join semi-lattice, and correct processes decide values that (1) lie on a single chain, (2) include their own proposals, and (3) include nothing beyond what was proposed. Lattice agreement has important practical applications, as it underpins atomic snapshot objects and replicated state machines with commutative operations. Yet, the best known protocols decide in $O(\log f)$ rounds, where $f$ is an upper bound on the number of faulty processes. In this paper, we break the logarithmic barrier. Namely, we present Join-IT, a synchronous Byzantine lattice agreement protocol that tolerates $f < n/3$ Byzantine processes and decides in $O\big( \frac{\log f}{\log \log f} \big)$ rounds. Join-IT uses no cryptography whatsoever, and its guarantees thus hold against a computationally unbounded adversary. Perhaps surprisingly, Join-IT is also remarkably simple. It sequentially composes two classical primitives: gradecast, which takes three rounds, and approximate agreement, which, at the precision Join-IT requires, takes $O\big( \frac{\log f}{\log \log f} \big)$ rounds. A single local step finally turns the output of approximate agreement into comparable decisions, at no additional cost in rounds.

Hair and Sahai have recently proposed a construction of witness encryption for NP satisfying semantic security. In this short note we observe that this recent witness-encryption construction is unconditionally extractable in the generic group model. This yields a construction of extractable witness encryption without assuming subexponential soundness of SNARGs, in contrast to the recent work of Jin (eprint:2026/2063), which requires this assumption. The result in this note, moreover, complements the concurrent work of Chen and Vaikuntanathan (eprint:2026/2346), who show the same construction to be public-coin extractable under a knowledge-style assumption; our argument is unconditional, but in the GGM.

A recent work by Belohorec et al. (Crypto, 2025) shows that the well-known PST multivariate polynomial commitment scheme is black-box extractable under falsifiable assumptions. They show that a minimally modified (extended) PST is extractable under an assumption ARSDH($n$), and that the canonical PST is extractable under an assumption GARSDH($n$). Both of these assumptions are new and more specialized than the original ARSDH assumption proposed by Lipmaa et al. (Eurocrypt, 2024) to prove black-box extractability of the univariate KZG polynomial commitment. A natural question is whether these assumptions are actually stronger than the original ARSDH assumption. We answer this negatively: we show that both ARSDH($n$) and GARSDH($n$) are equivalent to the original ARSDH assumption. Secondly, we point out a gap in the proof that canonical PST is extractable under GARSDH($n$) assumption.

Oblivious RAM (ORAM) is a powerful cryptographic primitive that hides both the contents of outsourced data and the access pattern to the data. However, it offers only a restrictive array-based interface. A principal obstacle to its deployment is building an efficient oblivious dictionary upon it. To build such a dictionary, the state-of-the-art layers an oblivious AVL tree over ORAM, avoids an expensive local position map, but forces every operation to traverse a full root-to-leaf path, costing $\Theta(\log n)$ ORAM accesses. We show this trade-off to be suboptimal, particularly when deployed in a common setup within a trusted execution environment like SGX. There, a small amount of client memory can reduce the position map recursion depth to three levels or less, rendering its overhead relatively small. With low position map cost, probabilistic hash tables prevail as dictionary data structures due to their small, constant number of accesses compared to $\Theta(\log n)$ path traversal of a tree. We implement and analyze oblivious, probabilistic hash tables over Path ORAM, including several different strategies: chaining, power-of-two-choices, stash-less cuckoo, and de-amortized cuckoo hashing. Execution of these algorithms within a secure enclave requires "double obliviousness", which in turn needs strict concrete maximum cost limits for each access that current literature does not provide. We derive these concrete padding parameters bounding the hash table rebuild probability to $\le 2^{-40}$ via large-scale simulation. In an SGX deployment, our constructions outperform oblivious trees by up to $20\times$ for $\mathsf{lookup}$s and $12\times$ for $\mathsf{insert}$s.

Attribute-based credentials (ABCs) enable privacy-preserving authentication by allowing users to prove statements about certified attributes without revealing unnecessary information. However, while ABCs hide undisclosed attributes, the credential verification process inherently reveals the issuer's identity, which can leak contextual information such as a user's nationality or residency. Issuer-hiding ABCs address this by concealing the issuer during verification, but introduce a critical accountability problem: if an issuer is compromised or acts maliciously, previously accepted presentations originating from that issuer cannot be singled out without significant privacy violation and high burden on the central authority performing the inspection. We propose an issuer-inspection mechanism that enables retrospective attribution while preserving privacy. An inspection authority can release keys allowing verifiers to locally identify presentations originating from a specific compromised issuer and a defined time period, without affecting other issuers or earlier time periods. Concretely, we formalize the syntax and security requirements of issuer inspection and provide a generic construction from standard cryptographic building blocks; we further present a concrete pairing-based instantiation using Groth's randomizable structure-preserving signatures, Schnorr-style proofs and an adaptation of Gentry's anonymous identity-based encryption. Our analysis of computational and communication costs indicates that the proposed functionality remains practical for realistic parameter choices.

We study the randomness required to share possibly correlated secret bits among parties connected by a graph. A dealer places shares on the edges so that each party can recover its own secret from its incident shares and learn nothing about the others beyond what its own secret reveals. Anilkumar et al. completely determined the minimum randomness required for three binary secrets. We extend this study to four secrets and obtain results for arbitrary numbers of secrets on general graphs. For four parties on a complete graph, we determine the minimum number of random states for every set of permitted secret combinations: the possible values are one, two, three and four. We also characterize when one random bit suffices on an arbitrary graph.

Secure weighted aggregation is essential for privacy preserving federated learning, yet existing schemes do not simultaneously provide post-quantum security, resilience to client dropouts, verifiability against malicious servers, and resistance to bounded collusion between the server and clients. This paper presents PQ-DVSA, a verifiable secure aggregation scheme that provides post-quantum security and resilience to client dropouts. PQ-DVSA protects both clients’ updated local models and aggregation weights, enables reconstruction of the aggregate mask for the active set after client dropouts, and allows clients to verify the server’s aggregation result under bounded collusion. Experimental results show that PQ-DVSA achieves learning performance comparable to exact weighted aggregation and reduces the runtime for encrypted submission at each client by up to 96% compared with SWAS, the closest existing scheme to PQ-DVSA.

Secure multiparty computation with provable identifiable selective abort (PISA), introduced by Kondi and Ravi (CCS 2025), guarantees that every honest party either obtains the computation output or a certificate that convinces any external auditor that a specific party cheated. Crucially, honest parties need not agree: some may get output while others receive evidence of cheating. In contrast, secure computation with identifiable abort (IA) requires just such unanimity; however, in the event that an honest party doesn't get output, it need merely be able to point to a cheater - not to prove their guilt. Secure computation with IA classically requires broadcast. Kondi and Ravi demonstrated that secure computation with PISA, on the other hand, can be built over point-to-point channels alone. While PISA is feasible exactly when guaranteed output delivery is, i.e. for $t < n / 2$, the best known construction over point-to-point channels requires six rounds. We settle the round complexity of PISA for all but a narrow band of thresholds. We prove that two rounds are impossible for $t \geq n /3$, even with arbitrary setup and computational assumptions; we give a three-round protocol for any $t < n/2$, which is therefore round-optimal for $n / 3 \leq t < n/2$; and we give a two-round protocol for $t < n/4$. The two-round protocol introduces a new primitive called one-or-nothing secret sharing with omissions.

Secure multi-party computation (MPC) enables privacy-preserving tasks such as auctions and voting. In practice, more than half of the parties may collude, making security against a dishonest majority desirable. Unfortunately, dishonest-majority MPC suffers from high communication and can achieve only abort security. For instance, in an auction, an adversary may abort after learning the outcome and rerun the protocol with a higher bid. Helper-aided MPC mitigates these limitations by introducing a semi-honest, non-colluding helper, a model that naturally fits settings with a central governing or coordinating entity and provides strong guarantees even when up to $n-1$ parties are malicious. The model assumes that the adversary can either semi-honestly corrupt the helper or maliciously corrupt up to $n-1$ parties (excluding the helper). While existing helper-aided protocols are fair i.e. either all parties receive the output or none do; they still allow the adversary to abort without any penalty and deny output to all parties. This behavior is undesirable in practice, as parties may incur the cost of computation without receiving the output. In this work, we design efficient helper-aided MPC protocols that achieve identifiable fairness: either all parties obtain the output, or—if an abort occurs—no party receives the output, and the honest parties identify at least one common cheater. We propose two protocols, $\mathsf{Alhena}$ for synchronous networks and $\mathsf{Wasat}$ for asynchronous networks which provide the stronger guarantee of identifiable fairness compared to the state-of-the-art fair protocols $\mathsf{Asterisk}$ (Kamarkar et al. IEEE S&P 2024) and $\mathsf{Castor}$ (Kamarkar et al. IEEE S&P 2026) in the respective network settings. Our experiments show that, in the online phase, $\mathsf{Alhena}$ and $\mathsf{Wasat}$ achieves speedups of $4-12.5\times$ and $2.5-5\times$ over $\mathsf{Asterisk}$ and $\mathsf{Castor}$ respectively. Furthermore, in the preprocessing phase, $\mathsf{Wasat}$ exhibits speedup of $\approx 3\times$ over $\mathsf{Castor}$. Notably, our protocols are designed in such a way that the online performance remains unaffected by active misbehaviour.

Retaining intermediate values can shorten a quantum cipher oracle but increase the logical qubits required by each parallel search worker. We propose a joint selection procedure for 80-round and revised 112-round CHAM-128/128 under a fixed global logical-qubit budget. It selects retained round addends, feasible integer allocations of search workers, and execution plans to minimize maximum scheduled logical depth subject to a target probability of recovering and accepting the original key. We evaluate libraries of 83 and 99 retention sets against a baseline whose retention choices are restricted to no retention and full retention. Both comparison groups use the same implementation and execution rules. Across 654 budget, success-target, and Toffoli-decomposition conditions per round count, the mean depth reductions are 11.12% and 8.39%, with strict improvements in 606 and 588 conditions, respectively. The selected retention count need not increase with the budget, and a fixed-circuit capacity discontinuity can disappear after reselection. The findings concern the measured libraries under an ideal-cipher success model and logical-layer costs.

Origami is a multivariate signature scheme submitted to the NGCC round-1 public-key call. We show that the submitted bilinear construction is a Rainbow-type scheme whose central map is exposed. The verification map is the layered signing map in a public coordinate order. The public key therefore gives an equivalent secret key, allowing signature forgery at about the cost of one verification (about $0.01$s at Origami-128). Our attack exploits this public layered structure and succeeds against the unmodified reference implementation on all four parameter sets and the official test vectors. We also refute the security proof's inversion assumption in a bilinear independent-coefficient model. The hidden local algebras introduced by Origami do not prevent the attack. They raise a separate problem: the specification treats constrained matrix coordinates as independent, and honest signatures lie in a proper subspace.

Notions like identity-based encryption (IBE) and attribute-based encryption (ABE) augment public-key encryption to provide fine-grained access control to encrypted data. In these settings, there is a single master public key that anyone can encrypt to. Users in turn possess different secret keys that determine which ciphertexts they can decrypt. The standard, or full, security notion for these schemes stipulates that a ciphertext computationally hides the message if the adversary does not possess a key that is allowed to decrypt. A relaxed notion of security that is often much easier to achieve is bounded-collusion security, where we only require security against adversaries that have an a priori bounded number of keys (and the scheme parameters can grow with this bound). For instance, it is known that vanilla public-key encryption implies bounded-collusion IBE (and ABE) whereas there is a black-box separation between public-key encryption and fully secure IBE. In this work, we develop a general methodology to upgrade a pairing-based encryption scheme with bounded-collusion security into one that is fully secure. We illustrate our methodology by applying it to two main applications: batched IBE and multi-authority ABE. First, in the case of batched IBE, we obtain the first pairing-based construction of batched IBE where there are no tag restrictions (in the generic bilinear group model). All previous pairing-based batched IBE schemes require attaching a tag to ciphertexts and secret keys, and moreover, restrict the adversary to an a priori bounded number of secret keys for each tag. Second, we use our techniques to obtain a multi-authority ABE scheme that supports conjunction policies in the generic bilinear group model. This is the first pairing-based scheme that makes fully black-box use of the group. Previous pairing-based multi-authority ABE schemes require a random oracle whose output is a group element (which implicitly assumes the underlying group supports a procedure for explainable oblivious sampling).

We study the computational problem $\mu$-SVP, in which the goal is to find a $\mu$-approximate shortest non-zero vector in a lattice $\mathcal{L}$, for constant approximation factors $\mu > 1$. Prior to this work, there was a large gap between the fastest algorithms for this problem whose correctness had been proven and the fastest heuristic algorithms, whose correctness has not been proven (but which seem to work well in practice). We construct a novel sieving algorithm that combines the key tool used in the fastest heuristic sieving algorithms (faster nearest neighbor subroutines) together with the perturbation argument used in sieving algorithms with proven correctness. The result is an algorithm whose correctness we prove and whose running time depends on a simple geometric quantity: the maximal size of certain spherical codes. Under a reasonable assumption about the maximal size of spherical codes, our algorithm's running time is roughly $2^{0.3066n}$ for large constants $\mu$, which is quite close to the best heuristic running time of roughly $(3/2)^{n/2} \approx 2^{0.2925n}$ and much faster than both the previous best known algorithm with proven correctness, which runs in time roughly $2^{0.802n}$ [Liu, Wang, Xu, and Zheng, 2011] and the very recent concurrent and independent work showing a $2^{n/2}$-time algorithm [Hhan, 2026]. (However, the algorithm of Hhan also solves $\mu$-SVP for $\mu =1$, while our algorithm only works for large constant $\mu$.) Using the best proven upper bound on the size of such spherical codes (which is almost certainly quite loose), we obtain a running time of roughly $2^{0.6078n}$, which is much better than the previous best work but notably slower than the concurrent work of Hhan.

A time-lock puzzle allows a sender to hide a message in a puzzle such that recovering the message requires substantially more sequential computation than the time required to generate the puzzle, even when parallel computation is allowed. Applications of time-lock puzzles include timed-release encryption, sealed-bid auctions, electronic voting, fair contract signing, coin flipping, and Byzantine consensus. However, time-lock puzzles are known to be impossible in the classical random oracle model. To overcome the classical barrier, in this work we consider quantum time-lock puzzles, in which the puzzle itself is a quantum state. Our construction in the quantum random oracle model achieves generation in one oracle round, solving in at most $T$ oracle rounds, and security against polynomial-width quantum adversaries of depth $o(T)$ for every polynomially bounded delay $T$, resolving an open problem posed by Mahmoody, Moran, and Vadhan (2011).

We give provable classical subexponential algorithms for secret recovery in growing parameter families associated with NIST third-round lattice candidates. For the Kyber/ML-KEM, FrodoKEM, SABER, NTRU LPRime, and Dilithium/ML-DSA families studied here, polynomial moduli and polylogarithmic coefficient scales yield recovery of the short secret component in expected time and space $2^{(1/2+o(1))n/\ln\ln n}$. For noisy or rounded linear relations, we exploit an exact gap in the squared Euclidean norm of a comparison vector defined by each coordinate guess. One Gaussian list suffices to identify every secret coordinate by binary search, without enumerating the others. We establish the required sampling guarantees through new geometric bounds for structured public operators over prime and power of two moduli. The construction builds on the Wagner-style Gaussian sampling framework of Ducas, Engelberts, and Loyer (CRYPTO 2025) and the low-error decision-LWE algorithm of Han, Gao, and Hu (2026). For quotient relations of NTRU type, we develop an affine slice search: fixing coordinates restricts candidate pairs to slices of the public lattice, and their estimated Gaussian masses guide the choice of each next coordinate. In the stated modulus window, Falcon's key generation quality condition supplies the required mass bound. The algorithm then recovers an equivalent signing key with high probability in time and space $2^{O(n/\ln\ln n)}$. The same search recovers the short key core for cyclic NTRU-HPS/HRSS. Together, these results give subexponential algorithms for problem families associated with all seven NIST third-round lattice candidates. Despite the subexponential complexity, our results do not establish a reduction in the concrete security of the currently specified parameter sets.

Batch Private Information Retrieval (Batch PIR) allows a client to privately retrieve multiple entries from a public database while amortizing query costs. However, concretely efficient schemes typically rely on per-client server state, such as client-specific evaluation keys, which makes queries linkable across sessions and complicates deployment. In this work, we initiate the study of doubly-stateless Batch PIR, where the server stores no per-client state and the client maintains no database-dependent hint. For this model, we construct a communication-efficient scheme that substantially reduces communication compared with the natural baseline of adapting off-the-shelf Batch PIR schemes by sending fresh evaluation keys with each batch query. The core technical ingredient is a single-key RLWE unpacking procedure that replaces the traditional tree-based approach, which requires logarithmically many Galois keys, with a linear walk over a cyclic Galois subgroup requiring only a single Galois key.

Deploying memory-heavy post-quantum cryptography (PQC) at the smart grid edge threatens real-time substation determinism, directly conflicting with the strict $\le 3 ms$ GOOSE tripping window of the IEC 61850 standard. To resolve this architectural tension, we propose a security-aware, hardware-in-the-loop benchmarking framework on the dual-core Xtensa LX7 (ESP32-S3) SoC running FreeRTOS. To prevent inter-core resource contention, the framework employs an asymmetric task-isolation design, pinning cryptographic operations to Core 1 while leaving Core 0 responsive to line-rate grid interrupts. Additionally, we define a programmatic heap-auditing methodology to model how heap_4.c maps key-state allocations across physical DRAM fragments while preserving the primary 128 KB contiguous system heap. Finally, we formulate an analytical latency model of the external Octal-SPI PSRAM interface, mathematically characterizing the CPU stall overhead ($C_{\text{stall}}$) induced when side-channel masking forces secret polynomial shares to spill over the external bus during non-sequential Cooley-Tukey NTT strides. This framework provides a rigorous methodology to characterize micro-architectural trade-offs, enabling utility engineers to plan post-quantum migration pathways without violating real-time grid constraints.

Recent Bitcoin bridge designs rely on verification of succinct proofs to process withdrawals. This requires off-chain garbled circuit evaluation of a succinct proof, the input labels for which must be encoded on chain in a manner compatible with malicious security. We assess the post-quantum vulnerability of these cryptographic components, and examine the costs of secure alternatives. Circuit sizes for post-quantum proving systems can be made smaller than the current pairing-based baseline, but at the cost of significantly higher proof sizes that incur greater cost and require multiple Bitcoin blocks to encode. We suggest avenues of future research to improve efficiency of proofs, circuit representations, and input encodings.

The paper presents the first-ever differential neural cryptanalysis of the Latin Dances family of Salsa, ChaCha, and Forró. First, we provide a systematic differential-neural study of the ARX stream cipher ChaCha. We train and compare six neural architectures, viz.: Gohr's residual network, DBitNet, an Inception network, an MLP-ResNet, an SE-ResNet, and a self-attention network on a 3-round reduced version of ChaCha. We train in both the classical single-pair setting and a multi-pair setting that combines up to sixteen ciphertext pairs through a log-odds rule. We extend the study for breadth to other ARX ciphers, Salsa, *ChaCha, and Forró. We provide the first-ever distinguisher for 4.5 rounds of Salsa with accuracy of 0.53 for one pair and 0.60 for 16 pairs. Also, for Forró the first-ever distinguisher for 1.25 rounds of Salsa with accuracy of 1 for single and multiple pairs. We also introduce a family of experimental round-1-XOR variants (\emph{XOR-1}) that isolate the contribution of the first round's diffusion to distinguishability. Finally, we investigate the trained 3-round ChaCha distinguisher with four explainability experiments and show that, although the output difference is its dominant feature, it is not a pure differential distinguisher: its decision is interpretable as a learned mixture of round-1 truncated differentials, five of which already account for $99\%$ of the high-confidence ciphertext pairs.

The Lattice Isomorphism Problem (LIP) is a relatively new problem that has gained increasing attention in the field of lattice-based cryptography. It is the underlying hard problem of the Hawk signature scheme, which has been submitted to the second NIST call for post-quantum signatures. In this paper, we propose to study the security of LIP in the presence of partial information on the secret solution, which can be obtained through side-channel attacks or by design. We propose a new cryptanalysis approach for LIP that embeds it into a shortest vector problem (SVP) based on a different lattice than the one considered in the specifications of Hawk, allowing to integrate hints. We also introduce conversion techniques that transform hints expressed on arbitrary linear combinations of the secret key coefficients into hints on the target lattice, enabling the integration of a broader class of linear leakages on sensitive values. We implement our attack and predictions using the LeakyLWEEstimator tool (Crypto 2020) and obtain concrete security estimates for Hawk in the key-recovery setting. We also observe that Hawk signatures carry intrinsic information about the secret key and show that this can be exploited as a source of hints, yielding a refined key-recovery complexity, thereby eroding the original security estimates. For example, we estimate a security loss of around 11 bits for Hawk-1024. Finally, we apply our framework to side-channel analysis results on Hawk, solving an open problem raised in a recent analysis (TCHES 2024) and discuss further attack paths enabled by fault-injection techniques. We believe that this new cryptanalysis approach for LIP and the integration of hints provide new insights towards a better understanding of its security.

We give a new framework for constructing post-quantum protocols based on graded monoidal actions. An essential difference between the graded monoidal action framework and the cryptographic group action framework is that our higher-rank problems give rise to infinite structures, where elements do not admit inverses, while cryptographic group actions are finite by definition. Nevertheless, we show that the hard problems for cryptographic group actions reduces to the corresponding family of hard problems for graded monoidal actions. However, the main motivation is that for general graded monoidal actions, the relevant problems admit no known subexponential quantum attacks, while still having enough structure to formulate some protocols based on cryptographic group actions, such as the Diffie-Hellman key-exchange. Our framework can, to the extent we make clear in the paper, be instantiated with the module-action on oriented principally polarized abelian varieties (PPAV's), generalizing the class group action on oriented elliptic curves. Although the theory involving the module-action is quite involved, the formulation of a graded monoidal action is strikingly simple, making it a suitable abstraction for constructing protocols in, which can then be instantiated with the module-action.

Belkheyar et al. introduced ChiChi as the even-dimensional, low-latency nonlinear core of ChiLow (Eurocrypt 2025), and Andreoli et al. generalized it into the SWAP and 4-cycle families (ToSC 2025/3), conjecturing five bounds on the linear height and component linear nullity of their inverses, supported by experiments in small dimensions. We settle all five conjectures: Conjectures 1–4 hold for every admissible branch length, and Conjecture 5 is false. In addition, we derive consequences for ChiLow's design and correct one value in the data of Andreoli et al.

We define an asynchronous ledger service ($\mathsf{AsyncLS}$) in the IITM-based universal composability (iUC) framework. The wallet-based service exposes a general state machine for a decentralized ledger-based application through registration, reads of committed application state, authenticated submission, and status queries with immutable final results. Each logical request binds the user's authorization to a finalized checkpoint and the applicable execution context. A confirmed outcome identifies the first eligible transaction and records application success or rejection. Strict expiry requires complete processing beyond the eligible height window with no recorded outcome, and certifies that the request has no application effect. We construct a protocol $\mathbf{\Pi}_{\mathsf{AsyncLS}}$ that realizes the ideal service using four components: Wallet, Relay, Adapter, and Replay. The proof separates the service construction from the implementations of Relay and Adapter while preserving ledger, clock, authentication, and setup interactions. We prove realization for the trusted and local implementations under their respective execution and trust assumptions. We use the service to construct an ORDI interactive payment and a parameterized execution layer above transaction ordering. These examples distinguish the ledger interaction protocol from the application state and effects exposed by the service. Each use requires the stated authorization, setup, ledger, clock, authentication, and ledger-effect assumptions.

We introduce MIKE (Module Isogeny Key Exchange), a post-quantum NIKE (Non Interactive Key Exchange) whose security relies on the CDH problem for the rank-$2$ Hermitian module action on supersingular elliptic curves. For NIST level~$1$, MIKE has very compact public keys of 80B, and using our constant time C implementation, the key generation takes 0.65ms and the shared secret takes 4.9ms (including key validation) on a AMD CPU at 3.3GHz.

Deploying Secure Multiparty Computation (MPC) to operate on data from real world sources requires many connective elements that have not received much attention in the literature. One prominent example is that MPC protocols typically assume conveniently structured data, whereas data in the real world comes in formats that are meant to be handled by string parsing engines. In this work, we give a new constant round protocol for securely parsing secret shared strings into an MPC-friendly format, built upon secure shuffle as a key primitive. Secure shuffle applies a permutation to a list while keeping both the permutation and the underlying data secret-shared at all times. While highly efficient protocols exist in the semi-honest setting, achieving malicious security has incurred significant overhead in both rounds and communication. We present Truffle, a new three-party shuffle protocol that is secure against one active corruption to bridge this gap. Truffle achieves an amortised round complexity that for the first time matches the state-of-the-art semi-honest protocol, while incurring only sublinear communication overhead. The core technique that underlies Truffle is a novel distributed verifier zero-knowledge proof that checks the correctness of a putative shuffle. We implement Truffle and show via benchmarks that it is performant enough to handle real application data. Beyond parsing secret shared data, secure shuffle finds applications in graph analytics, anonymous communication, Distributed Oblivious RAM, aggregate statistics, and secure sorting, each of which stand to benefit from the improvement that Truffle provides.

The shift to Post-Quantum Cryptography (PQC, a.k.a. quantum-resistant cryptography) is considered the immediate solution to the threat posed to public key cryptography/PKI by quantum computers. Due to the variety of PQC algorithms (and their characteristics), researchers have proposed different PQC migration strategies. For example, KEMTLS (Schwabe, Stebila, and Wiggers, CCS '20) replaces TLS handshake signing operations by Key Encapsulation Mechanisms (KEMs). However, KEMTLS requires KEM-based certificates (i.e., a certificate with a KEM public key), and the question of issuing KEM certificates on a large scale has received limited attention from the community. We address this research gap by comparing the performance of different Proof of Possession (PoP) approaches for KEMs and assessing their viability for practical adoption. To this end, we first propose and implement a non-interactive PoP for Hamming Quasi-Cyclic (HQC), a code-based post-quantum KEM selected by NIST for standardization. Our PoP is instantiated via the VOLE-in-the-Head (VOLEitH) paradigm. %VOLEitH is based on Vector Oblivious Linear Evaluation (VOLE). Setting, reproducibility, and practicality as design goals, we integrate and benchmark our approach against PoPs for Kyber and FrodoKEM (from Güneysu et al., CCS '22) in the ACME protocol for automatic certificate issuance. Our results show that, in general, Kyber allows faster issuance of KEM certificates but at a cost of losing either compatibility with the protocol (necessitating significant alterations to proposed internet standards) or breaking compatibility/compliance with NIST standards. Notably, our PoP for HQC holds compliance, compatibility, \emph{and} achieves smaller proof sizes. We also report integration choices and considerations, as well as network traffic analysis stemming from larger (KEM-based) Certificate Signing Requests (CSRs). Our testbed demonstrates the impact of large CSRs by simulating an unstable network. It shows that HQC-PoP's performance is competitive with the fastest options, thanks to its smaller proof sizes.

SLH-DSA is a standardized stateless hash-based signature scheme based on SPHINCS$^+$, but its signatures remain large. PORS+FP uses forced pruning to reduce the size of the bottom few-time signature (FTS) component, while BPORS+FP distributes repeated uses among independent PORS child keys. In BPORS+FP, each selected leaf reveals a fixed secret value, and a single pruning budget limits the total number of authentication nodes across all coordinates. We introduce BPORS-C+BFP, which replaces each secret at a child leaf with a short hash chain and assigns a separate authentication budget to each block of coordinates. The child Merkle tree authenticates each chain endpoint. Each selected chain still contributes one hash value to the signature, while its opening depth provides an additional encoding choice. For a fixed set of selected chains, a constant-sum constraint prevents forward hashing alone from converting one valid depth tuple into another. Under repeated use, signatures may disclose different positions on the same chain. We derive a generating-function upper bound on coverage and an exact counting method for individual pruning blocks that accounts for these disclosures and target acceptance. Separate block budgets confine pruning-induced dependencies, reducing the number of coordinates counted jointly and making exact calculation practical for small blocks. Replacing FORS in SPHINCS+ while keeping the hypertree and one-time signature parameters fixed, BPORS-C+BFP reduces complete-signature sizes by $8.3\%$--$18.1\%$ across six standard settings, compared with $3.7\%$--$13.4\%$ for BPORS+FP. Across three limited-use settings, the reductions relative to FORS are $32.5\%$--$36.5\%$ for BPORS-C+BFP and $22.0\%$--$26.0\%$ for BPORS+FP.

Matrix-native fully homomorphic encryption, introduced by Gentry and Lee, multiplies encrypted matrices with a Trace product and returns its four-component output to an ordinary ciphertext with a BigSwitch, whose keys over an extended ring dominate the key material of the scheme. Existing BigSwitches follow two routes: they either store one key per source, as in the original construction, or factor the secret through the trace and relinearize at run time, as in the Trace-Factored BigSwitch (TFB) of Park et al., which halves the keys at the price of $50\%$ more key switches and a whole switching error multiplied by the secret. Meanwhile, the Galois splitting of Park (Eurocrypt'25) decomposes such switches into base-ring diagonals, but it has not been used to reduce their keys. However, whether a BigSwitch can publish only the keys of TFB and still run at the speed of the original one has remained open. In this work, we first propose the pair-merge BigSwitch, which observes that the diagonals of a split BigSwitch are indexed by an inversion-closed coset $\kappa H$ and rewrites the target of a diagonal as $x\,g(s)+y\,s\,g(s)=g\big(g^{-1}(x)\,s+g^{-1}(y)\,s\,g^{-1}(s)\big)$, so that it borrows the product key of its inverse at the cost of one Galois step; it makes the $2n$ key switches of the original BigSwitch with $n/2+1$ instead of $n$ product keys, and we prove that no per-diagonal BigSwitch with $2n$ key switches holds fewer than $3n/2+1$ keys. Building on it, we propose public key rebasing, which turns Galois keys into product keys with one relinearization key placed one small modulus layer above the chain, so that the client publishes only the keys of TFB and a 10.6 MiB layer key, at the price of $1.5\times$ the resident keys of TFB on the server. Consequently, together with a Hermitian hop that finishes a partner diagonal of a Gram product with one Galois step, PairSwitch makes $2n$ key switches on general inputs and $3n/2+1$ on Gram products. On the parameters of Park et al. ($n=256$, $p=17$, $\log_2 PQ=200$), our implementation runs a BigSwitch $1.89$--$1.99\times$ faster than TFB and $1.28$--$1.38\times$ faster than the original BigSwitch, with $2.4$ bits less noise than TFB and $4.3$ bits more than the original, at a $128.3$-bit layer key; it is $2.45\times$ faster than TFB on Gram inputs. Our implementation and the raw logs are available at https://github.com/acprk/pairswitch-gl.

Hash-based signatures are the most conservative post- quantum signature family, and the stateful schemes XMSS and LMS are both standardized by NIST. Prior work has instantiated XMSS and SPHINCS+ with Korean cryptographic primitives, but no comparable Korean-primitive study exists for LMS. We fill that gap with K-LMS, an experimental variant that preserves the full LMS structure and domain separation and replaces only the hash. The substituted hashes are the Korean hash function LSH-256, in both its reference and its vectorized implementation, and a Tandem-DM double-block-length construction over the Korean block ciphers CHAM, LEA, and ARIA. A non-invasive bridge over the reference LMS implementation realizes eight interchange- able backends without editing a line of it. We evaluate key generation, signing, and verification latency, key and signature sizes, peak memory, a sweep over tree height and the Winternitz parameter, and implemen- tation complexity. Hash substitution leaves key and signature sizes, and the memory requirement of the LMS data structures, unchanged. We also isolate two measurement pitfalls that can distort such comparisons: a vector dispatch wrapper that re-runs its capability check on every digest, which costs an order of magnitude on our virtualized host, and the choice of software or hardware-accelerated SHA-256 as the baseline, which shifts any LSH vs. SHA-2 conclusion by a factor of about six. Profiling shows that LMS is dominated by 55-byte one-shot hashes (about 94 % of all calls), so scheme-level ranking cannot be extrapolated from long-message hash benchmarks. Against a fair software baseline, LSH-256 K-LMS signing is on par with SHA-256 LMS (0.84×), while hardware acceleration retains a ∼3.6× advantage where it is available. On the same host and with identical LSH-256 code, K-LMS runs 3.3– 3.9× faster than the published K-XMSS implementation, because LMS needs one hash call per Winternitz chain step where XMSS needs three.

Efficient multiplication over $\mathbb{F}_2[x]$ is a core primitive in classical and post-quantum cryptographic software. As ARM and RISC-V become increasingly relevant for open-source cryptographic libraries such as OpenSSL and liboqs, arithmetic kernels must be retuned across a wider range of Instruction Set Architectures (ISAs). High-performance arithmetic libraries recursively apply Karatsuba- and Toom-style decomposition rules, each splitting the operands into smaller subproblems and recombining the resulting products. The resulting decomposition schedule is the recursive tree of rule choices from the top-level multiplication down to the base kernels. However, hand-tuned schedules can miss better decompositions at large operand sizes, while ISA-specific primitive costs complicate cross-platform retuning. In this paper, we formulate recursive $\mathbb{F}_2[x]$ multiplication as a schedule-selection problem. The recursive rule space has optimal substructure, allowing dynamic programming (DP) over a compact ISA profile that accounts for base multiplication, XORs, memory traffic, and recursive overhead. The resulting schedules are materialized as dispatch tables or fixed-size kernels. Across x86-64, ARM64, RISC-V64, and RP2040, DP costs track runtime trends across input sizes, and the full rule set achieves $1.04$–$1.18\times$ geomean speedup over gf2x. HQC and BIKE integrations on the three 64-bit platforms yield $1.06$–$1.21\times$ and $1.01$–$1.70\times$ end-to-end speedups, respectively, against their platform baselines. We also evaluate Classic McEliece on these platforms. With prepared profiles, HQC/BIKE schedule selection takes 0.075–0.762 seconds, avoiding candidate compilation and benchmarking during search. The scheme provides a systematic alternative to hand tuning and measurement-driven per-size empirical search, reducing the effort required to port and retune carry-less multiplication kernels.

The One-Way-to-Hiding (O2H) theorem is a useful tool for analyzing reprogramming in the quantum random oracle model (QROM). It bounds the distinguishing advantage by the probability $\epsilon$ that a one-wayness attacker finds the reprogrammed point. A sequence of works has improved the tightness of this theorem. Currently, the Measure-Rewind-Extract O2H (MRE-O2H) theorem proved by Ge et al. (ASIACRYPT 2024) achieves the tightest known upper bound of $O(\sqrt{q}\cdot\epsilon)$, where $q$ is the number of quantum queries. This theorem follows the Double-Sided idea introduced by Bindel et al. (TCC 2019), which requires the one-wayness attacker to access both the original and reprogrammed random oracles, thereby imposing stronger requirements on the reduction. Moreover, it incurs a $q$-dependent loss of $O(\sqrt{q})$. In this paper, we address these limitations by proving two Extract-Amplify-Measure (EAM) O2H theorems. First, we prove a Single-Sided EAM-O2H (SSEAM-O2H) theorem, which achieves the same $O(\sqrt{q}\cdot\epsilon)$ upper bound as the MRE-O2H theorem, while the resulting attacker only needs access to either the original or the reprogrammed random oracle, reducing the requirements on the underlying reduction. Second, we prove a Double-Sided EAM-O2H (DSEAM-O2H) theorem, which retains the Double-Sided idea used in the MRE-O2H theorem but removes the $q$-dependent loss, yielding a tight $O(\epsilon)$ upper bound. As applications, we revisit the security of several Fujisaki--Okamoto variants proposed by Hofheinz et al. (TCC 2017) in the QROM, namely $\textsf{U}^{\slashed{\bot}}$, $\mathsf{FO}^{\slashed{\bot}}$, $\mathsf{FO}^{\slashed{\bot}}_{m}$, $\mathsf{FO}^{\bot}$, and $\mathsf{FO}^{\bot}_{m}$, and obtain the following results: The \textsf{IND-CCA} security of $\textsf{U}^{\slashed{\bot}}$ can be reduced to the \textsf{OW-CPA} security of the underlying PKE scheme. Compared with the previous proofs by Bindel et al. (TCC 2019) and Kuchta et al. (EUROCRYPT 2020), we avoid both the square-root loss and the $q$-dependent loss in the underlying adversary's \textsf{OW-CPA} advantage. The \textsf{IND-CCA} security of $\mathsf{FO}^{\slashed{\bot}}$, $\mathsf{FO}^{\slashed{\bot}}_{m}$, $\mathsf{FO}^{\bot}$, and $\mathsf{FO}^{\bot}_{m}$ can be reduced to the \textsf{IND-CPA} security of the underlying PKE scheme. Compared with the previous proofs by Ge et al. (ASIACRYPT 2024), we reduce the $q$-dependent loss from $O(q^{1.5})$ to $O(q^{0.5})$. Assuming unique randomness recoverability, the \textsf{IND-CCA} security of $\mathsf{FO}^{\slashed{\bot}}$, $\mathsf{FO}^{\slashed{\bot}}_{m}$, $\mathsf{FO}^{\bot}$, and $\mathsf{FO}^{\bot}_{m}$ can be reduced to the \textsf{OW-CPA} security of the underlying PKE scheme. Compared with the previous proofs by Ge et al. (ASIACRYPT 2024), we avoid the $q$-dependent loss in the underlying adversary's \textsf{OW-CPA} advantage.

Oblivious Message Retrieval (OMR) enables recipients to retrieve messages from an untrusted server without revealing which messages correspond to them. OMR is useful for privacy-preserving systems such as anonymous messaging and blockchains. Existing constructions are inherently built in the public-key setting and use Fully Homomorphic Encryption (FHE) to allow a detector to scan a public bulletin board and produce a compact encrypted digest containing only relevant messages. However, this design incurs a major practical limitation: sender-published signals are large (hundreds of kilobytes), leading to significant bandwidth, storage, and on-chain costs. In this work, we explore the efficiency gains achievable by moving to a private, stateful setting, and introduce stateful OMR, a new model in which senders and receivers maintain lightweight private state to enable more efficient anonymous communication. Based on this model, we design StOMR, a protocol that significantly reduces the size of sender signals compared to prior approaches. To support the required shared state, we further introduce an OMR Key Encapsulation Mechanism (OMR-KEM), which allows users to privately establish shared state and instantiate stateful OMR without out-of-band channels. We implement StOMR in C++ and evaluate it against the state-of-the-art systems PerfOMR (USENIX Security '24), SophOMR (USENIX Security '26), and InstantOMR (USENIX Security '26). Our results show that StOMR preserves detector performance while achieving a signal size approximately 550×, 650×, and 178× smaller than PerfOMR, SophOMR, and InstantOMR, respectively.

Nonlinear functions such as sign, comparison, and ReLU are commonly evaluated in CKKS by approximating them with polynomials. The sign jumps at zero, so inputs on the two sides of zero, however close, must be mapped to outputs that differ by a constant. Comparison is the sign of a difference, and ReLU and max inherit this requirement when computed through the sign at high output precision. To distinguish inputs separated by about $2^{-p}$, polynomial approximation needs $\Theta(p)$ multiplicative depth, and we show that, in a standard model where every level must keep the values of these inputs apart above the noise, its modulus consumption grows to $\Theta(p^2)$ bits. Evaluating the functions from radix-$B$ digits avoids this cost, but existing methods extract the $u$ digits of a real-valued input one at a time, with $u$ sequential bootstrappings. We obtain all $u$ digits in parallel with a single bootstrapping: each digit is produced with an error of at most one carry from the digit below, and carry look-ahead corrects all carries in $O(\log u)$ depth. For the sign, the same carry look-ahead combines the digits directly, without recovering them. As a result, close inputs separated by about $2^{-p}$ are distinguished with $\Theta(p)$ modulus bits instead of $\Theta(p^2)$, using $O(\log B)$ depth for table lookups and $O(\log u)$ depth for carry look-ahead, at the cost of $\Theta(u)$ slots per input. Benchmarks show a $2.04\times$ speedup for coefficient-integer digit decomposition at ten radix-64 digits and a $7.83\times$ speedup for sign evaluation on 1,024 real input pairs at $2^{-60}$ separation. The gain comes from where the precision is spent: a polynomial must keep the values of close inputs apart at every level, whereas the digits take only finitely many values, so our circuit, including its bootstrapping, runs at low precision, and the output precision is raised only at the end.

Extremely Lossy Functions (ELFs) are a standard model primitive that captures many useful properties of random oracles (Zhandry, Crypto 2016). While there are many variations of ELFs with additional properties, every construction (excluding obfuscation) has followed essentially the same template of bootstrapping from a sequence of ELFs secure only against fixed-size adversaries, and every construction was based on only the exponential hardness of DDH (or $k$-Lin), an assumption that is only reasonable over elliptic curves. We introduce and construct Extremely Lossy Trapdoor Hashing (ELTDH), a stronger notion that implies all known variations of ELFs. Our construction achieves ELTDH in one go, without bootstrapping from schemes secure for only fixed-size adversaries, which makes it simpler and more efficient than existing ELFs. We assume exponential security of the small-exponent discrete logarithm, together with polynomial security of decisional composite residuosity (DCR). Exponential security is only required in the size of the secret exponent, not the size of the group, so the assumption plausibly holds for multiplication modulo $N^2$ (and for many other cryptographic groups), despite the subexponential-time discrete logarithm attacks from index calculus. Our results diversify the assumptions underlying ELFs, while also giving a simpler construction.

Established multiple-precision software generally reserves Fast-Fourier Transform (FFT) multiplication for very large operands; for example, GMP reports full-product FFT thresholds of roughly 3000--10000 limbs. Becker et al. showed that Number-Theoretic Transform (NTT) multiplication can become advantageous much earlier on Cortex-M microcontrollers. It thus becomes an interesting engineering question to check where the crossover actually takes place on a big modern CPU. Our first-generation implementation on Cortex-A76 and Neoverse-N1 shows that the crossover point is around 10k bits when using ARMv8+ with Neon, using optimized and verified code. Motivated by the tighter Barrett bound of Becker, we developed the Second implementation, which eliminates additional reductions and pushes the crossover below 5.6k bits. We integrate our multipliers into OpenSSL RSA, resulting in end-to-end speedup for the public-key operations.

The Fujisaki--Okamoto (FO) transform (Journal of Cryptology, 2013) is the standard route from weakly secure public-key encryption to chosen-ciphertext security, and it underlies many practical post-quantum key-encapsulation schemes, including ML-KEM. Security proofs for FO are set in the (quantum) random oracle models. FO uses two hash functions: the derandomization hash~$H$, which turns the base scheme into a deterministic trapdoor function (TDF) by Encrypt-with-Hash, and the key-derivation hash~$G$. We ask whether it is possible to instantiate the hash functions in the FO transform while retaining its security guarantees. While prior work mainly focused on the $H$ step, our focus is the $G$ step, and we take an underlying injective TDF as given. We first show that the message-only implicit-rejection variant \smash{$\UmIR$}, a key-encapsulation mechanism formulation of FO that follows ML-KEM's choices of rejection and key derivation, is \emph{uninstantiable} in general. Namely, assuming standard LWE and subexponentially secure indistinguishability obfuscation and puncturable PRFs, for every efficient hash function family~$G$ with superlogarithmic output length there is a one-way, perfectly correct injective trapdoor function for which the resulting KEM is not IND-CCA2 secure. We next give sufficient conditions on~$G$ to instantiate the TDF-based \emph{hybrid-encryption} formulation of FO, rather than the KEM version. To this end, we introduce \emph{distributional injective extractability} (\DINJEXT{}), a new hash function property defined relative to a partially injective ``wrapping function.'' Under this assumption relative to the FO-derived wrapping function, combined with an achievable form of universal computational extractor security (Bellare, Hoang, and Keelveedhi, CRYPTO 2013) on $G$ and suitable assumptions on the base schemes, we obtain standard-model IND-CCA2 security. As evidence that \DINJEXT{} is achievable, we show that a random oracle satisfies it for every partially injective wrapping function, and that a quantum random oracle satisfies a formulation of it for the FO wrapping function, in both cases even relative to an oblivious sampling oracle. We leave a standard-model construction open.

The practical performance of Gröbner basis implementations depends on the polynomial systems being solved. This work evaluates 20 open-source imple- mentations with Magma as a proprietary reference on systems derived from small-scale AES over GF(2). The Easy, Medium, and Hard experiments use field equations and ten input instances each, comparing wall-clock runtime, peak memory, success rate, and CPU usage. Implementations with no successful runs are excluded from subsequent experiments. In Hard, msolve and Singular’s slimgb completed all ten runs successfully, with mean runtimes of 164 and 269 seconds and mean peak memory consumption of 3693 and 4343 MiB, respectively, com- pared with 319 seconds and 16853 MiB for Magma. During these runs, msolve used an average of 13.4 CPU cores, while slimgb and Magma used about one core each. Magma had the shortest mean runtime in Medium, whereas msolve was fastest in Easy and Hard. Changing the plaintext-ciphertext pair count affected implementations differently, and runtimes varied between instances. The results show that open-source implementations can be competitive alternatives to Magma, with their relative performance depending on the input systems.

The overwhelming majority of the Keccak instances standardized and used in practice today make use of the Keccak-$f$ [1600] permutation or reduced-round versions of it. There are a few use cases where using a smaller permutation width would be beneficial, notably when one has to hash many very short messages. To address this, the present note defines instances that use the Keccak-$p$[800, $n_r = 12$] permutation, collectively under the name MiniSHAKE.

An additive positive accumulator represents a growing set by a short public digest. Each inserted element has a membership witness, which may have to be refreshed after later insertions. An execution of $n$ insertions therefore defines a labeled update vector $d=(d_1,\ldots,d_n)$, where $d_i$ is the number of strict post-insertion refreshes of the witness created at time $i$. Previous lower bounds concern scalar quantities such as $\max_i d_i$ and $\sum_i d_i$. Even when both are known, they do not determine how the updates are distributed among the labeled witnesses. Let $\mathcal T_w([n])$ be the set of left-depth vectors of inorder binary trees on $[n]$ whose right-depth is less than $w$, and define the convex upward region \[ \mathcal G_w^{(n)}:=\operatorname{conv}(\mathcal T_w([n]))+\mathbb R_{\ge0}^n. \] Our main result constrains the entire expected update vector. For polynomial-time update specifications, let $m=\Theta(1+L/\log\lambda)$, where $L$ bounds the accumulator length. For every fixed $\delta>0$ and all sufficiently large $\lambda$, \[ \mathbb E[d]\in(1-\delta)\frac{m}{m-1}\mathcal G_{m-1}^{(n)}. \] Equivalently, there is one distribution $\Pi_{\lambda,\delta}$ over feasible trees such that \[ \mathbb E[d_i]\ge(1-\delta)\frac{m}{m-1}\mathbb E_{T\leftarrow\Pi_{\lambda,\delta}}[\ell_T(i)] \qquad\text{for every }i. \] Thus the same tree distribution constrains all labeled coordinates. The region $\mathcal G_w^{(n)}$ is characterized by its nonnegative linear inequalities. If \[ V_w(a):=\min_{T:\,\max_i\rho_T(i)<w}\sum_i a_i\ell_T(i), \] then $x\in c\mathcal G_w^{(n)}$ exactly when $a\cdot x\ge cV_w(a)$ for every $a\ge0$. For arbitrary history-dependent update specifications, we establish the corresponding inequality for every predetermined efficiently computable nonnegative weight vector $a$: \[ \mathbb E\!\left[\sum_i a_i d_i\right]\ge(1-o(1))\frac{m}{m-1}V_{m-1}(a), \] together with a corresponding lower-tail bound. Indicator vectors give position-independent cohort bounds; in particular, every predetermined cohort of size $k$ has benchmark at least $(k-m+1)_+$ up to the same factor. The combinatorial basis of these results is that the temporal-blocking vectors used in replay attacks and the vectors in $\mathcal T_w([n])$ have the same upward closure. To transfer this characterization to accumulator executions, we use fractional tuple packing, interval rounding, and conditional resampling controlled by the $L$-bit accumulator state. For the vector theorem, a separating direction is computed from independent executions before the replay attack is applied to a fresh execution. At fixed width, the same tree vectors describe the coordinatewise lower boundary of online-merger update profiles. Every feasible tree vector is realized by an online merger and, through the standard Merkle-forest construction, by an additive positive accumulator.

The LLL algorithm involves reductions and swaps, corresponding to projection and ordering conditions. But the transformation $\vec{b}'_i\leftarrow \vec{b}_i- \lfloor\mu_{i,k} \rceil\vec{b}_k$ is not a general size-reduction, where $\mu_{i,k}=\frac{\langle \vec{b}_i, \vec{b}_k^* \rangle}{\langle \vec{b}_k^*, \vec{b}_k^* \rangle} $, $\vec{b}_k^*$ is the orthogonalized vector of $\vec{b}_k$, which cannot ensure $\|\vec{b}'_i\|\leq \|\vec{b}_i\|$. The condition $ (\delta-\mu_{i+1,i}^2)\|\vec{b}_i^*\|^2\leq \|\vec{b}_{i+1}^*\|^2$ for $ \delta\in(1/4, 1)$, cannot ensure $\|\vec{b}_i\|\leq \|\vec{b}_{i+1}\|$. The two drawbacks possibly result in: (1) the first vector could be longer than others, (2) some vectors could be further reduced. In this paper, we present an optimized LLL algorithm which is independent of rthogonalization and reduces the complexity from $O(n^4)$ to $O(n^3)$. By a probabilistic argument, we show the new algorithm runs in polynomial time.

While hash-based signatures such as XMSS and SPHINCS$^+$ are well-established and play a key role in post-quantum cryptography, thresholdizing them to enable use in distributed systems remains a challenge. In particular, their lack of exploitable structure prevents any algebraic attempts that are otherwise possible in the context of classical signatures such as ECDSA, Schnorr, RSA, or BLS, whereas general-purpose MPC techniques are costly in round complexity. In this work, we construct and implement the first one-round threshold protocol for XMSS and SPHINCS$^+$, with concrete parameters yielding full backward compatibility. At a high level, the secret key is shared among the signing parties while the signing algorithm is evaluated homomorphically using a threshold fully homomorphic encryption scheme. Any $t$-of-$n$ parties, via threshold decryption, can collaboratively derive the signature, which is accepted by the unmodified RFC 8391 or FIPS 205 verifier. At a technical level, we develop efficient homomorphic SHAKE evaluation over discrete CKKS for varying batch sizes. Analyzing XMSS and SPHINCS$^+$ signing reveals parallel hash computations and data-dependent selections, which we handle through batching and homomorphic lookup to obtain end-to-end circuits. Our implementation amortizes SHAKE256/256 evaluation to $3.4\,\text{ms}$ per hash and completes online threshold XMSS signing in $0.69\,\text{s}$. Threshold SPHINCS$^+$ has roughly two orders of magnitude higher signing latency but over an order of magnitude lower setup latency than XMSS.

The Hamming-Quasi Cyclic (HQC) is the Post-Quantum Cryptography (PQC) Key Encapsulation Mechanism (KEM) algorithm recently selected by the National Institute of Standards and Technology (NIST) for standardization as an alternative candidate for the KEM category. While the algorithm is mathematically robust, several studies state that the physical implementation of HQC remains vulnerable to power-based side-channel attacks (SCA). Countermeasures for such SCAs primarily focus on masking and shuffling, which severely increase hardware resources, introducing additional performance overhead. To address this problem, this paper presents a resource-efficient, constant-time hardware architecture for HQC that features a novel idle-hardware reuse strategy as an SCA countermeasure. By intentionally reusing the KECCAK hardware to generate dynamic power during decoding, the proposed architecture scrambles secret-dependent power correlations with less than 0.5% area overhead for the countermeasure logic. The complete design is fully parameterized to support all NIST security categories (HQC-128, HQC-192, and HQC-256). A prototype implementation on an Artix-7 FPGA achieves a maximum clock frequency of 139 MHz while consuming 11,489 LUTs, 6,785 FFs, and 4 DSPs. Functional correctness is verified via NIST Known Answer Tests (KATs) across Key Generation, Encapsulation, and Decapsulation operations, and Test Vector Leakage Assessment (TVLA) confirms significant suppression of side-channel leakage.

Deep learning has become the dominant method for profiled Side-Channel Analysis (SCA), successfully recovering secret keys even in the presence of strong countermeasures. Despite its efficacy, Deep Neural Networks (DNNs) are predominantly black-box in nature. Evaluators do not know what information leakages are extracted and utilized across the network's layers. Yet, understanding this leakage flow is vital for designing more resilient cryptographic implementations. Existing explainability techniques often do not provide any explanation of the leakages at specific points within a layer's feature representation. In this work, we introduce GlimpseDNN, a novel model-agnostic framework designed to provide layer-by-layer visualizations that reveal how DNNs process physical leakage traces to achieve secret key recovery. GlimpseDNN utilizes the stochastic leakage model to provide characterization of the underlying leakage in the intermediate features of each layer. A key advantage of the stochastic leakage model is its dual capability: it can learn complex leakage models and is inherently interpretable through its learned weights. We validate the GlimpseDNN framework on a simulated traces and various public datasets, including ASCADf, ASCADr, ASCADf_desync50 and ASCADf_desync100. In particular, we show that even when leakages fail to be captured in the original traces, the GlimpseDNN framework manages to find these leakages by considering the deeper layers of the well-trained DNN. This provides evaluators an alternative to glimpse the underlying leakage for identifying specific implementation vulnerabilities used by DNN, ultimately aiding in the design of more robust, side-channel-resistant hardware.

Linear tests are a basic obstacle to pseudorandom functions built from low-depth circuits and secret linear or affine maps. Ball, Ducros, Erabelli, Kohl, Resch, and Scholl left open whether their bounded-query strong-PRF candidate in $\mathrm{AC}^0[2]$ resists general non-adaptive linear tests with polynomially many chosen queries. Boyle, Couteau, Gilboa, Ishai, Kohl, and Scholl left linear-attack resistance of their Sipser-based weak-PRF candidate open. We address both questions through a common correlation argument based on rare local events. Repeated Cauchy--Schwarz reduces the original correlation to a parity correlation of indicators of substantially rarer events while preserving the independence supplied by the underlying linear forms. Pairwise independence suffices to bound the resulting parity correlation by a constant below $1$, while higher-order independence gives stronger cancellation. For the candidate of Ball et al., this resolves the open problem for arbitrary polynomially many non-adaptive queries with unrestricted linear or affine dependencies. More generally, for every fixed $a\in(0,1)$ and $q\le2^{a(\log_2\lambda)^2}$, every such linear test has bias $\exp(-\lambda^{1-a-o(1)})$. For the Sipser-based family of Boyle et al., for every fixed $0<\varepsilon<2$, with overwhelming probability over $Q\le2^{(2-\varepsilon)(\log_2\lambda)^2}$ random samples, every linear attack has bias $\exp(-\lambda^{\varepsilon-o(1)})$. This establishes linear-attack resistance throughout this quasipolynomial-sample regime. Extending the guarantee to the conjectured subexponential weak-PRF regime remains open.

Bootstrapping is the main performance bottleneck in bitwise Fully Homomorphic Encryption (FHE), and practical acceleration requires careful orchestration of the blind rotation and external product chain under GPU resource constraints. This paper presents BOLT-FHE, a GPU bootstrapping framework that emphasizes block-local execution, on-chip tiling, and a unified MegaKernel supporting both gadget decomposition and modulus raising, with optional support for a recently proposed technique (Bergerat et al, CHES 2025) based on the common mask assumption (CM packing). Our design keeps the accumulator update chain within a single thread block and fuses NTT/INTT, external products, and accumulator updates using a fixed execution template. Two compile-time parameters—WPP (warps per polynomial) and IPT (items per thread)—control multi-warp cooperation and per-thread register footprint, enabling consistent kernel structure across different parameter sets. On an NVIDIA RTX 4090, BOLT-FHE reaches 40,166 bootstrappings per second at 128-bit security, demonstrating high-throughput TFHE bootstrapping on a commodity GPU. Compared to the state-of-the-art GPU implementation VeloFHE (Shen et al, CHES 2025), BOLT-FHE achieves 1.85×–2.92× speedups with gadget decomposition. In particular, for modulus raising, BOLT-FHE improves by 2.38×–2.42× without CM packing, and by 3.17×–3.31× under the best packing configuration, reflecting the combined benefits of fused arithmetic, more regular memory access, and amortization enabled by CM packing. Overall, BOLT-FHE shows that a portable, fused-kernel organization with explicit on-chip budgeting can substantially improve TFHE bootstrapping throughput while remaining compatible with both noise management paths.

Applying a GPU to FAEST v3 signing requires more than exploiting parallel computation: challenge grinding must preserve the minimum accepting counter selected by the original signing procedure, and single-sign latency and multi-sign throughput must be evaluated under distinct execution conditions. We implement GPU-assisted challenge grinding in which the GPU filters candidates over contiguous counter ranges in parallel, while the CPU performs the final acceptance checks in increasing counter order. For multiple independent signatures, we construct a CPU–GPU hybrid pipeline with two alternating signing-state slots, allowing CPU work for one slot to proceed while the GPU batch for the other slot is executing. Across the six non-EM FAEST v3 parameter sets evaluated on the same CPU–GPU system, the CPU–GPU path has lower representative single-sign latency for four parameter sets, whereas the optimized CPU path is lower for two. The largest representative same-session CPU/CPU–GPU latency ratio is 1.602799 for FAEST-192s. For multi-sign throughput with \(B \in \{2,4,8\}\), the CPU–GPU path has higher representative throughput in 9 of the 18 parameter–batch-size combinations, while the CPU path is higher in the remaining 9 under the predefined primary aggregation rule. Correctness validation confirms that GPU-assisted challenge grinding produces the same minimum accepting counter and final signature as the reference path for the evaluated configurations. These results show that the performance effect of GPU assistance is not uniform across the evaluated FAEST v3 signing configurations and depends on both the parameter set and whether the execution targets single-sign latency or the throughput of multiple independent signatures.

When post-quantum cryptography (PQC)-based over-the-air rekeying (OTAR) is evaluated over CCSDS Telecommand (TC) and Telemetry (TM) links, omitting endpoint processing time can change not only the final transport outcome but also the protocol execution path shaped by COP-1 retransmission and CLCW return feedback. This study instantiates the P1–P2–P3 exchange of a PQC-based Space Data Link Security (SDLS) key update over a CCSDS TC/TM transport model and performs paired comparisons between a zero-processing baseline, T₀, and a processing-aware model, T₁, whose service times are measured at seven logical stages of a study-specific Triple-KEM reference implementation. The two models are compared at three observation levels—final transport outcome, canonical event path, and continuous timing—while varying processing scale, finite contact time, direction-specific loss, and schedule phase. Under the canonical schedule with measured processing at αs = 1, no final-transport-outcome discordance is observed in the evaluated BCH and LDPC(512,256) TC-only or TM-only conditions, although some paired trials follow different canonical event paths. At some predefined TM-only processing-scale points, bidirectional final-outcome discordance is observed between success and P2-stage failure. The agreement state also varies with the evaluated finite contact time, and a schedule-phase case exhibits a larger transport-completion timing difference aligned with the TM slot structure. Under the evaluated conditions, the effect of omitting processing time therefore cannot be characterized by success or failure alone and must be interpreted together with event-path, timing, contact-time, and schedule conditions.

This paper proposes post-quantum cryptography (PQC) migration decision criteria for data in national and public institutions, based on the protection requirements of the National Network Security Framework (N2SF) and the cryptographic dependencies and operational states of data. The criteria distinguish payload retention, key rewrapping, re-encryption, communication migration, and signature renewal. Required actions are separated from decisions to allow, defer, or deny execution. Completion requires consistent results for the same object and version, recovery of registered copies, and current authority. A reference implementation examined these decisions under supported conditions. In 225 policy trials, completion/read rechecking and per-stage rechecking exhibited none of the unauthorized completions or reads observed with initial-decision reuse. Nine interruption trials confirmed resumption by reconciling artifacts with records. These results support the feasibility of the criteria in the local reference environment; institutional approval, production key management, and long-term preservation continuity remain unvalidated.

X-Wing combines ML-KEM-768 and X25519 for hybrid key establishment. On Cortex-M85, we adapted the coefficient representation and storage order of an MVE NTT to the existing ML-KEM path and optimized data-format transformations and X25519 arithmetic while preserving draft-10. During encapsulation, the two X25519 results share an inversion. We compared the eight-technique integrated implementation B8 with the baseline A0 in the same executable. Across ten paired comparisons from five independent reflashes of one EK-RA8M1 board, the minimum reported cycle reductions were 18.61% for key generation, 18.89% for encapsulation, 12.25% for decapsulation reusing an expanded key, and 15.22% for decapsulation including seed expansion. Nonvolatile storage increased by 35,692 B, including a 33,024 B fixed-base table. We separately report the cost and validation of B8S, which corrects identified secret-sign-dependent operand-address selections in B8. Some key-varying tests retained timing signals after this correction. Their causes remained partly unresolved, so no whole-program constant-time pass is claimed for B8S.

With FIPS 205 standardizing post-quantum signatures and ARMv8 spanning mobile, embedded, and server platforms, fast hash-based signing on ARM has become a pressing need. Since these schemes are dominated by hash calls, hash optimization largely determines performance. K-SPHINCS+ replaces the internal hash of stateless SPHINCS+ with LSH, a Korean standard hash family. However, prior K-SPHINCS+ work provides only reference C code, and existing ARMv8 LSH implementations mainly optimize single-call latency. We present two results on ARMv8-A. First, we reimplement three published LSH optimizations in hand-written AArch64 NEON assembly: the 2019 word-permutation technique; the 2023 ARMv8 P-domain placement and LSH-256 2-way approach; and the 2024 AVX-512 word-parallel and GPU lane-batching designs. We also test whether NEON scheduling guidance from a 2022 AArch64 Keccak/SPHINCS+ paper transfers to LSH. Every variant must pass 2,063 public known-answer test vectors and a differential test suite before benchmarking. No single-message NEON implementation beats the KISA portable C code compiled with clang -O3 (0.75–0.90×). Only message-parallel batching wins: for LSH-256, hashing two or four independent messages across NEON lanes reaches 1.53–1.66× and about 2.0× the throughput of sequential C. Second, we build, to our knowledge, the first optimized K-SPHINCS+ by integrating a four-message LSH batch core into the WOTS+ chain, FORS leaf, and Merkle tree computations of the SPHINCS+ reference framework. All six parameter sets pass the framework’s tests, and all three hash backends (reference C, single-message NEON, four-message NEON) produce byte-identical signatures. On the same machine, batched K-SPHINCS+ signs 2.5–2.6× faster than K-SPHINCS+ with reference C LSH and, for the 128-bit parameter sets, 2.9–3.2× faster than the SHA-256/SHAKE256 SPHINCS+ reference implementations. All code and raw measurements are public.

MAYO is one of nine third-round candidates in NIST’s process for additional post-quantum signatures. Its third-round specification of August 2026 changed the level-1 parameters and added a hash-derived linear term Λ to the verification equation, so earlier optimised implementations no longer match it. We present an optimised NEON implementation of MAYO Round 3 for the Apple M1 and compare it with the upstream NEON code on the same machine. A generator emits the sixteen GF(16) kernels of each parameter set as assembly whose output is byte-identical to that of the upstream intrinsics. Apart from the Λ kernel, the large kernels reach 86–96% of the speed an operation-count model predicts. A transposed constant-time echelon form needs 55–70% fewer cycles than the upstream one. An eight-way interleaved AES expands the public matrices at 0.18 instead of 0.43 cycles per byte. The linear term is expanded with NEON; with our changes off, its portable-C AES derivation takes 10–22% of signing and 18–37% of verification. As medians over seven function alignments, compact-key signing is 1.99–2.12 times faster than upstream on all four sets, and verification 2.11–2.62 times. A constant-time campaign with matched null runs finds the linear-algebra tests indistinguishable from their nulls, at 25% power for a twofold dispersion. The MAYO₂ signature test differs. Verification, which holds no secret, shows a key-fixed timing effect on public data, upstream as well; the signature test does not separate it from a secret one. All measurements are on one M1 Pro.

Homomorphic encryption computes anomaly scores without exposing inputs, but released scores and decisions can reveal a private threshold. We evaluate whether output policies limit numerical threshold information while preserving existing decisions, and whether this limitation also impedes decision prediction on other inputs. Policies distinguish internal-score and released-score decisions and share decision-loss and score-distortion constraints. Thresholds were estimated in all 45 plaintext experiments combining three intrusion-detection datasets, three scoring models, and five seeds. All 45 CKKS experiments combining the same datasets, five autoencoder seeds, and three independent keys yielded threshold-containing intervals after revalidating supplied starting intervals. A 16-query cap stopped every plaintext baseline search but served only 16 of 512 separate usage requests, reducing availability. Under random splitting, released-score quantization preserved 99.864% of decisions on average while limiting numerical threshold precision. Surrogates trained on 128 decision-only responses achieved mean balanced accuracy 0.817. With training-only preprocessing and a CIC-IDS2017 weekday split, model-wise balanced accuracies were 0.816–0.911. Separating time and Flow IDs across five resampled evaluations reduced model-wise means to approximately 0.5, showing that prediction transfer depends on data splitting. Threshold-dependent reselection of quantization width changed responses that matched under fixed widths. Selected CKKS boundary tests yielded one released-decision mismatch in 57 queries. Numerical threshold information and service decision prediction therefore require separate protection goals. Output policies must assess decision preservation and response rate alongside policy selection, data splitting, and numerical boundary conditions.

q0 preprocessing verification and native HE computation verification can each succeed without establishing that their results refer to the same canonical source. To address this source mismatch across verification paths, we propose a verifier-aligned public-input transfer procedure that links heterogeneous authenticated artifacts to a single canonical-source relation. The public verifier reconstructs challenges and targets from the actual statements, roots, approved verification keys, and authenticated positions. The chunk circuits then verify the source and mask commitments together with the canonical range, sign, and partial-sum relations. The full-input implementation processes 524,288 coefficients across 128 blocks and 4,096 native-bridge chunks. Public reconstruction and verification without stored challenge caches take 184.77 seconds, with 27,345,153 B of explicit public data. In a representative-block comparison for the same relation, sharing duplicate hash, range, and sign computations reduces the number of constraints by 33.53% and proving time by 31.10%, while preserving the proof-body size. In contrast, three upstream proof artifacts account for 88.44% of the total public data. These results show that eliminating redundant circuit computations is effective for reducing prover-side cost, whereas the dominant public-data cost originates from separate upstream proof artifacts. Prover computation and public-data size should therefore be treated as distinct optimization targets in source-binding verification. This work specifies the common-source relation between heterogeneous HE verification results and evaluates its implementation at full input scale.

The quantum threat to traditional public-key cryptography makes migration to post-quantum cryptography necessary. During migration, the presence of both post-quantum and traditional (PQ/T) algorithms does not establish that their outputs jointly determine a key or verification decision. We propose HyBind, an intraprocedural Python source-analysis framework using registered API contracts. HyBind traces component secrets to returned keys and checks whether signature acceptance requires both verifiers to succeed. Function-return and execution-effect checks account for alternative outcomes and changes to local bindings. Two internal presence-based heuristics give identical decisions for joint versus omitted secret contribution and AND versus OR verification, while HyBind distinguishes these structures. All 50 controlled fixtures match their specified outputs with the annotation assumption enabled. A separate suite of 33 programs, including 15 using native cryptographic APIs, matches its specified positive-finding counts in both settings. Native runtime checks exercise ML-KEM/X25519 key derivation and ML-DSA/Ed25519 acceptance. Relaxing return or effect requirements admits traditional-only key results as hybrid findings in the evaluated cases. HyBind provides the contributing calls and outcome evidence needed to review whether an individual traditional invocation participates in a PQ/T hybrid.

We show that the recent construction of witness encryption (Hair and Sahai, arXiv:2609.18275v1) is a public-coin extractable witness encryption scheme under the Knowledge of Orthogonality Assumption, or KOALA for short (Buellens-Wee, PKC 2019). As an immediate application, we obtain public-coin differing-input obfuscation (diO) from KOALA and indistinguishability obfuscation (iO).

Migration to post-quantum cryptography requires knowing not only which cryptographic libraries are present on a system, but which algorithms are actually executed at runtime. Static binary analysis answers the former question; the latter requires dynamic observation. We present a runtime cryptographic discovery system for Linux, built on eBPF user-space probes, that detects classical and post-quantum operations as they execute. Because key generation and encapsulation consume fresh randomness, the system treats randomness observations as temporal anchors and correlates them with the cryptographic calls that follow in the same process, producing a stream of confidence-scored events for a runtime cryptographic inventory. An ablation over three detection configurations shows that randomness alone is not a sound detector, while API detection reaches perfect precision and recall on classical and ML-KEM workloads with no false positives on random-only negatives, and the randomness anchor raises the confidence of those detections without adding any. A single probe set also covers native post-quantum support in current OpenSSL releases. Median detection latency is 28 μs (P99 48 μs), largely insensitive to a four-round tuning sweep, with overhead of 14–18% on a key-generation-bound workload, full detection under sustained and concurrent load, and stable behavior over a one-hour run. A case study across nine application cases drawn from or paired with the QED datasets shows where static and runtime views agree and how probe coverage determines what runtime discovery can observe.

Certificate issuance and per-connection signing impose different costs in TLS 1.3, and authentication cost can change depending on how signature algorithms are assigned to Root, Intermediate, and Leaf roles. PQC migration should therefore consider not only algorithm performance, but also role placement, certificate structure, network conditions, and server load. We evaluate all 13³ role placements formed by 13 signature parameter sets while holding the algorithm composition fixed and changing only the role order. The evaluation covers cryptographic operations, certificate issuance, path validation, TLS authentication, mixed traditional–PQC chains, network profiles, session resumption, and concurrent load. Across 286 groups containing three distinct algorithms, the median maximum/minimum ratios are 2.085 for TLS latency, 4.310 for Certificate body size, and 4.551 for path validation. Thus, role placement alone can produce about a two-fold difference in TLS latency and more than four-fold differences in certificate size and path-validation cost. Direct Root–Intermediate swaps yield a median TLS ratio of 1.003, whereas swaps involving the Leaf yield 1.775–1.788, indicating a stronger influence of Leaf placement. In eight ML-DSA-65/SLH-DSA-SHAKE-192s placements, two candidates remain nondominated when only the Certificate message is considered, but only one remains when the Leaf signature in CertificateVerify is included. This shows that certificate size alone may not represent the transmission cost of the full TLS authentication path. PQC certificate-chain design should therefore consider role-specific computation and transmission costs under the intended network and load conditions.

The command and authentication channels of unmanned systems (UAVs and UGVs) still rely on classical public-key cryptography, which large-scale quantum computers threaten. Migrating these channels to post-quantum cryptography (PQC) is therefore imperative, yet PQC keys and signatures are substantially larger, and sometimes slower, than their classical counterparts, while command links are tightly constrained in message rate, maximum transmission unit (MTU), latency deadline, and bandwidth. Whether a given PQC algorithm fits such a budget, and how to mitigate it when it does not, remains an open and practically important question. This paper studies the application of Korean PQC (KpqC: HAETAE, AIMer, SMAUG-T, NTRU+) to the authentication and key-establishment path of ROS2/DDS-Security, framed as a command-channel size-latency budget problem. We keep KpqC as the subject of study while using the NIST standards (ML-KEM, ML-DSA, SLH-DSA) as a familiar yardstick and classical ECDSA/ECDH as the migration baseline, giving a classical→NIST→KpqC three-way comparison on a single, consistent testbed. We define a feasibility envelope that maps each algorithm to the channel conditions it can meet, and we validate it with authentication-handshake measurements over emulated constrained links on a two-node testbed. Our results yield an application guideline indicating which KpqC candidate is admissible for which command-channel budget.

Post-quantum migration is no longer only an algorithm problem but a deployment problem: standardized schemes must be dropped into real protocol stacks, on real (often resource-constrained) targets, without giving up memory safety. The Korean Post-Quantum Cryptography (KpqC) competition standardized two KEMs (NTRU+, SMAUG-T) and two signature schemes (HAETAE, AIMer), distributed as memory-unsafe C. Building on our native-Rust KpqC implementation, we expose the schemes through a single pluggable provider and evaluate them across three deployment front-ends: (i) a rustls TLS 1.3 key-exchange group, (ii) an Open Quantum Safe (OQS) compatible C ABI that lets the native-Rust code stand in for the C reference behind the liboqs API, and (iii) an analytical CCSDS/SDLS satellite constrained-link model. All three are demonstrated end-to-end: a complete TLS 1.3 handshake using only a KpqC KEM for key establishment, a C program that drives the Rust KEMs and signatures through the OQS-shaped ABI, and a fragmentation/latency analysis over illustrative LEO/GEO link profiles. This work extends our earlier C/OQS-OpenSSL TLS benchmark of KpqC (Sim et al.) with a memory-safe Rust implementation, an explicit memory-footprint axis, and deployment breadth beyond localhost/LAN. On a constrained space link, the compact SMAUG-T key exchanges (SMAUG-TiMER 1280 B, SMAUG-T1 1344 B) are smaller and faster than ML-KEM-768 (2272 B). All seven KpqC KEM parameter sets and four signatures (AIMer and HAETAE modes 2/3/5) are demonstrated across the three front-ends. We further give NTRU+ a full memory-optimized build for all three sets, byte-identical and KAT-verified, that cuts peak stack by up to 25% at no measurable time cost (≈ 0.99× handshake latency).

Hybrid key exchange and Composite ML-DSA signatures in TLS 1.3 split one operation into a classical component and a post-quantum cryptography (PQC) component that do not depend on each other. Using a cryptographic workload of the TLS handshake rather than a full TLS connection, this paper measures whether running the two components at the same time on two pthread worker threads reduces latency compared with sequential execution. We evaluate the three ECDHE–ML-KEM groups of RFC 10024 with the matching Composite ML-DSA schemes, each with server authentication and mutual authentication (mTLS). Parallel execution keeps the order of operations, overlaps only the component pair of one operation, and is timed with all synchronization cost included. In an ARM and an x86 environment, parallel execution was faster in all six conditions, with speedups of 1.157×–1.281× and 1.041×–1.235×. The gain was large in the signature stages, where the two components take similar time, and small or negative in the key exchange stages, where one component dominates. In a low-power x86 environment, however, the same source code was slower in all six conditions (0.800×–0.917×). There, the overhead of waking and waiting for the worker threads exceeded the time saved, and it grew with the stage length, so a fixed cost per pair does not explain it. Independence of the components therefore does not guarantee a gain, and parallelization should be applied only after measuring in the target environment.

Cryptographic tokens that retain RSA credentials for compatibility with existing authentication systems require efficient private-key operations on small processors. Cortex-M0+ (M0+) lacks native widening multiplication, whereas Cortex-M3 (M3) provides it with operand-dependent latency. We optimize Montgomery multiplication and squaring using 15-bit limbs and integrate the kernels into RSA-2048 and RSA-3072 private operations based on the Chinese remainder theorem (CRT). On M0+, a wrapped sum and accumulated block quotients enable exact carry recovery. The squaring schedule integrates square and reduction columns without storing the complete square. On M3, we retain the established half-diagonal representation and double each buffer limb when it is first incorporated into Montgomery reduction, eliminating a separate buffer traversal. We establish accumulator bounds for exact Montgomery digit and carry recovery in both schedules. At operand widths of 1024 and 1536 bits, the M0+ representation and register mapping reduce Montgomery multiplication and squaring cycles by 12.60% to 13.11% against blocked two-word controls. The M3 schedule reduces Montgomery squaring cycles by 2.12% to 3.08% with half-diagonal initialization and triangular accumulation held fixed. Kernel replacement in otherwise unchanged RSA implementations reduces warm CRT cycles by 12.59% to 12.80% on M0+ and by 1.69% to 2.39% on M3. Our M3 Montgomery multiplication also uses 31.47% fewer cycles than a reproduced number-theoretic transform (NTT) implementation for 2048-bit operands with matched integers and canonical outputs.

A pseudorandom code (PRC), introduced by Christ and Gunn (Crypto 2024), is an error-correcting code whose codewords look uniformly random to anyone without the secret key. PRCs not only are natural cryptographic objects to study in their own right, but also have interesting applications such as undetectable watermarking of AI-generated content. Previous PRC constructions have centered on Learning Parity with Noise (LPN), often combined with additional assumptions. In particular, the original PRC of Christ and Gunn is based either on standard LPN together with the planted XOR assumption of Agrawal et al. (Crypto 2024), or on subexponential LPN. In this work, we construct PRCs from Learning with Errors (LWE), providing an alternative foundation for PRCs. Our construction is simple: a codeword is the one-bit rounding of an LWE sample, masked by a random string. The construction can be easily understood as an LWE analogue of the PRC of Christ and Gunn. Indeed, like theirs, it is based either on standard LWE together with the hardness of the planted $t$-SUM problem of Agrawal et al., or on subexponential LWE. However, as the rounding is not linear, its robustness is less straightforward, and we prove it using Fourier analysis.

Some asynchronous verifiable information dispersal (AVID) and data-availability protocols certify that a disperser's message is available once $2f+1$ of $n=3f+1$ parties, at most $f$ of them Byzantine, attest that they hold their erasure-coded fragments, and defer reconstruction and validation of the encoding until later. We call this design pattern reconstruct-later AVID. If the $f$ Byzantine attesters later withhold their fragments, reconstruction must succeed from the $f+1$ honest fragments that remain, and a Byzantine disperser chooses which $f+1$ after seeing the encoding symbols assigned to the honest parties. We call a subset of fragments that does not determine the message bad. Raptor codes are a tempting choice here: with modest coding overhead they have very small decoding-failure probability under random erasures, and a preliminary Walrus design and an earlier Walrus testnet used RaptorQ in this way. We show that the pattern is insecure with the standardized Raptor codes R10 (RFC 5053) and RaptorQ (RFC 6330). For a message of $K$ input symbols, every assignment of R10 encoding symbols to the honest parties contains a bad $(f+1)$-subset whenever $K>\lfloor\log_2(2f+2)\rfloor$, and every RaptorQ assignment whenever $K>7H_{\mathrm{HDPC}}+\lfloor\log_2(2f+2)\rfloor$, where $H_{\mathrm{HDPC}}$ is RFC 6330's number of high-density parity-check symbols. Under slightly stronger conditions, randomized polynomial-time algorithms find such subsets, and an implementation of the RaptorQ attack defeats an RFC 6330 decoder on every adversarial subset tested. The key ingredient is the Plotkin bound, which forces a nonzero input whose encoded image has low Hamming weight. For RaptorQ at $n=3f+1$, an empirical attack over $\mathbb{F}_{256}$ succeeds at every tested $f$ from $9$ to $45$ with $K=f+1$, far below the $f=77$ at which the bound above first applies, and empirical attacks over $\mathbb{F}_4$, $\mathbb{F}_{16}$, and $\mathbb{F}_{256}$ succeed at values of $K$ well below that bound. For R10, a smaller $K$ does not help: for every standardized $34\le K\le8192$ and every $n$ with $3f+1\le n\le4f\le65520$, explicit certificates give a bad subset for every assignment to the honest parties when the encoding-symbol identifiers (ESIs) are $0,1,\ldots,n-1$, and with probability at least $1/2$ when the ESIs are uniformly random. Benchmarks of our implementations show that the MDS alternative costs little: in our parameter regime, Reed-Solomon is often faster than, and never more than a small constant factor slower than, either R10 or RaptorQ, for both encoding and decoding.

Consider an asynchronous network of $n$ validators in which Byzantine validators hold less than one third of the stake. In erasure-coded reliable broadcast, validators relay fragments of the sender's message. A validator's relay-upload cost is the amount of fragment data it transmits outside the sender's initial dispersal. Assigning each validator a number of fragments proportional to its stake makes the heaviest validators relay far more data than the rest. We show that this imbalance is unnecessary. We give Balanced CT and Balanced MiniCast, adaptations of Cachin-Tessaro (CT) and MiniCast (Locher and Shoup, EUROCRYPT 2025) that retain stake-weighted voting but assign one fragment to each validator, giving every honest validator the same relay-upload bound. Their maximum relay-upload costs depend on how few validators can exceed one third of the total stake for CT, or two thirds for MiniCast. Stake skew can amplify MiniCast's advantage beyond the approximately twofold improvement in equal-stake networks. For the real-world Monad distribution with $n=200$, the leading maximum relay-upload costs, as multiples of the message size, are approximately $72.2$ for CT with proportional assignment, $8.7$ for Balanced CT, and $2.2$ for Balanced MiniCast. The balanced constructions pay for their low maximum cost with a higher total relay-upload cost. To reduce that total while retaining a prescribed maximum-cost bound, we give a new Capped Swiper heuristic. On eight real-world stake distributions, with at most $4n$ fragments per code, it lowers total relay-upload cost by 19-81% for CT and 16-71% for MiniCast relative to their balanced counterparts, while keeping maximum relay-upload cost at most 10% higher. We also give sender-aware variants of both constructions in which the sender relays no fragment data, reducing its per-broadcast burden.

Quantum one-time programs (Broadbent, Gutoski and Stebila, CRYPTO 2013) or OTPs for short, enable a functionality to be encoded into a quantum token that can be evaluated on a single chosen input and then becomes unusable. While powerful, this primitive is inherently stateless and tied to a setting in which a quantum token needs to be issued and distributed for every single evaluation of a circuit. This raises a natural question: can the one-time computation paradigm be extended to richer, stateful forms of controlled access, and would such an extension offer inherent advantages beyond standard OTPs? We introduce query-limited RAM programs (QLPs), a RAM-generalization of QOTPs that supports structured, stateful computation under bounded or policy-driven access. QLPs allow controlled sequences of evaluations while preventing adversarial forking or rollback of computational state. This enables new applications beyond stateless one-time programs, including quantum tokens for Turing Machines whose size depends only on code length (and not runtime), transferable $k$-time or budget-limited programs, and low-communication mechanisms for delegating computation in settings such as Software-as-a-Service. To construct QLPs, we introduce one-shot programs, unifying one-shot signatures (Amos, Georgiou, Kiayias and Zhandry, STOC 2020) with the single effective query paradigm (Gupte, Liu, Raizes, Roberts and Vaikuntanathan, STOC 2025). We prove that one-shot programs generically imply query-limited programs, demonstrating that the strengthened unclonability guarantees of one-shot signatures translate into enhanced functionality. Along the way, we clarify the relationship between signature-token primitives and quantum one-time programs via generic constructions, essentially showing that one-time signing programs imply one-time general computation.

We study cryptographic primitives that are both locally computable (i.e., in $\mathrm{NC}^0$) and exponentially secure. For pseudorandom generators (PRGs) and universal one-way hash functions (UOWHFs), we further require linear stretch and linear compression, respectively, which is essentially the best one can hope for in this setting. Such primitives simultaneously achieve an extreme level of security and efficiency: each output bit inspects only a constant number of input bits, while each input bit buys a constant amount of security and expansion/shrinkage, in an amortized sense. We refer to such primitives as \emph{bitwise optimal}. We prove that bitwise-optimal PRGs and UOWHFs can be obtained from \emph{any} exponentially secure one-way function (OWF) in $\mathrm{NC}^0$, thereby establishing an equivalence between these three primitives in the bitwise-optimal regime. Notably, an analogous equivalence is not known in the exponential-security regime for general, unrestricted cryptographic primitives without imposing an additional regularity condition. Our results combine the machinery of the author (Applebaum, FOCS'17) with new structural results on locally computable functions that may be of independent interest. We prove a sparsification theorem that reduces the output length of any exponentially secure local OWF to $O(n)$ while preserving exponential hardness, an input-locality reduction that bounds the number of outputs affected by each input bit, and a structural theorem showing that functions with bounded input locality are typically almost regular. Together, these ingredients remove the regularity assumption required by previous constructions and yield a non-black-box transformation from exponentially secure OWFs in $\mathrm{NC}^0$ to bitwise-optimal PRGs and UOWHFs. As an additional contribution, we prove a projection-based compression theorem for locally samplable sources.

In anonymous broadcast encryption, a ciphertext hides both the message and the set of recipients. In the general case, a lower bound of Kiayias and Samari forces the ciphertext to grow linearly with the number of recipients, a bound already met by the trivial per-recipient solution. The bounded universe is the setting where anonymous broadcast becomes concise, even asymptotically optimal and as efficient as the underlying public-key encryption. Far from a mere restriction, it is the building block for anamorphic communication against a dictator, where one must reach many (but boundedly many) recipients covertly, as put forth in the DPPY scheme at Eurocrypt '25. DPPY is, however, secret-key anamorphic encryption, where the broadcast layer itself must be hidden. Even a public-key variant does not suffice against a strong adversary, since a per-recipient public key lets a dictator ask for the matching secret key. This motivates hiding identities directly, with no recipient public key published, leading to identity-based anonymous broadcast in the bounded model, the focus of this paper. Technically, projective sampling (Ling, Phan, Stehlé and Steinfeld, LPSS, CRYPTO ’14), the tool underlying concise anonymous broadcast encryption, offers no key extraction: private keys cannot be produced from a projected key fixed in advance. We introduce trapdoor projective sampling that reverses the order of key generation in projective sampling: projected keys are fixed first as hashes of identities and compatible private keys are then preimage-sampled with a trapdoor. Adding a trapdoor is always a challenging objective, and we achieve it by showing that the LPSS projection space can be made far narrower - from m×(m−n) down to m×2n - without breaking the k-LWE security argument, and it is exactly at this width that the projection matrix can be generated with a trapdoor. We formalise the notion of trapdoor projective sampling with new security requirements, instantiate it from k-LWE, and obtain an identity-based anonymous broadcast whose ciphertext is as in LPSS, DPPY schemes. We also extend it to an unbounded identity universe under static corruption, with target sets kept bounded and adaptive.

Shmueli and Zhandry introduced permutable pseudorandom permutations (PRPs) and used them to construct trapdoor permutations with a full message domain but a sparse public-key space. We extend this approach to construct puncturable trapdoor permutations with full message and per-instance key domains in the common-reference-string (CRS) model. Our construction assumes a secure permutable PRP for general swaps, indistinguishability obfuscation, and an injective length-doubling pseudorandom generator, all secure against polynomial-time adversaries. Instantiating the underlying permutable PRP from indistinguishability obfuscation and one-way functions requires subexponential security. A one-time setup produces a CRS and a master trapdoor. For every honestly generated CRS, every bit string of the prescribed key length indexes a permutation of the full message space, allowing uniform public-key sampling without validation or rejection. The master trapdoor derives an inversion trapdoor for every key. The family supports two-level puncturing: the master trapdoor can be punctured at a key, and an individual trapdoor can be punctured at an output. For a uniformly sampled challenge key and output, recovering the missing preimage remains hard even when both punctured trapdoors are revealed. To our knowledge, this is the first family combining these full-domain properties, master trapdoor derivation, and two-level punctured security. We give three applications. In the random-oracle model, the family yields deterministic identity-based encryption with zero ciphertext expansion and adaptive weak-source pseudorandomness under a computational hardness condition on message sources. Security holds even given a key that decrypts every ciphertext except the challenge under the selected identity. The family also yields identity-based signatures with perfect uniqueness and adaptive unforgeability in the random-oracle model. Finally, puncturable trapdoors give a direct construction of hard-on-average End-of-Line instances, establishing PPAD hardness without passing through Sink-of-Verifiable-Line.

In FHEW/TFHE, a programmable bootstrap evaluates an arbitrary function of the encrypted message, encoded as the \emph{test polynomial} of a blind rotation. We work in a prime-power cyclotomic ring whose prime is the plaintext modulus $p$ (a \emph{design choice} that leaves the ring degree free as a security parameter) and compare the \emph{Single-Value Mode} (SVM), one rotation per function, with the \emph{Multi-Value Mode} (MVM), one \emph{function-independent} rotation shared by all. Factoring the test polynomial as $v^*_f = \mathfrak B^*_f\cdot \mathfrak w$, the function carried by the dual module and the rotated factor by the torus, lets a single hypothesis (a centered accumulator error of \emph{arbitrary} covariance $G$) cover both modes: the two variances are values of one $G$-form, and their ratio is the exact amplification. The $f$-independent factorizations are then parametrized by a non-zero ring element, the cofactor, and by the integer lift of the table: at a random lift the cofactor is chosen by a shortest-vector problem for an explicit quadratic form, then the lift by a closest-vector problem of rank $p-1$. In the spherical model that form is a trace norm and two designs compete: the canonical cofactor, of noise cost $p(p+1)/6$, and the pivot, which reads the integer table itself at noise cost $2p$, at a random lift; the optimized lift then favours the canonical cofactor on the generic tables. Under the other natural covariance, the block Laplacian, it is optimal for every $p$. Both cofactors are measured, in the key-noise regime, on a complete implementation, publicly available.

The one-way to hiding (O2H) theorem and its variants, which bound the distinguishing advantage in terms of the one-way advantage, are widely used in security proofs in the quantum random oracle model (QROM), particularly for key encapsulation mechanisms (KEMs). However, existing O2H bounds typically incur a security loss depending on the adversary's oracle query depth $d$ (i.e. the number of sequential layers of parallel queries), which can make both computational and information-theoretic bounds in KEM security proofs less tight. In this work, we establish a generic amplitude-amplification-based technique to many O2H variants to remove their depth-dependent factors by these theorems in the advantage bounds.This covers the Semi-Classical O2H (SC-O2H) [Ambainis et al., CRYPTO 2019] and Measure-Rewind-Extract O2H (MRE-O2H) [Ge et al., ASIACRYPT 2024] theorems, in which the constructed one-way adversaries have access to an indicator oracle $\mathbf{1}_S$ that checks whether the input is a valid solution to the one-way game. We identify conditions under which our enhanced O2H theorems can replace the original O2H theorems in existing security proofs. These conditions hold for a range of security proofs, including IND-CCA security proofs for KEMs obtained from variants of the U transformation in the Fujisaki-Okamoto (FO) framework. Applying our enhanced theorems in these proofs yields the following improvements in the depth dependence of security bounds: - When the one-way advantage is bounded information-theoretically, our technique eliminates the depth-dependent factors with only a constant-factor loss in the security bound. - When the one-way advantage is bounded by computational hardness assumptions, our technique eliminates the depth-dependent factors $d$ for SC-O2H and $\sqrt{d}$ for MRE-O2H, at the cost of increasing the constructed one-way adversary's running time by a factor that is only of the order of the square roots of the eliminated losses, namely $O(\sqrt{d})$ for SC-O2H and $O(\sqrt[4]{d})$ for MRE-O2H.

A succinct argument for machine execution convinces a verifier that a program compiled for a real instruction set ran correctly, with a proof far shorter than the execution and a check far cheaper than replaying it. We present Ziren, a production zkVM for MIPS32: it proves 77 user-mode integer instructions of MIPS32r2 and has proved Ethereum mainnet blocks end to end in production. Ziren is a CPU-less chip architecture: each executed instruction is one row of its opcode's chip. Each shard is proved by one lookup argument for all of its buses and one zerocheck for all of its constraints, and the claims on its tens of thousands of columns of differing heights are reduced by a jagged sumcheck to a single evaluation, opened by one batched WHIR proof. A recursion tree composes the shard proofs under an enumerated allowlist of verifying keys, and the determinism of 57 of the core machine's 62 chips (all but three preprocessed tables and two SHA-256 control chips) is extracted mechanically, as Lean 4 theorems, from the same constraint description the prover evaluates. On a configuration that precedes four later changes, proving throughput reaches up to 7.3 MHz on one NVIDIA RTX 5090 and scales horizontally across GPUs, reaching 24 MHz on four. Each proof stage of the analysed schedule has more than 100 bits of interactive soundness, and 93.5 bits of composite security over a block's tree of about 150 proofs. The end-to-end statement is conditional: it assumes round-by-round knowledge soundness of every node, compatibility of the composed extractors, that the recursion programs, which are not extracted, enforce the compose relation, and a property of the cross-shard digest to which we assign no value; identifying the trace with an execution also needs determinism of the two SHA-256 control chips and real-row exhaustiveness. All 104 extracted determinism theorems are proved in Lean 4: a propagation analysis derives every output column, and the derivation is replayed as step lemmas over gadget theorems proved once.

End-to-end cycle counts quantify lattice key-generation time on a microcontroller, but not which implementation decisions create that cost. We develop a controlled attribution method for public structure, candidate admission, and transform lifetime: how public data are organised, when candidate acceptance is checked, and whether transformed secret state is retained or reconstructed. On a fixed STM32L476RG Cortex-M4 target, paired runs within one executable keep the relevant secret, accepted candidate, or output key unchanged; separate measurements record resource effects. In our Bos-based structured-LWR implementation, reorganising public data exposes expansion and multiplication cost, and same-key, first-attempt comparisons show nearly additive admission and lifetime effects. We then test whether these explanations transfer across algorithms and rejection structures. In ML-KEM-512, whose KeyGen has no candidate rejection, retaining the secret's NTT-domain representation reduces cycles; a pre-specified ML-KEM-768 test preserves this direction but shows that the saving does not scale with module rank alone. HAETAE-5 tests both decisions inside a retrying KeyGen. Early checking stops rejected candidates before matrix computation, whereas deferred checking repeats matrix work across attempts and, under recomputation, rebuilds transformed secret state. The interaction grows with the retry count, while retention saves cycles at the cost of a larger KeyGen frame. Together, these experiments establish a compositional account of KeyGen cost: public structure defines the downstream computation for each candidate, while candidate admission and transform lifetime determine how many candidates execute it and how often reusable transformed representations are rebuilt. These relations yield directional predictions across the tested KeyGen structures, with paired measurements quantifying their cycle and storage consequences.

For $N$ a power of $2$, the negacyclic number-theoretic transform (NTT) maps a degree $N-1$ polynomial to its evaluations at the $N$ primitive $2N$th roots of unity. In-place butterfly algorithms such as Cooley-Tukey and Gentleman-Sande compute the negacyclic NTT in $O(N\log N)$ time and output the evaluations in a specific, standard order. We give in-place butterfly algorithms for the negacyclic NTT and its inverse that instead output the evaluations in an automorphism-compatible order. These algorithms have the same structure as Cooley-Tukey and Gentleman-Sande, differing only in their precomputed twiddle factors. Our automorphism-compatible butterfly algorithms are applicable to the packed fully homomorphic encryption (FHE) schemes CKKS and BGV/BFV, where the negacyclic NTT is a major component of ciphertext arithmetic. Using our automorphism-compatible butterfly algorithms, Galois automorphisms can be applied to ciphertexts stored in double-CRT format via a simple cyclic shift or adjacent-pair swap of the data. This is contrast to butterfly algorithms currently used that output in the standard order, where applying an automorphism requires performing an arbitrary-looking permutation of the stored data. Our automorphism-compatible butterfly algorithms remove the need for a dedicated automorphism functional unit used in FHE hardware accelerators.

Explicit equations for the locus $\mathcal{L}_n$ of genus-two curves with a maximal degree-$n$ elliptic subcover have been computed only for $n \le 5$, and by elimination, whose cost is not predictable in advance. The degree formula of [22] changes this. It gives $\deg_w F_n = k(H_{n^2}) - 10\,\nu(n)$ in closed form, and with it a reduced monomial support for the associated Humbert modular form $G_{n^2}$, so that the reconstruction becomes a determined linear problem whose every dimension is known before any computation begins. We carry this out for the first new case it opens, discriminant $36$: we determine $k(H_{36}) = 720$, $\nu(6) = 12$, $\deg_w F_6 = 600$ and an admissible modular basis of size $41962$, and we compute the four Siegel generators explicitly along Kumar's rational parametrisation of $H_{36}$, obtaining in particular a complete factorisation of $\chi_{10}$ whose factors recover the degenerate loci of the family from the modular side. We then draw the consequences for isogeny-based cryptography. The equation $\overline{F}_n$ decides optimal $(n,n)$-splitting at every point of the moduli space in characteristic $p$, with no hypothesis on the Newton polygon; this is asserted but not proved in the cryptographic literature, and the available proof excluded exactly the superspecial locus where the question is asked. The weight $k(H_{n^2})$ bounds, unconditionally and with explicit constants, the number of superspecial nodes that detection at level $n$ adds to the target set of the best known attack in dimension two. And the same torsion count $\nu(n)$ that appears in the degree formula governs the cost of both known detection routes, which places a barrier on raising the level and singles out $n = 6$ as the one case where a new equation can matter in practice.

In the random oracle model (ROM), proof of work (PoW) serves two roles in the Fiat–Shamir transformation. First, in challenge grinding, the prover must solve a puzzle for each candidate challenge, which amplifies soundness and reduces proof size and verifier time. This requires a non-amortizing PoW: computing $k$ distinct accepted puzzle–solution–proof triples costs, in expectation, roughly $k$ times the work of computing one. Second, PoW can prevent diagonalization attacks, in which the statement's circuit computes its own challenge. The XFS transformation of Arnon and Yogev (CRYPTO 2025) uses a strong PoW: an adversary that does substantially less work than the honest prover solves a random puzzle with only negligible probability, even after bounded preprocessing. Can a single PoW be both strong and non-amortizing? We prove that it cannot, whenever the verifier is sufficiently cheaper than the prover. Our main technical tool converts computational uniqueness into statistical uniqueness without increasing verifier query complexity. Combined with the search bound of Guan, Riazanov, and Yuan (CRYPTO 2025), which builds on Smyth (STOC 2002), it resolves their open question. To overcome this barrier, our XFS-with-grinding transformation for relativized $\Sigma$-protocols composes a strong PoW with a non-amortizing one. The resulting non-interactive argument retains the soundness amplification of grinding and the security guarantee of XFS in the relativized ROM, with additive prover work for the two PoWs.

In this paper, we present an algorithm for solving the Lattice Isomorphism Problem between input lattices that are isometric to the Construction A lattice of a certain code C. Our algorithm is a direct extension of a method due to Ducas and Gibbons (PKC 2023). We prove that the run time of our algorithm is $2^{O(n)}$ and that its success probability is $1+o(1)$ over a random choice of C. Crucially, our method works when the hull of C has arbitrary dimension while the method of Ducas and Gibbons is restricted to the case of a trivial hull.

Cryptographic security proofs often involve an adversary interacting with a larger, keyed oracle that consists of (potentially exponentially) many independent instances of a smaller, base oracle. Examples include ideal ciphers, which provide access to an independent random permutation for each key, and random oracles, which provide an independent random bit string for each input. However, showing quantum indistinguishability between two such keyed oracles can be tricky, since a single query made by an adversary may involve a superposition that covers all instances of the base oracles simultaneously. In this paper, we establish a generic indistinguishability lifting theorem of the following form: if the two base oracles are indistinguishable under quantum queries, then their corresponding keyed oracles are too, up to an O(q^2) multiplicative loss in distinguishing advantage, where q is the number of queries made by the adversary. Our lifting theorem applies to both statistical and computational settings, and to oracles that are stateful as well. It is also optimal in that it matches the obvious Grover search attack for a certain (contrived) choice of oracles. As an immediate application, we extend Carolan's compressed permutation oracle to an efficiently implementable compressed ideal cipher, and use it to prove preimage resistance of the Davies-Meyer compression function in the quantum ideal cipher model. Thanks to our lifting theorem, the soundness of our compressed ideal cipher reduces to that of Carolan's oracle, and any further improvement on the latter would automatically carry over to the former. As our second application, we give a modular construction that doubles the message length of any quantum-secure strong pseudorandom permutation. Along the way, we show that an existing two-round tweakable Feistel construction is indistinguishable from a random permutation under quantum bidirectional queries. This is done via a dedicated polynomial-method argument, which may be of independent interest.

We present $\mathsf{ATLAS}$, a lattice-based digital signature scheme built on the Fiat--Shamir with aborts paradigm, with security based on the hardness of the Module Learning with Rounding ($\mathsf{MLWR}$) problem. Unlike $\mathsf{Dilithium}$'s $\mathbf{t} = \mathbf{As}_1 + \mathbf{s}_2$ construction or $\mathsf{HAETAE}$'s bimodal, hyperball-uniform instantiation, $\mathsf{ATLAS}$ derives its public key via deterministic rounding, $\mathbf{t} = \lfloor \tfrac{p}{q}\mathbf{As}_1 \rceil$, eliminating the error term $\mathbf{s}_2$ and the explicit noise sampling it requires. This reduces key-generation cost and secret-key storage, and removes a component that both $\mathsf{Dilithium}$ and $\mathsf{HAETAE}$ would otherwise need to support, while keeping $\mathsf{ATLAS}$ structurally close to $\mathsf{Dilithium}$ to inherit its well-studied design and cryptanalytic track record. $\mathsf{ATLAS}$ targets three classical security levels, 128, 256, and 512 bits, using the smallest feasible ring degree $n$ and challenge weight $\kappa$ for each, with module dimensions $(k,l)$ tuned per level. To our knowledge, this includes the first \mlwr-based signature parameter set at the 512-bit level. $\mathsf{ATLAS}$ further adopts power-of-two moduli (e.g., $q=2^{23}$, $p=2^{18}$), replacing modular reduction with bitwise operations and removing rejection sampling from key parts of the scheme. Since such moduli preclude conventional NTT-based multiplication, we design a hierarchical Toom-Cook/Karatsuba decomposition with degree-8 schoolbook multiplication as its base case, accelerated via AVX2 vectorization and strided memory access. Finally, $\mathsf{ATLAS}$ supports both $\mathsf{SHAKE}$ and $\mathsf{KDF-SM3}$ as interchangeable symmetric back-ends, and we quantify the overhead of the $\mathsf{SM3}$-based instantiation relative to $\mathsf{SHAKE}$.

In this paper, we propose an understanding of classical Sigma protocols (as denoted by $\Sigma$-protocols in the literature) through the lens of the MPC-in-the-head (MPCitH) paradigm. We seek not to construct new schemes, but to build a formal bridge connecting these two foundational areas. While many elegant yet foundational Sigma-protocols were introduced decades ago as standalone algebraic or combinatorial interactive proofs, reconsidering them via the modern aspect of (extended) MPCitH significantly enhances our cryptographic insight into their underlying structures. We present a formal mapping that translates classical commitment-challenge-and-response into the internal views of virtual parties, communicating via private point-to-point or public broadcast channels, secret-sharing schemes, commitments, and MPC consistency/correctness checks. By deconstructing algebraic schemes as linear secret-sharing protocols over public channels and combinatorial schemes as discrete threshold MPC instances over private/public channels, we isolate the exact structural reasons why their soundness and efficiency characteristics diverge. The protocols include: - Algebraic schemes: Schnorr, Okamoto, Chaum-Pedersen, Guillou-Quisquater, GMR for QR and discrete log over an unknown-order group. - Combinatorial schemes: Stern, GMW for Graph 3-Coloring, and Graph Isomorphism, among others. Although reinterpreting these already elegant, classic proofs using a heavy-weight machinery like MPCitH might seem redundant, it deepens our understanding of their underlying design principles.

ORAM is a fundamental cryptographic technique that permits outsourcing memory storage while probabilistically hiding memory access patterns of client programs. We use the EasyCrypt proof assistant to obtain fully mechanized proofs of correctness and security of Simple ORAM [Chung and Pass, 2013] and Path ORAM [Stefanov et al., CCS 2013]. To the best of our knowledge, these are the first machine-checked proofs that cover the correctness bound, i.e., the failure probability, of an ORAM construction. Our proofs refine, simplify, clarify and slightly improve the paper proofs, and many parts of our development can be reused to obtain similar results for other ORAM constructions. As a final contribution, we provide a general library that handles the recursive composition of ORAM constructions to reduce storage demands on the client, and apply this to Path ORAM to capture a practically-relevant instantiation.

We study the problem of constructing highly nonlinear vectorial maps $F: \mathbb{F}_2^n \to \mathbb{F}_2^m$. Concretely, we want an $F$ and an $A = A(m,n)>0$ as small as possible, so that for every affine map $L: \mathbb{F}_2^n \to \mathbb{F}_2^m$ (of the form $L(x) = Mx + b$) we have: $$ \operatorname{agree}(F,L) := |\{x \in \mathbb{F}_2^n \mid F(x) = L(x)\}| \leq A. $$ Such questions have been studied by Nyberg [1991, 1993], Carlet and Ding [2004, 2007], Liu, Mesnager and Chen [2017], Nagy [2025], and Biryukov, Turecek, and Udovenko [2026]. There is a classical method of constructing such functions from bent-functions and Fourier analytic ideas; the best bound achievable by this method is: $$ A(m,n) = \Theta(2^{n-m} + 2^{n/2}), $$ and in particular, is never smaller than $2^{n/2}$. In this work, we show how to construct highly nonlinear functions beyond this Fourier bound. Concretely, we show how to construct for every $\gamma>0$, a function $F: \mathbb{F}_2^n \to \mathbb{F}_2^m$ with $m = \mathcal{O}_{\gamma}(n)$, achieving $$ A(m,n) \leq (1+\gamma)^n. $$ Surprisingly, we even achieve the same quantitative behavior for the much harder question of having low agreement with $m$-tuples of degree $d$ polynomials $Q: \mathbb{F}_2^n \to \mathbb{F}_2^m$, with $m = \mathcal{O}_{\gamma,d}(n)$. Here the previously best bounds were of the form $A(m,n) = \mathcal{O}(2^{-\frac{n}{2^{d+1}}} \cdot 2^n)$ of Ben-Sasson and Kopparty [Kopparty's thesis, 2010], based on Gowers-norm-type arguments. All our results generalize to all finite fields $\mathbb{F}_q$ in place of $\mathbb{F}_2$. Our methods are based on a new connection to classical results on counting solutions to systems of polynomial equations via algebraic methods. This connection brings us to basic questions in combinatorics, about graphs and hypergraphs with simultaneously a small number of edges and independent sets.

Quantum attacks based on Simon's algorithm rely on Boolean functions with hidden XOR periods. At ASIACRYPT 2025, Liu et al. introduced a symbolic automated search model for periodic functions used in distinguishers. However, for distinguishers on target ciphers, the search mainly works with truncated differences and does not jointly constrain exact differential propagation. A separate modeling gap arises in the key-recovery setting: the model does not cover the key-dependent periodic functions used in the polynomial-time key-recovery attacks presented by Canale et al. at CRYPTO 2022. In this work, we study automated search for two classes of periodic functions: periodic functions for distinguishers and key-dependent periodic functions for polynomial-time key-recovery attacks. For the former, we refine the symbolic search model of Liu et al. by adding fixed input differences, differential propagation, and probability constraints. Based on this model, we extend the periodic distinguishers of TWINE and LBlock from 10 rounds to 12 rounds, obtain a 12-round periodic distinguisher for LBlock-S, and find a full-round periodic distinguisher for ALLPC with verified probability \(2^{-9.06}\). For key recovery, we adapt the symbolic-state tracking used for distinguishers to key-dependent values. The model tracks key-dependent shifts and checks that the periodic core is exposed through an output-computable expression. With this model, we extend the attack on MISTY L-FK from 5 to 6 rounds and obtain new polynomial-time key-recovery attacks on Type-1/2 GFS and Skipjack-B variants with FK or KF round functions.

Post-quantum (PQ) migration is usually tracked per asset, with Mosca’s inequality and a share of “migrated” systems. For a flow of sensitive data, the relevant questions are different: is every session that carries it keyed by a quantum-safe secret, what evidence supports that claim, and what can an assessor establish from outside? We propose an assessment method whose unit is the data path and whose verdicts are tied to evidence. Key lineage is an algebra on break dates: a derived key falls when all its inputs fall, and a key falls when any of its copies falls. This covers TLS 1.3 resumption, key transport and keys wrapped several times. A verdict is a pair of strong-Kleene evaluations, one taking claims at face value and one admitting only claims that meet an evidence policy; the reachable pairs form four ordered labels. We characterize what an external probe can establish. A probe of the server decides a hop only if the server enforces PQ or cannot negotiate it; enforcement must be shown by a negative test paired with a positive control; a server that resumes sessions without a fresh key exchange leaves the layer undecided; and behind a load balancer the confidence of a negative test follows a sampling bound only under an independence assumption that a default balancer violates. We implement the probe and validate its inference rules on 22 configurations of five server stacks built on three TLS libraries, including confounders and a heterogeneous load balancer. The same nominal configuration yields different states across implementations, so declared configuration cannot replace runtime evidence. A protocol for an internet-scale enforcement study accompanies the paper

Binary codes used in correlation generation and proof systems need strong distance, fast ordinary and transposed encoding, and regular memory access. We introduce Single-Permutation INterleaved (SPIN) codes, combining a blockwise outer encoder, one global interleaver, and a recursive inner. Our main result is a Structured SPIN family with rate $1/2$ and $O(N)$ bit operations for ordinary and transposed encoding at its native output lengths $N$. With probability $1-o(1)$ over the random choice of the code, its minimum distance exceeds $0.11N$. The proof combines outer spectrum bounds with an analysis of structured support spreading and recursive state mixing. We formally verify these distance and rate guarantees in Lean. For finite lengths, a BCH-derived outer constituent and a fixed recursive inner give rate $1/2$ and relative distance greater than $0.10$, with setup-failure probability below $2^{-40}$. We certify this bound at message lengths $2^{16}$, $2^{18}$, $2^{20}$, $2^{22}$, and $2^{24}$ using rigorous spectrum inequalities, without assuming the constituent's exact weight spectrum. For pseudorandom correlation generators (PCGs), SPIN's transposed encoder computes $2^{20}$ $128$-bit correlation blocks in about $9.3$\,ms on one Ryzen 9 7950X thread after precomputation. This is approximately $3.4\times$ faster than the original rate-$1/2$ BAA codes of Kolesnikov et al.\ (CRYPTO 2026). Ordinary encoding has similar cost. With a precomputed code, libOTe's regular-noise Silent OT sender achieves $89.0$ million hashed OTs per second on one core, in batches of $2^{18}$. Timings exclude initial setup, base-correlation generation, and network transport. We also use SPIN in a Brakedown-style polynomial commitment scheme and integrate it into Flock. Commitment and one opening of $512$\,MiB take $509$\,ms on one core, with a 100-bit interactive fixed-matrix testing target; this excludes code-setup failure, extraction, and Fiat-shamir reductions. Within an optimized Flock implementation, replacing Ligerito with SPIN--Brakedown improves prover throughput by $1.63$--$2.29\times$ at the measured workloads, with larger proofs and slower verification. The comparison gives both backends the applicable shared implementation optimizations.

We construct fast linear codes over large fields using addition-only encoders and variants with small integer coefficients. A local precode is followed by rounds of a random permutation and a scan, a linear recurrence with a short feedback window. At dimension $2^{20}$, rate $1/2$, and $p=2^{128}-159$, two plain accumulators (unweighted prefix sums) give relative distance above $11.7\%$, except with probability below $2^{-49.64}$ over the sampling of the encoder. A binary subset-sum precode instead gives distance above $12.56\%$, except with probability below $2^{-22.05}$. These addition-only encoders use fewer than $6.8125n$ and $3.3125n$ field additions, respectively, for output length $n$. Both exceed the binary rate-$1/2$ Gilbert--Varshamov benchmark. The proof counts the supports and ranks of the zero equations a codeword must satisfy, retaining the dependence between cancellations. Coefficient size and scan width extend the tradeoff. On one core, with a common implementation and setup failure below $2^{-40}$, encoding time ranges from $12.171$ ms at proved distance above $11.7\%$ to $32.342$ ms above $42.987\%$. A coefficient-independent upper bound limits every encoder with two width-one scans after the Newton precode to $39.6855\%$. The distance and setup-failure bounds hold over $\mathbb F_p$ and every finite extension, covering all nonzero messages after setup. Timings are for $\mathbb F_p$. Extension preserves distance exactly because the encoder coefficients lie in the prime subfield. Changing characteristic requires a separate argument; we give field-transfer results in both directions, including counterexamples.

We prove that Expand--Accumulate (EA) codes approach the Gilbert--Varshamov (GV) distance as the code length grows. The result holds over the binary field and every fixed finite field. At fixed rate, encoding uses $O(n\log n)$ expected field operations, with a tunable inverse-polynomial probability of sampling a bad code. Fixed-memory wrapped binary Expand--Convolute (EC) codes satisfy the same guarantee. Allowing $O(n\log^2 n)$ expected field operations makes sampling failure negligible in the code length. These codes combine a sparse random linear map with an invertible recursive map. Our analysis uses exact input--output weight enumerators in place of the earlier concentration bounds. It also gives tighter constants in the logarithmic expected degree. For EA-based pseudorandom correlation functions, these bounds improve the degree--distance tradeoff that controls local evaluation cost. Separately, we obtain finite-length bounds at small degrees by replacing independent incidence with regional regularity. At rate one half, a two-sided regular EC ensemble with left/right degrees $10/5$ and memory $15$ reaches $99.99\%$ of the binary GV distance. The probability of sampling a generator below this distance is less than $2^{-32.49}$. We extend the construction to finite fields using independent nonzero edge labels and full-field convolution coefficients. These coefficients mix field components; scalar extension of a binary matrix does not. Over $\F_{2^{128}}$, degrees $24/12$ with memory $5$ reach $98.41\%$ of the rate-one-half GV distance with sampling failure below $2^{-45.03}$; degrees $26/13$ with memory $4$ reach the same distance with failure below $2^{-135.20}$. Every finite claim is certified with outward-rounded interval arithmetic. The results concern minimum distance of sampled ensembles; they do not provide a decoder or a complete protocol-security proof.

Secure computation often hashes high-entropy fixed-length values in inner loops. A public permutation with terminal Davies--Meyer feed-forward can expose the permutation value when an application applies another feed-forward step. We study an input-fed alternative that injects the input after every AES round. The base construction, $H_{128}:\{0,1\}^{128}\to\{0,1\}^{128}$, uses ten full AESENC-style rounds with keys $x+c_i$ and no AES key expansion. Its concrete analysis adapts differential, collision, linear, integral, and meet-in-he-middle (MITM) methods to this shared-input round-key interface. We prove a three-round integral distinguisher and give a five-round anchored MITM attack candidate with estimated time $2^{120}$; the remaining results provide reduced-round evidence rather than a proof of random-function behavior. On an AMD Ryzen 9 7950X, measured scalar and eight-lane AES-NI costs are within one percent of fixed-key AES-128; a sixteen-block VAES kernel is 2.3\% slower. Two extensions use the same input-fed principle. The tweakable construction $H_{128}^{\mathsf{tw}}$ splits a 72-bit public counter into an eight-bit tweak and a 64-bit epoch. One public schedule serves 256 consecutive positions, and consecutive fixed-key AES outputs under a published key supply the epoch schedules. Within one epoch, a pair with different tweaks can cancel at most one complete boundary injection. The construction also admits an exact 256-query two-round integral distinguisher. The wide construction $H_{256}$ maps 256 bits to 256 bits. It uses two AES lanes and adopts the column permutation and round constants of Haraka-256 v2 [KLMR16]. We analyze the differential, integral, collision, slide, rebound, and MITM mechanisms introduced by these extensions. A supporting ideal-permutation analysis shows that affine wrappers with one or two permutation calls fail generically. For three calls with independently uniform public constants, it gives a birthday-order bound when the distinguisher completes its primitive queries before querying the target. Finally, we define checkable punctured vectors and prove a GM-style protocol secure against static semi-honest corruptions in the ideal-OT and random-oracle model.

In this paper, we present a novel power analysis attack targeting a Falcon implementation protected by a masked preimage computation. By analyzing the ratio between the real and imaginary parts of the public hash polynomial, we demonstrate that the leakage during the share recombination phase can be exploited to recover the secret key. We propose two attack variants: a chosen-message attack, where the adversary controls input messages to force extreme coefficient ratios, and a non-chosen-message attack that filters for naturally occurring vulnerable hashes. Through experimental evaluations using the ELMO leakage simulator for an ARM Cortex-M0 architecture, our experiments achieve a 98.3% success rate with 4,000 traces. Finally, while a fully masked implementation of Falcon prevents our attack, we propose a practical countermeasure based on rejection sampling to avoid the prohibitive computational overhead of a fully masked Gaussian sampler.

ECLIPSE is the prime-degree signature construction the PRISM authors describe beside their salted scheme, with that salt, implemented. It exists because a two-dimensional isogeny signature carries an auxiliary isogeny the hash does not bind: the SQIsign round-3 specification says SQIsign cannot be strongly unforgeable for that reason, and PRISM's prime-degree variant has no auxiliary isogeny but was published without parameters, code or a running verifier. This paper is the first implementation, on the SQIsign round-3 primes: a verifier that evaluates the paper's criterion through one isogeny chain and a pull-back, a canonical wire format whose strict decoder recovers one coefficient from two Weil pairings, randomisable keys, two independent implementations that accept each other's signatures, and one key in both roles: a MIKE key pair at the level I prime is an ECLIPSE key pair, the public curve re-encoded and the signing key derived from the MIKE secret alone, with MIKE's code untouched. The only post-quantum precedent is CSIDH with CSI-FiSh, a group action; this is the first shared key in the SQIsign family. Signatures are 206 bytes at NIST level I, within 15 bytes of SQIsign at every matched state. In one session against the SQIsign reference's assembly build, signing is 2.6 times faster and verification costs twice as much, 1.6 times with the public key prepared once. A formal strong-unforgeability (SUF-CMA) argument is left to future work.

Secure multi-party computation (MPC) considers the problem of securely computing a function across $n$ parties such that no adversary controlling $t$ corrupted parties may learn any additional information beyond the function output. For information-theoretic security in the honest majority setting, recent works have made tremendous progress in reducing the MPC communication costs for large circuits obtaining as low as $\tilde{O}(|C|)$ total communication. To date, all information-theoretic MPC protocols require an additive $\tilde{\Omega}(n^2)$ communication independent of the circuit size that becomes the dominant cost for small circuits. In this work, we consider the problem of building more efficient information-theoretic MPC protocols with $o(n^2)$ communication for small circuits. For corruption threshold $t< (1/2-\epsilon)\cdot n$, we present an information-theoretic MPC protocol secure against adaptive and malicious adversaries with subquadratic communication for a wide range of circuits, including those in which the number of input parties $I$ satisfies $|I| = o(n)$, circuit size $|C| = o(n^{1.5}/|I|)$, and circuit depth $\mathsf{depth}(C) = o(n)$; for example, $|C| = o(n^{3/4})$ and $|I| = o(n^{3/4})$ input parties. To our knowledge, this is the first information-theoretic MPC protocol with $o(n^2)$ communication for a wide-range of circuit classes. Furthermore, we note the requirement of sublinear input parties $|I| = o(n)$ is necessary to obtain $o(n^2)$ communication due to the $\Omega(|I| \cdot n)$ lower bound by Damgård {\em et al.} [EUROCRYPT'16]. To obtain our new MPC protocol, we develop new techniques for key MPC subroutines including randomness generation, player virtualization and output reconstruction with $o(n^2)$ communication leveraging the sublinear number of input parties, $|I| = o(n)$, and randomized output distribution with unpredictable communication patterns. Finally, we also prove a separation showing that $o(n^2)$ communication MPC is impossible for adversaries with stronger than standard adaptive rushing capabilities even for constant-size circuits.

Programmable bootstrapping is a central procedure in the FHEW and TFHE families of fully homomorphic encryption schemes, but its computational cost remains a major performance bottleneck. Multi-value bootstrapping amortizes this cost by sharing a blind rotation among several functions evaluated on the same encrypted input. However, the standard choice of common factor for multi-value bootstrapping can produce unnecessarily large noise amplification for many collections of lookup tables, thereby reducing the practical benefits of sharing the blind rotation. The main contribution of this work is a log-unit lattice search for selecting common factors that substantially reduce this amplification. This search is complemented with LUT shifting, which generates alternative function-preserving test-polynomial representations and further enlarges the search space. Both optimizations are performed offline and leave the online procedure of multi-value bootstrapping essentially unchanged. The proposed construction is evaluated in TFHE at failure probability $2^{-128}$. For example, on 256-bit homomorphic integer multiplication, it achieves a latency speed-up of $1.47\times$ and a throughput improvement of $1.59\times$ relative to a baseline that evaluates each output with a separate programmable bootstrapping.

This paper considers the problem of building blind signatures in pairing-free groups. We provide the first three-move blind signature which is provably one-more unforgeable, in the random-oracle model, under the minimal assumption that the discrete logarithm (DL) problem is hard. Our construction in fact achieves one-more strong unforgeability, and also supports partial blindness. Blindness is statistical, also in the ROM. Our construction makes black-box use of the underlying group and does not rely on non-black-box techniques. For most such constructions, three moves are necessary by a recent result of Dietz, Kastner, and Tessaro (CRYPTO '26). We build on recent work by Chairattana-Apirom, Reichle, and Tessaro (CRYPTO '26), which achieved the same combination of round complexity and security guarantees, but under the stronger decisional Diffie--Hellman (DDH) assumption. In particular, we follow the same paradigm of boosting the security of a weakly secure scheme (namely, the Okamoto--Schnorr blind signature) to a fully secure one by authenticating the initial nonce. We provide, however, a substantially different instantiation of this paradigm that dispenses with the use of DDH and establishes security from DL alone.

Homomorphic secret sharing (HSS) enables non-interactive distributed evaluation of functions on secret-shared inputs. While two-party HSS is well understood, multiparty constructions remain limited in expressiveness and efficiency. We present a general framework for constructing multiparty HSS from two-party semi-private HSS (which in turn can be instantiated using distributed discrete logarithms) via a new party virtualization paradigm. In a semi-private HSS, some designated inputs may be fully known to specific servers, while the remaining inputs remain hidden. Starting from two-party semi-private schemes, we obtain $N$-party semi-private HSS supporting compositions of polynomial computations and restricted multiplication straight-line programs, for $N = O(\log \lambda / \log \log \lambda)$. We further upgrade semi-private HSS to fully private HSS for functions of polynomial degree and polynomially bounded Waring rank. As a consequence, we obtain multiparty distributed point functions with key size polynomial in $\lambda$ and $\log |D|$, for a domain $D$ of superpolynomial size. When the underlying two-party scheme supports offline/online sharing, the resulting multiparty DPFs are programmable. Our framework admits instantiations under standard assumptions including DCR and class-group assumptions.

We present the first formal verification results for the highly optimized additive Fast Fourier Transforms (FFTs) in two different code-based post-quantum cryptosystems: Classic McEliece and Hamming Quasi-Cyclic. Since Classic McEliece is already a standard and HQC is being standardized, they may both see wide adoption in the future. The Gao-Mateer and Frobenius additive FFTs during decoding are clearly the most intricate, error-prone components in the two cryptosystems respectively. They are not only complicated and mathematically intricate, but also aggressively optimized in practical implementations. A main problem of this verification is the $>2^{14}$ independent bit-variables in each multiplicand. Aside from adding a vector syntax and improving various syntactic transformations to the open-source tool CryptoLine, we also formulate additive FFTs as Chinese Remainder Theorem decompositions which factors the verification problem into local checks feasible for computer algebra systems like Singular. The workload was also tractable: the calendar time for the formal verification in this paper was less than three months for our very limited workforce.