International Association
for Cryptologic Research

Threshold signatures reduce the risk of single-key compromise by distributing signing authority, but each key share remains exposed to compromise of the software and infrastructure that execute the protocol. We present RSS, a threshold signing service that runs share generation and signing inside Trusted Execution Environments (TEEs). We integrate GG20 threshold ECDSA, FROST, and threshold BLS into the EnGINE experimentation framework and evaluate local and Google Cloud deployments using AMD SEV-SNP and Intel TDX. Our experiments separate distributed key generation (DKG), preprocessing, and online signing, and cover up to 40 logical protocol participants distributed across four physical hosts or confidential VMs (CVMs). In matched-platform comparisons, confidential execution adds limited overhead relative to protocol and deployment effects. DKG is the main scaling bottleneck: for 40 participants, it completes within seconds in the evaluated configurations, whereas signing completes in tens of milliseconds. Threshold BLS is approximately twice as slow as FROST for comparable values of $n$ and $t$. These results establish the performance feasibility of executing threshold-signature workloads inside CVMs under benign-operation assumptions. The evaluation does not cover a complete attestation-bound provisioning lifecycle, persistent-state rollback protection, or Byzantine fault behavior.

We introduce information-theoretically private quantum protocols for two-party Hamming distance when both parties must output the same estimate. Classically, for input length $n$, information-theoretic protocols require $\Omega(\sqrt{n})$ error under pure differential privacy and $\Omega(\sqrt{n}/\log n)$ error under strong approximate differential privacy, whereas computational security permits $O(1)$ error. In Klauck's honest, nonpreemptive, message-preserving model, we give an $O(n)$-communication quantum protocol with pure $\varepsilon$ quantum differential privacy (QDP) and expected error at most $\frac{2}{\sinh \varepsilon}+\gamma,$ for every $\gamma>0$. For approximate $(\varepsilon, \delta)$ QDP, an exact finite-cycle hockey-stick calculation yields strictly smaller error, while preserving the $O(1)$-versus-$\Omega(\sqrt{n}/\log n)$ separation for $\delta=o(1/n)$. Thus, quantum communication achieves $O(1)$ information-theoretic error, matching the accuracy available classically only under computational assumptions.

The main construction uses a guarded coherent round trip and an equal-Gram rigidity principle that prevents an honest player from retaining input-dependent complementary information. We also separate this model from weaker prescribed-channel privacy, which already admits an exact classical realization, and from fully retention-robust security, against which measurement-and-abort attacks remain possible. Therefore, we identify preservation of non-orthogonal quantum messages as a resource for privacy, but leave open whether a separation exists in the malicious setting.

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.

A secret-sharing scheme allows a dealer to distribute a secret $s$ among $n$ parties such that only predefined “authorized” sets of parties can reconstruct the secret, and all other “unauthorized” sets learn nothing about $s$. Families of authorized sets are called access structures, and a scheme is called linear if its sharing map is linear in the secret and the dealer’s randomness. We show that every $n$-party access structure can be realized by a linear secret-sharing scheme for one-bit secrets with maximal share size of $2^{\lceil n/2\rceil-1}+1$ bits. A counting lower bound for monotone span programs shows that almost all access structures require linear share size $2^{n/2-o(n)}$, which makes our upper bound tight. Our scheme is considerably simpler than previous schemes that obtained share size $2^{cn+o(n)}$ with $1/2\leq c<1$.

We also present a variant of this linear construction that is tailored for monotone k-DNFs access structures (also known as $k$-upslices). Then, by combining it with a non-linear scheme of Applebaum et al. (STOC 2020), we derive a scheme for all access structures with share size $2^{0.496n+o(n)}$. This improves the previous upper bound of $2^{0.585n+o(n)}$ by Applebaum and Nir (CRYPTO 2021), and establishes a separation between the worst-case non-linear and linear exponents. Plugging the quadratic construction of Beimel, Othman, and Peter (CRYPTO 2021) into this framework yields quadratic schemes of share size $2^{0.4995n+o(n)}$, separating the quadratic and linear exponents.

The linear scheme for upslices and its proof were discovered in conversations prompted by the author with GPT-5.6 Sol and Claude Fable 5.

