International Association
for Cryptologic Research

Secure key leasing (SKL) is a quantum cryptographic primitive that enables the leasing of decryption keys to delegated users with the guarantee that, once revoked, the lessees irreversibly lose decryption capability. A key feature that makes SKL practically relevant is classical revocation: the ability to revoke keys at any time and from anywhere, without relying on a quantum channel.

In this work, we revisit SKL schemes for public-key encryption (PKE) and identity-based encryption (IBE), and present a new approach for concrete efficiency under the standard Learning With Errors (LWE) assumption. First, we refine the security analysis of the Dual-Regev SKL-PKE scheme with classical revocation from [Ananth, Poremba, and Vaikuntanathan, TCC 2023; Ananth, Hu, and Huang, TCC 2024], establishing security under the polynomial hardness of LWE with polynomial modulus. Together with the resource efficiency of the Dual-Regev-based construction, our analysis shows that this approach yields the most quantum-efficient known SKL-PKE scheme. Second, we present a simple and efficient construction of selectively secure SKL-IBE with classical revocation from standard LWE. Our approach directly extends the Dual-Regev SKL-PKE within the IBE framework of [Agrawal, Boneh, and Boyen, Eurocrypt 2010], avoiding garbled circuits and obfuscation-based assumptions and achieving improved concrete efficiency over prior generic approaches.

Multi-party computation (MPC) enables multiple parties to jointly process sensitive data without revealing their inputs. However, existing MPC protocols remain inefficient for high-dimensional sparse data. In plaintext, sparse linear algebra algorithms address this problem using two fundamental primitives, Scatter and Gather.

We propose SparseMPC, an outsourced MPC protocol that securely implements Scatter and Gather and uses them to perform sparse matrix multiplication. Our protocol supports an arbitrary number of data owners and provides a low memory footprint, constant round complexity, and low communication cost. Beyond sparse matrix multiplication, SparseMPC provides a foundation for efficiently realizing a broader class of sparse computations in outsourced MPC.

Autonomous agents are increasingly used to plan and execute paid workflows on behalf of users. Existing agentic-payment frameworks support this delegation through merchant-admission authorization credentials but require the user to specify merchants before execution. However, complex paid workflows often span multiple services and merchants, and agents may choose among them based on intermediate results. This creates two limitations: (1) requiring the user to choose each merchant in advance either limits the agent's adaptability or forces the user back into the loop; and (2) reusing a stable identifier across merchants lets observers link separate paid calls and infer the user's broader intent. To address these limitations, we introduce MinMandate, which grants adaptive merchant selection within user-approved task bounds and derives fresh per-call payment views without introducing a stable cross-merchant identifier. Extensive experiments on AgentDojo tasks demonstrate that, when 50% of merchants are unavailable, MinMandate improves task success by 32.7 percentage points on average across four tested planners compared with an AP2 baseline that preauthorizes one merchant per service class. Reintroducing a reusable public payment-layer handle in the Stable Handle ablation raises attacker task-recovery success by 27.4 percentage points on average, isolating the privacy cost of a stable join handle. The code is available at https://github.com/Zora-G/minmandate.

Certified deletion enables a party to prove that it has erased the sensitive information contained in a quantum state. Bartusek and Raizes (CRYPTO 2024) gave the first secret-sharing scheme with privately verifiable deletion. Subsequently, Katz and Sela (EUROCRYPT 2025) constructed secret-sharing schemes with publicly verifiable deletion under computational assumptions. Constructing such a publicly verifiable scheme without cryptographic assumptions remains open.

In this work, we introduce an intermediate notion called unanimously verifiable deletion, where deletion certificates are verified jointly by the parties in the protocol. While private verification relies on the dealer and public verification allows any third party to verify deletion, unanimous verification assigns the verification responsibility to the parties in the secret-sharing scheme themselves. We construct an information-theoretically secure linearly homomorphic threshold secret-sharing batch scheme with adaptive unanimously verifiable deletion. In particular, to obtain its linear-homomorphic property, we exploit a linearly homomorphic structure of BB84-type states that enables linear operations on encoded values while preserving certified deletion. More generally, this structure can be used to upgrade certain primitives with certified deletion to their linearly homomorphic counterparts.

As another major contribution, we demonstrate an application of this batch scheme by constructing outsourced multi-party computation (MPC) protocols for arbitrary arithmetic circuits. Our outsourced MPC has honest classical clients and quantum servers, and achieves adaptive unanimously verifiable deletion security in the trusted-preprocessing and security-with-abort setting, supports public output reconstruction, and is secure against malicious, rushing quantum server adversaries for any $t

Large-state ARX-based S-boxes have become a key component of modern lightweight cryptographic designs, yet deriving tight security bounds for their differential and linear properties remains challenging. In this paper, we study the security of Alzette, the 64-bit ARX-based S-box used in the SPARKLE permutation, and present a general framework for the analysis and design of large-state ARX S-boxes. We introduce SMCS, a hybrid search strategy that combines MILP-based optimization with SMT-based model checking, enabling the computation of tight bounds on maximum expected differential probabilities and linear correlations. Using SMCS, we refine existing bounds for Alzette and, for the first time, establish tight linear bounds (resp. differential bounds) for up to 15 rounds (resp. 14 rounds). Building on these results, we propose S-box configurational encoding, an automated design method for ARX-based S-boxes, and introduce a new family of S-boxes called AFS (ARX-Feistel Structure) with 32-bit and 64-bit instances. We show that selected AFS instances achieve strictly better resistance to single-trail differential and linear cryptanalysis than SPECKEY and Alzette, respectively, while preserving comparable hardware and software costs. Finally, we present the first bit-based SMT model for optimal long-trail decomposition and apply it to derive more accurate bounds for SPARX-128 and SPARKLE. Our results show that replacing the S-boxes with AFS instances yields substantial improvements in cryptanalytic security margins.

Noise flooding is a standard defense against decryption attacks on approximate homomorphic encryption, but its security proof is unusually sensitive to composition. Replacing each of \(q\) adaptive decryption answers with a statistically close simulation and applying an ordinary hybrid argument loses linearly in \(q\). The cryptographic proof instead accumulates conditional Kullback-Leibler (KL) costs and converts to statistical distance once, giving the parameter-critical square-root loss.

We machine-check this argument using Rocq and SSProve. Given any fully homomorphic encryption scheme that is approximately correct and IND-CPA secure, we formalize a reduction for every \(q\)-query IND-CPAD adversary and prove \[ \Pr[\mathsf{IND\text{-}CPAD}_{\mathsf{NF}}^{\mathcal A}=1] \leq \beta_{\mathsf{CPA}}(\mathcal B_{\mathcal A,q}) + \frac{\sqrt{qn}}{2\gamma}. \] where \(n\) is the plaintext dimension and \(\gamma\) is the flooding-width multiplier. Our proof constructs a new relational program logic over SSProve semantics. Its Pythagorean judgment composes conditional KL budgets without converting them to statistical distance, and a verified trace compiler lifts a local oracle rule to arbitrary adaptive programs with a single final conversion.

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.