We present Thunderbolt, an off-chain protocol that transfers Bitcoin UTXO ownership with seconds-scale latency, requires no channel graph, no routing, and no liquidity rebalancing, and lets the recipient be offline at the time of transfer. A single UTXO is locked once on-chain under a fixed public key jointly held by the current owner and a threshold committee; ownership then passes through an unbounded sequence of holders; each transfer is a purely off-chain, asynchronous operation whose on-chain cost is zero. The chain sees exactly two transactions regardless of how many transfers occur. The core invariant is an algebraic cancellation: at each transfer the recipient's fresh secret is added to the holder's share and subtracted from the committee's share, so both shares rotate while the on-chain key stays fixed. To enforce this, the recipient publishes an invoice to a shared append-only ledger (the Thunderbolt Ledger): a public commitment, an encrypted copy for himself, and an encrypted copy for the committee, together with a zero-knowledge proof that all three encode the same fresh secret. The sender fetches the invoice, verifies the proof, homomorphically folds her secret into the recipient's ciphertext to produce a new ownership credential, and publishes the result with a second zero-knowledge proof. Both proofs use a single Sigma-protocol response to force the same witness across elliptic-curve and Paillier verification equations, requiring no trusted setup. The committee operates under a standard $(t,n)$-threshold honest-majority assumption: at most $t{-}1$ of $n$ members may be corrupted. The recipient decrypts at any later time; the committee subtracts the fresh secret from its share. By binding each transfer to a distinct fresh secret and context identifier, multiple UTXOs can be transferred independently in parallel. On our benchmark machine, a complete off-chain transfer finishes in 1022ms with a combined proof size of 3.8KB. General-purpose SNARK (Succinct Non-interactive Argument of Knowledge) backends are orders of magnitude slower on the same relations: even a reduced-parameter instantiation already exceeds our native proving time by two orders of magnitude, and a faithful realization at the deployed 3072-bit Paillier modulus exceeds the memory budget of consumer hardware.