Blockchain networks rely on transaction fees for resource allocation and spam prevention. Ethereum's gas mechanism and its adoption by Layer-2 rollups serve this dual purpose, but gas-based fee markets produce unintended consequences: ineffective spam deterrence at low fee levels, poor user experience, privacy leakage, and revenue instability for rollup operators. We present an idealized protocol architecture for gasless sequencer admission in Ethereum Layer-2 rollups based on Rate-Limiting Nullifiers (RLN) and a non-transferable reputation token (Karma). Users transact within a per-epoch gasless quota. Transactions beyond that quota use a gas-paid overflow path. RLN enforces the quota via zero-knowledge membership proofs, preserving pseudonymity for users within quota against on-chain observers while exposing violators through reputation slashing. We present the architecture and transaction flow, analyze spam-attack economics through a parameterized cost comparison on a flat per-identity quota model (labeled flat-$N$, an analysis model for the spam stress test), and describe Status Network (SN), a deployed Ethereum L2 that implements this design.

We study square 4-Tensor Isomorphism over finite fields in the average-case model where the first tensor is uniform and the second is arbitrary. The closest polynomial-time method exploits a higher-dimensional flattening kernel. The denser corank-one stratum occurs on the $1/q$ scale, but its one-dimensional kernel loses the matrix-pair information used by that method. We make this minimal defect algorithmically useful. After normalizing the left and right kernel matrices to the identity, the residual action becomes a pair of adjoint actions on $\mathfrak{sl}_n$. The normalized flattening induces a uniform map $\Phi\in\mathrm{GL}(\mathfrak{sl}_n)$; its two Gram operators yield linked projective spectral matrix pairs. We prove constant-probability scalar common-centralizer bounds for their actual orthogonality-conditioned distribution, recover both residual conjugations without enumerating field elements, and lift them to all four tensor factors.

For every odd prime power $q\geq 5$ and $n\geq 5$ with $\operatorname{char}(\mathbb{F}_q)\nmid n$, this gives a randomized partial algorithm with expected $\operatorname{poly}(n,\log q)$ running time that is correct on at least $c/q$ of uniform first tensors, for an explicit universal $c>0$. Its only randomized components are Las Vegas finite-field subroutines. We also give a complementary large-field result on tensors whose three standard $2|2$ flattenings are invertible. These results concern certified average-case complexity, and both tractable events are efficiently recognizable.

Matrix Code Conjugacy asks whether two matrix subspaces are related by one simultaneous change of basis. A recent average-case algorithm reaches a $\Theta(1/q)$ fraction when the code dimension equals the matrix size, but a general code basis carries an additional unknown coefficient-space action. We bypass that action rather than recover it. A nonzero generator $A$ of a one-dimensional trace hull defines the homogeneous functionals $X\mapsto\operatorname{Tr}(A^rX)$. A transverse moment selects a nondegenerate complement of the hull, and trace duality turns the moments into basis-independent homogeneous matrices inside the code. The pair $(A,M_2)$ transforms only by ambient conjugation and a known scalar weight.

For every odd prime power $q$, odd $n\ge 5$, and $2\le m\le n^2-2$, we obtain a deterministic partial search-and-decision algorithm that is correct for at least a $1/(35q)$ fraction of uniformly random $m$-dimensional first codes, against every second input. Its bit complexity is $\operatorname{poly}(n,m,\log q)$; the certified fraction is $\Theta(1/q)$. The proof counts the actual correlated projection law of $M_2$, including its endpoint atoms, and never models it as an independent random matrix. A direct corollary gives the same $\Theta(1/q)$ scale in the independent-uniform ordered-tuple model. The result excludes characteristic two and even $n$, and it does not by itself yield a general Matrix Code Equivalence algorithm.

Subspace differential uniformity (SDU) measures the concentration of a differential distribution table (DDT) on affine subspaces. We determine the exact optima of the two axial affine-SDU coordinates in dimension five and establish a strict gap between locally admissible support designs and supports realizable by almost perfect nonlinear (APN) permutations. We first prove that every $16$-subset of $\mathbb{F}_2^5$ meets some affine $3$-flat in at least six points. Equality holds precisely for balanced quadratic indicators of polar rank four, forming a single affine orbit represented by $\operatorname{supp}(\operatorname{Tr}(x^3))$. This gives the relaxed axial optimum $12$. We then classify all $900$ ordered monomial-trace candidates $M_{r,s}(u,v)=\operatorname{Tr}(u^r v^s)$: exactly $100$ attain both relaxed axial optima, yielding $20$ labelled arrays and three product-linear types up to transpose. Despite satisfying regularity and zero-vector-sum constraints, every optimal type violates a global necessary condition for DDT realizability: its two-dimensional character transform contains a negative coefficient where a vectorial Walsh square is required. Finally, the published exhaustive affine classification of five-bit APN permutations, together with direct recomputation of all five class representatives, gives realizable axial minimum $14$, attained simultaneously by the $x^{15}$ class. Thus local incidence and vector-sum constraints permit score $12$, whereas genuine APN-permutation DDT supports require score $14$.

Degree-sum-freedom is a local criterion for division-property propagation from affine input spaces. The published version states that this criterion is invariant under extended-affine (EA) equivalence. We show that this assertion does not hold beyond ordinary sum-freedom and quantify the resulting variation. First, the natural Gold APN pair $x^3$ and $x^3+x$ has exact proper-flat values 3 and 2 on an infinite sequence of dimensions. We then study a known complete-mapping family of EA-equivalent, differentially 4-uniform permutations $F_b,G_b$ on $2r$ bits. For every odd $r$ and every $1\le c\le\lfloor(r-3)/2\rfloor$, we determine their exact codimension-$c$ profiles: $\mu_c(F_b)=2c$ and $\mu_c(G_b)=r+c-1$, equivalently $\tau_{2r-c}(F_b)=2r-2c$ and $\tau_{2r-c}(G_b)=r-c+1$. Thus the gap is $r-c-1\ge(r+1)/2$ simultaneously over a linear-size range of proper affine codimensions. The mate upper bound follows by specializing known generalized-degree duality with the exact source profile established here. The matching uniform lower bound is family-specific: after an associated-graded reduction, odd codimensions are detected by one classical consecutive Moore determinant, whereas even codimensions require a jointly nonvanishing family of replacement minors. A cyclic carry classification proves that the selected coefficients are complete reduced coefficients. These results concern local affine-input division-property behavior; they do not yield a multiround distinguisher or an attack on a concrete cipher.

The MACsec Key Agreement protocol, defined in IEEE 802.1X, manages and distributes ephemeral Secure Association Keys for Ethernet links protected with MAC security (IEEE 802.1AE). Prior work has shown that baseline MKA may scale poorly on shared medium Ethernet multidrop links and that formal worst-case bounds significantly exceed automotive startup targets, motivating alternative solutions such as In-line Key Agreement. However, in practice, to preserve compatibility, integration effort, and alignment of standardization, automotive systems are more likely to optimize a MACsec/MKA architecture than to completely replace it. This paper presents novel automotive MKA optimizations targeting secure startup times on shared medium networks and evaluates them through detailed network simulations. Unlike previous work focused on baseline MKA or deterministic worst-case analysis, we study the full startup-time distribution of the optimized protocol under realistic startup scenarios. We quantify the effect of the proposed optimizations on Time-To-Key-Agreement and show how the resulting empirical distributions can be translated into conservative simulation-derived practical startup-time bounds suitable for OEM timing budgets. The resulting bounds are intended as simulation-derived engineering bounds under the modeled startup assumptions, complementing formal worst-case analysis with distributional information on typical, tail, and upper-end behavior.

Candidates for post-quantum migration carry additional costs compared to their pre-quantum counterparts, especially for signatures, and they lose attractive properties of schemes such as BLS: homomorphism, and hence direct signature aggregation.

We propose a methodology through which a pre-quantum primitive may still be securely used past Q-day (the advent of quantum computers) in settings where forgery of signatures or cryptographic proofs need only be prevented for a bounded lifespan (transient quantum security). The idea is to bind a fresh, ephemeral, ordinary pre-quantum key to a long-term post-quantum identity once per lifespan window, so a forgery under the fresh key is useful only for that window, and to derive the fresh key so that its exposure never leaks the long-term secret.

Our main case study is the post-quantum migration of Ethereum consensus, where we give a solution that keeps relying on BLS and (i) retains signature aggregation, central at Ethereum's scale, without a SNARK prover, so the consensus-critical aggregate stays a single ~96-byte BLS signature, about three orders of magnitude smaller than the hundreds of kilobytes a SNARK-aggregated hash-based alternative needs per aggregate, as in the current proposal for post-quantum Ethereum consensus; and (ii) needs only an additional ~590-690 bytes per epoch of per-validator reveal traffic.