Linkable Ring Signatures (LRS) allow anonymous signing on behalf of an ad hoc ring, while making any two signatures by the same signer publicly linkable. Traceable Ring Signatures (TRS), introduced by Fujisaki and Suzuki [PKC'07], strengthen linking to tracing: two signatures on different messages additionally reveal the signer's public key. Since cheating almost always means signing two distinct messages, for example two conflicting transactions, traceability turns detection into accountability and makes misbehavior costly. However, TRS remain far less studied and deployed than LRS. We identify two gaps and address both. First, the security notions inherited from [PKC'07], anonymity, linkability, and exculpability, do not capture attacks specific to tracing. For example, they together do not imply unforgeability, a fundamental requirement for all signature-like primitives. We close this gap by introducing extended linkability and extended exculpability, which reflect the security requirements of TRS more faithfully than their standard counterparts. Second, all existing TRS schemes trace in $O(n)$ time for a ring of size $n$, whereas LRS link in $O(1)$. Over a pool of $\ell$ signatures, pairwise tracing therefore costs $O(\ell^2 n)$ against $O(\ell^2)$ for linking. We design a new TRS framework with $O(1)$ tracing for valid signatures. Instantiated from DDH with Bulletproofs [S&P'18], it yields signatures of $(64\log n+544)$ bytes on Curve25519. To our knowledge this is the shortest TRS for $n \ge 12$, and it is on par with state-of-the-art DLog-based LRS schemes. TRS thus gains traceability at essentially no cost over LRS.

We present four quantum-safe schemes: the Kyber (ML-KEM) and FrodoKEM key encapsulation mechanisms, and the Dilithium (ML-DSA) and Falcon (FN-DSA) signature schemes. We also develop the mathematical background on lattices needed to understand why Kyber, FrodoKEM, Dilithium and Falcon are regarded as lattice-based cryptosystems, and we provide insight into the computational hardness of the underlying lattice problems. The exposition is intended to be accessible to senior undergraduate students and beginning graduate students.

Distributed shuffling is a core primitive underlying mix-nets, electronic voting, and, more recently, single secret leader election (SSLE) protocols for proof-of-stake blockchains. In these settings, a collection of resource-constrained parties jointly permutes a list of ciphertexts or commitments in order to conceal the correspondence between inputs and outputs. Existing security analyses of such protocols typically rely on heuristic anonymity measures or implicitly assume honest behavior; therefore, they fail to capture statistical dependencies that arise when shuffling is partial and some participants are corrupted. In this work, we introduce a new security model for distributed shuffling that accurately reflects the setting of real-world attacks by explicitly accounting for adversarial corruption and information leakage. Our model allows an adversary to corrupt a subset of shufflers and track selected elements throughout the execution, as well as query the resulting permutation afterwards. We then turn to studying Whisk in this model, the shuffle-based SSLE mechanism proposed for Ethereum. Leveraging Markov-chain techniques, we show that security can only be guaranteed for more stringent parameters than currently proposed. We evaluate the performance impact of changing these parameters on the Ethereum network.

The Kim mapping, which belongs to the only known CCZ-equivalence class in even dimension that contains an APN bijection, and the APN bijections in dimension 9 exhibited by Beierle and Leander, all have a univariate representation corresponding to a cyclotomic mapping (aka Wan-Lidl polynomial), and they are all linearly-equivalent to functions with a highly-structured multivariate representation. In this paper, we show that functions having these properties, which correspond to multivariate projective mappings, i.e. multivariate functions whose coordinates are homogeneous, actually appear in the CCZ-equivalence classes of almost all known infinite families of APN functions. However, this behavior is not inherent to the APN property. Indeed, we prove that the vast majority of the known sporadic examples of APN functions in dimension 6 and 8, including almost all APN functions whose automorphism group is reduced to the automorphisms derived from their affine derivatives, are not CCZ-equivalent to an affinely self-equivalent function.

XtM (XOR-then-MAC) is provably optimal against quantum adversaries. As of March 2025, no production cryptographic library implements it. HKDF, with weaker security guarantees, is deployed in 91% of the 44 libraries we examined. This gap is not accidental.This Systematization of Knowledge (SoK) introduces the (A, P, φ) framework to explain it: A measures authentication strength, P measures IETF standardization maturity, and φ measures implementation complexity. To our knowledge, this is the first falsifiable, quantitative model predicting cryptographic adoption grounded in observable software engineering indicators. We apply this framework to seven combiner families and 44 cryptographic libraries, validate φ against measured integration LOC across 9 real-world repositories, and derive predictions verifiable by 2028.Our evidence suggests that implementation complexity is a first-order explanatory factor in cryptographic adoption. The most deployable construction is not the most secure one in isolation: it is the most secure one engineers can integrate, audit, and maintain at scale.

Token-weighted voting is widely used in DAO governance, but public voting weights together with weighted tallies can reveal identifiable voters' choices. Publishing only the final outcome reduces this disclosure, yet an output policy alone does not prevent a privileged participant from reconstructing the exact weighted tally during computation. We present a verifiable winner-only tally-hiding construction for weighted binary voting. Registered weights are bound to credentials in zero-knowledge ballots, while weighted contributions remain encrypted through aggregation and comparison against a public threshold. The blockchain adjudicates ballots, an off-chain backend performs the encrypted computation, and exact ciphertext and transcript bindings allow any public verifier to check that the published outcome corresponds to the accepted ballots. The only tally-derived plaintext output is the outcome bit. The construction is parameterized by electorate size and contribution width; our prototype and formal transcript-privacy result deliberately study a bounded eight-voter, eight-bit instance with 134 encrypted gates and an actual three-of-five final release. For honest execution by all five trustees, we prove passive-public-observer backend transcript privacy from the accepted ciphertexts and outcome alone. Privacy against malicious sub-threshold trustees remains open.

An oblivious key-value store is a data structure that can encode and decode $n$ key-value pairs in a table of size $m$ obliviously. After encoding, one cannot distinguish the encoded key-value pairs from other key-value pairs in the input domain. In this paper, we first propose a data structure called Peelable Garbled Bloom Filter (PGBF), which encodes the key-value pairs in a similar way to peeling and unpeeling an \emph{onion}. Specifically, it can divide the key-value pair set (i.e., onion) as multiple subsets (i.e., peels) and order them from the outermost peel to the innermost peel by using a counting Bloom filter. However, using a small expansion rate (i.e., $\eta=m/n$) in PGBF will result in a non-empty core issue with non-negligible probability. To handle this issue, we propose Multi-PGBF by combining multiple PGBFs to do the peelings and unpeelings recursively. In addition, we propose a variant C-Multi-PGBF by clustering a large set into small sets to achieve faster encoding efficiency. Our experiments show that Multi-PGBF and C-Multi-PGBF obtain the best encoding and decoding efficiency. Multi-PGBF improves the encoding time of RR (CCS’22) by $65.1\%\sim 77.6\%$, while C-Multi-PGBF improves the encoding time of the clustered RR variant by $60.2\%\sim 64.7\%$. For decoding, Multi-PGBF is $28.6\%\sim 62.4\%$ faster than RR (CCS'22) and $89.7\%\sim 96.3\%$ faster than RB-OKVS (Usenix'23). When integrated into the state-of-the-art two-party and multi-party private set intersection protocols (Eurocrypt'21, Usenix'24), Multi-PGBF and C-Multi-PGBF lead to faster protocols than those using existing OKVS constructions in most settings.

In nonadaptive combinatorial group testing, given $n$ items with at most $d$ positives, the goal is to identify them using as few pooled tests as possible. A $t\times n$ binary matrix represents the design, where rows are tests and columns are items. The matrix is $d$-disjunct if no column is contained in the Boolean union of any $d$ others. Let $T(d)$ be the minimum $t$ for which such a matrix exists with $n>t$. Shangguan and Ge proved $T(d)\ge \frac{15+\sqrt{33}}{24}d^2$ by counting private pairs (IEEE Trans. Inf. Theory, 62(12):7518-7521, 2016). In this paper, we strengthen their argument by introducing a column-deletion recurrence in which the light-heavy threshold varies with the recursive state $z=(n-t)/d^2$, rather than remaining fixed. This yields the improved bound $T(d)\ge 0.9283d^2-O(d)$. The analytic core reduces to a first-order ODE, and a self-contained interval-arithmetic certificate verifies that the solution reaches the required contact point.

We revisit the notion of Simulation Extractability (SE) for SNARKs in the updatable setting. We demonstrate that existing formal definitions of SE in this setting are insufficient to guarantee the required non-malleability in real-world scenarios. Towards this, we first identify and frame a malleability vulnerability: a cross-SRS reinterpretation attack, which shows that an adversary can reuse or maul proofs across different, correlated SRSs generated through the update procedure. This is made possible because existing security definitions fail to model an adversary’s ability to observe simulated proofs relative to various derived SRSs. To close this security gap, we propose a revised and stronger security notion of Updatable Simulation Extractability (USE) which was originally defined in [GKK+22]. Our definition models a dynamic environment where the SRS is adaptively updatable by the adversary, who can also query simulation oracles for proofs under the resulting family of reachable SRSs. This captures the full extent of the adversarial capabilities observed in practice. Finally, we provide positive results for popular polynomial-IOP-based SNARKs, and show that these schemes satisfy our stronger USE notion, provided the circuit-specific SRS is securely bound into the proof transcript, e.g., via a correct implementation of the Fiat-Shamir transformation.

We present Grand Danois, a new post-quantum multilinear polynomial commitment scheme from lattices for polynomials over $\mathbb{F}_q$ that achieves polylogarithmic $O(\lambda \ell)$ verification complexity and proof sizes. We build on the general approach introduced in Hachi (ePrint 2026/156) with three key changes. First, we switch to the vanishing Short Integer Solution (vSIS) assumption to obtain structured public parameters for our commitment scheme and utilize this structure to design a sumcheck protocol amenable to succinct verification. Second, rather than casting ring relations into $\mathbb{F}_{q^k}[X]$, via the residual technique of Hachi, we express multiplication by fixed $\mathcal{R}_q$ elements through its rotation matrix, which lets the verifier fold each row of the constraint matrix in time linear rather than quadratic in the ring degree $d$. Third, we modify the quadratic relation used in Hachi and Greyhound (CRYPTO 2024) so that it becomes compatible with proving norm bounds using Johnson-Lindenstrauss projections. This is achieved through an adaptation of the structured projection strategy introduced in RoK and Roll (ASIACRYPT 2025). This has the benefit for communication complexity in that proving norm bounds and correct polynomial evaluation are integrated into a single protocol, reducing the number of commitments sent by the prover. Furthermore, we impose additional structure on our random projections to reduce the witness size even more aggressively during each round of recursion without sacrificing verification complexity. Under the vSIS assumption, our construction yields an estimated proof size of roughly $80$ KB for $2^{32}$-size polynomial evaluations.

Side-channel analysis (SCA) is commonly evaluated by reporting the number of traces required to reduce the rank of the correct key. Still, such evaluations remain empirical and do not explain how many traces suffice for reliable recovery, how profiling and attack data contribute separately, or when additional traces cannot overcome weak key distinguishability. We address these questions through a Probably Approximately Correct (PAC) formulation of profiled and non-profiled SCA. Our framework treats candidate-key scores as the common cryptanalytic object and separates finite-sample estimation from the intrinsic separation between the correct key and competing hypotheses. This distinction enables confidence guarantees for key rank and helps determine whether an attack failure is due to insufficient data or an inherently weak attack score. We instantiate the framework with representative profiled and non-profiled attacks chosen for their analytical tractability. Experiments on ASCAD-f and ASCAD-r show that this analytical tractability does not come at the cost of impractical attack performance. The profiled attack achieves exact recovery with tens of attack traces, whereas the non-profiled single-attack rank certificate guarantees exact recovery with about 1,000 traces. These results are competitive with recent ASCAD attacks and, in the non-profiled setting, substantially below the smallest trace counts identified in prior studies, while additionally providing finite-sample guarantees on key rank. More generally, the same finite-sample rank analysis can be adapted to other learners and distinguishers by deriving the corresponding score-gap guarantees. Overall, the framework turns trace complexity from an empirical attack observation into a reusable finite-sample criterion for key recovery.

A multilinear secret-sharing scheme shares a vector secret and can therefore amortize share size over the secret dimension. This amortization can invalidate lower bounds proved for one-dimensional linear schemes, and the best previous explicit lower bound for multilinear schemes was quasipolynomial, $n^{\Omega(\log n)}$. We prove that the Razborov--G\'al rank measure survives amortization: the normalized size of a multi-target monotone span program is at least the rank measure of the function it computes. Combined with the rank witnesses of Pitassi and Robere, this gives an explicit family of access structures for which every perfect multilinear scheme over every finite field has average and maximum information ratio $2^{\Omega(n)}$. The worst-case multilinear information ratio is therefore $2^{\Theta(n)}$, answering a question of Beimel. We further extend the bound to schemes whose sharing algorithm is arbitrary and whose reconstruction is affine-linear, under pairwise statistical privacy below one; combined with the degree-reduction theorem of Beimel, Othman, and Peter, this yields exponential normalized lower bounds for every fixed reconstruction degree whenever the secret dimension is $2^{o(n)}$.

The notion of Best-of-Both-Worlds introduced in the work of Ishai et al. (CRYPTO 2006) investigated whether an MPC protocol can simultaneously provide two incomparable security guarantees depending on the number of corrupted parties. As a special case of this, Chaum et al. initiated the study of protocols that tolerate unbounded corruption within a certain adversary structure and PPT corruption of any number of parties beyond that. More recently, Acharya et al. (CRYPTO 2023) formalized this notion as MPC with fall-back security. Although the feasibility of such protocols has now been thoroughly studied in prior works, most of the existing protocols require round complexity linear in the number of parties and the computation size. In this work, we study the round complexity of MPC with fall-back security in the threshold corruption setting, presenting constant-round protocols for optimal thresholds. We present a semi-honest fall-back secure protocol for $t < \frac{n}{2}$ with 3 rounds, in the plain model, whereas the best known protocol in the same setting takes at least 11 rounds. In the CRS model, we present a maliciously fall-back secure protocol for the same threshold with 4 rounds, satisfying unanimous abort (UA). Finally, we extend this to a 5-round protocol that satisfies fairness in the presence of unbounded adversaries for $t < \frac{n}{2}$ corruptions and UA tolerating PPT adversaries for arbitrary corruption beyond that. In the malicious setting, we construct the first constant-round fall-back secure protocols.

We present a practical framework $\mathsf{DumboMix}$ for asynchronous anonymous broadcasts with guaranteed output delivery (G.O.D., a.k.a. robustness), enabling a set of $n$ servers to privately solicit $N$ messages from distinct clients, such that these messages remain secret until they are revealed in uniform random order. Here, asynchronous G.O.D. ensures that all messages are eventually randomly mixed despite (i) arbitrary malicious behaviors by up to $\lfloor (n-1)/3 \rfloor$ Byzantine servers and (ii) unpredictable network delays and jitters. At the core of $\mathsf{DumboMix}$, we first propose a couple of practical mixing methods $\mathsf{DumboMix1}$ and $\mathsf{DumboMix2}$ for Shamir-secret-shared multi-party computation (MPC) over $\mathbb{Z}_p$, along with their server-optimized variants. When randomly mixing $N$ messages, their online phases require only $\mathcal{O}(1)$ multiplicative depth, expected $\mathcal{O}(N^2)$ scalar multiplications (between public and shared values), and up to $\mathcal{O}(N)$ MPC multiplications (between shared values). Moreover, assuming a robust underlying MPC framework, they guarantee that all revealed inputs are uniformly shuffled. In contrast, existing techniques fail to achieve all these performance and functionality features: The DC-net variant $\mathsf{Blinder}$ (CCS’20) may reveal a non-negligible fraction of inputs without shuffling them; Butterfly switching networks in secret-shared MPC (CCS’19) incur $\mathcal{O}(\log^2 N)$ multiplicative depth; RabbitMix (Security’24) requires $\mathcal{O}(N^2)$ MPC multiplications; and PowerMix (CCS’19) incurs $N^{3}/2$ scalar multiplications. We finally implement our new mixing methods within $\mathsf{DumboMPC\text{++}}$, our computation-optimized implementation of the state-of-the-art robust AMPC framework $\mathsf{DumboMPC}$ (Security’25), which provides more concretely efficient offline preprocessing while preserving asynchronous G.O.D. and optimal resilience. We then conduct extensive evaluations with $n=4$ to $31$ servers under varying network settings, revealing that our new mixing methods achieve 44.8--65.9× (resp. 37.1--52.7×), 4.8--7.1× (resp. 3.9--5.5×), and 2.7--4.0× (resp. 5.1--7.2×) speedups over RabbitMix, PowerMix, and the butterfly switching network, respectively, when shuffling 1024 messages in LAN (resp. WAN).

Linear cryptanalysis measures the correlation of a cipher with the characters of the group used to define differences. If that group is replaced by a second elementary abelian group structure on the same set, here the one coming from a binary bibrace, then the admissible masks are no longer the ordinary scalar products: exactly half of them survive, and the other half are forced to be quadratic. Beyne’s geometric approach develops linear cryptanalysis over an arbitrary finite abelian group, providing a natural framework for this setting. We instantiate it on the group of a particular bibrace and apply it to Craft. Over this group the Midori/Craft S-box has four probability-one relations, forming a small subgroup of the dual which the S-box preserves in both directions. Inside that subgroup a mask propagates deterministically and linearly, so the search for the best trail is a minimum weight codeword problem, which we solve exactly by complete enumeration rather than heuristically. A trail costs correlation, and it restricts the key to a weak-key class. The two are usually derived from the same data. We show that the correct reading, obtained by analysing the diffusion layer and the key addition together rather than separately, gives a class several bits larger than the one obtained cell by cell. One concrete consequence is that Craft’s round constants, whatever their values, impose no restriction at all. On Craft we obtain weak-key distinguishers up to eighteen rounds. At fourteen rounds the squared correlation is 2−44 over a class of 2^108 keys, against 2−62.12 for the designers’ linear hull, which is the best known linear result on the cipher and holds for all keys. On that class we therefore improve the best linear correlation by eighteen bits at equal round count, and we reach four rounds further than the best known linear hull. Both the distinguishers and the weak-key criterion are verified experimentally, with a negative control on random keys.

Masked hardware design is a central countermeasure against side-channel analysis (SCA), but its practical deployment remains costly due to the overhead and design complexity of secure implementations. To manage this complexity, modern masked circuits are increasingly built from composable masked building blocks, referred to as gadgets. However, improving the implementation quality of such gadgets is challenging because optimization must not violate formal security requirements. This paper studies the optimization of masked hardware gadgets under formal security by comparing conventional CAD transformations with a security-aware design automation framework based on evolutionary algorithms. The conventional CAD flow explores structural alternatives exposed by technology mapping, FRAIG-based rewriting, and retiming, whereas the evolutionary framework adaptively explores alternative gate-level realizations through circuit-specific mutation, crossover, and multi-objective selection. The resulting implementations are evaluated for power and area while enforcing functional correctness and compliance with the probing model through equivalence checking and pre-silicon side-channel verification. Our results show that conventional CAD techniques can yield substantial improvements in selected cases, up to 60%, but their behavior is not systematic under strict masking constraints. In contrast, the evolutionary framework provides a controlled, adaptive search over alternative gate-level realizations and produces security-preserving implementations with measurable improvements over naïve synthesis, reaching up to 15% reduction in power and area in selected cases. We validate the optimized designs using industry-standard synthesis and pre-silicon side-channel verification tools. We further show, for AES, that additional savings remain possible even relative to a state-of-the-art compressed masked design.

Remote state preparation (RSP) is a central primitive in quantum cryptography, enabling classical parties to remotely construct quantum states using only classical communication. As a result, RSP serves as a key building block in numerous protocols involving classical clients and quantum servers, allowing classical parties to leverage the advantages offered by powerful quantum computers. All known constructions of RSP rely on strong cryptographic assumptions, typically variants of trapdoor claw-free functions (TCFs). In this work, we initiate the study of a weaker form of remote state preparation, which we call eavesdropper-blind remote state preparation (EB-RSP). Informally, EB-RSP requires blindness only against external observers who see the transcript of the honest protocol, rather than against the quantum server itself. Despite this relaxed adversarial model, the resulting notion remains sufficient for useful cryptographic applications. In particular, we show that two-message EB-RSP already suffices to construct quantum public-key encryption with classical public keys and quantum ciphertexts. We then construct two-message EB-RSP protocols from specific one-way group actions, yielding a first step toward RSP-type primitives based on assumptions that do not rely on trapdoors. Finally, we observe that existing RSP constructions are likely naturally adaptable to the two-message EB-RSP notion; we demonstrate this explicitly for a concrete TCF-based RSP construction.

When two S-box layers of a round are separated by no key addition, the round correlation is a signed sum over all compatible intermediate masks, not a product of layer correlations, so the product rule can fail in either direction. Our central finding is that evaluating this intra-round sum exactly changes the assessment of the published linear cryptanalysis of SPEEDY, whose two S-box layers are separated only by ShiftColumns. We first develop the linear cryptanalysis of this setting: an exact one-round algorithm with a decidable exactness condition for the product rule, a dependency-graph decomposition, a covering-number bound strengthening linear-trail weight bounds, and a Walsh-support criterion in which the affine dimension of that support, limited by the endpoint key masks, fixes the key-recovery transform cost. Potentials use the independent-round-key model; complexities are in equivalent encryptions. Applied to SPEEDY, these tools revise published results: a reported five-round mask sequence has exact correlation $2^{-90.0962}$, not $2^{-93.0147}$; the new bound raises the unrestricted five-round weight bound from $53.7714$ to $62.2616$ bits; and the full-round attack on SPEEDY-7-192 reported at time $2^{158.06}$ needs at least $2^{199.97}$ encryptions in the pruning class considered. For SPEEDY-6-192 we give a six-round known-plaintext attack (data $2^{169.84}$, time $2^{170.20}$, memory $2^{156}$) and show that the attack class defined here contains no attack with data and time both at most $2^{128}$, its time being at least $2^{136.302}$. The same exact evaluation also revises a four-round differential-linear correlation.

\emph{Modular Polynomial Commitment Schemes (Mod-PCS)} extend standard PCSs by enabling provable evaluation of integer polynomials modulo a random modulus, providing a natural foundation for SNARKs that operate directly over large integers without emulating arithmetic in finite fields. Only two Mod-PCS constructions are known. The first (Campanelli and Hall-Andersen, IACR ePrint 2024) serves primarily as a feasibility result and is impractical and not post-quantum secure due to its reliance on groups of unknown order. The second (Garetta et al., CRYPTO 2025) introduces the weaker notion of \emph{relaxed} Mod-PCS, but is not fully succinct: committing to a multilinear polynomial with $N$ terms and $B$-bit coefficients requires $O(\sqrt{N}B)$ proof size and verification time. We present a black-box transformation that builds relaxed Mod-PCS from any standard PCS, enabling new constructions. Instantiating our transformation with a tensor-code PCS yields the first relaxed Mod-PCS with $O(\log (N+B))$ proof size and verifier time, which is transparent and plausibly post-quantum secure. Using this scheme within the framework of Garetta et al., we obtain the first fully succinct SNARK for the Customizable Constraint System over $\mathbb{Z}_B$, achieving $O(B\log N + N\log N \log B)$ prover time and $O(\log (N+B))$ verifier time and proof size. Our approach relies on a commitment-switching technique for integer polynomials and a new batched integer commitment scheme from any PCS. We further introduce improved arguments for integer addition and multiplication, correctness of the number-theoretic transform, and general Diophantine relations over committed integers.

Two novel symmetric multidimensional affine nested variations of the Hill Cipher are presented. The Hill Cipher is a block polygraphic substitution encryption scheme based on a linear transformation of plaintext characters into ciphertext characters. In the time since Hill first published his encryption scheme, variations, modifications, and improvements of theoretical and practical importance have been published every year indicating that the Hill Cipher is an active area of cryptography research. The first variation presented in this paper incorporated invertible key matrices of orders 2, 4, and 8 such that the matrix values of the 2×2 matrix rotate positions with each block of characters in a similar manner to the rotating letter wheels of a German Enigma Encoder, then results of the 2×2 key matrices output are passed to 4×4 key matrices, and 8x8 key matrix, 4×4 key matrices, and rotative-value 2×2 key matrices. The second variation is configured with invertible key matrices of orders 4, 8, and 16 without rotation of matrix values in a similar manner to the first variation. In both variations, plaintext characters of each block are operated on by exclusive-or (XOR) vectors prior to multiplication with the matrices to create the affine ciphers. Strengths, weaknesses, and other considerations are provided in the discussion. Two proposals are also argued with rationale for a more robust character set for encryption and the increase in modulus that the character set allows, and the possible advantages and disadvantages of affine XOR vectors.

MD-Hill-SPN is the first Hill-based construction to combine a multi-tier diffusion mix layer, a memory-hard KDF, and a simultaneous multi-metric empirical evaluation. Two independent runs of the full metric suite yield: (a) full plaintext avalanche from round 1 (mean 63.97–64.67 of 128 bits, ideal 64); (b) the differential-probability sampling floor of 2 × 10−5 reached at round 4 (50,000 of 50,000 output differences distinct, both sessions); (c) algebraic-degree lower-bound saturation at the maximum observable value from round 1; (d) linear-bias indistinguishable from random (combined exceedance 4.40%, below the 4.55% noise floor); and (e) branch numbers at the Singleton (MDS) bound for every tier (B = 5 for 4 × 4, B = 9 for 8 × 8, B = 17 for 16 × 16), computed exhaustively over weight-1 inputs. MD-Hill-SPN therefore moves beyond theoretical construction to a construction that passes a defined empirical evaluation suite: avalanche, differential sampling, linear-bias probing, algebraic-degree lower bounds, and MDS branch numbers under single-key, known-plaintext conditions with fixed parameters, an evaluation no prior Hill cipher variant has reported in full.

Threshold signatures are deployed in settings where an adversary may run many concurrent signing sessions and corrupt signers adaptively. Two-round schemes make this especially delicate. Their first-round messages are independent of the signed message and can be preprocessed offline, so a later corruption must reveal randomness that is consistent with commitments already published in prior transcripts. Existing adaptive constructions address this tension by adding rounds, relying on algebraic or knowledge assumptions, or paying non-tight losses from guessing the corruption pattern, the decisive session, or the final transcript. We construct $\mathsf{TPilaf}$, the first two-round threshold signature scheme that combines partially non-interactive signing with a fully tight proof against adaptive corruptions. The scheme is pairing-free and is built in prime-order groups from the $\mathsf{MDDH}$ assumption in the random-oracle model. Its first-round messages can be generated offline, and any threshold set of signers can aggregate their second-round shares into a single publicly verifiable signature. The proof combines two ingredients. First, we introduce a linearly homomorphic dual-mode commitment with targetable opening. This lets the simulator open an already fixed commitment to the aggregate target imposed by a later Fiat-Shamir challenge. Second, we use profile-wise zero-sum masking with posterior completion. Corruption openings and signing responses are therefore sampled from the exact conditional law while values already visible to the adversary remain cached. Together, these tools enable a delayed branch-decision argument. The reduction waits until the adversary's own queries determine the last touched coordinate, completes only latent state, and then binds the forged hidden branch. The final bound has no combinatorial loss in the number of users, threshold, sessions, or corruption patterns, and contains only the explicit bad-event and assumption terms appearing in the theorem.

Verifpal, introduced in 2019, is a symbolic protocol verifier that traded analytical generality for a modeling language a working engineer could read without training. Its own paper called the resulting soundness argument "incomplete, semi-formal, in-progress," and the fair conclusion at the time was that Verifpal was a teaching tool standing beside two research tools. The engine that paper described has since been replaced outright. Where the 2019 engine searched forward, enumerating combinations of wire values to mutate under four tuned parameters, the new engine is goal-based: it starts from the query it is trying to contradict, breaks that requirement into subgoals, and forces a binding whenever a subgoal can be discharged in only one way, with the search bounded by the protocol's own term structure. This paper gives the first formal account of the replacement: its semantics, equational theory, knowledge closure and goal-directed solving. Soundness does not depend on the solver: before an attack is reported, a small trusted region re-checks that the attacker controls every slot the attack touches and can derive every term it installs, then re-executes the protocol and re-tests the query, so a solver bug can cost a missed attack but cannot produce a false one. The language is also simpler and more capable: public-key cryptography no longer needs a special kind of value, key encapsulation mechanisms are expressible, and a primitive can be declared weak or forgeable at the call site. Every principal is now analyzed as several concurrent sessions holding their own fresh values, which brings attacks needing two instances of one role (such as Millen's necessarily-parallel $f^n g^n$) within reach. Attack traces are always reproducible and are written almost entirely in the modeler's own names, which greatly improves the usefulness and readability of Verifpal's findings. Verifpal still comes with limits: no observational equivalence, a fixed equational theory, and while parallel execution is now genuinely supported, it is over a bounded number of sessions rather than unbounded replication. Our answer to the title's question is that Verifpal has become a different instrument rather than a smaller one, worth using alongside its two peers rather than instead of them.

Authenticated Key Exchange (AKE) is a cornerstone of secure communication, especially in resource-constrained IoT environments where lightweight and post-quantum security are paramount. While lattice-based cryptography offers promising solutions, existing post-quantum AKE protocols often prioritize strong security notions, such as the use of an IND-CCA encryption scheme, incurring overheads incompatible with IoT devices. This raises a critical question: Can one-way security (OW), a weaker but potentially more efficient notion, suffice for secure AKE in the post-quantum era? We address this challenge by revisiting the ALIKE framework (ISO/IEC 29192-4), which achieves OW-CCA-based AKE using deterministic RSA. However, RSA’s quantum vulnerability and the lack of lattice-based OW-CCA schemes hinder its applicability today. Our work bridges this gap through three key contributions. First, we prove that the Hash-Before-Encrypt (HBE) paradigm generically transforms deterministic OW-CPA schemes into OW-CCA-secure ones. We additionally present the Fujisaki–Okamoto transform and its security proof construction, providing a reference for understanding the efficiency advantages of the proposed HBE-based approach. Second, we modify Bai et al.’s efficient lattice-based OW-CPA scheme to a deterministic variant and rigorously prove its security. Third, we generalize the SPAKE framework to support our OW-CCA construction, enabling post-quantum AKE with minimal assumptions, implement and benchmark the resulting protocol, demonstrating state-of-the-art efficiency for lightweight, quantum-resistant AKE. By relaxing security requirements from IND-CCA to OW-CCA while preserving adaptive security we achieve a practical balance between robustness and performance, paving the way for deployable solutions in constrained environments like IoT and connected vehicles.

Motivated by digital signature algorithms ranging from Falcon to fully-anonymous ring signatures used in Signal-style key exchange, such as Gandalf, we revisit a fundamental problem in post-quantum security proofs: distinguishing oracle functions whose outputs are sampled independently from distributions $P$ and $Q$ that are close. In the context of signatures, closeness is often measured via Rényi divergences, which yield multiplicative bounds in the classical setting. A counterexample shows that such multiplicative-error bounds for distinguishers with classical oracle access have no analogue for quantum access, and we provide two alternative approaches based on small-range distributions and reprogramming techniques. We also give a concrete, optimal bound for the case where $P$ and $Q$ are close in statistical distance. We apply these techniques to the motivating constructions. (i) We give the first QROM security proof for Falcon that avoids oracle indistinguishability arguments based on statistical distance. This is crucial, as Falcon's ROM proof relies on Rényi divergence, while the statistical distance induced by its parameters is too large to yield meaningful bounds. (ii) We formalize and abstract the ring signature construction used in Gandalf as a modular framework by defining ring trapdoor preimage-sampleable functions (RPSFs), for which we obtain two QROM proofs. We also provide two QROM security proofs for AOS ring signatures, adapting existing QROM techniques. Together with our results on RPSF-based ring signatures, this yields QROM security proofs for a broad class of fully-anonymous linear ring signature constructions, including Gandalf and the AOS-based constructions Erebor and MayoRS.

We give an explicit compression collision for all 28 rounds of the KoalaBear Poseidon instance with parameters $(t,\alpha,R_F,R_P)=(16,3,8,20)$, in the setting where the round constants are fixed before the MDS linear layer is chosen. The main problem is to construct a single linear layer that simultaneously controls two executions through both the full and partial rounds. We do this by tracking their midpoint and half-difference. In each two-round block, one prescribed image of the linear layer cancels the midpoint against the next round constant, so the following odd cubic S-box receives opposite states and resets the midpoint to zero. Two additional images are reused throughout the permutation to return the half-difference to the same one-dimensional subspace. The resulting trajectory constraints determine a linear layer, while a scalar recurrence closes the final difference under feed-forward. For the KoalaBear instance we obtain a collision in all sixteen output coordinates with an MDS matrix satisfying the prescribed linear-layer checks. The scalar construction reduces to low-degree equations and admits a family of parameter choices, so the collision is not an isolated instance. The result exposes an adaptive correlation between fixed round constants and a subsequently chosen linear layer that matrix-only checks do not capture.

Differential-based attacks represent the best known results for many block ciphers. Such attacks usually demand that the adversary an choose plaintexts (CP) or ciphertexts (CC) in subspaces to satisfy differential trails. However, many widespread modes of operation or applications prohibit the adversary from directly choosing inputs for the majority of primitive calls. While Biham and Shamir already suggested a straightforward trade-off for standard differential attacks in their work on the DES, studies on advanced differential-based types, such as impossible-differential, rectangle, or mixture attacks, have surprisingly received little attention so far. In this work, we study applications of differential-based attacks in the random known-plaintext model (RKP) of the above. For the AES as the probably most widespread block cipher, we derive the best existing distinguishers and attacks in the RKP model on all versions, improving earlier results by at least one round. Interestingly, we show that Demirci-Selcuk meet-in-the-middle attacks with differential enumeration, which require much related data, can also be effective in that setting without approaching the full codebook too closely. For several of our attacks, we showcase differences between the models as trails that lead to the best known attack complexities under chosen data are suboptimal in the RKP model, and can be replaced by better trails. While our results do not threaten the security of the full AES, and their complexities are too high to represent any threats, we hope to inspire cryptographers to also consider attacks in the RKP for future attacks.