Security holds as long as a standard pairing-based variant of the computational Diffie-Hellman problem (co-CDH') cannot be broken by a quantum computer within the 6.4-minute duration of an Ethereum epoch; we discuss the hardware and time budgets such a break would require today, and how they may shrink as quantum hardware improves.

We also provide a formal model and security analysis for the construction, and, of independent interest, a new analysis of BLS where the secret key is sampled similarly to the Dodis-Yampolskiy VRF (IACR PKC 2005) and the adversary is given a related group element as leakage.

Privacy-preserving distributed ledgers enable transaction processing systems in which users can submit transactions without revealing their identities or transaction details. Regulated and institutional settings impose additional requirements: authorized parties must be able to efficiently trace transactions to their originators without compromising overall system privacy. Existing approaches suffer from important limitations, including restricted parallel transaction formation, high computational overhead, and overly broad auditor access to user secrets. We present a framework for efficient tracing that eliminates concurrency issues while limiting auditor access. We formalize our security requirements via an ideal functionality and propose a black-box construction based on pseudorandom functions and anonymous credentials, with two concrete instantiations: one using hash-based PRFs and zk-SNARKs, and another using algebraic PRFs and Sigma protocols. Our experimental evaluation demonstrates practicality, incurring only a few milliseconds of overhead for the added tracing capabilities.

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

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, so public-key UC realizations require a trapdoor or an idealized setup.

Spartan is a SNARK for R1CS that can be instantiated with any multi- linear 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 only 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 the byte lookup tables used by Binius64 for evaluating bit-valued linear maps.

Thus, BinarySpartan is not a new proof system but rather a natural instantiation of Spartan over binary fields; we implement and evaluate it end to end. On a MacBook Pro M4 Max (using only its 12 performance cores, and without GPU/Metal acceleration), BinarySpartan proves BLAKE3 at 410,000 hashes/second and SHA-256 at 219,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.

We prove two deterministic inapproximability results.

First, for every fixed $\epsilon>0$, Euclidean $\mathrm{GapCVP}^{(2)}$ is NP-hard with gap factor $n^{1/8-\epsilon}$ under deterministic polynomial-time many-one reductions, where $n$ denotes the lattice rank. Consequently, the Euclidean closest vector problem is NP-hard to approximate within the same factor. This improves the previous $n^{1/400}$ hardness factor in Chapter 7 of the OpenAI report [Ope26].

Second, for every fixed $\epsilon>0$, binary nearest codeword and binary syndrome decoding are NP-hard to approximate within $n^{1/4-\epsilon}$ under deterministic polynomial-time many-one reductions, where $n$ denotes the binary block length. This improves the previous $n^{1/200}$ hardness factor in Chapter 7 of the OpenAI report [Ope26].

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.

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

Video conferencing software, including Zoom, Microsoft Teams, and Cisco Webex, use human-driven key verification ceremonies to protect end-to-end encrypted meetings against a potentially malicious service provider. The client software shows each participant a code that they must compare; if the codes match, the call is considered secure. Prior security analyses assumed authenticated out-of-band channels for the comparison, but this is generally unrealistic. The codes are short-lived, so the ``in-band'' channel being verified is, itself, the most natural one to use. We seek to understand the implications of this common practice, asking whether it can be secure and under what conditions.

To this end, we formalize the notion of a Human-to-Human Group Key Agreement protocol, modeling an authenticated group key exchange between people, rather than their cryptographic keys. We identify that the security of these protocols relies on the pre-existing capacity of people to consistently recognize one another, avoiding any global identification scheme or trusted external infrastructure.

We present a construction, prove it secure in our model, derive concrete bounds, and discuss non-examples demonstrating the definition's subtlety. Our results highlight the approach's usability issues and reliance on unforgeability of human-authenticated video streams---an assumption additionally challenged by recent advances in deepfakes.

Private information retrieval (PIR) is a fundamental cryptographic primitive that allows a client to retrieve an entry of a database from a server without revealing which entry was retrieved. PIR security is traditionally defined with a distinguishing game that ensures the clients' access patterns are kept private from a semi-honest server. Verifiable PIR (VPIR) adds another game-based property that holds against a malicious server: the server is bound to a particular database and cannot cause a client to retrieve a database entry that is inconsistent with this database. Recent work by Alon and Beimel [ITC 2025] deviated from the traditional game-based PIR definitions and contributed a definition of standalone simulation-based security for multi-server PIR. Their techniques, however, do not readily extend to single-server VPIR and do not consider concurrent protocol composition when PIR is used as a building block within a larger application.

In this work, we further the study of simulation-based VPIR security. We are the first to formalize a universally composable (UC) definition of VPIR in the single-server setting by giving an ideal VPIR functionality. We motivate the need for UC security by showing how game-based VPIR properties fail under sequential and concurrent protocol composition. We also demonstrate the generality of our UC VPIR functionality by providing two realizations based on a trivial PIR and VeriSimplePIR [de Castro and Lee, USENIX Security 2024].

Additionally, we introduce a new kind of VPIR, called Updatable VPIR (UVPIR), which guarantees to clients that (1) database updates are authorized by permissioned clients and (2) responses to their queries are consistent with a specific version of the PIR database. We show that UVPIR can be constructed in a black-box manner on top of any VPIR protocol.