We present a method for secure pattern matching over encrypted texts using TFHE. Our approach realizes a fully secure binary search algorithm by leveraging two operational modes of integer-input TFHE. While the BGV-based method of Bonte and Iliashenko (CCSW '20) requires $O(|P| \cdot |T|)$ secure character comparisons to find a pattern $P$ in a text $T$, our method reduces this to $O(|P|\log |T|)$ comparisons, achieving improved scalability for large texts. As a result, our method can find a pattern of length 100 in an encrypted text containing genomic data of one million characters in less than 5 minutes, where prior work would require approximately 5 days for the same task. These results highlight the practicality of TFHE and its potential for large-scale secure string search.

An adaptor signature scheme can be seen as committing to a signature using an NP statement, in such a way that (1) the commitment, called a presignature, is verifiable, (2) the corresponding witness enables opening the commitment (adapting the presignature), and (3) seeing a valid commitment-opening (presignature-signature) pair leaks the witness. In the blockchain space, where signed transactions must be broadcast to the public to take effect, this last property allows "forcing" a party to leak a witness for possibly multiple presignatures issued for the same NP statement. This then gives rise to many applications such as atomic swaps or payment channels. Importantly, in prevailing adaptor signature schemes, presignatures are already technically signatures, in that they are non-interactive zero-knowledge proofs of knowledge of the signing key. This has a number of consequences, most important being that the presignature constitutes evidence of intent to participate in a protocol based on adaptor signatures. Perhaps surprisingly, however, for many practical applications, this strong "binding" of presignatures turns out to be non-essential. In this work, we revisit the definitions of adaptor signature schemes, demonstrating that prevailing security requirements are often too strict. To this end, we formally define fair signature exchange (FSE) and abandon the assumption implicit in prior work that adaptor-based FSE must be "symmetric" with both parties using the same adaptor signature scheme. The resulting relaxation of security requirements leads us to the notion of presignature deniability, an extension to adaptor signature schemes that we define formally and construct from various assumptions.

Dynamic universal accumulators compress an evolving set into a short digest with membership and non-membership witnesses for each element. Bilinear Pairing (BP) accumulators offer succinct witnesses and fast verification, but their public parameters size, witness generation and dynamic costs scale linearly with the set size in the trapdoorless setting. To address this bottleneck, we present HACC, a trapdoorless hierarchical accumulator that organizes capacity-bounded BP accumulators over ordered buckets into a $t$-ary tree. By fixing the node capacity $t$, HACC is a pairing-based accumulator whose public parameters can be independent of the set size $n$. Its ordered buckets yield native non-membership proofs and $\mathcal{O}(t\log_t n)$ witness generation cost, and non-cascading bucket split and merge mechanisms keep it fully dynamic at worst-case $\mathcal{O}(t\log_t n)$ dynamic cost with amortized $\mathcal{O}(1)$ witness updates. Its witnesses are of size $\mathcal{O}(\log_t n)$ and verify with as many pairings, which an optional path compression via polynomial multiproofs reduces to a constant for read-heavy epoch-based settings. We prove HACC correct and sound under the $t$-SDH assumption in the random oracle model. Experimentally, under comparable budgets, HACC accelerates element update and witness generation by $8.0\times$--$5087\times$ over a monolithic BP accumulator (Nguyen, CT-RSA'05, Damgård et al., eprint'08, and Srinivasan et al., CCS'22) while consuming $15.6\times$--$15933\times$ smaller public parameters.

This paper presents a pairing-based non-interactive batch argument (BARG) for NP in the common reference string (CRS) model with constant-size proofs and constant-cost verification. Our construction is fully black-box in its use of the underlying group and achieves a weak form of somewhere extractability under a new $q$-type assumption in composite-order pairing groups. We further show that this extractability guarantee implies somewhere soundness. Prior pairing-based BARGs in this setting suffer from proof size and verification cost proportional to the size of the Boolean circuit computing the NP relation, and our work removes this dependence. Technically, our starting point is the Waters--Wu framework [Asiacrypt'25] and the main idea is to replace the univariate polynomial commitment with a bivariate polynomial commitment together with univariate sumcheck arguments. This allows us to compress both wire and gate checks into a constant number of algebraic identities, leading to constant-size proofs and constant-cost verification. As a demonstration of the resulting somewhere-sound BARG, we show that it simplifies and improves existing generic constructions of NIZKs and rate-1 BARGs. In particular, we obtain: -a generic construction of NIZKs for NP from our somewhere-sound BARG, together with a one-time dual-mode commitment scheme with extraction and a leakage-resilient weak pseudorandom function. The resulting proof size is independent of the circuit size, whereas prior work incurs circuit-size-dependent proof overhead and either requires a local PRG or commits to all internal wires; -a generic construction of rate-1 BARGs from pairing-based assumptions by combining the somewhere sound BARG obtained from our construction with existing rate-1 fully local somewhere-extractable hashing. The resulting proof size is $h+\mathsf{poly}(\lambda,\log\ell)$, whereas prior work either requires proof size $h+o(h)\mathsf{poly}(\lambda,\log\ell)$ or relies on a RAM SNARG with partial-input soundness. Both generic constructions rely on weaker or fewer cryptographic primitives than prior work and the construction of NIZK also avoids the complicated parameter selection in prior work.

We present $\textsf{Sluice}$, a read-write streaming Groth16 prover that reduces $\textit{prove-phase}$ random-access working memory from $\mathcal{O}(N)$ to $\mathcal{O}(\log N)$ once the CRS, QAP, and witness are materialized as private streams. It preserves the standard Groth16 interface: a proof of 3 group elements, 3-pairing verification, and unchanged verifier contracts. Our key technical contribution is $\textit{Split-Butterfly-Merge}$ ($\mathsf{SBM}$), an NTT algorithm in the read-write streaming model with $\mathcal{O}(\log N)$ memory, $\mathcal{O}(N \log N)$ total I/O, and $\mathcal{O}(\log N)$ sequential passes over external storage. Combining SBM with streaming sparse R1CS evaluation and chunked Pippenger MSM yields a verifier-compatible Groth16 proving path that exchanges RAM for sequential storage I/O and wall-clock time. Our prototype uses a fixed-window MSM engineering point; the measurements validate memory reduction and proof compatibility, while the theorem states the asymptotically tuned MSM schedule. We implement $\textsf{Sluice}$ over BN-254. Direct prove-only runs produce valid 128-byte proofs through $N=2^{25}$. The same-size bounded-memory comparison is at $N=2^{23}$: $\textsf{Sluice}$ succeeds under an 8GB Linux cgroup cap, whereas the standard prover is killed under 8GB and 12GB caps and succeeds only at 16GB. These results position $\textsf{Sluice}$ as a storage-rich, RAM-limited proving option rather than a replacement for optimized in-memory provers.

The Bitcoin Lightning Network secures hundreds of millions of dollars, yet channel endpoints rely on vulnerable single online keys. Although threshold signatures are routinely used to protect on-chain Bitcoin, no practical deployment has been possible for Lightning channels. This is because thresholdizing a Lightning party requires nesting a threshold signature scheme inside of an established two-party MuSig2 protocol without altering its nonce exchange or message flow. In this work, we resolve this limitation by formalizing nested threshold multi-signatures, a new cryptographic primitive for thresholdizing one participant inside a multi-signature protocol. As an instance of this primitive, we present Iceberg, the first construction for nested threshold MuSig2 signatures. Iceberg enables one side of a Lightning channel to operate as a $t$-of-$n$ threshold group while appearing to the counterparty as a standard MuSig2 participant. As a result, threshold custody can be deployed unilaterally on today's Lightning Network without requiring any modifications to Bitcoin, the Lightning protocol, or channel counterparties. We prove the security of Iceberg, integrate a prototype into a production Lightning node, and benchmark its performance. Our measurements show that thresholdizing a Lightning channel incurs only modest overhead, since a threshold group tolerating one corrupted member sustains over $93\%$ of the payment throughput of an unmodified endpoint.

We construct (1-hop) fully homomorphic encryption (FHE) schemes with chosen-ciphertext (CCA) security from the learning with errors (LWE) assumption in the standard model. Security of our construction only relies on the circular-secure LWE, which matches the assumptions needed for FHE with the basic chosen-plaintext security. Besides, the scheme achieves a security notion that is strictly stronger than the CCA1 security. Prior FHE schemes with even just CCA1 security require either the random oracle model or non-falsifiable assumptions. The construction follows the well-known Naor-Yung double encryption paradigm. However, unlike previous works [Boneh et al., ITCS 2012; Canetti et al., PKC 2017; Manulis and Nguyen, Eurocrypt 2024], which employ general zero-knowledge succinct non-interactive arguments of knowledge (ZK-SNARKs), we design a special succinct argument to prove the validity of FHE ciphertexts. The succinct argument is constructed from batch arguments for NP and a new primitive called predicate extractable commitment, which may be of independent interest.

The current state of the art for cryptanalysis generic rank-2 module LIP schemes invokes an SVP oracle on the canonical real embedding, discarding the quaternionic structure made available by the reduction of rank-2 module LIP to the reduced-norm Principal Ideal Problem (nrd-PIP) over quaternion algebras (we note, that since writing, this is no longer the case for certain instances, such as Hawk). We address this gap by giving, to our knowledge, the first lattice reduction algorithms over quaternion rings applied in a cryptographic setting, and the first description of quaternion BKZ. We extend the celebrated LLL algorithm to leverage algebraic properties of quaternion orders and novel post-processing steps to design an LLL algorithm for lattices in not-necessarily-maximal orders. The strategy is to reduce over the Euclidean overlattice and then post-process, giving two routines: one returning a basis of a sublattice with the best bounds, the other a true basis of the original lattice at the cost of output quality. We further consider blocksize two BKZ as a generalisation of the LLL algorithm, and then extend this to arbitrary blocksize; utilising results on the shortness of Gauss and HKZ reduced bases and the relationship of successive minima for our specific sublattice. We then apply these algorithms to ideal lattices arising from nrd-PIP, including those instances given by rank-2 MLIP over cyclotomic fields such as Hawk, via a modification of the canonical embedding that preserves both dimension and quaternionic structure. This allows us to reduce a lattice basis of rank a constant factor of four smaller than the standard real embedding, improving basis bounds and asymptotic complexity in the generic setting.

Repeat--accumulate--accumulate (RAA) codes are sparse random linear codes with linear-time encoders. Although RAA ensembles can have linear minimum distance with high probability, this does not determine how often a randomly sampled code falls below a prescribed relative-distance threshold. We determine this lower-tail probability and identify the rare mechanisms that dominate it. Let \(n\) be the message length, \(r\ge4\) a fixed repetition factor, and \(N=rn\) the block length. For the randomly scaled ensemble \[ G=R\Pi_1V_1A\Pi_2V_2A, \] where \(R\) is repetition, \(A\) is the prefix-sum accumulator, \(\Pi_1,\Pi_2\) are independent uniform interleavers, and \(V_1,V_2\) have independent uniform nonzero diagonal entries in \(\mathbb F_q\), we prove that, for every fixed \(0<\delta\le1/2\) and \(\gamma>0\), \[ q-1\ge\gamma N \quad\Longrightarrow\quad \mathbb P[d_{\min}(G)\le\delta N] =\Theta_{r,\delta,\gamma}(N^{1-r}). \] For the unscaled ensemble \[ G_0=R\Pi_1A\Pi_2A, \] if \(\operatorname{char}(\mathbb F_q)>r\) and \(0<\delta\le1/10\), then \[ \mathbb P[d_{\min}(G_0)\le\delta N] =\Theta_{r,\delta}(N^{2-r}). \] Thus random scaling improves the failure probability by one power of \(N\). We also prove \[ \mathbb P[d_{\min}(G)\le\delta N] =\Omega_{r,\delta}\!\left( N^{1-\lceil r/2\rceil}(q-1)^{-\lfloor r/2\rfloor} \right), \] showing that linear field growth is necessary, in asymptotic order, for the constant-factor \(N^{1-r}\) law.

Expand–accumulate (EA) codes are sparse linear codes underlying constructions of correlated pseudorandomness and field-agnostic succinct arguments. In “Field-Agnostic SNARKs from Expand–Accumulate Codes” (CRYPTO 2024), Block et al. conjectured that a single fixed-row-weight EA component already achieves constant relative distance with inverse-polynomial failure probability. We prove this conjecture in a stronger, field-uniform form. For every rate $R\in(0,1)$, there exists $\delta_R>0$ such that, for every target exponent $C>0$, one can choose $\gamma=\gamma(R,C)>0$ for which the fixed-row ensemble with $t=\lceil\gamma\log N\rceil$ satisfies \[ \mathbb{P}\!\left[ \min_{x\in\mathbb{F}_q^{\lfloor RN\rfloor}\setminus\{0\}} \operatorname{wt}(xEA) \le \delta_R N \right] \le N^{-C} \] for all sufficiently large $N$. The same constants work for every prime power $q$; in particular, the field may vary arbitrarily with the block length. Thus, a single fixed-row-weight EA component is asymptotically good over all finite fields, and its polynomial reliability exponent can be made arbitrarily large by increasing the row-weight constant. The proof separates sparse and high-weight messages. Sparse messages are handled through expansion and a compact analysis of accumulator cancellations, while high-weight messages are controlled by a surplus of linear constraints over large fields and a stochastic accumulator analysis over bounded fields. A terminal-boundary obstruction shows that, for $t=\Theta(\log N)$, inverse-polynomial failure is qualitatively optimal.

Anonymous tokens with private metadata bit (ATPM) have received increased interest as a method for anonymous user authentication while also allowing the issuer to embed trust signals inside the token that are only readable by the authority who holds the secret key. However, all existing ATPM protocols require interaction during issuance as the client must send a blinded request and wait for the issuer to sign, introducing latency and scalability bottlenecks. In this work, we present the first Non-interactive Anonymous Token (NIAT) scheme with a private metadata bit. Our design builds on structure-preserving signatures on equivalence classes (SPS-EQ) and recent advances in non-interactive blind signatures. With NIAT, tokens can be issued without any online interaction, enabling asynchronous pre-computation and drastically reducing issuer workload. We formalize NIAT security definitions, propose an efficient construction under standard assumptions and experimentally evaluate its performance. We also present an extension to our NIAT construction that allows the identification of clients who attempt to double-spend a token (i.e., present the same token twice) and argue that non-interactive schemes are uniquely positioned to offer this essential feature.

Lattice-based blind signatures have attracted significant attention in recent years due to the rapid growth of digital currencies, the increasing demand for privacy-preserving digital interactions, and the ongoing transition toward quantum-resistant cryptographic primitives. While blind signatures provide anonymity guarantees, achieving fairness without compromising privacy to a third party remains a challenging problem. Blind adaptor signatures (BAS) address this limitation by enriching blind signatures with conditional-execution functionality, enabling fair exchange while preserving user anonymity. In particular, a BAS scheme allows a user to engage in an atomic swap with a verifier using an adapted blind signature obtained from a signer, thereby maintaining privacy against the signer while ensuring fairness between the user and the verifier. In this work, we observe that the ABDLOP commit-and-prove framework (CRYPTO 2022) exhibits a dichotomic structure that can be leveraged to realize adaptor functionality. Building on this, we propose a lattice-based blind adaptor signature (L-BAS) scheme that simultaneously achieves fairness along with the privacy guarantees of blind signing. Compared with the underlying lattice-based blind signature scheme, our construction incurs only a modest overhead, increasing the signature size by approximately 5.2 KB while largely preserving the efficiency of the original system. We formally analyze the security of the proposed construction and prove that it satisfies extractability, unique extractability, computational pre-verification soundness, one-more unforgeability, and blindness under standard lattice-based assumptions. Our results demonstrate that fairness can be incorporated into lattice-based blind signatures with minimal performance degradation, making the proposed scheme a practical candidate for privacy-preserving and quantum-resistant fair exchange applications.

In dynamic group signature schemes (GSS), forward security ensures that newly joined members cannot generate valid signatures for past time periods. Additionally, non-frameability prevents even privileged entities, such as the group manager or key issuer, from falsely attributing signatures to honest users. Most GSS either lack non-frameability or face significant efficiency challenges when updating signing keys to ensure forward security. In this paper, we introduce a forward-secure dynamic group signature scheme that guarantees non-frameability. We also present an alternative scheme that, while lacking non-frameability, offers higher efficiency compared to existing schemes with comparable security. For both protocols, we propose efficient revocation mechanisms that allow an authority to revoke users without requiring re-registering existing users. Additionally, we propose a technique that enables the verification process of both protocols to be performed in batches. We prove the security of our schemes, ensuring the standard dynamic GSS security notions; anonymity, traceability and non-frameability (second scheme). Experimental results demonstrate that our schemes are competitive in both computational and communication efficiency when compared to existing literature.

Updatable Public-Key Encryption (UPKE) augments the security of PKE with Forward Secrecy properties. While requiring more coordination between parties, UPKE enables much more efficient constructions than full-fledged Forward-Secret PKE. Alwen, Fuchsbauer and Mularczyk (AFM, Eurocrypt’24) presented the strongest security notion to date. It is the first to meet the needs of UPKE’s most important applications: Secure Group Messaging and Continuous Group Key Agreement. The authors provide a very efficient construction of an Updatable Key Encapsulation Mechanism (UKEM), implying UPKE, that satisfies their notion with classic security based on the Computational Diffie-Hellman (CDH) assumption in the Random Oracle Model (ROM). No existing post-quantum UPKE/UKEM construction is known to meet the AFM definition. We present and implement practical secret-key recovery attacks in the AFM adversarial model for all proposed parameter sets of two PQ schemes including the most efficient one to date, due to Abou Haidar, Passelègue and Stehlé (APS, Asiacrypt’23). If the UKEM schemes were used in a real-world group messaging application, the attacks would correspond to realistic execution scenarios, even when targeting a 100% success probability. Next, we present the first post-quantum UKEM construction meeting (a slight relaxation of) the AFM security notion. When based on the Module-LWE assumption, our construction is more efficient than prior PQ constructions, while achieving stronger security. More concretely, public key sizes are about 1/2 that of APS and ciphertext sizes are about 14% smaller. As the AFM security proof relies on random self-reducibility of CDH, which has no analogue for lattices, we develop a new proof technique for strong UKEM, identifying the core properties required from the underlying (lattice-based) encryption scheme.

Lattice-based zero-knowledge proofs are now efficient enough for practical use, but in all known constructions a single prover holds the entire witness and is therefore a single point of failure. Thresholdizing them is understood only for three-round $\Sigma$-protocols, which certify shortness only $\textit{approximately}$. The $\textit{exact}$ statements needed by applications such as anonymous credentials require more rounds and rely on rejection sampling, and neither property survives thresholdization. We construct the first lattice-based threshold zero-knowledge proof systems for exact relations. The witness is Shamir-shared among $\mathtt{n}$ parties, any $\mathtt{t}$ of them can jointly produce a proof, and the proof has the same form as a single-prover proof, only a factor $\sqrt{\mathtt{t}}$ larger, with verification unchanged. We thresholdize the product proof of Attema, Lyubashevsky, and Seiler (CRYPTO 2020) and the exact proof of Esgin, Nguyen, and Seiler (ASIACRYPT 2020), making both rejection-free using Hint-MLWE and evaluating them over threshold homomorphic encryption. We define threshold commit-and-prove protocols with the corresponding zero-knowledge and simulation-extractability notions, and prove our constructions secure against passive adversaries that statically corrupt at most $\mathtt{t}-1$ parties. Of independent interest, we show that the Fiat--Shamir transforms of both proof systems are simulation-extractable in the random oracle model, and that MLWE remains hard when secrets are drawn from the subring fixed by a ring automorphism.

Private Set Operations (PSO) enable mutually untrusted parties to securely compute arbitrary functions (e.g., union, intersection, and cardinality) over their private input sets. These operations have wide applications in many real-world scenarios. Existing PSO protocols fall short of practical deployment for several reasons. (1) \textit{Function-specific}. Real-world privacy-preserving applications often require multiple set operations within the same task, while existing solutions typically address individual functionalities (e.g., intersection or union) in isolation, making it difficult and costly to support diverse set operations in a unified and efficient manner. (2) \textit{Lacking malicious security}. As PSO is commonly employed in highly sensitive applications, it is often necessary to provide strong security guarantees against malicious adversaries. Unfortunately, most existing works only achieve semi-honest security, which limits their practical applicability. (3) \textit{Restricted settings}. The majority of existing works focus exclusively on the two-party setting. How to extend them securely and efficiently to the multi-party setting while tolerating a malicious majority remains unclear. To date, designing a maliciously secure multi-party PSO (mPSO) framework that efficiently supports diverse set operations remains an open challenge. This paper presents the \textit{first} maliciously secure mPSO framework, named UM-PSO, that supports a broad range of set operations with practical efficiency. At the core of our framework is a function-independent preprocessing phase that prepares a reusable pool of secret-shared items, which can then be leveraged to securely compute diverse set functionalities in the online phase. To achieve malicious security efficiently, we design verification mechanisms on top of SPDZ-based authenticated secret sharing, along with tailored techniques and optimizations to further improve practical performance. We implement our protocols and report concrete performance results. For a representative setting with 5 parties and a total of $2^{12}$ 128-bit items, our framework achieves an online running time of $0.627$ seconds and incurs $3.35$ MB of communication. Compared to the baselines, our framework achieves up to $51\times$ speedup and up to a $76\times$ reduction in communication.

Modern public-key cryptography is threatened by advances in quantum computing. As a result, there has been a shift towards cryptographic algorithms that can resist attacks by a quantum computer. However, these algorithms use significantly longer keys, and produce larger ciphertexts and digital signatures than their classical counterparts. These bigger sizes pose problems for devices that are bandwidth- and/or power-limited, and wish to establish a secure, quantum resistant communication channel with another device. In order to reduce the overhead of using these algorithms in challenging environments while maintaining security posture, we present Compact Authenticated Key Exchange – Hiding Identities (CAKE-HI). To evaluate our protocol, we compare the key exchange handshake size and computational efficiency of mutual authenticated TLS and CAKE-HI. Measurements show that CAKE-HI significantly reduces the handshake size and the computational overhead of establishing a quantum-secure link. In addition, we formalize and prove security properties about CAKE-HI in the symbolic and computational model using the protocol analysis frameworks Verifpal and CryptoVerif.

Private repositories remain readable to Git hosts despite transport and at-rest encryption. We present SafeHub, an end-to-end encrypted Git hosting system. It encrypts repository contents and semantic metadata - file names, commit messages, authors, branches, issues, pull requests, and refs - so the host sees only ciphertext, opaque identifiers, lengths, and order. Each repository is a Messaging Layer Security (MLS) group, providing admin-mediated membership, post-compromise healing, and per-invite history windows. Ordinary Git behavior is preserved within each member's window: branches, merges, and blame still work. Forward-only members start from a join shallow snapshot rather than the full past. Confidentiality alone is not enough: Git's hash-linked objects do not protect mutable refs. SafeHub records refs in an encrypted, device-signed, hash-chained manifest that detects rollback against a member's own anchor and host forks when members compare checkpoints; force-pushes require administrator co-signatures. We specify a single ideal functionality F_safehub for the system and prove that SafeHub universally composably realizes it against a malicious server and adaptive member corruptions, in a hybrid model over group key agreement and certification, assuming secure erasure in the quantum random oracle model. Our NIST PQ Category-5 Rust prototype measures full-stack push, pull, fetch, clone, merge, rebase, and force-push on a client-server pair of AWS Graviton4 hosts, together with the epoch rotation and consolidation that Git has no counterpart for. Against Git on its lowest-overhead native transport, wall-clock push runs 1.45x plain Git at a 0.05 MB delta and 0.98x at a 5 MB one, its marginal cost 46.7 ms/MB against Git's 49.3. We compare SafeHub with five other systems - plain Git, git-crypt, git-remote-gcrypt, and a reimplementation of the closest peer - over a single transport, with clients and remotes on separate hosts. The comparison separates designs whose cost follows the edit from designs whose cost follows the whole file. For a fixed 1 KiB edit, with the edited file growing from 10 KiB to 8 MiB, SafeHub's cost per update remains constant at 6.7 kB, because it seals the packfile Git has already built, whereas the systems that encrypt each file individually grow with the file and reach 8.39 and 13.4 MB. On that shared transport SafeHub is the fastest of the six at push, pull, fetch, merge, rebase, and force-push, each constant in history depth, and its stored size matches plain Git to within 0.2%, whereas the per-file encryption used by the other systems costs 13 to 21 times as much. The cost that does not amortize is clone, which grows with sealed history: a host that cannot read a repository cannot repack it.

Oblivious transfer (OT) is a foundational tool in secure computation. Random OT-correlated pairs of the form $(r_0,r_1)$ and $(b,r_b)$, where $r_0,r_1,b \stackrel{{}_\$}{\leftarrow} \{0,1\}$, significantly speed up secure computation protocols. Pseudorandom correlation functions (PCFs), introduced by Boyle et al. (FOCS 2020), are an efficient means of non-interactively generating correlated pairs. In a PCF, two parties store short keys that are used to locally generate large amounts of correlated pairs. While pre-quantum PCFs for OT achieve highly compact key sizes (e.g., $30$ kB), a significant gap remains in the post-quantum regime, where existing solutions rely on lattices or learning-parity-with-noise-style assumptions and yield much larger keys. We construct compact post-quantum PCFs for OT. Our construction has key sizes in the range of $100$ kB, approaching the compactness of pre-quantum PCFs and seven times smaller than the most compact state-of-the-art post-quantum alternatives. The key size of our PCF remains invariant regardless of the target number of OTs, in contrast to prior alternatives. We estimate a throughput of $7$ OTs per second for our PCF. We additionally provide a security proof in the quantum random oracle model, constituting the first such analysis of a post-quantum PCF. The core of our construction is a new, compact constrained pseudorandom function (CPRF) for inner-product membership predicates. Its security is based on a natural extension of the parallelization problem, which we introduce as the parallelization problem with auxiliary inputs. We provide an extensive analysis of this assumption as well as an implementation of our construction.

We present the first fully distributed, code-based polynomial commitment scheme (PCS) that achieves linear prover time and polylogarithmic communication for multilinear polynomials. Our construction builds on Brakedown with proof composition. We design a distributed proof of correct linear encoding. Codeword validity is reduced to a sumcheck relation over the sparse parity-check matrix, whereas systematic consistency is verified through multilinear evaluation checks. These techniques preserve linear prover complexity while reducing the communication size between sub-provers to polylogarithmic scale. We implement our construction and evaluate it on multilinear polynomials ranging in size from $2^{22}$ to $2^{28}$. The prover exhibits near-linear parallel scalability. Compared with existing evaluated distributed PCS implementations with 8 parties, it reduces communication by at least $13\times$ at every tested polynomial size, while its prover time remains within $1.31\times$ of the fastest implementation. These results demonstrate that our asymptotic communication improvements translate into substantial concrete savings while retaining efficient proving.

Pseudorandom error-correcting codes (PRCs), introduced by Christ and Gunn at CRYPTO’24, combine pseudorandomness with error correction, providing a natural abstraction for robust watermarking and steganography on generative AI models. Subsequent standalone notions, which are ideal security for secret-key PRCs and CCA-style security for public-key PRCs, are oracle-based and do not capture composable use with explicit parties, sessions, and corruption. We give a UC treatment of PRCs via corruption-aware ideal functionalities for both settings. Under non-adaptive corruption, the UC notions recover the standalone ones. Under adaptive corruption, we identify a common obstruction: dummy codewords sampled before corruption, together with their neighborhoods, must later be opened as valid PRC codewords. We formalize this as a decoder-non-committing code (NC-PRC), which any adaptively UC-secure realization must induce. We then capture failures of such openings via targeted low opening capacity, show it rules out robust NC-PRCs, and prove that LDPC-based PRCs have this property hence do not admit a NC-PRC. On the positive side, we sketch two compilers to lift error-correcting codes to admit NC-PRCs: a secret-key one from a puncturable PRF and indistinguishability obfuscation (iO), and a public-key one from a smooth projective hash function (SPHF), both evading the barrier via programmable acceptance. Finally, we identify a fresh-codeword explanation barrier for public-key PRCs: accepted unseen codewords cannot be explained from public information without violating pseudorandomness, hence public-key UC realizations require a trapdoor or an idealized setup, and PRC-based watermark detection is inherently designated-verifier.

The approximate Closest Vector Problem (CVP) is a core computational problem underlying many post-quantum lattice-based signature schemes, including Dilithium, one-more-ISIS, and HuFu. While the security of these schemes is typically expressed in terms of the Inhomogeneous Short Integer Solution (ISIS) problem, it is well-known that ISIS can be efficiently reduced to approximate CVP. Despite its foundational role, approximate CVP with non-negligible approximation factors remains far less explored than other lattice problems such as SVP or LWE, creating a critical gap in both theory and practice. In this work, we bridge this gap by advancing the Colattice framework for solving approximate CVP with large approximation factors. More concretely, (1) We define a practical version of the Colattice algorithm and propose a randomized Nearest Colattice for generating more than one approximate closest vector. (2) Define a formal strategy space for blockwise approximate CVP. (3) Propose a polynomial-time strategy selection algorithm and prove its correctness under standard lattice heuristics. (4) Building on this, we design an efficient security estimator for approximate CVP in both Euclidean and Infinity norms, and extend it to approximate batch-CVP attack settings. (5) By applying this estimator, we perform concrete security evaluations of Dilithium, HuFu, and one-more-ISIS. Our results reveal that almost none of the evaluated schemes withstand approximate batch-CVP attacks with $2^{32}$ queries. (6) We integrate a slicer and Colattice into G6K-CPU, leveraging the Locality-Sensitive Hashing (LSH) technqiue for nearest neighbors search (NNS). This is the first practical implementation of an NNS-accelerated slicer. Our results demonstrate the practical efficiency of approximate CVP and batch-CVP attacks, highlighting the need for more accurate security estimation. These findings underscore the practical importance of accurate approximate CVP modeling and call for a reassessment of current parameter sets in post-quantum signature schemes.

Folding/Accumulation schemes are a powerful tool for building scalable proof systems. However, standard approaches for leveraging folding schemes, such as IVCs or PCDs, require embedding hash functions (modeled as random oracles) into recursive circuits, introducing both security concerns and significant proving overhead. We re-envision how to use folding schemes, and introduce Symphony, the first proving paradigm that leverages folding schemes as a black box without embedding hashes in SNARK circuits. It is memory-efficient, parallelizable, and plausibly post-quantum secure, with polylogarithmic proof size and verification. The (low-memory) prover requires O(log log n) passes of the input data and its computation is dominated by committing to the input witnesses. A core component of our construction is a new lattice-based folding scheme that compresses a large number of NP-complete statements into one in a single shot. Furthermore, we design a generic compiler that converts a folding scheme into a SNARK without embedding the Fiat-Shamir circuit into proven statements.

Ghoshal, Ishai, Jain, and Sun recently introduced a novel quasipolynomial-time distinguisher for GRS subcodes (including Goppa codes), leaving key recovery as an open problem. This note presents an approach for turning the distinguisher into a full key-recovery attack. The overall complexity is dominated by a few executions of the distinguisher, and the approach is experimentally validated on Goppa codes over $\mathbb{F}_4$. We conjecture that this recovery route applies to binary Goppa codes as well.

In the context of PKE schemes, Gagliardoni et al. proposed at PQCrypto 2021 a qIND-qCPA security notion (a superposition-based analogue of the classical IND-CPA security notion), by using the theory of so-called type-2 unitary operators. On one hand, this notion is very natural, closely mirrors the classical intuition, and can be handled without relying on complex techniques such as Zhandry’s compressed oracles. On the other hand, it is restricted to a certain class of PKE schemes (so-called isometric). Moreover, it is not immediately clear how to extend the definition to chosen-ciphertext attack (CCA) scenarios, mainly due to the possibility of decryption failures – something that is entailed by most quantum-resistant PKE schemes. In this work, we use the theory of type-2 operators to extend superposition-based security notions to any PKE schemes, in the CPA and CCA setting, without Zhandry’s compressed oracle technique. We start first by showing that a trivial extension of Gagliardoni et al.’s techniques to the general case is not possible, even for the CCA1 case, by identifying barriers preventing the realization of a ‘natural’ type-2 decryption operator. Then we define a subclass of PKE schemes (which we call ‘strongly decryptable’ ), for which it is easy to circumvent the aforementioned barriers and to define superposition-based CCA1 and CCA2 notions. Further, we introduce a novel transformation (that we call ‘purification’) which applies to any PKE scheme, producing a ‘quasi-PKE’ scheme, for which it is possible to define properties that mimic the security notions defined for strongly decryptable schemes; we can thus ‘unload’ the security definitions for an arbitrary PKE scheme on its purification. Finally, we show implications and separations between our security notions, as well as constructions.

Practical implementations of synchronous MPC protocols typically require each party to advance to the next round as soon as they have received all expected messages. This deviates from the theoretical synchronous round-based model, where instead each party advances in the next round after a timeout. To capture this gap between theory and practice, Asharov, Chandramouli, Cohen and Ishai in Eurocrypt 2025 proposed a new model where the adversary is super-rushing. In this, the adversary can see future messages of some honest parties before delivering current-round messages to slower ones. In this work, we study super-rushing security in both the computational and statistical settings, and design round-preserving compilers that transform standard synchronous MPC protocols into ones secure against super-rushing adversaries. Ours is the first work to investigate the security of computational MPC protocols against a super-rushing adversary.

This work describes a digital signature scheme constructed from a zero-knowledge proof of knowledge of a pre-image of the Rescue Prime Optimized (RPO) permutation. The proof of knowledge is constructed with the DEEP-ALI interactive oracle proof combined with the Ben-Sasson--Chiesa--Spooner (BCS) transformation in the random oracle model. The EUF-CMA security of the resulting signature scheme is established from the UC-friendly security properties of the BCS transformation and the pre-image hardness of the RPO permutation. The implementation of the scheme computes signatures in 13 ms and verifies them in 1 ms on a single core when the BCS transform is implemented with the Blake3 hash function. (The multi-threaded implementation signs in 9.2 ms and also verifies in 1 ms.) These speeds are obtained with parameters achieving 122 bits of average-case security for \( 2^{122} \)-bounded adversaries with access to at most \( 2^{64} \) signatures.

SQIsign is an isogeny-based post-quantum signature scheme whose public keys and signatures are remarkably compact. However, since SQIsign relies on arithmetic in quaternion algebras over the field of rational numbers, no fixed-precision integer arithmetic for SQIsign had been established until recently, hindering constant-time implementation and deployment on memory-constrained devices. Recent work by Kim et al. instantiated an SQIsign implementation with fixed-precision integer arithmetic by deriving uniform worst-case bounds for the quaternion algorithms used in key generation and signing. Nevertheless, the resulting precision budget remains large, exceeding 13 times the public key size. Consequently, this forces implementations to reserve wide integer buffers throughout the computation. This increases the memory footprint and reduces the suitability of fixed-precision SQIsign for constrained platforms. In this work, we present compact quaternion algorithms that substantially reduce the fixed-precision memory requirements of SQIsign. First, we modify and analyze quaternion algorithms for SQIsign, in which large intermediate integer values appear. Then, we derive the improved uniform worst-case size bound on integers during the key generation and signing procedures. As a result, we reduce the required precision budgets from 7026/10713/14150 bits to 1665/2521/3319 bits for the NIST-I/III/V security levels, respectively, corresponding to improvements of $76.30\%$, $76.47\%$, and $76.54\%$. We also provide a fixed-precision implementation of SQIsign applying these improved precision budgets and accelerating previous inefficient implementation of fixed-precision integer arithmetic. Compared with the previous fixed-precision implementation, our implementation achieves performance improvements larger than $99\%$ for both key generation and signing procedures at each security level.

RIPEMD-160 is an ISO/IEC hash function standard based on the Merkle-Damgård structure with a double-branch compression function. There have been many attempts at modular differential attacks on reduced RIPEMD-160, with the best previous result being a 40-step practical collision attack achieved in 2023. That attack constructs a simple local collision in round 2 of the left branch to minimize uncontrolled conditions. To achieve this, differences must be introduced into many message words, which constrains the maximum number of steps that can be attacked. To overcome this limitation and target more steps, we propose a new differential characteristic structure that abandons the sparse local collision in round 2 and instead uses a single continuous differential characteristic spanning rounds 1 to 2 for each branch. This structure allows us to inject a difference into only one message word. Using an automatic search tool based on the high-performance parallel SAT-solver PRS, we identify suitable differential characteristics by imposing more control over conditions, differences, and the probability of proper propagation. Based on the differential characteristics, we identify three colliding message pairs for 42-step RIPEMD-160 with theoretical time complexity of approximately $2^{47.4}$, thereby improving the best practical collision attack by 2 steps on this hash function.

A $(k,n)$-robust combiner for a primitive $\mathcal{P}$ combines $n$ candidate instantiations of $\mathcal{P}$ into a single scheme that remains secure as long as at least $k$ of them remain secure. Robust combiners have been extensively studied for primitives such as hash functions, public-key encryption, and oblivious transfer, but much less is known in the setting of cryptographic groups. In this work, we initiate the study of robust combiners for cryptographic groups in Maurer's generic group model (GGM), where algorithms access group elements only through abstract algebraic operations. We ask whether one can combine $n$ candidate groups into a single group that remains secure provided that at least $k$ of the underlying groups remain secure. A natural baseline is the direct-product construction, which preserves search hardness but fails for decisional assumptions and incurs substantial representation overhead. We show that these limitations are in fact inherent. Our first result is a complete impossibility for the decisional Diffie--Hellman assumption: for every polynomially bounded $n$ and $k$ with $k<n$, there is no generic $(k,n)$-robust combiner for cryptographic groups that preserves DDH security. Our second result gives a tight threshold for search assumptions in the regime where $n$ and $k$ are fixed constants. For the discrete logarithm problem, robust generic combination is possible when the combined group order is large enough to encode the secrets of $n-k+1$ components; concretely, if $\log N \ge (n-k+1)\lambda$, where the component groups have distinct $\lambda$-bit prime order, then a robust combiner exists. Conversely, if $\log N \le (n-k)\lambda$, then no generic $(k,n)$-robust DLog-secure combiner exists. These results identify a fundamental limitation of robust hedging at the group level. Decisional assumptions such as DDH cannot be robustly combined in the GGM, while search assumptions admit robustness only at essentially optimal representation cost. Consequently, robustness for group-based cryptography must in general be achieved at higher layers, such as protocol design or key derivation.

Threshold signatures have regained a strong interest recently, driven by applications in cryptocurrencies and NIST's ongoing call for threshold schemes. Among them, FROST - a classical threshold Schnorr signature scheme already in real-world deployment - stands out. Its appeal lies in three core features: partially non-interactive signing, non-interactive identifiable abort (IA), and proactive security. In contrast, while post-quantum (PQ) threshold signatures have seen significant advances in recent years, no existing scheme simultaneously provides even two of these features. Considering the imminent need to migrate to PQ cryptography, this state-of-the-art remains unsatisfactory. In this work, we propose Hermine, a lattice-based threshold signature that offers the full feature set of FROST under standard lattice assumptions. Hermine is designed to efficiently support the Medium scale of parties ($N \le 64$) as defined in the NIST threshold call, producing a small \Raccoon signature of size $11$ KB. Our main technical contribution is introducing an everywhere-short secret sharing, which splits a short secret vector $\mathbf{s} \in R_q^\ell$ into short shares and admits a short linear reconstruction algorithm. While the resulting construction appears intuitive, its security proof requires a non-trivial, fine-grained analysis of the information on $\mathbf{s}$ that is inherently leaked by the short shares. Furthermore, we formalize game-based unforgeability and IA definitions with proactive security, which may be of independent interest.

Zero-knowledge execution of high-level programs proceeds by repeatedly evaluating CPU steps. Each such step privately selects and evaluates an instruction (possibly involving memory access) from a rich instruction set. Building on this paradigm, ZEE (Heath et al., S&P'21) realized a full toolchain supporting arbitrary $\texttt{ANSI C}$ programs, demonstrating this capability by proving SIR- and CVE-reported bugs in off-the-shelf Linux programs $\texttt{sed}$ and $\texttt{gzip}$. We revamp the state of the art by building a new constant-round ZK system ZEE200, which is about $20\text{-}40\times$ faster than ZEE. ZEE200 is built on a novel and convenient cryptographic framework for efficiently proving general statements represented as real-world programs. Our framework integrates several crucial recent advances, such as Tight ZK CPU (Yang et al., CCS'24) and fast ZK RAM (Yang and Heath, USENIX Security'24). We develop better encodings for $\mathbb{Z}_{2^{32}}$ arithmetic, and numerous low-level optimizations. Compared to ZEE's $\approx 10$ KHz CPU speed on a limited ISA, ZEE200 runs at $\approx 200$ KHz (still on a commodity laptop and a LAN!), while supporting a much richer ISA. For example, we rerun a ZEE's benchmark, proving a SIR-reported vulnerability in off-the-shelf Linux utility $\texttt{sed}$. On a 2021 ThinkPad X1 Carbon Gen 9 under a simulated $1$Gbps LAN (single-threaded), ZEE200 completed the proof in $1.5$ seconds, compared to ZEE's $30.1$ seconds, a $20\times$ improvement.

We prove that row-wise interleaving does not impose a linear loss on two coding-theoretic soundness properties used in recent IOP/SNARK analyses: generator mutual correlated agreement and curve decodability. For generator-MCA, let $G:\Omega\to\mathbb{F}_q^\ell$ be a coefficient generator over a finite seed set and let $C$ be an $\mathbb{F}_q$-additive code. For every interleaving width $s$ and distance parameter $\delta$, we show $$ \varepsilon_G(C,\delta) \le \varepsilon_G(C^{\equiv s},\delta) \le \left(1+\frac1q+\cdots+\frac1{q^{s-1}}\right)\varepsilon_G(C,\delta). $$ Moreover, if $|\Omega|\le q$, then the transfer is exact: $$ \varepsilon_G(C^{\equiv s},\delta)=\varepsilon_G(C,\delta). $$ In particular, affine-line MCA is invariant under row-wise interleaving. This answers the known interleaving-loss question and removes the linear interleaving factor from the affine-line MCA bound. It also implies that polynomial-generator MCA bounds transfer to interleaved codes without an additional interleaving-width factor. We further establish interleaving stability for curve decodability. We introduce a marked formulation, prove its equivalence to the standard definition for $\mathbb{F}_q$-additive codes and $1\le b\le a\le q$, and use it to transfer curve decodability to row-wise interleavings. If $C$ is $(\ell,\delta,a,b)$-curve-decodable and $\binom{a}{b}\le q$, then $C^{\equiv s}$ is also $(\ell,\delta,a,b)$-curve-decodable for every $s$. We also give a field-size-weighted variant that transfers larger base-code witness parameters to smaller interleaved-code witness parameters.

Secure comparison is a fundamental building block frequently employed in various applications of secure multiparty computation, such as secure machine learning. Such protocols based on secret sharing (SS) typically excel in throughput, but they historically suffer from higher (online) round complexity. To address this issue, Attrapadung et al. (AsiaCCS 2022) proposed a protocol with two online rounds in the client-aided model (i.e., assuming a trusted third party in the offline phase), and Lu et al. (USENIX Security 2025) proposed a protocol with three online rounds in the plain model. In this paper, we propose a plaintext comparison protocol with two online rounds in the plain model. While keeping the lowest online round complexity, our protocol also reduces the total bit complexity. For example, for the case of 64-bit integers, the total bit complexity of our protocol is 25.7% of Lu et al.'s protocol and 23.3% of Attrapadung et al.'s protocol adjusted to the plain model.

We give a two-transcript key-recovery attack on TALUS-MPC in TALUS v4. TALUS was presented in the second round of the NIST Threshold Call Preview Talks. In Algorithm 3 of TALUS v4, the committee's nonce polynomials are evaluated at all $N$ points so that any $T$ parties can sign. An adversary controlling the coordinator and $T-1$ parties can reuse the same pooled nonce with two quorums whose only common members are corrupt. Each participating honest party uses its signing share once, yet the coordinator obtains $\mathbf{z}_0=\mathbf{y}+c_0\mathbf{s}_1$, $\mathbf{z}_1=\mathbf{y}+c_1\mathbf{s}_1$. The nonce cancels on subtraction. Moreover, no invertibility assumption in $R_q$ is needed: the response equations lift to $\mathbb{Z}[X]/(X^{256}+1)$, and every nonzero $c_0-c_1$ is invertible in the cyclotomic field $\mathbb{Q}[X]/(X^{256}+1)$. Thus two distinct challenges recover $\mathbf{s}_1$ exactly; since the TALUS v4 public key includes the full $\mathbf{t}=\mathbf{A}\mathbf{s}_1+\mathbf{s}_2$, the adversary also recovers $\mathbf{s}_2$ and forges signatures.

This note collects, in compressed form, some techniques for modular multiplication with word-size (“short-limb”), or at most a-handful-of-words sized moduli as they are used in implementations of lattice-based cryptography: Barrett reduction and multiplication (in signed and unsigned flavors, with exact error, range, and canonicality analyses), Montgomery reduction and multiplication (including the folded-constant form, the precise equivalence with Barrett multiplication, even moduli, the multi-limb case, and the k-reduction), Plantard multiplication (the original unsigned algorithm, the signed variant, and a variant taking signed inputs to the canonical unsigned representative in [0,q)), and modular multiplication via the explicit Chinese remainder theorem. These are compressed out of my lecture slides in the class Post-Quantum Cryptography at National Taiwan University 2020--2025 (EE 5176/921 U2540). All numerical examples, ranges, and windows stated here have been verified by exhaustive or randomized machine search; several constants and ranges correct typos and miscalculations that circulated after lectures.

Mutual correlated agreement (MCA) bounds how many points on an affine line of received words can agree with codewords on many coordinates when the line does not admit a common codeword explanation on those coordinates; the corresponding line parameters are called bad. MCA arises in the soundness analysis of code-based proof systems. For Reed-Solomon codes with arbitrary prescribed evaluation sets, existing deterministic bounds apply only at integer error budgets strictly below the exact Johnson boundary. Fix integers $r\ge2$ and $h\ge1$. For every sufficiently large $K$, let $L\subseteq\mathbb{F}_q$ be any set of $n=rK$ distinct points and set $C=\operatorname{RS}_{<K}(\mathbb{F}_q,L)$. At error budget $E=\left\lfloor{n-\sqrt{n(K-1)}}\right\rfloor+h$, we prove that every affine line has at most $O_{r,h}(K^6)$ bad parameters. Hence \[ \varepsilon_{\mathrm{mca}}(C,E)=O_{r,h}(K^6/q). \] Thus, at each fixed rate $1/r$, any fixed number of integer steps beyond Johnson admits a deterministic polynomial bound on the number of bad parameters; in relative-radius units, the gain is $O(1/n)$. We also derive a MCA upper bound for maximum distance separable (MDS) codes from a sharp lower bound on the number of rejected local membership tests. For Reed-Solomon codes over sufficiently large fields, the resulting endpoint bound is exact whenever at most $K+1$ agreements are required. It yields exact $2^{-128}$ thresholds for four explicit smooth-domain codes of length $64$: we identify the largest safe integer budget and prove that the next one is unsafe. As a concrete application to the Grand MCA Challenge, we exhibit a single prime field $\mathbb{F}_Q$, with $Q<2^{256}$, that supports the required smooth domains at all four target rates. With $K=2^{18}$, the first post-Johnson budget has MCA error below $2^{-128}$ at rates $1/2,1/4,1/8,$ and $1/16$, as does the second such budget at rate $1/8$.

At ITCS 2020, Bartusek, Ishai, Jain, Ma, Sahai, and Zhandry proposed a framework for witness encryption based on affine determinant programs and gave a concrete witness encryption candidate. Yao, Chen, and Yu later broke the separate ADP-based indistinguishability-obfuscation candidate, while noting that their attack did not apply to the witness-encryption construction. More recently, Soukhanov et al. proposed witness encryption from arithmetic affine determinant programs. Soukhanov subsequently described a commutator attack on that construction and noted that the original ADP construction is also subject to the attack for sparse circuits. The recovery of hidden column spaces in our attack uses this commutator technique. We give a deterministic polynomial-time attack that recovers the encrypted bit from the public ciphertext matrices of this candidate. It covers every $q\geq 1$ in the theorem's recovery range, including $q(n)=\lceil n^\varepsilon\rceil$ for all sufficiently large $n$. Outside a fixed finite set of primes, it applies to every SUBSET-SUM instance whose coefficient vector is nonzero modulo $p$ and that has no Boolean solution modulo $p$. On an explicit efficiently generated family of integer NO instances, the encrypted bit is recovered with probability $1-\mathrm{negl}(n)$ under the field-size convention of the original paper.

Goldreich-Levin reductions are ubiquitous in cryptography: they convert an algorithm capable of guessing $\langle r, m \rangle$ (mod $2$) for a hidden string $m$ and a random challenge $r$, to one that is capable of extracting the entirety of $m$. Here, we describe a "simultaneous" Goldreich-Levin reduction for two entangled parties who are capable of guessing $\langle r, m \rangle$ given uniformly random identical challenges $r$. This allows to upgrade any unclonable encryption scheme satisfying "search" security to one satisfying the gold standard of unclonable "indistinguishability". As a corollary, we show that the simplest candidate unclonable encryption scheme from BB84 states satisfies unclonable indistinguishability. This result was discovered by GPT-5.6 Ultra after a few interactions. Our prompts included recent results on unclonable encryption by Ananth and Sahai, and Ragavan.

Linear error-correcting codes with fast encoding and high minimum distance are a central primitive across modern cryptography. They appear prominently in at least two domains: (1) pseudorandom correlation generators (PCGs), which enable sublinear-communication generation of correlations such as oblivious transfer and vector oblivious linear evaluation, and (2) zero-knowledge proof systems, where linear-time encoders underpin proof soundness and scalability. In both settings, the prover or sender must multiply by a large generator matrix $\mathbf{G}$, often with dimensions in the millions, making computational efficiency the dominant bottleneck. We propose a generalized paradigm for building crypto-friendly binary codes with provable minimum distance. Roughly speaking, these codes are based on randomized turbo codes such as repeat-accumulate codes. We prove linear asymptotic minimum distance and compute the exact expected weight spectrum for concrete sizes. We observe that our codes approach the Gilbert-Varshamov distance bound and outperform prior constructions. We construct several novel codes, the most promising of which we call Block-Accumulate codes. Among codes with provable distance, our code is $8\times$ faster than the state of the art on a CPU and $50\times$ faster on a GPU; even against aggressive parameters with conjectured distance, it is $3\times$ and $20\times$ faster, respectively. Under these parameters, this yields overall PCG speedups of $2.5\times$ on the CPU and $15\times$ on the GPU, achieving a projected 200$+$ million OTs per second, or about 100 million binary Beaver triples per second, on the GPU (excluding the one-time 10 ms GGM seed expansion). We also observe a $2\times$ encoding speedup and half the peak memory consumption in the Blaze zero-knowledge (PCS) scheme of Brehm et al. (EUROCRYPT~'25).

Bitcoin Improvement Proposal 327 specifies a variant of the MuSig2 multi-signature protocol that is becoming widely adopted in Bitcoin applications. This protocol enables multiple participants to collaboratively compute (BIP 340) Schnorr signatures for a single aggregate public key efficiently, while preventing external parties from distinguishing whether multiple signers were involved. It has been widely proposed that it should be secure to allow MuSig2 participant keys to themselves be "nested" MuSig2-aggregated keys. No security argument has previously been presented for this practice, though various applications have been proposed that assume the security of such an operation. In this work, we propose NestedMuSig2, a recursive variant of MuSig2 that enables a tree of nested cosigners to privately generate aggregate Schnorr signatures while maintaining all of the efficiency and security benefits of MuSig2, including non-interactive public key aggregation. Nested signers in this scheme cannot distinguish between cosigners that are using further nesting and those that are not. In particular, this means that NestedMuSig2 is compatible with all existing protocols that use MuSig2. We reduce the security of NestedMuSig2 to the AOMDL assumption in the random oracle model. Similarly, we reduce the security of a more efficient and compact variant to the AOMDL assumption in the random oracle model used in conjunction with the algebraic group model.

In real-world applications of SNARKs, non-native arithmetic is a key bottleneck. It introduces large overheads, and proof system designers often resort to non-standard SNARK-friendly hash-functions or other means like elliptic curve cycles to mitigate its costs. Besides performance concerns, non-native circuit arithmetization is also a major cause of implementation errors. In a collection of 27 critical bugs in real world ZK systems (0xPARC/zkbugtracker), 9 were related to non-native arithmetization. We tackle these challenges by constructing a minimal overhead SNARK for integer computation that generically handles non-native arithmetic. We follow the recipe of Zaratan (PKC 26), which proves an integer relation such as $a\cdot b = c + u\cdot m$ by fingerprinting---reducing it to the same relation but over a randomly sampled prime field. Realizing this recipe requires an integer mod-PCS that commits to integer polynomials and opens their evaluations modulo a random prime, which is crucially chosen after the underlying PCS's setup and commitment phases. Our central contribution is Limber, the first practical integer mod-PCS construction that asymptotically has $o(1)$ multiplicative commitment overhead and can be instantiated with any standard field polynomial commitment scheme, including ones over small fields. Combining Limber with a PIOP for integer R1CS over the random prime yields our SNARK. We demonstrate its practicality by implementing our scheme and showing that we can prove RSA arithmetic more than $67\times$ faster than prior circuit-based approaches.

Towards bridging the gap between passively and actively secure multiparty computation (MPC), the use of sublinear distributed zero-knowledge (DZK) proofs gained popularity. Such proofs enable extending a passively secure protocol by adding a verification step whose communication is sublinear in the circuit size. For arbitrarily many parties and a dishonest majority, adding a trusted dealer enables efficient computation, as recently shown by Asterisk (IEEE S&P'24) without requiring DZK. This setting is also compatible with DZK, as shown by Boyle et al. (CRYPTO'21). Unfortunately, their approach is not tailored to computation over a ring $\mathbb{Z}_{2^k}$, often favored for concrete efficiency and practicality, resulting in high computational overhead. In the honest majority setting with few parties, Li et al. (CCS'24) optimized DZK to rings, achieving significant performance improvements. In this work, we propose the first sublinear verification protocol that is both, designed for the $n$-party dishonest majority setting with a dealer, and tailored to computation over a ring $\mathbb{Z}_{2^k}$, combining and improving upon both approaches above. Previous approaches used $n$ DZK proofs to check correct behavior for each individual party. Instead, we show how to verify in a single, novel DZK proof that all parties together behave correctly. This decreases the communication complexity for verification from $\mathcal{O}(n \cdot \log m)$ to $\mathcal{O}(n + \log m)$ ring elements per party for $m$ multiplications. Hence, for the first time, active security using DZK scales well with the number of parties $n$. We provide the first public implementation for DZK with arbitrary $n$ and a dealer and show its practical efficiency. For $m=10^6$ multiplications across 30 layers, communication increases by only 0.7% over the passively secure base protocol with only moderate computation overhead. This becomes especially useful in a WAN setting, where we achieve active security at only 34% run time overhead over the passive variant. Compared to Asterisk (IEEE S&P'24), our protocol has 1.8x better communication and improves run time by 2.5x in WAN and 11.9x in LAN.

Non-local search-to-decision asks whether two noncommunicating parties, given the two shares of a bipartite encoding of a uniformly random string $x\in \mathbb{F}_2^n$, can both predict the same random parity $\langle r,x\rangle$ without there also being local measurements with which both parties recover $x$. We prove that if their optimal probability of both recovering $x$ by local measurements is $p$, then their probability of both answering a common parity challenge correctly is at most $\min\{1,\frac12+5p^{1/22}\}$. The result is motivated by applications to unclonable cryptography, including unclonable encryption and quantum copy-protection. The proof is information-theoretic and does not provide an efficient extractor. The proof and the exposition were developed with assistance from ChatGPT using GPT-5.6 Sol Pro and Codex in the Ultra reasoning mode.

Redeemable real-world asset tokens can trade onchain faster than their backing assets can be sold or settled. An immediate-exit facility cannot treat reported net asset value (NAV) as fully liquid. Within our scope, the mechanisms we compare do not jointly provide permissionless access, order-splitting resistance, and favorable small exits. In this paper, we propose a Proprietary Request for Quote (Prop RFQ), an onchain facility that prices exits against available reserves and mitigates, but does not eliminate, split-order incentives. Its quote combines NAV, an order-size curve, a funded-liquidity wall, decaying sell pressure, and a cadence response to repeated sells. The design seeks to keep isolated small exits useful while limiting reserve depletion and gains from splitting a concentrated exit. We evaluate the implemented Solana pricing path with fixed workloads and ablations, then sweep 15,120 parameter configurations. At the reference parameters, cadence reduces aggregate split advantage by 9.67% against matched pressure-only pricing, improves 34 of 40 split workloads, and raises worst-case reserve remaining from 10.49% to 17.66%. No simple policy or Prop RFQ ablation in our comparison dominates the reference configuration on common metrics. After correcting epoch rollover, implementation quotes match the explicitly rolled model at every tested recovery point. However, low-value sells enable cheap cadence griefing.

In 1978, Yao studied the subset product problem and proved its NP-completeness. Later, Galbraith, Zobernig, and Li considered a prime-based modular variant and studied its average-case hardness. More recently, Li introduced the general problem of unknown-coefficient multivariate exponential system solving and studied its hardness systematically in an abstract setting. Li's framework implies a noisy modular variant of subset product as a special case. In this paper, we study this noisy subset product problem in a concrete setting, prove equivalence relations among several related variants, and use these results to construct a post-quantum non-alternating key exchange scheme, with a natural one-sided interpretation as a key encapsulation mechanism. Unlike other noise-based schemes, such as lattice-based schemes, our construction does not rely on an additional reconciliation plaintext. Instead, the receiver is able to recover the sender's ephemeral secret key itself. Moreover, we reduce indistinguishability security directly to the search version of the noisy subset product problem, without relying on a separate decisional assumption.

Differential cryptanalysis is one of the main methods of cryptanalysis and has been applied to a wide range of ciphers. While it is very successful, it also relies on certain assumptions that do not necessarily hold in practice. One of these is the hypothesis of stochastic equivalence, which states that the probability of a differential characteristic behaves similarly for all keys. Several works have demonstrated examples where this hypothesis is violated, impacting the attack complexity and sometimes even invalidating the investigated prior attacks. Nevertheless, the hypothesis is still typically taken for granted. In this work, we propose AutoDiVer, an automatic tool that allows to thoroughly verify differential characteristics. First, the tool supports calculating the expected probability of differential characteristics while considering the key schedule of the cipher. Second, the tool supports estimating the size of the space of keys for which the characteristic permits valid pairs, and deducing conditions for these keys. AutoDiVer implements a custom SAT modeling approach and takes advantage of a combination of features of advanced SAT solvers, including approximate model counting and clause learning. To show applicability to many different kinds of block ciphers like strongly aligned, weakly aligned, and ARX ciphers, we apply AutoDiVer to GIFT, PRESENT, RECTANGLE, SKINNY, WARP, SPECK, and SPEEDY.

Update: We retract the claim that main construction in the paper is cryptographically secure. In particular, the trapdoor functions generated in Algorithm 1 from three dimensional tensors are efficiently distinguishable from random tensors, since their two dimensional slices (in the longest dimension) are rank deficient. We leave the article as a record, in hopes that some of the techniques are useful in other contexts. Weyman and Zelevinsky generalised Vandermonde matrices to higher dimensions, which we call Vandermonde-Weyman-Zelevinsky tensors. We generalise Lagrange interpolation to higher dimensions by devising a nearly linear time algorithm that given a Vandermonde-Weyman-Zelevinsky tensor and a sparse target vector, finds a tuple of vectors that hit the target under tensor evaluation. Tensor evaluation to us means evaluating the usual multilinear form associated with the tensor in all but one chosen dimension. Yet, this interpolation problem phrased with respect to a random tensor appears to be a hard multilinear system. Leveraging this dichotomy, we propose preimage sampleable trapdoor one-way functions in the spirit of Gentry-Peikert-Vaikuntanathan (GPV) lattice trapdoors. We design and analyse ``Hash-and-Sign'' digital signatures from such trapdoor one-way functions, yielding short signatures whose lengths scale nearly linearly in the security parameter. We also describe an encryption scheme. Our trapdoor is a random Vandermonde-Weyman-Zelevinsky tensor over a finite field and a random basis change. We hide the Vandermonde-Weyman-Zelevinsky tensor under the basis change and publish the resulting pseudorandom tensor. The one way function is the tensor evaluation derived from the public tensor, restricted so as to only map to sparse vectors. We then design the domain sampler and preimage sampler demanded by the GPV framework. The former samples inputs that map to uniform images under the one-way function. The latter samples preimages given supplementary knowledge of the trapdoor. Preimage sampling is a randomised version of interpolation and knowing the basis change allows efficient translation between interpolation corresponding to the public and trapdoor tensors. An adversary seeking a preimage must solve a pseudorandom multilinear system, which seems cryptographically hard.

Modern vehicles have evolved into highly interconnected Software-Defined Cyber-Physical Systems (CPS), integrating embedded electronics, wireless communications, artificial intelligence, and Advanced Driver Assistance Systems (ADAS). While these technological advances have significantly improved vehicle safety, efficiency, and driving automation, they have also introduced a rapidly expanding cyber-physical attack surface. Consequently, automotive cybersecurity has become an active research area encompassing attacks on physical vehicle components, access and authentication mechanisms, electronic and software systems, and autonomous driving technologies. Although numerous studies and surveys have investigated these security threats, the existing literature remains fragmented, often focusing on specific vehicle subsystems or individual technologies. This paper presents a comprehensive survey of attacks and defense mechanisms targeting modern vehicles through a unified and orthogonal taxonomy that classifies the literature into four research directions: attacks on vehicle body and physical systems, vehicle access and engine start systems, electronic and software systems, and ADAS and autonomous driving systems. For each direction, the associated security issues, representative attacks, and existing countermeasures are systematically reviewed and analyzed. Furthermore, the survey identifies current research trends, highlights existing research gaps, and discusses future challenges toward the development of comprehensive and resilient automotive security solutions.

Copy-protection is one of the main applications of quantum information in cryptography. In copy-protection, we encode a functionality in a reusable quantum state so that it cannot be split into two states (called freeloader adversaries) that remain simultaneously useful. Despite a long line of research, previous works have only been able to show security with respect to independently sampled challenges in the plain-model. However, arguably a more natural security notion considers the two freeloader adversaries receiving the same challenge. This so-called identical-challenge security notion is also connected to other fundamental quantum cryptographic primitives such as unclonable bits (i.e. unclonable encryption) and copy-protection of point functions. In this work, first we make progress on the definitional foundations of these primitives, and then prove security in the plain model for our new stronger definitions, in particular also resolving the question of copy-protection with identical challenges and copy-protection of point functions. In more detail, we obtain the following results. -- Copy-protecting decryption keys (Single-decryptor encryption).} We define a new natural security notion for single-decryptor encryption (SDE) called {correlated challenge security}, and show that implies all previous security definitions for SDE, including identical-challenge security. Then, we prove that, assuming indistinguishability obfuscation (iO) and one-way functions, the SDE construction of Kitagawa and Yamakawa (TCC'25) satisfies correlated challenge security. We also provide an almost complete characterization of the relationship among previous SDE security notions. --Copy-Protecting General Functionalities with Correlated Challenges. We define correlated challenge unclonable puncturable obfuscation (UPO), allowing arbitrary correlations among challenge points and puncturing bits, plus auxiliary information before and after splitting. Security requires only conditionally uniform bits and $\lambda^c$ average conditional min-entropy in each point separately, for any constant $c>0$; thus, in particular the challenge points may be identical. Assuming polynomially secure post-quantum iO and quantum-hard LWE, we construct correlated UPO for arbitrary polynomial-size keyed circuits with input length at least $\lambda^c$, answering the open question of Ananth, Behera, Huang, Kitagawa, Yamakawa (EUROCRYPT'26) and Çakan-Goyal (EUROCRYPT'26). --Applications Our results yield the first plain-model copy protection for point functions, $k$-point functions, and compute-and-compare programs under natural security definitions, and identical-challenge copy protection for general puncturable functionalities. The technical core of our results is a new decisional monogamy theorem for coset states, which both simplifies the proofs and generalizes the results of existing copy-protection constructions, which may be of independent interest.

The Permutation Code Equivalence Problem (PEP) and Permuted Kernel Problem (PKP) are two notorious computational problems over linear codes used for building post-quantum digital signature schemes. Although traditionally analyzed over prime fields, recent proposals, such as the signature schemes PERK and SETH, have considered extension fields to improve efficiency and compactness. In this work, we analyze the hardness of solving PKP and PEP when instantiated over field extensions. For binary field extensions, by exploiting a reduction to a structured variant of the Regular Syndrome Decoding Problem (RSD), we uncover new polynomial-time parameter regimes for both PKP and PEP, including families of self-orthogonal PEP instances and all self-dual instances over extensions of degree $\nu>4$. We also adapt the permutation-based Regular-ISD algorithm of Esser and Santini for RSD (CRYPTO '24) to PKP-derived instances, and uncover regimes of parameters for which it improves upon the state-of-the-art. Moreover, we present a reduction from a broad family of PEP instances over extension fields with odd characteristic to the Graph Isomorphism Problem, yielding a polynomial-time algorithm to solve those instances. Overall, our results invalidate the use of PEP over extension fields for most of the scenarios, and provide novel insights into the security of PKP over extension fields.

Rotational-XOR (RX) cryptanalysis extends rotational cryptanalysis by combining rotational relations with XOR translations, enabling the analysis of symmetric-key primitives even in the presence of symmetry-breaking constants. Existing analyses of RX characteristics, however, typically rely on independence assumptions when estimating characteristic probabilities, which may lead to inaccurate probability evaluations and even incompatible characteristics. In this paper, we introduce the first application of the geometric approach to RX cryptanalysis. Inspired by the quasidifferential framework of Beyne and Rijmen, we develop an algebraic representation of RX characteristics and establish exact formulas expressing fixed-key RX characteristic probabilities in terms of rotational-quasidifferential trails. As a result, RX characteristics can be analyzed without relying on round-independence assumptions. By incorporating the key schedule into the state space, we further derive an exact expression for the Expected Rotational-XOR Probability (ERXP), the RX analogue of the Expected Differential Probability (EDP). We apply the framework to the AND-RX ciphers SIMON and SIMECK. In particular, we experimentally validate the theoretical predictions of the framework through the fixed-key analysis of a previously known RX characteristic for SIMECK32/64. We also revisit incompatible RX characteristics of SIMECK48/96 and SIMECK64/128, identifying additional constraints that lead to incompatibility. Finally, we reanalyze rotational-XOR differential rectangle attacks on SIMECK48/96 and obtain corrected estimates of the corresponding weak-key classes. These results demonstrate that the proposed framework provides an effective tool for the exact analysis of RX cryptanalysis and establishes a foundation for the study of rotational cryptanalytic techniques within the geometric approach. We further derive an explicit rotational-quasidifferential transition matrix for modular addition for arbitrary nonzero rotation offsets, extending the framework to the main nonlinear operation of ARX designs.

Rijndael-256 (R256), the 256-bit block variant of the Rijndael family, is practically relevant in ongoing NIST draft discussions on wider-block standardization and in several NIST post-quantum signature candidates. Relative to AES, R256 combines a wider $4\times8$ state with non-standard ShiftRows offsets $(0,1,3,4)$, invalidating key assumptions behind many AES-oriented optimizations. We study how these mismatches manifest on three targets and develop three corresponding adaptation strategies: wider classical bitslicing on Cortex-M4, Reuse with Reshuffling on AArch64, and Amortize the Mismatch on CUDA. This yields a bitsliced Cortex-M4 implementation with secret-independent control flow and memory access patterns (4,962 cycles/block), an AArch64 pre-shuffle design that reuses the AESE instruction with AddRoundKey folded in (up to 6,520 MB/s), and a CUDA shared-memory T-table implementation reaching 81.16 GiB/s; we report throughput on AArch64 and CUDA because per-block cycle measurement is not directly available on those platforms. Replacing the R256 cryptographic core in four NIST PQC reference codebases on Apple M2, with minimal integration changes where needed, yields signing speedups of $1.18\times$--$114.3\times$ and verification speedups up to $155.6\times$, with the end-to-end gain governed by each scheme's R256 fraction.

Sum-check and Fast Fourier Transforms (FFTs) dominate the computational cost of modern zero-knowledge proving systems, such as HyperPlonk (Eurocrypt 2023) and FRI-based schemes like DeepFold (USENIX Security 2025). Despite numerous optimizations, existing efforts remain fragmented across algorithmic, protocol, and implementation layers, leaving significant CPU performance potential untapped. We present MamaBearZKP, a co-designed framework that bridges these layers to enable high-throughput ZK proving on modern CPUs. At its core, MamaBearZKP leverages MamaBear, a 49-bit prime field ($p = 2^{49} - 2^{34} + 1$), and introduces a systematic vectorization framework specifically tailored for the AVX-512IFMA execution model. By treating field arithmetic, protocol structure, and low-level hardware primitives as a unified optimization target, MamaBearZKP achieves unprecedented efficiency. We instantiate our framework in a HyperPlonk-DeepFold prover and obtain single-thread speedups of up to $42\times$, $33\times$, $15\times$, $21\times$, and $21\times$ for ZeroCheck, ProductCheck, DeepFold Commit, DeepFold Open, and end-to-end proof generation, respectively, compared to a Goldilocks-based baseline on the same platform. With 8-thread execution, the corresponding speedups increase to as much as $64\times$, $47\times$, $81\times$, $45\times$, and $45\times$. Across our end-to-end evaluations, MamaBearZKP also achieves up to $18\times$ single-thread speedup over Plonky3, which already uses an AVX-512 BabyBear backend. Rather than resulting from isolated improvements, these gains arise from a synergistic cascading effect: the 49-bit field’s headroom enables efficient lazy reduction, which paves the way for high-performance fused fold-and-evaluate kernels. The efficiency of these kernels facilitates a unified stay-packed dataflow throughout the HyperPlonk and DeepFold stacks; it is precisely this end-to-end dataflow that materializes the hardware throughput of AVX-512IFMA into realized performance gains.

We show that the CRT-FHE scheme of Pradhan et al. is insecure for laws within its assumed error distribution range. The secret key follows from the public key by a single ring inversion whenever the public multiplier is a unit. The plaintext is recovered from any ciphertext under such a law without the secret key, for every multiplier, giving chosen-plaintext advantage $1/2$. We further show that the transformation from ordinary Ring-LWE to CRT-RLWE does not preserve the error distribution, so it does not establish that CRT-RLWE is at least as hard as Ring-LWE. One mechanism underlies both. The Chinese remainder theorem (CRT) function is reduced modulo $p_1p_2$ while its output is used modulo a coprime modulus $q$, so under every zero-preserving section an error in $p_2\mathcal{R}$ encodes to zero. The law $p_2B_1$ is so confined, meets the stated conditions, and decrypts correctly. Confinement is not a weakness of scale: scaling any baseline law by $p_2$ leaves its ordinary Ring-LWE problem exactly equivalent, while the reduced encoder destroys every error it produces. The reduction discrepancy is a multiple of $p_1p_2$ and not of $q$, so the small-error premise of the proof cannot remove it, and at the reported parameters a single error coefficient refutes the identity while satisfying that premise. The centered binomial $B_2$ separates the coefficient laws at total variation distance $3/8$, and at the reported dimension that distance between the induced polynomial laws is exponentially close to one.

We propose a new private Approximate Nearest Neighbor (ANN) search scheme named Pacmann that allows a client to perform ANN search in a vector database without revealing the query vector to the server. Unlike prior constructions that run encrypted search on the server side, Pacmann carefully offloads limited computation and storage to the client, no longer requiring computationally-intensive cryptographic techniques. Specifically, clients run a graph-based ANN search, where in each hop on the graph, the client privately retrieves local graph information from the server. To make this efficient, we combine two ideas: (1) we adapt a leading graph-based ANN search algorithm to be compatible with private information retrieval (PIR) for subgraph retrieval; (2) we use a recent class of PIR schemes that trade offline preprocessing for online computational efficiency. Pacmann achieves significantly better search quality than the state-of-the-art private ANN search schemes, showing up to 2.5$\times$ better search accuracy on real-world datasets than prior work and reaching 90\% quality of a state-of-the-art non-private ANN algorithm. Moreover on large datasets with up to 100 million vectors, Pacmann shows better scalability than prior private ANN schemes with up to $63\%$ reduction in computation time and $24\%$ reduction in overall latency.

NTRU is one of the longest-tested lattice-based public-key encryption families and is often viewed as a compact alternative to (R/M)-LWE. Yet, after three decades of research, its potential for compactness remains an open area for further exploration: recent designs such as NEV (Asiacrypt 2023) and DAWN (Asiacrypt 2025) suggest that there is still room for improvement. This raises a natural question: Has NTRU reached its compactness limit? If not, how compact can it be while still remaining secure and efficient? Motivated by this question, we aim to formalize a unified relationship between compactness and efficiency under the required security level. We present a common two-stage view of NTRU decryption. In the first stage, the decoder constructs a small set of candidate wrap-around errors. In the second stage, it verifies these candidates using either algebraic redundancy or trapdoor-derived distributional information. We introduce Free Candidate Localization (FCL), a generic first-stage method that ranks coordinates by their proximity to the centered boundary. FCL could be used in most lattice-based encryptions; we instantiate it in ML-KEM to achieve a $10\%$ smaller ciphertext at the cost of a $5\%$ slower overall runtime in the reference C implementation under NIST-I. We organize modern NTRU encryptions into two frameworks. NTRU with Encoding leverages algebraic structure via auxiliary quotient rings. NTRU with Trapdoor exploits geometric structure through the NTRU trapdoor, then verifies candidate corrections using distributional tests. These frameworks give a common language for existing NTRU designs and for the compactness searches in this paper. Within an explicit search model, we derive heuristic compactness frontiers for both frameworks. At NIST-I, the encoding frontier yields a total public-key plus ciphertext size of 812 bytes, and the trapdoor frontier yields a size of 754 bytes, $15\%$/$21\%$ smaller than the previous lowest size of 964 bytes in DAWN. Furthermore, we propose END, an instantiation of NTRU with Trapdoor plus FCL. At NIST-I, \textsf{END} has a 384-byte ciphertext, which is exactly half the size of the 768-byte ciphertext of ML-KEM-512, and is $12-19\%$ smaller than the shortest prior NTRU-style ciphertexts in BAT (TCHES 2022) and DAWN. In our reference C implementation, the combined encapsulation and decapsulation cost of END-512 is about $3\%$ higher than that of ML-KEM-512.

With the growing deployment of secure multi-party computation (MPC) in data-intensive applications, the offline generation and distribution of authenticated multiplication triples has become a key scalability bottleneck. Existing software-only preprocessing protocols, such as MASCOT and LowGear, typically incur substantial interaction and computation costs when the number of participants or the triple demand is large. This paper proposes a trusted execution environment (TEE) server–assisted aggregated offline deployment scheme that moves expensive interactive preprocessing into a remotely attested enclave and distributes participant-specific authenticated triple shares over authenticated-encrypted channels. Conceptually, the enclave serves as a TEE-backed pseudorandom correlation generator (PCG) that outputs authenticated correlated randomness for MPC with one-way delivery. We design an end-to-end workflow covering remote attestation, per-participant session establishment, and encrypted distribution. The proposed protocol applies to both semi-honest and malicious adversaries; we provide a security analysis against malicious adversaries with abort. Experimental results show clear efficiency improvements over MP-SPDZ implementations of MASCOT and LowGear. Specifically, the proposed scheme achieves a generation rate three times that of MASCOT, while exhibiting linear scalability up to 100k participants. Furthermore, by employing a streaming processing strategy, it efficiently supports the generation of up to 10M triples with an amortized time significantly lower than that of purely software-based protocols, enabling practical and highly scalable preprocessing for large-scale heterogeneous MPC deployments.

Public-key encryption (PKE) is a fundamental primitive in modern cryptography, and many PKE schemes have been standardized and widely deployed. To reason about security in complex and highly compositional environments, Zhandry and Zhang (CRYPTO 2020) initiated the study of indifferentiability for public-key cryptosystems. However, their construction for PKE departs substantially from the design paradigms used in practice, and to date no practical public-key encryption schemes are known to achieve indifferentiability. In this work, we further investigate indifferentiability for public-key encryption, asking whether it can be achieved for practical, standardized schemes. We provide evidence that the answer is yes: slightly augmented standardized group-based encryption schemes can indeed achieve provable indifferentiability. Our contributions are threefold: -- Identifying a barrier in the existing ideal PKE model: We revisit the ideal PKE definition of Zhandry and Zhang and identify an artificial requirement---namely, pseudorandom public keys and ciphertexts---that constitutes an inherent barrier to achieving indifferentiability from groups. -- Redefining the idealized model for PKE: We propose a revised ideal PKE model that removes this pseudorandomness requirement, thereby opening the possibility of achieving indifferentiable public-key encryption from practical group-based schemes. --Making standardized PKE indifferentiable: We consider two public-key encryption schemes standardized in ISO/IEC 18033-2---Elliptic Curve Integrated Encryption Scheme (ECIES) and Public-Key Secure Encryption (PSEC)---and show that, under slight augmentation, both are indifferentiable from our revised ideal PKE. In conclusion, our work advances the development of indifferentiable yet practical public-key encryption schemes, enabling future research and protocol design to build on standard PKE schemes while enjoying strong composability guarantees.

Ring signatures provide signer anonymity for ad hoc sets of public keys. Generic Abe-Ohkubo-Suzuki (AOS) transforms are well understood for plain Fiat--Shamir and hash-and-sign signatures, but not for their rejection-sampling variants: Fiat--Shamir with aborts (FSwA) and hash-and-sign with retry (HSwR). We formalize AOS ring transforms for FSwA and HSwR and analyze their security in the quantum random-oracle model. For unforgeability, we reduce security under adaptive ring-signing queries to security without signing queries using essentially the same assumptions as in security proofs for the corresponding ordinary signatures; handling adaptive corruption additionally requires the simulation property to remain valid after key exposure. Strong unforgeability additionally requires response uniqueness and special soundness for FSwA, or second-preimage resistance and non-invertibility for HSwR. The residual no-signing-query requirement admits generic reductions, but with loss exponential in the number of honest keys. Finally, an ML-DSA case study shows that augmented public keys achieve the required key-exposure simulation while identifying its limitations; we also identify conditions for candidate HSwR instantiations.

The main barrier to practical fully homomorphic encryption remains the latency and cost of bootstrapping, the ciphertext refresh step that enables unbounded computation. We design new methods that reduce both the latency and the circuit depth of bootstrapping in the FHEW/TFHE framework, which represents the state-of-the-art for lightweight bootstrapping and for computing deep and unstructured Boolean functions over encrypted data. Our first contribution leverages LWE with a sparse small-norm secret, an assumption known to be equivalent to standard LWE and already widely used in FHE constructions. For an LWE secret of dimension $n$ and Hamming weight $h$, we obtain bootstrapping procedures whose arithmetic complexity decreases from $\tilde O(n^2)$ to $\tilde O(n h)$ $\mathbb{Z}_q$ multiplications while preserving the same asymptotic number of additions. Concretely, this yields a $4.5$--$7.5\times$ practical speedup for gate and functional bootstrapping over the state-of-the-art OpenFHE implementation. Our second contribution introduces a new RLWE variant with structured secrets, called \emph{\mainrlwevarianttext}, and uses it to significantly reduce the circuit depth of FHEW/TFHE bootstrapping via a new relinearization-free BV multiplication technique. In concrete parameter settings, this reduces the number of sequential NTT/INTT layers required for bootstrapping to just 3, compared to more than 500 in standard FHEW/TFHE, while keeping the overall number of unit 32 or 64-bit word operations comparable to standard FHEW/TFHE bootstrapping. This substantial depth reduction suggests the potential for significantly lower bootstrapping latency on parallel, high-throughput architectures such as GPUs. Finally, we analyze the security of the new RLWE assumption underlying our depth reduction, including worst-case-to-average-case and search-to-decision reductions, as well as evaluations against concrete attacks.

In their CRYPTO 2023 paper, Fuchs, Rotella, and Daemen reduced the universality of key-then-hash (KTH) functions built from public permutations to differential properties of the underlying permutation. Subsequent work analyzed KTH Parallel with fixed-length public functions and related variable-length universality bounds [12,13]. We develop a corresponding framework for key-recovery attacks on KTH-based MACs. We first revisit the weak-key classes identified by Handschuh and Preneel for NH, NMH*, WH, and Square Hash. For the KTH attacks considered here, these classes are solution sets of controlled differentials. These translated sets may still satisfy HP08's broad operational weak-key criterion. Our claim is different: KTH offset invariance translates every such solution set through every absolute key with unchanged probability and oracle-query cost, so the attacks do not identify intrinsically exceptional absolute keys. For these controlled attacks, this gives a strong KTH form of the UHF "regularity" sought by Handschuh and Preneel: the complete attack profile is homogeneous over absolute key space. We then show that, for every fixed-length KTH map with no probability-one nonzero differential, any two distinct key-prefix candidates can be distinguished by a generalized differential test. If its generalized derivatives are affine, one retained successful fixed-output equal-length differential leaves an affine coset and at most \(\lceil \log_2 \#S_0 \rceil\) further suitably chosen successful events determine the prefix, under the stated computational and interface assumptions. Finally, we apply the framework to NH and Xoodoo[3]. Under reusable-reference WC(S), unequal-length NH image tests simultaneously test one candidate for each word of a multiplication pair and recover both \(w\)-bit words with one generation query and at most \(2^w+1\) verification queries, approximately half the verification-query cost of the Handschuh-Preneel recovery. For Serial[Xoodoo[3]], published three-round trails yield recovery of a reusable 384-bit KTH key block in \(2^{42}\) expected differential trials, or \(2^{43}\) MAC-oracle calls.

Zero-knowledge proofs are an operational infrastructure for rollups, private payments, verifiable execution, and zkVM applications. We treat them as succinct proofs of validity whose privacy properties depend on the system and the mode of use. Published benchmarks often compare different workloads, proof modes, and hardware paths, which makes their results hard to interpret. This work presents a unified host-agent framework for benchmarking heterogeneous proving systems under a common execution and reporting method. Each prover runs in an isolated containerized agent and is selected through a scheme-adapter layer. The agent reports canonical JSON artifacts linked to a hashed run manifest and workload-specific semantic contracts. The host checks the public semantic fields and the agent's verification flag to ensure backends are compared on the same declared public claim, even when their circuits, traces, or guest pipelines differ. We evaluate circuit-based, transparent, GPU-accelerated, folding, and zkVM systems: Groth16, ICICLE, Halo2, Plonky3, Winterfell, Nova, RISC Zero with CUDA and Groth16 wrapping, and SP1 with and without AVX. The suite uses six primary workloads with comparable semantics, together with secondary hash workloads that expose specialization. No prover family dominates all deployment criteria. At 8 CPU cores, Plonky3 and Winterfell have the smallest across-case proving-time and RAM figures. Groth16 and ICICLE produce sub-kilobyte proofs. Winterfell has the lowest host verification time. zkVM systems trade larger proofs and higher memory for programmability. On the Merkle-path micro-benchmark, pairing artifacts remain sub-kilobyte, whereas wrapping a zkVM receipt yields a Groth16-sized artifact at a high proving cost. GPU acceleration helps most after fixed setup costs are amortized. The main contribution is methodological: validate the statement being proved, disclose the security profile, and report resource limits in addition to proving time.

Decentralized lending protocols encode credit markets as smart contracts whose design choices affect gas cost, capital efficiency, liquidation behavior, and risk allocation. We compare Aave V3, SparkLend, Compound III, and Morpho Blue in matched Ethereum fork tests with wstETH collateral, USDC debt, and one fixed chain state. The tests measure call-path gas, annualized rates, thirty-day debt growth, maximum borrow capacity, and liquidation outcomes. It is important to note that the observed orderings for gas costs and rates are specific to this test artifact and could change under different collateral assets or utilization regimes. Within this setting, Morpho Blue has the lowest measured interaction call-path gas and highest borrow capacity, while shifting risk selection to isolated permissionless markets. Furthermore, Morpho Blue's evaluation uses a deployed market for rate measurements but a constructed market for liquidation testing. Aave V3 and SparkLend provide broader pooled-market abstractions with higher measured call-path gas. Compound III simplifies borrowing around one base asset per market; its low-gas absorb step is offset by a separate buy collateral liquidation path. We provide a Foundry-based Ethereum-fork test suite for reproducing these measurements and comparing lending-design trade-offs.

Decentralized Finance (DeFi) continues to experience rapid growth, yet a significant portion of capital remains inefficiently utilized in overprovisioned lending reserves or inactive liquidity positions. This paper presents two extension-based improvement proposals aimed at increasing capital efficiency in DeFi protocols. The first addresses idle capital in pool-based lending by adding an allocation layer that can deploy otherwise unused liquidity into external yield-generating strategies. The second targets inactive concentrated-liquidity positions through a position-management layer that automates range migration. Both proposals are examined in terms of motivation, mechanism design, expected effects, implementation approach, and practical limitations. Evaluation results are proposal-specific: the lending analysis indicates meaningful supplier-yield uplift under selected external-yield assumptions, while the range-migration analysis focuses on active-time sensitivity and execution cost. Prototype benchmarks suggest that both mechanisms can be implemented as modular extensions, but also expose additional gas overhead and proposal-specific risks, including external-strategy dependence, recall and loss-allocation concerns, and range-policy misconfiguration.

We remove the Boneh--Lipton conjecture from the proof of Corrigan-Gibbs and Wu (CRYPTO~2024) that Jacobi signatures modulo $N=p^2q$ are one-way. This relates the one-wayness of the pseudorandom generator proposed by Damg{\aa}rd in 1988 to a standard number-theoretic problem alone.

Several decentralized applications and blockchains, such as blockchain-based voting systems or Proof-of-Social-Capital, require a strict one-account-per-person policy, yet public identity records often expose sensitive attributes or enable offline attribution. This work presents a Proof-of-Uniqueness blockchain-based registry that composes an issuer-signed verifiable credential, two zero-knowledge proofs, a threshold verifiable oblivious pseudorandom function (vOPRF), and a smart contract. The first proof authorizes a blinded evaluation of an issuer's certified canonical identifier, and the second validates the OPRF transcript and binds the resulting global nullifier to a wallet. The design further binds issuer authorization, credential status, validity bounds, canonical encoding, and replay state. Its person-level guarantee is conditional on a stable injective identifier within a coordinated issuance namespace and a stable, valid OPRF key. Confidentiality holds against public observers and against fewer than the OPRF threshold of nodes, but not against an issuer that actively probes its own identifiers. Our prototype couples Noir and UltraPlonk circuits, three local threshold OPRF nodes, and a Solidity contract. For one fixed-schema credential input, it derives a single wallet-bound deterministic nullifier, verifies a real 2,144-byte proof on-chain, and rejects a repeated nullifier with $O(1)$ lookups. One real enrollment consumes 615k gas, and proof construction takes about 65 seconds on one desktop software thread.

Memory-Hard Functions (MHFs) are a cryptographic primitive designed to protect passwords and other low-entropy secrets against brute-force attacks. The strongest and most natural formalization of memory-hardness is sustained space complexity (SSC), which measures how long an attacker's memory remains above a given threshold. Ideally, one would like to ensure that any parallel attacker must sustain $\Theta(N)$ memory for $\Theta(N)$ steps, while the function can also be computed in sequential time $\Theta(N)$. Unfortunately, this goal is impossible to achieve. Thus, the appropriate objective is to establish strong tradeoffs between sustained space complexity and cumulative memory complexity (CMC), another strong notion of memory hardness. Blocki and Holman (CRYPTO 2022) achieved strong SSC/CMC tradeoffs in the dynamic pebbling model, but their construction relied on expensive combinatorial graphs, and the pebbling abstraction does not rule out more efficient attacks in the stronger Parallel Random Oracle Model (PROM). We address both limitations. We construct a new data-dependent MHF (dMHF), DEGSample, and prove the first SSC/CMC tradeoff for dMHFs directly in the PROM. In the dynamic pebbling model, DEGSample achieves the same ideal tradeoff as prior work: any dynamic pebbling strategy either sustains $\Omega(N)$ memory for $\Omega(N)$ steps or incurs a maximal CMC penalty $\Omega(N^{3-\epsilon})$. In the PROM, we prove that any attacker either sustains $\Omega(N)$ memory for $\Omega(N)$ steps or incurs a steep CMC penalty of at least $\Omega(N^{2.5-\epsilon})$. To prove this, we introduce a new graph property called ancestral robustness and show that, together with another property called fractional depth-robustness, it suffices to obtain strong PROM tradeoffs via a natural dynamization procedure to turn the graph into a dMHF. The PROM lower bound combines a time-space trade-off argument with an extraction procedure that converts any PROM execution into a cost-equivalent pebbling of the realized graph.

While decentralized identity management systems strive for autonomy, most still rely on centralized mechanisms (e.g., phone numbers or government-issued IDs) to achieve Sybil resistance and prevent fake identity attacks. This article proposes an identity management architecture that ensures robust Sybil resistance and is fully decentralized, unlike the systems currently in widespread use. The proposed solution synergizes facial biometric verification with anti-Sybil social graph analysis. By leveraging blockchain technology, zero-knowledge proofs, and trusted execution environments, the system ensures the uniqueness, anonymity, and privacy of registered users without relying on centralized authorities. The operation of the proposed system was demonstrated through simulations of a network of 100 entities across three social graph models and through a proof-of-concept implementation that utilizes fast Plonky2 zero-knowledge proofs. To our knowledge, this is the first work that proposes a Sybil-resistant identity system without sacrificing decentralization and privacy, while not relying on any centralized credential issuers.

A folding scheme reduces the task of checking multiple NP instances into checking a single instance, providing an efficient route to incrementally verifiable computation (IVC). We identify five desirable properties of a practical folding scheme: constant recursion overheads, multi-folding, linear scaling with the number of instances, no extraneous commitments, and modularity. No existing scheme achieves all five simultaneously. We introduce NeutronNova, the first folding scheme to achieve all five. The prover's work is dominated by the cost to commit to its witness -- with no extraneous commitments -- and the recursive verifier performs only three group scalar multiplications and a constant number of hash computations. We construct NeutronNova modularly using the reductions of knowledge (RoK) framework around a core relation called zero-check, and build folding schemes for circuit satisfiability (CCS), grand products, and lookups by reducing each to zero-check. In experiments, NeutronNova folds a SHA-256 circuit with $2^{20}$ constraints in 91 ms, a ${\approx}10\times$ improvement over Nova. Several subsequent works have used NeutronNova to achieve new results, including space-efficient SNARKs with optimal prover time, packed sum-check protocols over small fields, and client-side zero-knowledge proofs with low end-to-end latency.

Spartan is a SNARK for R1CS that can be instantiated with any multilinear polynomial commitment scheme. We instantiate Spartan over a binary field, using Ligerito as the commitment scheme along with the ring-switching technique of Diamond and Posen; we refer to the instantiation as BinarySpartan. It is transparent, so it requires no trusted setup, and it provides polylogarithmic-sized proofs. Its security rests on a hash function, so it is plausibly post-quantum. We apply well-known optimizations to Spartan and sum-check: the SIMD R1CS of Phalanx; the next multilinear extension of SuperSpartan; sum-check optimizations from Gruen, from Dao and Thaler, and from Bagad, Dao, Domb, and Thaler; and Binius64’s byte lookup tables, which speed up the prover’s early rounds of Spartan’s outer sum-check. All but the last optimization were developed in the context of prime fields and in fact over large prime fields in the elliptic curve group setting. Furthermore, they are widely used in modern Spartan implementations. Thus, BinarySpartan is a natural instantiation of Spartan over binary fields. We implement and evaluate BinarySpartan end to end. On a MacBook Pro M4 Max (using only its 12 performance cores, and without GPU/Metal acceleration), BinarySpartan proves BLAKE3 at 547,000 hashes/second and SHA-256 at 255,000 hashes/second, including witness generation. These clear the 200,000 hashes/second rate proposed as sufficient for a post-quantum Ethereum transition, as well as the roughly 30,000–180,000 hashes/second a possible post-quantum Bitcoin transition would require. We also evaluate BinarySpartan on the Ethereum Foundation’s client-side proving benchmark, where it proves a single SHA-256 of a 2 KiB message in 6.2 ms, making it the fastest scheme in the benchmark suite.

Zero-knowledge proofs based on VOLE have recently become a promising approach for designing post-quantum signature schemes. Such schemes are constructed by having a signer prove knowledge of a secret input for a prescribed one-way function. In this work, we optimize VOLE-based signature schemes from syndrome decoding (SD) and the permuted kernel problem (PKP). Despite relying on different one-way functions, these schemes share a common modeling method. Elementary vectors are compressed into shorter witnesses and then reconstructed through low-degree polynomials. We propose a unified framework for elementary-vector encoding and reconstruction. By choosing different parameters, this framework captures previous modeling approaches for SD and PKP as special cases. Based on this framework, we propose an optimized encoding and reconstruction approach that reduces the extended witness size and hence the final signature size. At NIST Level I security, our SD- and PKP-based schemes achieve “signature + public key” sizes of 3,496 and 3,341 bytes, respectively, improving over the corresponding 3,775 bytes of SDitH v2.0 and 3,577 bytes of PERK v2.2. Furthermore, we construct a 3,673-byte post-quantum ring signature for rings of 2^20 members, which is 27% and 70% smaller than those of Chiang et al. (CCS ’25) and BLOOM (ASIACRYPT ’22), respectively.