We show that under a plausible number-theoretic conjecture, for any constant $s$ there exists an $s$-server private information retrieval (PIR) protocol that on an $n$-bit database requires communication $\exp(O((\log n)^{1/s} (\log \log n)^{1-1/s}))$. This achieves a superpolynomial improvement in communication when $s \geq 4$; previous constructions attaining the same communication required $2^{O(s)}$ servers. Our number-theoretic conjecture is implied by existing conjectures, namely the generalized repunit conjecture and Schinzel's hypothesis H (either one of these conjectures would suffice alone). Our result builds on the "matching vector family + $S$-decoding polynomials" framework pioneered by Efremenko (STOC 2009) and recently refined by Ghasemi, Kopparty, and Sudan (STOC 2025). The main ingredient is a framework for constructing $S$-decoding polynomials with only $k+1$ nonzero coefficients modulo special products of $k$ primes, resolving an open problem posed by Ghasemi and Kopparty (ITCS 2026). By the lower bound shown by Ghasemi and Kopparty, this is the minimum achievable sparsity. We also empirically validate our construction and make our result unconditional for all $s \leq 15$. We also apply our techniques to regimes where $s$ grows with $n$, showing under a stronger variant of our number-theoretic conjecture that the communication complexity of $s$-server matching-vector PIR can be superpolynomially reduced from the previous state of the art for any $s \leq \exp(o(\sqrt{\log \log n/\log \log \log n}))$. The main result for $s = O(1)$ and its proof were discovered in a GPT-5.5 Pro conversation prompted by the authors.

A quantum one-time program scheme is a functionality-preserving compiler that transforms a program into a quantum state that can be used to obtain only one output of the program. Our goal is to design quantum one-time programs that can be realized on existing quantum technologies. Our contributions are two-fold: 1. We design a BB84 state-based quantum one-time program scheme in the stateless trusted hardware model that is resilient to single-qubit corruption errors and detectable erasure errors. To illustrate, under independent noise with a 90% detectable erasure rate and a 3% Pauli Y-error rate on surviving qubits, a signature token of 39,801 BB84 qubits achieves forging probability at most $\small 2^{-128}$ against at most $\small 2^{32}$ classical verification queries, with honest failure probability below $\small 10^{-6}$. Prior to our work, [Behera, Sattath, and Shinar TQC'22] studied a BB84 state-based quantum one-time program scheme resilient to independent single-qubit corruption errors; our construction treats detectable erasures separately. 2. We give two extensions to our scheme. First, we study the setting wherein the same trusted hardware can be reused across different independently generated quantum one-time programs. Second, we study the setting wherein multiple trusted hardware devices are used and the security holds as long as at least one of them is not compromised.

We describe the design, implementation, and experimental evaluation of Magnetar, a transparent proof system for RV64I program executions (i.e., a zkVM). Magnetar is the first zkVM to simultaneously satisfy the following three properties: 1. General-purpose proving. Magnetar proves programs compiled to the general-purpose RV64I ISA. An implementation of the Ethereum Virtual Machine (EVM) written in Rust or Go can therefore run inside Magnetar, yielding a zkEVM for proving executions of existing EVM smart contracts. 2. Hash-based, post-quantum security. Magnetar’s cryptographic security is rooted in standard hash functions (e.g., SHA-256 or SHA-3). 3. Efficient recursion. Magnetar’s verification work is dominated by evaluating standard hash functions. Magnetar’s proof engine, BinarySpartan, is well-suited for such bit-oriented computations, so verifying a proof is itself an efficient proving workload. Unlike prior general-purpose zkVMs, Magnetar does not rely on circuit-friendly algebraic hash functions such as Poseidon or Poseidon2, elliptic-curve or lattice assumptions, or a conjectured Reed–Solomon proximity gap. Even prior zkVMs commonly described as hash-based rely on elliptic-curve or lattice assumptions in their core proving machinery, provide only about 100 bits of security, or rest on conjectured soundness; some do more than one of these. Finally, we implement Magnetar in Rust and experimentally evaluate it. We find that, at 120 bits of provable security and with 12 performance cores on an M4 Max MacBook Pro, Magnetar proves 2^{22}-cycle executions at 7.2–8.7 million cycles per second, with proofs of about 600 KiB that verify in 11–13 ms. Across 15 application workloads, Magnetar’s proving throughput is 24–66× that of SP1 Hypercube, a hash-and-more-based zkVM; 12–37× that of Jolt-Dory, a curve-based zkVM; and 6–20× that of Jolt-Akita, a lattice-based zkVM, with geometric-mean speedups of about 39×, 18×, and 9.6×, respectively. An optimized Magnetar proves 222-cycle executions at 9.5–12.8 million cycles per second, which increases each geometric-mean speedup by about 1.3×. Magnetar’s proofs are about 4.6× smaller than SP1 Hypercube’s; Jolt’s proofs are under 100 KiB, but they rely on elliptic-curve or lattice assumptions.

Shift-invariant permutations of \(\mathbb F_2^n\) are particularly attractive in symmetric cryptography because of their regularity and implementation efficiency. Constructing such permutations with an explicit algebraic structure remains a challenging problem. In this paper, we study a family of shift-invariant transformations of \(\mathbb F_2^n\) constructed from a recursively defined sequence of mappings \(\{\gamma_j\}_{j\ge 0}\) associated with landscapes. First, we prove that, under an explicit dimension condition relating \(n\) to the support of the landscape, the sequence \(\{\gamma_j\}_{j\ge 0}\) has the polynomial composition property if and only if the corresponding landscape is quasi-conserved on \(\mathbb F_2^n\) with a nonzero special index. Then, we determine the eventual zero or periodic behavior of \(\{\gamma_j\}_{j\ge0}\), including the exact index at which the sequence either first vanishes or becomes periodic, together with the least eventual period, and establish linear independence until the first linear relation occurs. When the polynomial composition property holds, we establish an explicit isomorphism between the group of permutation elements in the monoid generated by these mappings and the unit group of a quotient ring \(\mathbb F_2[z]/\langle p(z)\rangle\), where \(p(z)\) is a monomial or a binomial determined by the landscape. This framework reduces the tasks of testing bijectivity, computing iterates, and determining compositional inverses and orders of permutation elements to polynomial computations. Finally, we apply the results to mappings represented by binomials and trinomials in the quotient ring, obtaining explicit criteria and formulas, and tabulate more than one hundred representative constructions of shift-invariant permutations, recovering and unifying several previously studied families.

We prove that the Succinct Learning with Errors assumption, introduced by Wee (CRYPTO '24), and the Decomposed Learning with Errors assumption, introduced by Abram, Malavolta, and Roy (CRYPTO '25), are equivalent under appropriate parameter settings. Abram, Malavolta, and Roy proved that Succinct LWE implies Decomposed LWE. We establish the converse implication, showing that Decomposed LWE implies Succinct LWE.

Bosley and Dodis (TCC 2007) proved that a class of imperfect randomness sources that suffices for information-theoretic encryption of messages longer than the logarithm of the key length must admit deterministic extraction of nearly uniform bits, and asked whether the same is true of two-out-of-two secret sharing. Aggarwal, Chung, Obremski, and Ribeiro (TCC 2022) gave a positive answer for schemes that are in addition leakage-resilient or non-malleable; the original question remained open. We answer it in the negative. For every $b\ge2$ we construct a class of flat sources on $\{0,1\}^{b+2}$, each of min-entropy at least $b$, together with a perfectly correct and perfectly private two-out-of-two scheme that shares a $b$-bit secret into two $(b+1)$-bit shares using any source in the class, and we show that every deterministic map from $\{0,1\}^{b+2}$ to $\{0,1\}$ is at statistical distance at least $1/6$ from uniform on some source in the class. This implies that sharing a long enough secret does not require extractable randomness. The proof is a short parity argument. The idea of the construction extends to other thresholds: for two-out-of-$n$ and $r$-out-of-$r$ sharing we give perfect schemes with $(b+1)$-bit shares, private for classes of flat sources from which no single bit can be extracted with error below $1/(4n-2)$ and $1/(2(2^r-1))$, respectively.

We introduce the SHEDAG (Somewhere Honest Entropic sources over Directed Acyclic Graphs) source model, a general framework for multi-block randomness sources with causal correlations. A SHEDAG source is defined over a directed acyclic graph (DAG) $G$, whose nodes output $n$-bit blocks. Honest nodes output mutually independent blocks, which are uniformly random by default and, more generally, may have high min-entropy. Corrupted nodes output arbitrary functions of their causal views (all predecessors in $G$). We tightly characterize the conditions under which zero-error and negligible-error randomness extraction from SHEDAG sources is possible. \begin{description} \item[Zero-error extraction:] We show that perfect extraction from SHEDAG sources with $t$ corruptions is possible if and only if $G$ contains an \emph{unrelated set} (an antichain under reachability) of size at least $t+1$. In particular, if every unrelated set has size at most $t$, no function can extract a perfectly uniform bit. We also give a polynomial-time algorithm for finding a maximum unrelated set, thereby efficiently determining the largest corruption threshold $t$ for which perfect extraction is possible. \item[Negligible-error extraction:] We introduce a graph parameter, called the \emph{resilience} of a DAG $G$, that characterizes the feasibility of randomness extraction with \emph{negligible} error in the block length. We define two variants of this parameter, $\res_\uni(G)$ and $\res_\ent(G)$, corresponding to uniform and entropic honest nodes, respectively. We show that when honest nodes are uniform, negligible-error extraction is impossible when the number of corrupted nodes $t>\res_\uni(G)$. When honest nodes are entropic, we show that negligible-error extraction is impossible when $t>\res_\ent(G)$. Complementing these impossibility results, we establish the following: \begin{itemize} \item[(i)] There exists an explicit extractor for SHEDAG sources with $t\leq \res_\uni(G)$ corrupted nodes and honest blocks that are uniform over $\bits^n$, achieving output length $\Omega_N(n)$ and error $2^{-\Omega_N(n)}$. Here $N$ is number of vertices of the DAG $G$. \item[(ii)] There exists a non-explicit extractor for SHEDAG sources with $t\leq \res_\ent(G)$ corrupted nodes and honest blocks of min-entropy $k\geq \poly\log n$, achieving output length $k^{\Omega(1)}$ and error $2^{-k^{\Omega(1)}}$. \end{itemize}

Homomorphic message authentication codes (HMACs) allow users to authenticate data using a shared secret key, while supporting computation over authenticated data. Given data $(m_1, \ldots, m_n)$ and their tags $(\sigma_1, \ldots, \sigma_n)$, anyone can evaluate a circuit $C$ on the data and tags to produce a succinct tag authenticating the output $C(m_1, \ldots, m_n)$. Importantly, tags remain succinc -- of size polynomial in the security parameter $\lambda$ -- regardless of the size of $C$. This work introduces an enhanced variant of HMACs called algebraic HMAC (aHMAC), in which all tags (input and output) take the form $\Delta \cdot m + K$, as in standard information-theoretic MACs. We construct an aHMAC from group-based assumptions, including variants of the DDH and DCR assumptions, and use it to obtain group-based constructions of several cryptographic primitives: - Succinct CDS for circuits. For any $P: [N]^k \to [N]$ represented by circuit, we obtain a Conditional Disclosure of Secrets protocol with poly$(\lambda, k, \log N )$ communication. - Succinct PSM for simple programs. For any $P:[N]^k \to [N]$ represented by a truth-table or shallow branching program, we obtain a Private Simultaneous Messages protocol or a garbling scheme with poly$(\lambda, k, \log N )$ communication. - Constrained PRFs for circuits. We obtain the first group-based constrained pseudorandom functions for general circuits, improving over a previous construction for NC1 circuits. Prior to our work, these applications could only be obtained from lattice assumptions or indistinguishability obfuscation.

We study the local leakage resilience of Shamir secret sharing, where an adversary leaks a bounded number of bits from every share. For $n$ parties and reconstruction threshold $k$ over a prime field $\mathbb{F}_p$ with $p>n$, we prove the following. (1) There is an absolute constant $c_{\mathrm{bh}}<1/2$ such that, for $k\ge c_{\mathrm{bh}}n$, Shamir sharing is resilient to arbitrary one-bit leakage from every share. The best previous threshold was $0.668n$. (2) For every fixed $0<\delta<1/2$ and $k\ge(1/2+\delta)n$, Shamir sharing is resilient to $\left\lfloor\frac{\delta}{24}\log_2 n\right\rfloor$ bits of arbitrary local leakage per share. By a recent attack, this number of bits is optimal up to a constant factor depending on $\delta$. (3) For every fixed threshold rate $c>0$ and $k\ge cn$, Shamir sharing is resilient to quadratic-residue leakage and to almost all local leakage functions of up to $\eta_c\log_2 p$ bits, for a constant $\eta_c>0$. All three results follow from one analytic framework, which we develop for generalized Reed--Solomon codes: local leakage from a uniform codeword is statistically close to the same leakage from independent uniform field elements. The framework expresses the leakage distance as the norm of a function on the leakage outputs. The Efron--Stein decomposition splits this function into orthogonal components indexed by supports of dual codewords. Two tools bound the components: list recovery of the dual code, which is ordinary list decoding for one-bit leakage, and a generalized von Neumann inequality for MDS systems of linear forms that retains linearly many Gowers norms. The first tool gives the result above half, the second gives the constant-rate result, and applying both to different ranges of supports in the same decomposition gives the result below half.

Zero-knowledge succinct non-interactive arguments of knowledge (zkSNARKs) are increasingly used within larger cryptographic protocols, making security under composition essential. Generic compilation to Universal Composability (UC) requires straight-line, black-box extraction while preserving succinctness and controlling prover cost. We introduce verifiable reconstructible straightline codes (VRSCs), a primitive that separates public hiding, transcript-based reconstruction, binding, and proof non-rerandomizability. This abstraction exposes a missing security requirement in the witness-succinct UC compiler of Ganesh et al. (EUROCRYPT 2023). Permuting previously revealed evaluation openings produces a fresh accepting proof with non-negligible probability without violating non-extrapolation, invalidating the claimed simulation argument. Proof non-rerandomizability captures this attack at the certificate level. Our construction prevents transfers between repetitions through verifier-enforced disjoint evaluation domains. We formulate a generic UC lifting theorem in terms of VRSCs and give a pairing-based instantiation using a Fischlin-style search over authenticated codeword symbols. Structured Reed--Solomon encoding and jointly computed KZG openings reduce certificate-generation work from quadratic to \(O_{\lambda}(n\log n)\), where \(n\) is the witness size. Only a linear-time encoding check enters the underlying SNARK circuit. To our knowledge, this is the first generic UC lifting compiler that simultaneously achieves quasi-linear prover overhead and constant additional proof size and verification work with respect to the witness size.

The succinct LWE (CRYPTO~'24) and decomposed LWE (CRYPTO~'25) assumptions are two recently introduced variants of the celebrated LWE problem, known to imply the existence of numerous new cryptographic primitives. Yet, the hardness of these problems has thus far remained poorly understood, since there is no known reduction to LWE. In this work, we study these lattice problems from a foundational perspective. Our main technical contribution is a worst-case-to-average-case reduction from \emph{superlattice SVP} (SuperSVP) to succinct SIS. We introduce SuperSVP as a variant of SVP for general lattices in which the solver is additionally given, as a hint, a short basis for a related superlattice. Combining this result with our quantum reduction from succinct SIS to succinct LWE, which is an analog of Regev's SIS-to-LWE reduction, and with our search-to-decision reduction establishes worst-case hardness for succinct LWE. Finally, we show that succinct and decomposed LWE are equivalent, extending this conclusion to decomposed LWE. Overall, our work places succinct and decomposed LWE on firmer theoretical ground and, as a direct consequence, establishes the \emph{worst-case} hardness of a variety of cryptographic primitives, known to be implied by these assumptions.

We study the Add/XNOR decision problem: given $n$ words of $n$ bits each, choose between addition modulo $2^n$ and bitwise XNOR at each position of a left-associative expression so that its final value is zero. We prove NP-completeness by a deterministic polynomial-time reduction from binary SUBSET-SUM. Independent four-bit guard fields force each successful four-operation gadget to consist entirely of additions or entirely of XNORs. Normalization by XNOR parity prevents later gadgets from repairing a failed guard, while control bits and zero padding enforce the target and the equality of operand count and word width. The reduction also yields a $2^{o(n)}$-time exclusion under the Exponential Time Hypothesis and NP-completeness when the word width is a fixed positive rational power of the operand count. An exact meet-in-the-middle algorithm uses $O^*(2^{(n-1)/2})$ time and space, where $O^*$ suppresses polynomial factors in $n$. We also quantify the reduction's solution multiplicity and the output marginals for independently uniform operands. The optimal exponential rate and average-case complexity remain questions for further work.

Non-interactive batch arguments (BARGs) for $\mathsf{NP}$ enable proving the validity of $k$ $\mathsf{NP}$ statements with a proof whose size is independent of $k$. Threshold BARGs are a natural generalization that enables proving that at least $t$ out of $k$ statements are valid. Unfortunately, existing threshold BARG constructions have the drawback that the size of the common reference string (CRS) grows polynomially with $k$. This is the case even when the statements have a short description (e.g., when considering index languages). Moreover, other than constructions based on indistinguishability obfuscation ($i\mathcal{O}$), prior constructions could only achieve computational soundness. In this work, we construct the first threshold BARG with statistical soundness for an expressive class of trapdoor threshold languages from either circular-secure fully homomorphic encryption or from witness encryption in combination with the learning with errors assumption. Moreover and importantly for our applications, the size of the CRS only scales polylogarithmically with $k$. Next, we combine our threshold BARG with a new technique for sampling pseudorandom permutations in order to build weighted threshold signatures with a statistical unforgeability guarantee. Then, in combination with witness encryption, we obtain a weighted threshold encryption scheme that supports $\lambda$-bit weights. Decryption is entirely non-interactive in our setting. Previously, such a scheme was only known from $i\mathcal{O}$. If we additionally work in the random oracle model, then we obtain a weighted threshold encryption scheme that supports arbitrary weights with silent setup. In the silent setup model, users choose their own public/secret keys and no longer need to rely on a central authority to generate and issue decryption keys.

The Noisy Linear Equations problem involves finding the solution to a random linear system over a finite field given noisy evaluations. This is a generalisation of various learning problems widely used in cryptography, including Learning with Errors (LWE), Learning with Rounding (LWR), and Learning Parity with Noise (LPN). We present a new sample-preserving search-to-decision reduction for Noisy Linear Equations that has complexity $\mathrm{poly}(n,m,\log q, q/\sigma)$, where $n$ is the dimension of the secret, $m$ is the number of samples, $q$ is the modulus, and $\sigma$ is the magnitude of the noise (defined suitably for the kind of noise involved). In particular, this implies search-to-decision reductions for LWE and LWR that run in time $\mathrm{poly}(n)$ even if the modulus $q$ is exponentially large, as long as the noise-to-modulus ratio $\sigma/q$ is non-negligible. Our reduction works for prime moduli $q$. If $q$ is composite, it instead produces a list that contains a small multiple of the solution. Prior to this work, known search-to-decision reductions for LWE and LWR either did not preserve the parameters of the problem (i.e., $m$, $n$, $\sigma$, and $q$), or had complexity that scaled polynomially with either $\sigma$ or the largest prime factor of $q$.

Many hash-based proof systems check that committed words are close to Reed–Solomon codewords by testing one random combination of them. Their soundness analysis uses a proximity gap: if the combination agrees with a codeword on many positions, so do the original words, on the same positions, except for a few exceptional challenges. Such gaps are known above the Johnson threshold, about $\sqrt\rho$ for rate $\rho$, and extending them below it would shrink proofs. Recent work does so in large characteristic, but not over binary fields, where some of the fastest proof systems run. We show that beyond-Johnson proximity gaps fail over binary fields. Our first construction applies to any additive domain (a binary linear subspace) filling a constant fraction of a containing binary field. Over a suitable extension challenge field and at rate $1/4$, it gives two words that can simultaneously match codewords on at most $25\%$ of the positions, while their combinations approach the $50\%$ Johnson threshold for superpolynomially many challenges. This rules out any $\mathrm{poly}(N)/|\mathbb F|$ bound on the exceptional probability below Johnson. On Binius64's domain (length $2^{27}$, $128$-bit challenges), the combination reaches $49.4\%$ agreement with probability above $2^{-30}$. The construction also rules out polynomial-size decoding lists below Johnson: one word agrees with superpolynomially many codewords at agreement approaching $50\%$, whereas earlier superpolynomial lists needed the rate, or the agreement–rate gap, to vanish. Our second and third constructions cover every additive domain, including the sparse domains used by LeanVM and Flock. At rate $1/16$, the second gives $(N-1)(N-2)/6$ exceptional challenges at the Johnson threshold itself, when the domain lies in a proper subfield of the challenge field. For domains larger than $2^{20}$, this rules out even $90$ bits of soundness from a single beyond-Johnson proximity-gap check over a $128$-bit challenge field. The third construction trades agreement for larger exception counts: at rate $1/2$ and length $2^{22}$, its combinations reach $53.125\%$ agreement from common agreement $50\%$, with probability at least $2^{-20}$ over a $192$-bit challenge field. Finally, at every fixed rate, some constant agreement above the rate makes every challenge exceptional, over $\mathrm{poly}(N)$-size challenge fields. All of our results are formally verified in Lean.

Linear correctors reduce the bias of random bits via parity (XOR), but their guarantees are known mostly for independent bits, an assumption violated by many physical entropy sources. We give a general, exact formula for the parity bias of dependent bits from a (hidden, possibly non-homogeneous) Markov chain, as a product of twisted transfer kernels. Under next-bit unpredictability, i.e. conditional bias at most $\beta$, the decay is governed by $\beta$ itself: sharp for a one-bit context, $|\mathrm{bias}|\le\beta^{\lceil n/2\rceil}$, and \emph{near-optimal} for an $m$-bit context, within a factor $3^{1/3}\approx1.44$ of the best possible per-bit rate, which is at least $\beta^{1/(m+1)}$ (attained by a noisy LFSR) and asymptotically equal to it as $\beta\to0$. Against the best previous bound (Zhou and Bruck, ISIT 2011) we \emph{correct the exponent} and \emph{tighten the bound on $n$ bits by a factor of about $2^{\lfloor(n-1)/2\rfloor}/\beta$}, with a matching construction. The decay is non-monotone, so a corrector should be certified at every operating length, or via the envelope $\beta^{\lceil n/2\rceil}$. Finally, bounded memory is necessary: if unpredictability is imposed on the full history, XOR-ing does not reduce the bias at all.

Motivated by recent constructions and barriers in secret sharing, we study multislice functions. These functions, parametrized by a width parameter $w$, take the value 0 on inputs of Hamming weight below a base value $k$, 1 on inputs of weight above $k+w$, and are monotone in between. We first investigate formulas over multislice gates, which generalize the formulas over slices model (Applebaum et al., TOCT 2026). We prove that, although multislices compute complicated functions, they do not help in computing the worst-case function when $w\ll n$; that is, there is an explicit monotone function such that for every $w$, every formula over multislice gates of width $w$ that computes it, regardless of its depth and gate fan-in, has size $2^{\Omega\left(n/((w+1)\log^2 n)\right)}$. Our lower bound is based on a randomized Karchmer-Wigderson protocol for multislices that can be amortized across the formula. As a complementary result, we show how to realize multislices using slice gates, i.e., multislice gates of width 0; the construction uses a simple peeling recursion. Consequently, every width-$w$ multislice on $n$ variables has a formula over slice gates of size at most $2n^{w+1}$ and depth $(w+1)$. The same construction allows to compute multislices with small monotone real formulas and circuits, two models introduced by Pudl\'ak (J. Symb. Log., 1997) in the context of proof complexity. This result also has an application to secret sharing: it yields, for sufficiently long secrets, multilinear secret-sharing schemes for width-$w$ multislices with maximal information ratio $n^{O(w+1)}$, which is polynomial for every fixed $w$. In addition, we prove that an explicit access structure requires shares of size $2^{\Omega(n)}$ in every secret-sharing scheme from a family of schemes that captures all currently known constructions for general access structures with share size $2^{cn+o(n)}$, for $c<1$. Our proof goes through an exponential lower bound on the size of formulas over so-called CDS gates and ideal linear gates.

Fully Homomorphic Encryption for RAM programs (RAM-FHE), introduced by Hamlin, Holmgren, Weiss, and Wichs (Crypto 2019), allows a server to evaluate a RAM program on encrypted data at a per-step cost sublinear in the memory size $N$, whereas standard FHE must read the entire memory for every memory access. In a celebrated work, Lin, Mook, and Wichs (STOC 2023) gave the first, and to date the only, construction from a concrete assumption, namely Ring-LWE. In this work, we construct a RAM-FHE scheme from plain LWE that evaluates each step of a RAM program in $o(N/\log N)$ time. While the scheme is barely sublinear, even such a slight saving over the linear cost of standard FHE was not known to be achievable from unstructured, plain LWE. As Lin, Mook, and Wichs did, we build RAM-FHE by extending a Doubly-Efficient Private Information Retrieval (DEPIR) scheme. Since the only DEPIR from plain LWE, due to Lee (Crypto 2026), relies on a Common Reference String (CRS) that is incompatible with the extension, we show how to remove the CRS and obtain a DEPIR from plain LWE in the standard model, which may be of independent interest.

The distinguishing variant $\Delta$LIP of the Lattice Isomorphism Problem underlies the security proofs of a growing family of lattice-based schemes. As the special genus is the strongest efficiently computable invariant of a lattice, such a proof may replace the lattice used by the scheme with a random lattice of the same genus. This raises the question of how hard lattice problems actually are on such random lattices. We answer it, under GRH, with a worst-case to average-case reduction inside any special genus $\mathcal{G}$ of Hermitian lattices of fixed rank $r \geq 2$ over a cyclotomic field $K$ of degree $d$: for each of $\mathrm{(H)SVP}$, $\mathrm{HCVP}$, $(\Delta)\mathrm{BDD}$, $\mathrm{DSP}$ and $\mathrm{DGS}$, solving the problem on a random class of $\mathcal{G}$, drawn from its natural distribution, is as hard as solving it on the worst-case lattice of $\mathcal{G}$, at the cost of a factor $p = \mathrm{poly}(d) \cdot {\det}_{\mathbb{Q}}(\Lambda)^{O_r(1)/d}$ in the approximation factor. The reduction is a random walk on the Kneser $\mathfrak{p}$-neighbour graph of $\mathcal{G}$: neighbours stay close enough to transfer problem instances, while the walk equidistributes quickly, a fact we deduce from spectral bounds for the associated Hecke operators. As an application we give a direct and tight security proof for a minimal LIP-based KEM, resting on two independent assumptions: that the lattice it uses is indistinguishable from a random lattice of its genus, and that $\Delta$BDD is hard on that genus. Unlike existing LIP-based proofs, this requires neither an ad-hoc lattice of the form $q\Lambda \oplus (q+1)\Lambda$, nor the tightness loss caused by the dense sublattice such proofs rely on.

The Universal Composability (UC) framework provides a paradigm for security definitions that allows for arbitrary composition, but has been criticized for being unamicable to the concrete security approach, as the meaning of a concrete UC-security statement is hard to interpret in practice. This work aims at alleviating this concern in the context of Password-Authenticated Key Exchange (PAKE): we show that any concrete UC-security statement for PAKE can be easily converted to a concrete game-based security statement, whose real-life meaning is clearer. We also briefly discuss potential generalizations of our result to other cryptographic primitives.

Timed cryptography captures computations that inherently require a prescribed amount of time, even in the presence of parallelism, and has emerged as a central notion due to its broad applications in both practice and theory. A natural question is how timed cryptographic primitives relate to traditional cryptography, in particular to primitives in Minicrypt. Guan and Montgomery (CRYPTO 2024) show that sequential functions do not imply one-way functions (OWFs) via black-box reductions. Their result, however, leaves open whether adding public verifiability (a substantially stronger requirement) suffices to imply OWFs. We study this question via verifiable delay functions (VDFs), which require substantial sequential time to evaluate, yet produce a unique output that is efficiently and publicly verifiable. We show that VDFs do not imply OWFs via fully black-box, relativizing reductions. Combined with prior results showing that VDFs cannot be constructed in the random oracle model, this establishes that there is no black-box implication in either direction between VDFs and OWFs. Our proof develops a new oracle separation technique that combines the random oracle with a carefully designed complexity-theoretic oracle inspired by Kolmogorov complexity.

A long-standing hypothesis in artificial intelligence and neuroscience posits that intelligence is closely related to compression: the ability to compress information efficiently intuitively reflects capacities associated with intelligence and learning. Indeed, recent experimental works verify this intuition by showing connections between the capabilities of large language models (LLMs) and their ability as compressors: for instance, Deletang et al. (ICLR'24) demonstrate that LLMs can be used as powerful compressors, and Huang et al. (COLM'24) show that the compression ability of LLMs is highly correlated with their performance on benchmarks for knowledge and reasoning. In this work, we initiate a theoretical study of this connection. Our main result is that LLMs (formally modeled as next-token predictors) are equivalent to monotone (a.k.a. order-preserving) compression algorithms---namely, compression algorithms where the encoding process preserves the ordering of the inputs---in the sense that the one can be constructed from the other while preserving the same error up to an additive gap of 2. We next show that the monotonicity is required for this equivalence to hold if and only if cryptographic (infinitely-often) one-way functions exist. As a direct corollary, we get a cryptographic result of independent interest: the notion of next-bit pseudoentropy (a computational analogue of entropy) of a distribution is equivalent to monotone incompressibility of the distribution. (Previously, it was only known (Haitner et al., ITCS'23) that incompressibility implies next-bit pseudoentropy.)

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

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

We study the Batch Learning Parity with Noise (LPN) variant, where the oracle returns $k$ samples in a batch and draws the noise vector from a joint noise distribution $\mathcal{D}$ over $\mathbb{F}_2^k$ instead of from an i.i.d. product distribution. This model captures a broad range of correlated or structured noise patterns studied in cryptography and learning theory. Consequently, understanding which dependent-noise distributions preserve the hardness of LPN has become an important question. On the hardness side, we design several reductions from standard LPN to Batch LPN. Our reductions identify broader classes of noise distributions $\mathcal{D}$ that preserve LPN hardness, extending the prior hardness results of Golowich, Moitra, and Rohatgi (FOCS 2024). We show hardness in three regimes: 1. If $\mathcal{D}$ satisfies a mild Fourier-analytic condition $\sum_{\mathbf{s}\neq \mathbf0}|\widehat{P}_{\mathcal{D}}(\mathbf{s})|\le 2\varepsilon$, then Batch LPN is as hard as standard LPN with noise rate $1/2-\varepsilon$; 2. If $\mathcal{D}$ is $\Omega(\eta \cdot k 2^{-k})$-dense (i.e., every error pattern occurs with probability at least $\Omega(\eta \cdot k 2^{-k})$) for $\eta < 1/k$, then Batch LPN is as hard as standard LPN with noise rate $\eta$; 3. If $\mathcal{D}$ is a $\delta$-Santha--Vazirani source, then Batch LPN is as hard as standard LPN with noise rate $1/2-\varepsilon$ whenever $\delta\le O(2^{-k/2}\varepsilon)$, improving the previous $O(2^{-k}\varepsilon)$ dependence (in Golowich et al.). On the algorithmic side, we extend Arora and Ge's (ICALP 2011) linearization attack to show that Batch LPN can be solved when the noise distribution assigns sufficiently small probability to at least one point, complementing our second hardness result. We also observe that a nontrivial Fourier coefficient with magnitude close to one yields a simple reduction to low-noise LPN, giving an algorithmic counterpart to our first hardness result. Our reductions are based on random affine transformations and are analyzed through the lens of Fourier analysis, providing a general framework for studying dependent-noise LPN variants.

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

Deniable secret sharing (DSS; Canetti et al, TCC 2025) is designed for a scenario where an adversary is able to bribe or coerce all shareholders to divulge their shares of a secret. A deniable secret sharing scheme is equipped with a faking function that enables shareholders to produce fake shares that look like real shares, but do not actually reveal any additional information about the secret. Existing DSS constructions require the fakers to jointly compute on their shares, without considering how this computation might be realized. In this paper, we investigate two crucial properties of such computations: the extent to which the fakers themselves learn information about the secret (privacy against fakers), and the number of messages they need to exchange (message complexity). Message complexity can be seen as a measure of faking conspicuousness, if the adversary is able to observe network traffic. We prove that to obtain the strongest notion of DSS, any information-theoretic construction requires the fakers to exchange a non-zero number of messages, which could be large (depending on the access structure). We describe a general construction that matches this lower bound in many cases, e.g. for threshold access structures. Furthermore, for linear secret sharing schemes, we prove that certain unqualified sets must learn the secret as a result of faking. Moving to the computational setting, we describe two constructions which require no interaction beyond the knowledge of who the fakers are. This implies that both inconspicuousness and privacy against fakers are achieved. The first construction requires the share size to be exponential in the number of shareholders, but assumes only a PRG. The second construction has small shares, but assumes virtual black-box obfuscation. We see the latter construction as a stepping stone for a future iO-based instantiation. All of our lower bounds and constructions consider general access structures.

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

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

Based on techniques discovered in the better.codes autoresearch project, we show that Reed-Solomon codes of rate $\rho$ and block length $n$ over a field of sufficiently large characteristic, have $C\cdot n$ list size bound when requiring fractional agreement $\alpha$ with a received word; where $C,\alpha$ are constants depending only on $\rho$ and $\alpha<\sqrt{\rho}$. This complements the recent breakthrough results [BCPZZ26,Jeronimo26] achieving $n^c$ list size bounds with agreement $\rho+\epsilon$ for any constant $\epsilon>0$ with an unspecified constant exponent $c$.

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

While quantum position verification aims to certify a prover's location using quantum information, existing security definitions only guarantee that part of the successful adversarial party is in the claimed location. This leaves open the possibility that a distributed team of adversaries can jointly simulate a prover in a way that defeats the intended meaning of ``being at a location'' in position-based cryptography. We introduce stronger notions of position verification that we call quantum localization, which requires that there is a specified, unclonable state at the verified spacetime point -- and that this state can be found nowhere else. We show that quantum localization leads naturally to a meaningful notion of trajectory verification, in which quantum information is verifiably tracked through space and time. We construct quantum localization and trajectory verification protocols using quantum anchor states, which generalize coset states from unclonable cryptography. The security of our schemes is proven in the classical oracle (i.e. ideal obfuscation) model, which can be heuristically instantiated in the plain model using post-quantum indistinguishability obfuscation. We also introduce and instantiate the concept of functionality localization, which guarantees that the adversary has the ability to compute a secret function at the verified spacetime point, and this function cannot be computed anywhere else. This raises the intriguing possibility of localizing computational capabilities in space and time. More broadly, we believe our notions of quantum localization and subsequent feasibility results provide stronger foundations for position-based cryptography. At a conceptual level, our results also explore the tight link between two fundamental notions in physics -- location and information -- thus serving as a natural foundation for cryptographic capabilities tied to physical spacetime.

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

We present a neural network-based pipeline for efficiently generating fast matrix multiplication (FMM) algorithms of small but arbitrary dimensions $(n,m,k)$. Our neural network is general and tunable to output FMM schemes with specific properties, and in this paper we specifically target aspects that are useful and important in practical implementation, such as ternarity (coefficients in $\{-1, 0, 1\}$), sparseness and a low number of additions after optimization (addition reduction carried out separately). We generate and optimize thousands of FMM algorithms and show that our generation method is beneficial in terms of performance across the entire FMM pipeline (both the FMM generation itself and optimization of additions). We discuss performance metrics and utilize heatmaps to visualize and understand this performance. We achieve record-low arithmetic (additive) complexity for various combinations of dimensions. For $(n,m,k) = (2,2,k)$, our method performs particularly well. Our improvement compared to previous results increases with $k$. We show that the (addition) optimization process can behave very differently depending on the dimensions considered, indicating how further improvements (beyond our results) can be targeted. In particular, in the $(n,m,k) = (2,2,k)$ setting, we show evidence of structural FMM properties coming into play, concretely showing that FMM generation with a minimal number of additions is sometimes suboptimal with respect to the entire FMM pipeline. Finally, we make our neural network implementation, our generated FMM schemes, heatmap utilities and datasets publicly available.

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

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

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

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

One-time programs (OTPs) aim to let a user evaluate a program on a single input while revealing nothing else. Classical OTPs require hardware assumptions. Quantum measurement offers a possible physical basis for one-time use: obtaining an output may irreversibly disturb the program needed for further computation. Yet deterministic functionalities remain impossible due to gentle-measurement attacks (Broadbent, Gutoski and Stebila, 2013). While recent works achieve positive results for randomized functionalities with high-entropy outputs (Gunn, Movassagh 2025; Gupte, Liu, Raizes, Roberts, Vaikuntanathan 2025), the fundamental limits and the strongest achievable security notions remain poorly understood. Inspired by classical obfuscation, we ask for a “best-possible” one-time compiler: a generic transformation that, for any functionality, leaks the least amount of information compared with any other one-time implementation. We show that a generic best-possible one-time compiler cannot exist even for classical randomized functionalities assuming $\mathsf{SZK} \not\subseteq \mathsf{BQP}$. Given this impossibility, we identify a natural subclass of one-time compilers called “testable one-time program” compilers, which output quantum states augmented with reflection programs for themselves. (1) We formulate a simplified, generalized Single-Effective-Query (SEQ) simulation security notion for quantum channels. The definition uses self-adjoint implementations whose behavior under arbitrary quantum interactions depends only on the channel. We show that SEQ security implies best-possible testable one-time security. (2) We construct SEQ-secure OTPs for all quantum functionalities in the classical oracle model, yielding the first positive results for arbitrary quantum channels beyond classical randomized functionalities. Thus, SEQ security could serve as a testable one-time analogue of virtual black-box (VBB) security in the many-time obfuscation setting. Finally, we propose stateful quantum indistinguishability obfuscation (stateful quantum iO) — quantum state obfuscation for stateful quantum programs. It implies best-possible testable OTPs and is achievable in the classical oracle model, thus giving us a promising approach towards best-possible testable OTPs in the plain model.

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

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

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

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

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

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

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

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

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

Can simple processes appear highly complex? Gowers (Comb. Prob. Comp. '96) conjectured that repeatedly composing local random reversible operations can yield global permutations that are indistinguishable from random. In this work, we study the unitary quantum analog of this question, in an attempt to make new progress on this longstanding conjecture. Our first result shows that statistical moment matching in the form of unitary designs does not generically lead to pseudorandomness---even for the simplest quantum processes: for every fixed $t$, we give an efficiently samplable family $\{\nu_n\}_n$ of distributions on one- and two-qubit gates such that, after $T=O_t(n^2\log^2 n)$ independent steps, the resulting $n$-qubit ensemble is an approximate unitary $t$-design with negligible error $\exp(-\Omega(\log^2 n))$, yet an efficient quantum algorithm distinguishes it from random using only $O_t(\log^2 n)$ queries. This refutes the unitary analog of the Hoory--Magen--Myers--Rackoff conjecture (ICALP '04) for permutations. Our second result is a stronger separation between unitary designs and pseudorandom unitaries at polynomially bounded moments; our counterexample, however, requires highly structured ensembles, in contrast with the simple local walks from before. This suggests caution when using unitary designs to model information scrambling in black-hole physics, as even maximally scrambled systems can exhibit structure which is accessible to efficient experiments. Motivated by these findings, we then propose new conjectures for how pseudorandomness can plausibly emerge within simple quantum processes, such as random quantum circuits.

AI systems increasingly produce outputs from confidential data, such as a fitness-for-duty assessment from medical records or the predicted properties of a drug candidate from its secret structure. It is important to verify that such outputs are correct without revealing the underlying data. A recent line of work studies verification of AI outputs via interactive proofs and debate for oracle-aided computation, where correctness may depend on an oracle such as human judgment, a physical experiment, or the web. These works focus on verification by a verifier that runs much faster than the computation. However, such efficient verification is impossible for general oracle-aided computation, and these works therefore rely on additional assumptions. We focus instead on privacy: allowing the verifier to run in time polynomial in the computation, we ask whether interactive arguments for oracle-aided computation can be zero knowledge, so that the verifier learns nothing about the confidential data beyond the correctness of the output. We prove that, in general, they cannot. In the random oracle model, there are no zero-knowledge proofs for all oracle-aided computations, even if both the prover and the verifier are allowed to run much longer than the computation itself. The impossibility extends to debate, a canonical model for scalable oversight. On the positive side, we show that if the oracle attaches a cryptographic signature to each of its answers, then every oracle-aided computation can be verified in zero knowledge with an efficient prover and verifier, assuming only collision-resistant hash functions. Beyond privacy, this also gives an alternative approach to scalable oversight that relies neither on an honest opponent, as in debate, nor on the robustness of the computation, as in prior single-prover protocols.

Fully anonymous secret-sharing schemes ensure two properties at once: for any fixed secret, the combined shares of every unauthorized set of participants are uniformly random, and every authorized set can reconstruct the secret exactly using only the share values, without needing to know which participant holds which share or in what order the shares appear. It was previously open whether such schemes exist for nontrivial exact-threshold parameters 2 < t < n. For the smallest previously open threshold, t= 3, we give, for every n≥4, an explicit fully anonymous scheme for one-bit secrets, with 2⌈log n⌉-bit shares and a perfect reconstruction algorithm running in poly(log n) time. The next result, found by ChatGPT, shows that for every 1 ≤t ≤n there exists a fully anonymous perfect (t,n) threshold secret-sharing scheme for one-bit secrets, in which each share has length O(tlog n) bits. The proof is purely existential and does not provide an efficient construction. Moreover, ChatGPT identified a simple construction of a fully anonymous perfect scheme for every access structure A; if A contains ℓ authorized sets, then each share consists of ℓ2 bits. The authors subsequently verified and streamlined the proofs on their own and take full responsibility for their correctness.

An important open question in quantum cryptography is the construction of publicly-verifiable NIZKs for QMA. Classically, one can construct NIZKs for NP in the random oracle model (and sometimes in the standard model) by compiling an honest-verifier ZK (HVZK) $\Sigma$-protocol for NP using the Fiat–Shamir transformation. Broadbent and Grilo introduced a quantum analog of a $\Sigma$-protocol (which they call a $\Xi$-protocol) in which the prover's first message is quantum, and show that HVZK $\Xi$-protocols exist for QMA. However, it is not clear how to compile such protocols into NIZKs in the (Q)ROM, because the Fiat–Shamir transformation seems to be incompatible with quantum messages. In this work we give formal evidence that this is indeed the case: we show that if generic "Fiat–Shamir-like" compilers for quantum protocols exist in the QROM (with small completeness and soundness error) then QMA = BQP.

In this article, we derive the weight distribution of linear codes stemming from a subclass of (vectorial) $p$-ary plateaued functions (for a prime $p$), which includes all the explicitly known examples of weakly and non-weakly regular plateaued functions. This construction of linear codes is referred in the literature as the first generic construction. First, we partition the class of $p$-ary plateaued functions into three classes $\mathscr{C}_1, \mathscr{C}_2,$ and $\mathscr{C}_3$, according to the behavior of their dual function $f^*$. Using these classes, we refine the results presented in a series of articles \cite{Mesnager2017, MesOzSi,Pelen2020, RodPasZhaWei, WeiWangFu}. Namely, we derive the full weight distributions of codes stemming from all $s$-plateaued functions for $n+s$ odd (parametrized by the weight of the dual $wt(f^*)$), whereas for $n+s$ even, the weight distributions are derived from the class of $s$-plateaued functions in $\mathscr{C}_1$ parametrized using two parameters (including $wt(f^*)$ and a related parameter $Z_0$). Additionally, we provide more results on the different weight distributions of codes stemming from functions in subclasses of the three different classes. The exact derivation of such distributions is achieved by using some well-known equations over finite fields to count certain dual preimages. In order to improve the dimension of these codes, we then study the vectorial case, thus providing the weight distributions of a few codes associated to known vectorial plateaued functions and obtaining codes with parameters $[p^n-1,2n, p^n-p^{n-1} - {p}^{(n+s-2)/2}(p-1)]$. For the first time, we provide the full weight distributions of codes from (a subclass of) vectorial $p$-ary plateaued functions. This class includes all known explicit examples in the literature. The obtained codes are minimal and self-orthogonal virtually in all cases. Notably, we show that this is the best one can achieve---there are no $q$-ary self-dual minimal codes for any prime power $q$, except for the ternary tetracode and the binary repetition code.

We give a Monte Carlo algorithm for exact Euclidean SVP on Haar-random lattices with arithmetic time $(3/2)^{n/2+o(n)}$ and space $(4/3)^{n/2+o(n)}$, up to polynomial factors in the logarithmic condition number of the input basis. The leading exponents match those of heuristic lattice sieving. For a set of lattices of Haar measure $1-o(1)$, the algorithm succeeds with probability $1-o(1)$ on every input basis. Our algorithm regenerates each sieve list by running a Markov chain on the nonzero lattice points in a smaller ball. The parent list supplies signed increments. Each step reports all admissible proposals and assigns each the same probability, with the remaining probability assigned to staying put. The resulting chain is symmetric and has uniform stationary distribution. Trajectories using independent transition randomness produce endpoints jointly close to independent uniform samples once the chain mixes. Matrix Chernoff bounds transfer a Laplacian gap from the full angular graph to the graph defined by the parent list. The main proof task is to establish the required graph estimates on Haar-random lattices. We do so by adapting Rogers's moment method to centered trace moments and lattice-point counts. Spherical filtering reports the complete proposal sets and the final short differences within the claimed bounds.

Targeted hitting-set generators (HSGs) are primitives that have recently attracted attention in the study of pseudorandomness and derandomization. Recent works have shown that sufficiently strong targeted HSGs can be used to soundly instantiate the Fiat--Shamir transformation, yielding non-interactive protocols against uniform PPT adversaries in the plain model (i.e., without any setup phase for selecting a cryptographic hash function). In particular, Chen et al. (STOC 2025) combined this paradigm with the MPC-in-the-head technique to construct a non-interactive witness-indistinguishable argument for NP from a non-interactive commitment scheme and a targeted HSG. Inspired by these results, we explore other cryptographic applications of this paradigm. Our main result is a black-box construction of a non-interactive witness-indistinguishable commit-and-prove scheme against uniform PPT adversaries in the plain model. Following Chen et al., we obtain our construction by combining the MPC-in-the-head technique with the targeted-HSG-based Fiat--Shamir paradigm. The construction relies on an injective one-way function with efficiently recognizable range and a sufficiently strong targeted HSG. The latter is the same targeted HSG used by Chen et al. and can be instantiated under a very strong but plausible complexity-theoretic assumption.

We study two central problems in threshold cryptography from lattices: (1) threshold encryption with silent setup for general thresholds $t \geq 2$, where no post-quantum constructions were previously known, and (2) threshold fully homomorphic encryption (TFHE) with sublinear parameters, an open problem since the work of [Boneh et al.; CRYPTO'18]. We introduce $\textit{$(\alpha,\beta)$-Scaled Linear Secret Sharing Schemes}$ (LSSS), a relaxation of standard LSSS in which each authorized set $S$ reconstructs a scaled version of the secret, $\gamma_S \cdot k$, where both the reconstruction coefficients and the set-dependent scaling factor $\gamma_S$ are bounded over the integers. Unlike prior approaches based on bit decomposition, this preserves the uniform distribution of unauthorized shares. Building on this, we obtain: 1. $\textbf{Silent Threshold and Distributed monotone-policy encryption.}$ We provide the first post-quantum construction supporting: (i) threshold policies with ciphertexts growing as $\tau^{16} \cdot \mathsf{poly}(\lambda, \log N)$, where $\tau = \min(t^2,N{-}t)$, and (ii) DNF formulas with fully compact parameters. Our constructions are proven secure under the decomposed LWE assumption in the random oracle model. If we additionally rely on a common reference string, then the ciphertext size for our threshold policy scheme can be reduced to $\tau^4 \cdot \mathsf{poly}(\lambda, \log N)$ under the Succinct LWE assumption. 2. $\textbf{Decentralized TFHE with silent setup.}$ We provide the first $\textit{decentralized}$ TFHE, for threshold policies and DNFs, from the decomposed LWE assumption. Our construction supports homomorphic evaluation of arbitrary circuits, one-round distributed decryption, and silent setup. This was left as an open problem by [Boneh et al.; CRYPTO'18] and, prior to this work, we did not have any non-trivial construction for decentralized TFHE from any assumption. 3. $\textbf{Sublinear centralized TFHE from LWE.}$ We also extend our techniques to $\textit{centralized}$ TFHE. We provide a TFHE scheme under the standard LWE assumption, where all parameters are simultaneously sublinear in $N$ for any threshold $t$ as long as $\min(t^2,N{-}t)=o(N^{1/6})$. This breaks the $\omega(N)$ barrier that has persisted in the TFHE literature since 2018.

We study bandwidth fee mechanisms (BFMs) for pricing threshold certified transaction dissemination before consensus. BFMs are analogous to transaction fee mechanisms (TFMs) introduced by Roughgarden (2021), except that they price blockchain communication rather than computation. Separately pricing this bandwidth is especially relevant when transaction dissemination is separated from consensus and execution. We model BFMs as a two-sided procurement auction between users who submit transactions and validators who receive and forward them. Any validator may be assigned as the source of a transaction and forward it to a threshold of attesters. The model accounts for the source validator's receipt of the user submitted transaction and the subsequent transfers between validators. It abstracts away unrestricted multi-hop gossip and network topology. In this work, we focus on settings where transactions must be certified/attested by a threshold of network nodes before consensus, and we develop the following results. - We characterize the limits of myopic incentive compatibility for BFMs: No non-trivial transcript-based BFM can prevent profitable collusion between two validators, and no non-trivial BFM can simultaneously satisfy incentive compatibility for individual user, individual validator, and coalition of one validator and one user. - In contrast, once we restrict attention to unilateral deviations, we present a greedy-route posted-price mechanism that is incentive compatible for every individual user and validator. \item We study how the bandwidth price should evolve across blocks. Assuming validators execute honestly, we propose an EIP-1559-style price-update rule and show that its fluid approximation has a unique fixed point, which is locally stable for small enough step sizes. In large markets, prices that start near this point stay near it with high probability over any fixed time horizon. \end{itemize}

Hash-based signatures offer a conservative foundation for post-quantum authentication, but their large signatures impose substantial communication and storage costs. For security parameter $\lambda$, discrete-logarithm-based signatures have length $O(\lambda)$, while known hash-based constructions have quadratic signature length, up to logarithmic factors, even for one-time signing. Is this gap inherent? We prove what are, to the best of our knowledge, the first lower bounds on the length of signature schemes in the (pure) random oracle model. Our bounds apply to schemes with non-adaptive verifiers and a natural security property called salted soundness: a scheme with such security is unforgeable even against an adversary that is granted a limited ability to resample and restore oracle answers. This class essentially captures all known hash-based constructions (possibly after low-cost modifications). We show that the combined public-key and signature length of a one-time signature scheme must be $\Omega(\lambda^2/\log\lambda)$. For many-time signatures, we prove the stronger conclusion that the signature length alone must satisfy the same lower bound, irrespective of the public-key length. More precisely, if the relevant length is $o(\lambda^2/\log\lambda)$, then an adversary making $2^{o(\lambda)}$ random-oracle queries breaks salted soundness with inverse-polynomial probability. Our proof uses the high-entropy hitting lemma of Haitner, Nukrai, and Yogev (Crypto 22) to transform a short signature scheme into a scheme whose verifier makes only a few queries. We then apply the Barak and Mahmoody-Ghidary (FOCS 07) attack on one-time signatures with a low-query verifier. Balancing these two steps yields the near-quadratic lower bounds.

We investigate an algebraic approach to the Syndrome Decoding Problem, based on a reformulation of the Hamming weight constraint and its integration with the Information Set Decoding paradigm. We begin with a systematic analysis of the Hamming variety, deriving its defining equations in terms of elementary symmetric functions. Since these equations may have high degree, we exploit convolution identities for elementary symmetric functions, together with factorizations based on Lucas' identity, to derive an equivalent formulation with auxiliary variables and equations of bounded degree. Building on this modeling, we generalize the ISD paradigm through an ISD-like decoding strategy, implemented by the GBDecode algorithm, in which only a subset of an information set is fixed. This approach reduces the size of the combinatorial search space at the cost of solving the associated multivariate nonlinear systems. To handle this algebraic component, we employ the MultiSolve algorithm, which replaces a single Grobner basis computation with a collection of computations on simpler systems, obtained by exhaustively assigning a varying number of indeterminates over the finite field. This provides a tunable balance between combinatorial search and algebraic solving. We evaluate the resulting approach experimentally on instances of the Syndrome Decoding Problem for random binary linear codes, using parameters corresponding to the NIST Security Category 1 parameter set of the Classic McEliece cryptosystem. The experiments assess the feasibility of this combinatorial-algebraic approach and provide insights into the practical behavior of Grobner basis techniques within an ISD-like decoding framework.

Efficient evaluation of multivariate polynomials over finite spaces is an important problem in algebraic cryptanalysis, particularly in exhaustive-search attacks on multivariate public-key cryptosystems. Existing fast exhaustive-search techniques, including those of Bouillaguet et al. (CHES 2010), Dinur (EUROCRYPT 2021), and Furue and Takagi (PQCrypto 2023), mainly target the complete space $\mathbb F_q^n$, whereas many cryptanalytic applications require evaluation only over structured subsets. Recently, Liu et al. proposed a memory-efficient algorithm for evaluating degree-$d$ polynomials over product Hamming balls \[ B(\textbf{\textit{n}},\textbf{\textit{w}})=B(n_s,w_s)\times\cdots\times B(n_1,w_1)\subseteq\mathbb F_2^n, \] where $\sum_{i=1}^{s}n_i=n$ and $B(n_i,w_i) \subseteq \mathbb F_2^{n_i} $ denotes the set of vectors of length $n_i$ and having at most $w_i$ nonzero coordinates. In this work, we extend this structured-subset paradigm by developing a unified derivative-based framework, comprising initialization and evaluation phases, first over prime fields $\mathbb F_q$ and subsequently over arbitrary finite fields $\mathbb F_{q^\rho}$ through basis expansion. We derive two initialization methods with time complexities $\mathcal O(nrM)$ and $\mathcal O(rM^2)$, where $M\leq\min\{\binom{n+d}{d},q^n\}$ and $r=\min\{d,q-1\}$. After initialization, evaluation over $B(\textbf{\textit{n}},\textbf{\textit{w}})$ requires $\mathcal O(d|B(\textbf{\textit{n}},\textbf{\textit{w}})|)$ arithmetic operations, apart from a linear setup cost. The corresponding overall memory bounds are $\mathcal O((M+r^2)\log q+n\log(nq))$ and $\mathcal O(((d+1)M+r^2)\log q+n\log(nq))$, respectively, and are independent of the number of evaluated points.

Non-local search-to-decision asks whether the difficulty of two non-communicating (non-local) parties both predicting $x$ given a bipartite state (that possibly depends on $x$) implies the difficulty of non-local parties both predicting the inner product $\langle r,x\rangle$, for a uniformly random $r$. This problem and its variants have been extensively studied and are motivated by applications to unclonable cryptographic primitives such as unclonable encryption and copy-protection. We study the identical-challenge setting, in which both parties receive the same uniformly random vector $r$, in contrast to the independently sampled challenges considered in prior works. We demonstrate positive results for the cases when $x$ and $r$ are vectors over $\mathbb{F}_2$ and over large finite fields. As a consequence, we obtain a conceptually different proof of indistinguishability-secure unclonable encryption.

We describe a Las Vegas algorithm for the principal ideal problem in matrix rings $M_g(O)$ for $g \geq 2$, over maximal orders $O$ in the rational quaternion algebra $B_{p, \infty}$ ramified at $\infty$ and a prime number $p$. Under plausible heuristic assumptions, the method has expected polynomial runtime. An implementation in SageMath shows that it runs very efficiently in practice, with compact output. Our main auxiliary result is a method for finding endomorphisms of superspecial abelian varieties (i.e., powers of supersingular elliptic curves) with a prescribed kernel.

In a multi-instance problem, the adversary is given $n$ independent problem instances and succeeds if it solves at least $k$ of them. We study the generic hardness of a broad class of multi-instance problems over prime-order groups, including multi-instance Computational Diffie-Hellman (CDH), Square Diffie-Hellman (SDH), Inverse Diffie-Hellman (IDH), and Linear Kernel Diffie-Hellman (LKDH). As expected, we show that, in generic groups, solving multi-instance CDH and SDH is as hard as solving $k$ independent discrete logarithm instances. In contrast, although the single-instance versions of CDH and IDH are known to be equivalent, we establish generic upper and lower bounds showing that multi-instance IDH (and LKDH) can be significantly easier to solve than multi-instance CDH in certain parameter regimes. All problems, however, offer $1/2(\log(p)+\log(k))$ bits of security. Our lower-bound techniques extend Yun's information-theoretic hyperplane query model (EUROCRYPT 2015). At the core of our approach lies an inductive argument showing that, in order to establish a generic-group lower bound, it suffices to bound the adversary's "zero-hyperplane-query" advantage in the hyperplane query model. For the multi-instance problems considered in this work, we derive such bounds using techniques from algebraic geometry. More precisely, we analyze the Krull dimension of suitable algebraic varieties, either by explicitly computing Gröbner bases or by upper bounding the number of algebraically independent elements in the associated coordinate rings.

We correct two errors in Section~8 of the above-mentioned paper concerning the seed parameters proposed for BLS27 elliptic curves (embedding degree $k=27$) at the $256$-bit and $192$-bit security levels. In both instances, the disclosed seeds produce a composite $r(x)$, violating the primality condition essential for constructing pairing-friendly curves. Additionally, for the $192$-bit seed the characteristic $p(x)$ is also composite. We provide verified corrected seeds for each security level, obtained by exhaustive search, and confirm with SageMath that both $p(x)$ and $r(x)$ are prime in each case. All other results of the original paper remain valid.

Decentralised proof of personhood, cryptographically binding a digital identity to a unique living human without a trusted central authority, is a foundational problem in permissionless networks. We present a novel protocol, Secure-GYID (S-GYID), resilient to Identity Theft Attack (i.e., adversarial authorities substitute a victim's biometric fingerprint under a malicious public key) and Ghost Key Attack (i.e., colluding authorities fabricate a registration for a non-existent user). Our protocol closes both vulnerabilities by replacing raw biometric transmission with an encryption-based digital fingerprint derivation $F = E(pk_u, P_u)$ computed under a one-way, chosen-plaintext-secure, deterministic scheme, so that no authority can substitute or forge a binding pair without knowledge of the user's secret key. S-GYID further introduces a three-stratum generational authority hierarchy with bounded tenure and VRF-based session selection to limit long-term collusion structurally. We prove Identity Theft Resistance, Biometric Detectability, and Ghost Key Resistance under standard cryptographic assumptions, and provide a hypergeometric session-capture analysis that establishes concrete parameter design rules for both the key activation and authority promotion thresholds.

Non-uniform security allows an adversary to receive bounded advice about an oracle before attempting a fresh challenge. This captures the most realistic attacks and has already been studied extensively in prior work. In this work, we introduce an operator-norm approach for non-uniform security in the quantum random oracle and random permutation models. This new approach yields a unified reduction for both search success probability and distinguishing advantage. Previously, the reduction only worked with success probability even in the decision games, yielding a worse bound. Our framework enables tight bounds for Yao's box, both with and without salting, and improved bounds for pseudorandom generators. We also prove an optimal generic salting theorem for decision games. By defining a property of a game, which separates the contributions of the existing queries in the offline stage and subsequent online queries, we obtain stronger bounds for specific salted constructions. These include salted permutation inversion, tight up to logarithmic factors, and salted random-function inversion, tight up to logarithmic factors and the gap already present in classical function inversion.

Micali's construction of succinct non-interactive arguments (SNARGs) combines a probabilistically checkable proof (PCP), a vector commitment, and the Fiat--Shamir transformation. Its security is established in the random oracle model, but replacing the random oracle with an explicit hash function presents a fundamental challenge: Fiat--Shamir can fail for interactive arguments, and certain choices of the commitment scheme make Micali's construction unsound for every instantiation of the Fiat--Shamir hash. We show how to instantiate Micali's construction in the standard model assuming LWE and function vector commitments with \emph{function statistical binding} for $\Ppoly$, obtaining a non-adaptively sound SNARG for $\NP$. Our construction combines such a commitment with an LWE-based correlation-intractaxble hash and a PCP satisfying a new property, \emph{shadow soundness}. A PCP shadow is a short digest that preserves the information needed to determine the verifier's decision. By statistically binding the commitment to this shadow, we obtain the sparse relation needed to prove Fiat--Shamir soundness. We construct shadow PCPs for $\NP$ whose shadow algorithms lie in $\NC$, and we give a feasibility instantiation of the commitment scheme from strong assumptions. Our results thus identify a concrete cryptographic target for instantiating Micali's SNARG under weaker assumptions, and show that the framework does not admit an attack that succeeds for every choice of its components.

We study local rewriting after an assumed erasure step in an ideal oblivious-transfer protocol. Bob transforms his retained record while Alice's actual record remains fixed. Exact rewriting between shared-source and independent-source records is possible in both directions precisely when the retained records of the shared source are independent. For balanced deterministic maps retaining $k$ and $\ell$ bits from an $n$-bit source, the optimal error over the maps is $\max\{0,1-2^{n-k-\ell}\}$. For fixed full-row-rank linear maps, it is $1-2^{-d}$, where $d$ is their row-space intersection dimension. A nonlinear example shows that an optimal approximate rewrite may change Bob's marginal distribution.

In this work, we establish the first separation between computation with bounded and unbounded space, for problems with short outputs (i.e., working memory can be exponentially larger than output size), both in the classical and the quantum setting. Towards that, we introduce a problem called nested collision finding, and show that optimal query complexity can not be achieved without exponential memory. Our result is based on a novel ``two-oracle recording'' technique, where one oracle ``records'' the computation's long outputs under the other oracle, effectively reducing the time-space trade-off for short-output problems to that of long-output problems. We believe this technique will be of independent interest for establishing time-space tradeoffs in other short-output settings.

The M operation was introduced by Yura as an alternative to the max operation appearing in the box-ball system (BBS) to construct a BBS over finite fields. The Me operation is a version of the M operation for an elliptic curve $E$ over a finite field ${\mathbb F}_p$. As with the M operation, the Me operation satisfies the idempotent law and does not satisfy the associative law. Nevertheless, for $P,Z \in E({\mathbb F}_p)$ and $n \in {\mathbb N}$, the 1st Me-scalar multiplication $P_{n,Z}^{\,I}$ with auxiliary element $Z$ can be defined. Moreover, for $P,Z \in E({\mathbb F}_p)$ and $n \in {\mathbb Q}_+$, the 2nd Me-scalar multiplication $P_{n,Z}^{II}$ with auxiliary element $Z$ can be defined. This paper shows the following properties that may be useful to construct cryptographic protocols: $(P_{n_0,Z}^{\,I})_{n_1,Z}^{\,I}=(P_{n_1,Z}^{\,I})_{n_0,Z}^{\,I}$, $(P_{n_0,Z}^{II})_{n_1,Z}^{II}=(P_{n_1,Z}^{II})_{n_0,Z}^{II}=P_{n_0n_1,Z}^{II}$; the 1st MeDLP and the 2nd MeDLP, which are Me versions of the ECDLP, are difficult to solve on classical computers under certain conditions; the 1st MeCDH and the 2nd MeCDH, which are Me versions of the ECCDH, are NOT difficult to solve; and the sequence $\{ P_{n,Z}^{II}:n=1,2,3,\ldots \}$ is nonperiodic unless it is constant.

On a blockchain, users compete for scarce block space in an auction run by the miner to get their transactions confirmed in the block. This auction is called transaction fee mechanism (TFM). Recent work [Rou21, CS23, SCW23] has been focused on incentive compatibility (IC), requiring that honest behavior maximizes the payoff for each type of strategic player: users, the miner, or miner–user coalitions. In this work, we introduce rational-harm proofness (RHP), which rules out deviations that harm honest parties without also reducing the deviator’s own utility relative to the honest baseline. RHP closes a gap left by IC: IC does not forbid utility neutral yet externally harmful deviations. For example, in a second-price auction, the second-highest bidder can increase the winner’s payment without affecting their own payoff. Such deviation is eliminated by RHP. We characterize TFMs satisfying RHP alongside incentive compatibility for users (UIC) and miners (MIC). For finite block size, we develop a complete characterization in two models: - In the plain model---where a single miner unilaterally implements the auction---we prove a tetrilemma (3-out-of-4 impossibility): among the four desired properties {positive miner revenue, UIC, MIC, RHP against miner–user coalitions}, no mechanism achieves all four simultaneously. This trade-off is tight: any three are jointly achievable in the plain model. - In the MPC-assisted model---where a committee of miners jointly implement the auction via multi-party computation (MPC)---we construct a randomized TFM with a positive miner revenue that achieves UIC, MIC, and RHP against all three types of strategic players. We further show that randomness is necessary: any deterministic TFM satisfying UIC and RHP in this model must confirm no transactions when the number of users exceeds the block size. Finally, we show that IC and RHP are incomparable: for each strategic role, there are mechanisms satisfying one but not the other in both models. Our results broaden the design objectives for TFMs: beyond incentive compatibility, mechanisms should also preclude costless harm to honest participants.

We study interactive proofs of proximity (IPP) for model evaluation: a resource-limited verifier interacts with an untrusted prover, typically the model owner, to certify statistical properties of a model under an unknown input distribution. Our formulation is shaped by the constraints of practical evaluation: it separates sampling the input distribution from querying the model and evaluating its output, allowing their costs and access patterns to be treated independently; it distinguishes real audit data (black-box sampling) from generated data (chosen-randomness, or gray-box, access to the sampler); and it allows the prover and the verifier to score outputs with different evaluators, as happens when scores come from human or judge models. We focus on doubly-sublinear $\mathsf{IPP}$s, in which both the verifier and the designated honest prover use sublinear resources, and on (weighted) Hamming weight properties, which capture the expectation of a Boolean evaluation rule under an unknown distribution and, consequently, a broad range of model-evaluation statistics. As a first step, we give a tolerant $\mathsf{dsIPP}$ for ordinary Hamming weight. For completeness and soundness radii $\varepsilon_c <\varepsilon_f$ and gap $g=\varepsilon_f-\varepsilon_c$, its logarithmic-round instantiation uses $\tilde{O}(1/g)$ verifier queries and $O(1/g^2)$ honest-prover queries, improving the cubic dependence of Amir, Goldreich, and Rothblum [ITCS 2025]. We prove matching query lower bounds up to polylogarithmic factors. We then study distribution-weighted Hamming weight under several access models. Under black-box sampling, the verifier uses $\Theta(1/g^2)$ samples but only $\tilde{O}(1/g)$ evaluations, and we show that the quadratic sample complexity is necessary in the interior regime. With chosen-randomness access to a sampler, the problem reduces to ordinary Hamming weight, giving $\tilde{O}(1/g)$ verifier calls and evaluations. When the two parties' evaluators may disagree arbitrarily on a $\rho$-fraction of the distribution and by up to $\gamma$ elsewhere, we give protocols that remain doubly sublinear whenever $g$ exceeds twice the mean mismatch $\kappa = \rho + (1-\rho)\gamma$. Finally, we show how our technical results can improve the efficiency of model evaluation in natural motivating scenarios by shifting the bulk of the evaluation burden to the model owner while letting any number of auditors verify claims cheaply; we apply them to auditing criteria including accuracy, group fairness, calibration, harmlessness, usefulness, and average-case robustness.

The communication complexity of computing a function in the two party setting can be much smaller than requiring one of the parties to send its input. We revisit how this communication complexity must change if the function must be computed securely. Hubáček and Wichs show that any protocol for computing a function securely must communicate at least as many bits as the length of the function's output. However, all positive results in this direction require much more communication than optimal. In particular, the state of the art for general protocols requires a $\textit{multiplicative}$ overhead polynomial in the security parameter, achieving only ''rate 0'' asymptotically. We show that, assuming the existence of input-succinct indistinguishability obfuscation for Turing machines, it is possible to achieve constant rate for this task. This compiler works even when the original protocol communicates single bits in each round, which is the main obstacle in prior works, and necessitates the use of obfuscation. The compiler can be based on standard non-succinct indistinguishability obfuscation for circuits (instead of Turing machines) in the common random string or random oracle models.

Succinct arguments are central cryptographic objects, underlying various applications such as blockchains and image authentication. Almost all succinct arguments used in practice follow the commit-and-open paradigm introduced by Kilian (STOC 1992): commit to a probabilistic proof, then open the few locations the verifier queries. Decades of work have generalized and optimized this paradigm, yet its exact provable security in the standard model remains unclear. Existing analyses proceed by rewinding, and they leave gaps: strict-time analyses lose an inverse-polynomial factor, while expected-time analyses are sharper but apply only to special cases of this paradigm. We resolve both gaps. On the negative side, we show that the strict-time loss is inherent: no strict polynomial-time reduction relying on a black-box extractor can achieve negligible knowledge error (unless the underlying language is easy). On the positive side, we give a new expected-time analysis, achieving negligible soundness and knowledge errors via an expected polynomial-time reduction against expected polynomial-time adversaries, at the full generality of the paradigm, capturing multi-round and functional variants such as polynomial and linear IOPs compiled with the corresponding commitments. This is the first standard-model analysis to reach this regime for succinct arguments deployed in practice.

We record the following bound: almost all Boolean functions $f : \{0,1\}^n \times \{0,1\}^n \to \{0,1\}$ require $2n - 2\log n - O(1)$ bits of communication for perfect two-party conditional disclosure of secrets with a one-bit secret. This only gives a factor 2 improvement over the previous best bound due to Applebaum, Holenstein, Mishra and Shayevitz [EUROCRYPT 2018], but at least (nearly) matches the input length. The proof is a straightforward compression argument that uses the birthday bound to give a succinct representation of transcript collisions (the latter being a technique from Feige, Kilian and Naor [STOC 1994], refined in Applebaum et al.). Viewing transcript-collision testing as an elementary case of distribution testing extends the argument to imperfect correctness and privacy. We do not currently know how to extend the argument to an explicit hard predicate.

We discover two laws governing public-key key exchange and public-key encryption. The first states that a non-interactive key-exchange scheme is secure only if it is kleptographically insecure. The second states that a public-key encryption scheme is secure only if it is kleptographically insecure. They give two impossibility results: no kleptographically secure non-interactive key exchange with pseudorandom shared keys exists, and no kleptographically secure public-key encryption with pseudorandom ciphertexts exists. More precisely, no non-interactive key-exchange scheme can simultaneously establish pseudorandom shared keys and support black-box execution in which the user observes only the public keys and the final shared keys output by the black box, and no public-key encryption scheme can simultaneously have pseudorandom ciphertexts and support black-box execution in which the user observes only the public keys and plaintexts input to the black box and the ciphertexts output by it. Our argument turns the very shield of a primitive into a spear against itself, showing that the security guarantee of the primitive is precisely what enables a kleptographic attack. We instantiate the laws with two post-quantum schemes: CSIDH and Regev encryption.

A secret sharing scheme is a cryptographic primitive that allows a dealer to share a secret among a set of parties, so that only authorized subsets of them can recover it. The access structure of the scheme is the family of authorized subsets. In a weighted threshold access structure, each party is assigned a weight according to its importance, and the authorized subsets are those in which the sum of their weights is at least the threshold value. For these access structures, the share size of the best known secret sharing schemes is either linear on the weights or quasipolynomial on the number of parties, which leads to long shares, in general. In certain settings, a way to circumvent this efficiency problem is to approximate the access structure by another one that admits more efficient schemes. This work is dedicated to the open problem posed by this strategy: Finding secret sharing schemes with a good tradeoff between the efficiency and the accuracy of the approximation. We present a method to approximate weighted threshold access structures by others that admit schemes with small shares. This method is based on the techniques for the approximation of the Chow parameters developed by De et al. [Journal of the ACM, 2014]. Our method provides secret sharing schemes with share size $n^{1+o(1)}$, where $n$ is the number of parties, and whose access structure is close to the original one. Namely, in this approximation the condition of being authorized or not is preserved for almost all subsets of parties. In addition, we apply the recent results on computational secret sharing schemes by Applebaum et al. [STOC, 2023] to construct computational secret sharing schemes whose share size is polylogarithmic in the number of parties.

Marcus, Spielman, and Srivastava [MSS15] established the existence of Kadison--Singer partitions. We provide polynomial-time algorithms for the Kadison--Singer problem. For Hermitian matrices $A_1,\ldots,A_m\in\mathbb C^{n\times n}$ of rank at most one, we give two algorithms that find signs $\sigma\in\{\pm1\}^m$ satisfying $\|\sum_i \sigma_iA_i\|\le C\|\sum_i A_i^2\|^{1/2}$. The deterministic algorithm achieves $C=3.3443$ using $\widetilde O(mn^2+n^{4.75})$ arithmetic operations. The randomized algorithm achieves $C=4.8628$ using $\widetilde O(mn^2+n^{3.58})$ arithmetic operations in expectation. For vectors satisfying $\sum_i a_ia_i^*=I$ and $\|a_i\|^2\le\alpha$, the algorithms yield partitions $[m]=I_1\cup I_2$ satisfying $\|\sum_{i\in I_j}a_ia_i^*-I/2\|\le (C/2)\sqrt\alpha$ for $j=1,2$.

Hash-based signature schemes present an appealing proposition: they are broadly regarded as the most conservative in terms of assumptions, and their efficiency profiles suit many applications. However, little is known about their compatibility with threshold signing, which is common practice today in domains like digital asset security. Especially in the context of an impending migration to post-quantum cryptography, this gap in the literature leaves uncertain what hash-based standards would imply for applications that rely on threshold signing. In this work, we develop a new framework by which to analyze such hash-based schemes, and prove inherent barriers to designing an entire class of efficient (fully distributed) threshold signing protocols. Our framework is simple, and yet powerful. Our results encompass standard schemes such as XMSS and SLH-DSA. Our approach is to connect hash-based signatures to the literature on straight-line extraction in the random oracle model. We then apply and build upon techniques from the recent work of Doerner et al. (Crypto '24) to show that threshold signing protocols for hash based schemes must—beyond a certain number of signers—use the circuit representation of the hash function, i.e. it can not use the hash function as a black box. We then give a more fine-grained analysis for the specific case of the Winternitz signature scheme—a building block of both NIST standards—and show that it can not permit even two-party signing with blackbox use of the hash function.

We study the matrix signing problem for positive semidefinite matrices, assigning one sign to each original matrix regardless of its rank. This includes the higher-rank Kadison--Singer partition problem [KS59] when the matrices sum to the identity. For arbitrary positive semidefinite matrices $A_1,\ldots,A_m\in\mathbb C^{n\times n}$, we prove that there are signs $\sigma_i\in\{-1,1\}$ such that $\|\sum_i \sigma_i A_i\|\le 3.34963\|\sum_i \operatorname{tr}[A_i]A_i\|^{1/2}$. We give a deterministic algorithm achieving this bound in $\widetilde O(mn^2+n^{4.75})$ real arithmetic operations. Inspired by the Lee--Sidford barrier, we use a potential function built from Schatten norms to obtain a square-root logarithmic dependence on the rank. Under the additional assumptions $\sum_iA_i=I$, $\|A_i\|\le\alpha$, and $\operatorname{rank}(A_i)\le r$, we obtain a discrepancy of at most $\min\{1,3.48745\sqrt{\alpha\log(2r)}\}$. We also give a deterministic algorithm achieving a discrepancy of at most $\min\{1,4.171\sqrt{\alpha\log(2r)}\}$ in $\widetilde O(mn^2+n^{6.38})$ real arithmetic operations. This dependence on $\alpha$ and $r$ is optimal up to an absolute constant when $0<\alpha\le1/256$ and $r\ge256\alpha^{-6}$: even diagonal matrices can force every signing to have a discrepancy of at least $\min\{1,\sqrt{\alpha\log(2r)}\}$. For a zero-one incidence matrix with at most $d$ ones in each row and each column, our deterministic algorithm achieves a discrepancy of $O(\sqrt{d\log(d)})$, recovering Harvey's bound [Har15] by a different method. We give a deterministic construction of a single spanning tree that is simultaneously spectrally thin with respect to any given collection of $k\ge1$ positive edge weightings of the same graph, assuming small edge leverage in every weighting. The tree retains the original edge weights, and its thinness bound grows only logarithmically with $k$.

Recent work has introduced the Hamiltonian phase state (HPS) assumptions, which postulate that Hamiltonian phase states can be used to instantiate pseudorandom and one-way state generators. Additionally, it has been conjectured that these assumptions can be true, even if one-way functions do not exist. This is exciting, because if true, then the HPS assumptions provide a route to the instantiation of Microcrypt. In this work we falsify this conjecture, by proving that if the HPS assumptions are true, then one-way functions exist. While this removes the possibility of instantiating genuine Microcrypt cryptography with Hamiltonian phase states, it shows that the HPS assumptions provide novel inherently quantum assumptions for the construction of classical cryptography. Technically we achieve this via a method for the construction of one-way puzzles from one-way state generators and tailored "measure first, ask later" state certification protocols. This generalizes prior constructions of one-way puzzles from one-way state generators via classical shadows and allows us to relate properties of the one-way puzzle to properties of the state certification protocol used in the construction. Specifically, if the state certification protocol admits efficient classical post-processing then one obtains an efficiently verifiable one-way puzzle, and if the state certification protocol can be efficiently classically simulated in a certain sense, then one obtains a classical one-way puzzle, which implies one-way functions. The latter observation allows us to prove that the HPS assumptions imply one-way functions, by exploiting properties of state certification protocols for phase states. The former observation provides a new toolbox for the construction of efficiently verifiable one-way puzzles by exploiting tailored state certification protocols for pseudorandom and one-way state generators.

A Gaussian leftover hash lemma (LHL) states that, for a matrix $\mathbf{X}$ with discrete Gaussian columns and a sufficiently wide Gaussian vector $\mathbf{v}$, the product $\mathbf{X}\mathbf{v}$ is close to a discrete Gaussian. Over the integers this is a classical tool, and Albrecht-Felderhoff-Lai-Lapiha-Woo (EUROCRYPT'26) recently extended it to modules over a number field $K$ of degree $d$. In every version, the lemma rests on two facts about the kernel lattice of $\mathbf{X}$: that $\mathbf{X}$ is surjective, and that the smoothing parameter of the kernel is small. We prove both facts with a single analytic estimate. An exact identity expresses the Gaussian mass of the dual kernel, multiplied by the index of the image of $\mathbf{X}$, as an integral of one-dimensional periodic Gaussian sums over a torus. Bounding this integral below two forces the index to be one, which is surjectivity, and bounds the smoothing parameter at the same time. No separate surjectivity argument and no GRH are needed. For smoothing error $2^{-\lambda}$ the smoothing parameter is $O_K(\sqrt\lambda)$ with explicit constants, once $\mathbf{X}$ has $m\gtrsim dr\ln(srm)$ columns, and a deterministic lower bound shows that this order is optimal. The width $s$ of the matrix enters only through the number of columns. Over power-of-two cyclotomic fields the theorem even applies to matrices whose integer coefficients follow a discrete Gaussian of width one. In the SIS-to-$k$-SIS reduction of Albrecht et al. (EUROCRYPT'26), the new bound lowers the hint width from $d^{39/2}\lambda^{9/2}$ to $d^{3/2}\lambda^{3/2}$ and the norm loss from $d^{41/2}\lambda^{5}$ to $d^{3/2}\lambda^{2}$, up to logarithmic factors. Additionally, we also formalized the main results of the paper in Lean.

Pseudorandom codes (PRCs) are error-correcting codes whose codewords are computationally indistinguishable from uniformly random strings to any efficient adversary. Most prior PRC work focuses on Hamming error channels; nevertheless, the few proposed constructions on edit channels are not optimized for a stochastic channel with both Hamming and synchronization errors. We study PRC over a stochastic memoryless Binary Substitution-Insertion-Deletion (BSID) channel and its generalized $q$-ary version. At each current input symbol, the channel inserts a uniformly random symbol without advancing with probability $P_i$, deletes and advances with probability $P_d$, or transmits and advances otherwise; a transmitted symbol is then replaced uniformly by another alphabet symbol with probability $P_s$. We first prove that the majority based PRC construction of Christ and Gunn remains robust over the BSID channel whenever $1-P_i-P_d>0$ and $P_s<1/2$, by proving its majority decoding after the BSID channel recovers more than half of the original coordinates by a constant margin with overwhelming probability. Then we propose a unique-decodable public-key multi-bit PRC on a constant alphabet constructed by letting the Christ--Gunn majority component protect control information and the Haeupler--Shahrasbi synchronization/list-recovery construction encodes the high-rate payload. For every sufficiently large admissible constant alphabet q depending on the channel parameters, the PRC is robust against a q-ary SID channel bounded by $P_i+P_d<1$, $P_s<$1, and its rate approaches the genie-aided capacity upper bound of the channel when q approaches infinity.

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.

A pseudorandom code (PRC) is a cryptographic primitive combining pseudorandom encryption and error-correcting codes (Christ and Gunn, CRYPTO 2024). That is, any polynomial number of codewords are pseudorandom, and decryption tolerates a constant rate of bit-flips. Although this might seem like a natural combination of standard properties, it is a fundamentally new object: PRCs are black-box separated from many primitives, including one-way functions, public-key encryption, and even virtual black-box obfuscation (Döttling et al., Garg et al., TCC 2025). Pseudorandom codes were introduced to build watermarks for AI-generated content. In particular, they imply watermarks that preserve the model's quality in a strong sense and withstand modification of the content. This relationship makes pseudorandom codes an inviting area for researchers: improvements to this simple theoretical object yield better watermarks. Beyond watermarks, PRCs have been used to construct error-correcting codes against computationally bounded channels (Lu et al., CRYPTO 2026), and techniques underlying them have led to new public-key encryption schemes (Döttling et al., CRYPTO 2026, Dyseryn et al. ASIACRYPT 2026). This survey aims to equip the interested researcher with tools to make progress in the area. We detail the current landscape of definitions, techniques, and applications. A main contribution is introducing new tricks and assembling existing tricks to generically strengthen PRCs (e.g., from substitution-robustness to random-deletion-robustness). We also show natural weakenings of PRCs that can be constructed from OWFs or even unconditionally. We conclude with a number of concrete open questions.

A randomized encoding for a promise problem is a randomized reduction whose outcome distribution on input $x$ can be simulated within some distance $d$, called privacy, using only one bit of information about $x$: whether it is a YES or NO instance. The encoding is one-sided if this property holds only for YES instances. Our main contribution is showing that (classical and quantum) one-sided randomized encodings have privacy and correctness amplification: any problem with a randomized encoding with privacy $1-1/poly(n)$ and error $1/2-1/poly(n)$, also has an encoding with negligible privacy and error. We then use this result to obtain the following statements: - We show that NISZK, the class of problems that have a non-interactive (statistical) zero-knowledge proof, has strong zero-knowledge amplification, i.e., every problem with a non-interactive zero-knowledge proof with zero-knowledge error $1-1/poly(n)$, also has a non-interactive zero-knowledge proof with negligible zero-knowledge error. This solves a problem open since the work of Goldreich, Sahai, and Vadhan (CRYPTO '99). - The worst-case hardness of a problem that has a perfect (i.e., zero error) one-sided encoding implies one-way functions (OWFs). And if the encoding is quantum, it implies one-way state generators (OWSGs). We then conclude that by removing the error from one-sided randomized encodings, the worst-case hardness of the complexity class SZK becomes sufficient for the existence of OWFs. - Weak and imperfect indistinguishability obfuscation (iO) implies OWFs assuming that the Polynomial Hierarchy does not collapse to its third level. Here, weakness means that the computational distance between the obfuscated circuit and the original circuit is $1-1/poly(n)$, and imperfectness means that the error is $1/2-1/poly(n)$. To achieve this privacy and correctness amplification, we study randomized encodings through the lens of lossy reductions (Ball et al. ITCS 2020). In particular, we introduce an extended and flexible notion of lossy reductions, and show that it is equivalent to randomized encodings. This equivalence serves as the base of our main results and might be of independent interest.

Folding protocols cross public-randomness boundaries: input-dependent information must be fixed before a challenge is known, while the required output may depend on it. We ask how much state must be retained after accounting for information already available at the boundary. With unrestricted prechallenge preprocessing and linear postchallenge readout, a retained representation is feasible exactly when its coordinates span, modulo this available information, every output direction induced by the supported challenges. Thus the minimum retained width is the dimension of this residual output space. The width depends on both the admissible source domain and the actual challenge support. Coordinatewise multiplication of length-\(n^2\) vectors has width \(n^2\) on the full product domain but \(2n-1\) when both inputs lie in the dimension-\(n\) Reed–Solomon code evaluated at \(n^2\) distinct points. Below the exact-width threshold, for independent uniform inputs to a bilinear map, we characterize the optimal exact-reconstruction probability by a rank-weighted subspace optimization. Bilinear side information couples the missing directions through a common linear correction, so optimizing them independently can fail. Applying the framework to direct homogeneous quadratic folding on a full product domain, an algebraic separation condition on the challenge family forces width at least \(rk\), where \(r\) is the dimension of the span of mixed bilinear outputs. Scaled-Cauchy challenges attain this bound on any support of at least \(2k+1\) distinct non-pole values and yield an explicit matching \(rk\)-coordinate polynomial representation.

Middle-Product LWE (MP-LWE) can inherit hardness from Ring-LWE over many number fields. Peikert and Pepin developed a direct reduction using field traces. Njah Nchiwo and Pellet-Mary (NP26) proved polynomial loss for the route through Polynomial-LWE under an additional condition on the defining polynomial. Recently, Pellet-Mary and Xia (PX26) unified both routes and proved polynomial loss for defining polynomials with polynomially bounded coefficients under suitable modulus conditions. We analyze Peikert and Pepin's trace reduction for monic irreducible integer polynomials $f$ of degree $n\ge2$ with coefficients of absolute value at most a fixed $B\ge1$. First, when the prime modulus satisfies $q\nmid[\mathcal O_{\mathbb{Q}(\theta)}:\mathbb{Z}[\theta]]$, where $\theta$ is a root of $f$, we prove the existence of multipliers with primal loss $O_B(n\sqrt{\log n/\log\log n})$ and dual loss $O_B(n^2)$. The multipliers have polynomial-size descriptions and serve as advice. Second, whenever the polynomial class is nonempty, every $Q\ge21$ admits a prime $q\in[Q,2Q]$ for which the index condition holds for at least a $1-O_B(n\log n/Q)$ fraction of the polynomials. At the same prime, we prove the same lower bound when counting the distinct number fields defined by these polynomials. Both coverage bounds tend to one as $n\to\infty$ if $Q/(n\log n)\to\infty$. Third, we prove that the trace reduction can match the linear noise bounds achieved by NP26's reduction through Polynomial-LWE. For the same defining polynomial, Ring-LWE variant, and MP-LWE parameters, a suitable trace multiplier exists whose linear noise amplification is no larger than that achieved by NP26's multipliers.

We give a sharper bound on the error introduced by replacing a random permutation oracle with Carolan’s compressed permutation oracle. Building on Rosmanis’s representation-theoretic approach, we represent exact permutation states in the compressed oracle’s database space, allowing a direct comparison of the two query operations. For a uniform permutation on N points, this comparison bounds the soundness error by 4q/√N after q ≤ N/4 queries. As the main application, we obtain tight query complexity for constant success probability in sponge preimage and collision search by substituting this bound into Carolan’s search reductions. The same analysis improves bounds for the one-more problem and cycle finding, and gives tight query complexity for constant success probability in keyless Davies–Meyer collision search

Adaptive reprogramming is a central tool for proving security in the quantum random oracle model (QROM). Recently, it has been extended to the setting when an oracle-dependent advice is in presence. However, the existing result is restricted to classical advice, and addresses only a single reprogramming. Extending it to n reprogrammings through naive hybridization yields a loss that is linear in the number of reprogrammings. In this paper, we establish an adaptive reprogramming theorem that accommodates quantum advice, and has a tighter overall security loss that only scales in the cubic-root of n, with an attack that matches the number of queries required in order to reach constant advantage. Using our reprogramming theorem, we provide improved time-space tradeoff bounds for PRG security of random oracles, and an IND-CPA security proof of salted pseudo one-time pad, in the quantum advice setting. Along the way, we also identify and prove a folklore lemma about indistinguishability of two oracles, which may be of independent interest. As another application, we provide a generic security analysis of Fiat-Shamir and hash-and-sign signature schemes, in QROM with quantum advice. We do so via a two-step modular analysis, where in the first step we perform a generic UF-CMA to UF-NMA reduction using our reprogramming theorem, and in the second step we provide a characterization of when such a scheme satisfies UF-NMA security, which we then use to discuss security of several signature schemes in this model.

Covert communication can be achieved without anamorphic encryption.

Let $C_0$ be the least constant such that, for every finite family of vectors $u_1,\ldots,u_n\in\mathbb C^d$ and independent finitely supported real random variables $\xi_i$, there are values $\varepsilon_i\in\operatorname{supp}(\xi_i)$ satisfying $\|\sum_{i=1}^n(\varepsilon_i-\mathbb{E}[\xi_i])u_i u_i^*\| \leq C_0\|\sum_{i=1}^n\mathrm{Var}[\xi_i](u_i u_i^*)^2\|^{1/2},$ where $\|\cdot\|$ denotes the operator norm. This rank-one matrix discrepancy formulation generalizes the signing formulation of the Kadison--Singer problem [KS59], resolved by Marcus, Spielman, and Srivastava [MSS15b]. Let $C_1$ be the least constant such that, for every $\epsilon>0$ and every finite family in $\mathbb C^d$, in every dimension $d$, satisfying $\sum_{i=1}^n u_i u_i^*=I$ and $\max_{i\in[n]}\|u_i\|^2\leq\epsilon$, there are signs $\varepsilon_1,\ldots,\varepsilon_n\in\{-1,1\}$ such that $\|\sum_{i=1}^n\varepsilon_i u_i u_i^*\|\leq C_1\sqrt\epsilon.$ Taking the $\xi_i$ to be independent symmetric signs gives $C_1\leq C_0$, since $\|\sum_{i=1}^n(u_i u_i^*)^2\|\leq\epsilon$ under these hypotheses. The general formulation allows arbitrary finite real supports and does not require $\sum_{i=1}^n u_i u_i^*=I$. Kyng, Luh, and Song [KLS20] proved $C_0\leq4$. We prove $2\leq C_1\leq C_0\leq2.176$. This improves the bounds $\sqrt2\leq C_0\leq3$ of Xie, Xu, and Zhu [XXZ21]. We conjecture that the optimal constant is $C_0=2$.

Secure multiparty computation (MPC) enables mutually distrustful parties to compute on private digital inputs. We initiate the study of $\mathbf{spatiotemporal}$ $\mathbf{MPC}$, extending this paradigm to functionalities whose inputs additionally depend on physical facts such as the parties' locations, times, or trajectories. Such protocols must simultaneously hide spatiotemporal information and ensure its physical consistency: a malicious party should not be able to make the functionality operate on a spatiotemporal input inconsistent with its actual physical state. The main conceptual challenge is to formulate extraction of spatiotemporal information within the simulation-based security framework. We introduce $\mathbf{arguments}$ $\mathbf{of}$ $\mathbf{spatiotemporal}$ $\mathbf{knowledge}$, following the principle "I prove, therefore I am:" rather than defining physical presence directly through a mathematical relation, we define it operationally through the ability to complete a sound spatiotemporal verification protocol. Accordingly, an extractor recovers a spatiotemporal point from a successful prover and certifies its physical validity by using the extracted prover to succeed in an auxiliary spatiotemporal verification protocol. Building on this notion, we define universally composable (UC) security for spatiotemporal MPC, capturing privacy, physical consistency, and composability. We provide constructions achieving this new MPC notion. We first construct UC-secure commit-and-prove protocols for spatiotemporal knowledge: in the CRS model under LWE against quantum provers without pre-shared entanglement, and in the QROM against quantum provers with unbounded pre-shared entanglement. Using these protocols, we obtain general-purpose UC-secure spatiotemporal MPC from semi-honest post-quantum MPC. We also extend our framework to UC-secure spatiotemporal multiparty quantum computation over private quantum inputs and classical spatiotemporal information.

In this note we find large primes $p$ such that $\Phi_k(p)$ is $B$-smooth for the cyclotomic polynomials $\Phi_k$, with $k = 3,4$ and $6$, and a sufficiently small smoothness bound $B$. These primes hence provide the first instantiation of integer factoring challenges that, a priori would be difficult to factor but, are actually easy to factor with traditional algorithms not typically used in practice.

$1+1 \equiv 0$---while looking strange at first glance, this is certainly true in GF(2). In this paper we propose the two field-like structures \FlipInts\ and \FlipPolys\ as potential alternative building block for crypographic schemes---in particular in the post-quantum setting. Both structures have $2^d$ elements for some positive integer $d$ and are derived from the natural numbers $N$ in the first case and the univariate polynomial ring GF(2)$[t]$ in the second case. We call the generalization of these two structures FlipFields. In addition, we see examples how they can be used for post-quantum cryptography, in particular Unbalanced Oil and Vinegar, Learning with Errors and Saber. There is also a discussion of cryptographic primitives that are most likely not suitable for FlipFields or at least not easy to tweak. As the structures are very new, this paper also includes a list of OpenProblems.

Multiplicative zero-knowledge ($\mathsf{MZK}$) replaces the negligible statistical distance required by statistical zero-knowledge ($\mathsf{SZK}$) with symmetric $(\varepsilon,\delta)$ approximate max-divergence between real and simulated verifier views. Prior work established efficiency gains from this relaxation; we study its computational power. With negligible completeness, soundness, and additive simulation errors, \[ \mathsf{HVMZK}[\varepsilon]=\mathsf{MZK}[\varepsilon]=\mathsf{SZK} \qquad\text{for }\varepsilon(n)=O(\log n), \] where $n$ is the input length. Taking the union over polynomial leakage bounds gives \[ \mathsf{MZK}[\mathrm{poly}]=\mathsf{HVMZK}[\mathrm{poly}]=\mathsf{PSPACE}, \] even with zero additive simulation error. For every fixed $c>0$, a polynomially padded $\operatorname{TQBF}$ language remains $\mathsf{PSPACE}$-complete and belongs to $\mathsf{MZK}[O(n^c)]$. A linear-leakage protocol for $\operatorname{SAT}$ separates $\mathsf{MZK}$ from $\mathsf{SZK}$ unless the polynomial hierarchy collapses to its second level. Padding yields $\mathsf{NP}$-complete separators at every fixed positive polynomial exponent. Under a subexponential weakening of the nonuniform nondeterministic Strong Exponential Time Hypothesis, every polylogarithmic level $\mathsf{MZK}[O((\log n)^j)]$ with fixed $j\geq2$ strictly contains $\mathsf{SZK}$. The logarithmic threshold is tight relative to oracles: every polynomial-time computable, polynomially bounded superlogarithmic leakage budget admits an oracle separating classical $\mathsf{MZK}$ from quantum statistical zero-knowledge. Finally, fraction statistical knowledge complexity exactly characterizes one-sided real-to-simulator multiplicative simulation, with the sharp knowledge parameter and negligible statistical error.

Private information retrieval (PIR) inherently requires public-key cryptography. A recent line of work suggests that this barrier can be avoided in secret-key PIR, where the client first preprocesses an N-bit database and retains only a short secret key. This line of work has yielded communication O(N^\epsilon) for any constant \epsilon under the Learning Parity with Noise (LPN) assumption in a high-noise regime not known to imply public-key cryptography, and communication O(N^{1/2}) under one-way functions. Whether compression beyond N^{1/2} can be achieved without relying on structured assumptions such as LPN has remained open. We show that interaction enables polylogarithmic communication in the random oracle model. We construct a secret-key PIR protocol with O(log N ) rounds and polylogarithmic total communication. Alternatively, for any constant \epsilon, we obtain a constant-round protocol with communication O(N^\epsilon). We also obtain protocols with similar communication in the plain model under the weakest version of LPN, with maximal noise rate 1/2 − o(1). Our main idea, inspired by the free-XOR technique for circuit garbling, is to make secret-key preprocessing homomorphic under XOR, while relying on security against related-key attacks.

Succinct arguments are a fundamental cryptographic primitive for verifying computational claims with small communication. In the classical setting, succinct arguments for NP can be constructed from unstructured hardness alone (e.g., hash functions) by compiling probabilistically checkable proofs (PCPs) or interactive oracle proofs (IOPs) for NP via the commit-and-open paradigm. In contrast, known succinct arguments for QMA rely on ``structured'' cryptographic primitives, or on the quantum PCP conjecture. We construct the first succinct argument for QMA in the quantum random oracle model (QROM) without relying on additional cryptographic assumptions or unproven conjectures. This yields succinct arguments for QMA from unstructured hardness alone, showing that ideal hash functions not only suffice for succinct arguments for NP but also for QMA. Underlying our result is an efficiency-preserving transformation that compiles quantum interactive oracle proofs (QIOPs), a recently introduced interactive generalization of quantum PCPs, into quantum arguments for the same language, via a natural quantum commit-and-open paradigm. Our transformation applies to every QIOP with public-query soundness, a notion that we formalize to capture a natural requirement of the commit-and-open paradigm and is satisfied by a known QIOP for QMA. As a key ingredient in our transformation, we formalize and construct extractable vector commitments for quantum states with local openings in the QROM, which may be of independent interest.

We give deterministic exact recovery for almost all square four-tensors over every finite field. For every \(n \ge 2^{24}\) and prime power \(q \ge 2\), an explicit \(\mathrm{GL}_n(\mathbb{F}_q)^4\)-invariant family contains a \(1-O((\log n)^2/n)\) fraction of all \(q^{n^4}\) coefficient arrays, with an explicit failure bound uniform in \(q\). Membership and isomorphism decision and recovery against every target are deterministic in \(\operatorname{poly}(n,\log q)\) bit time, with four invertible factors over the original field. The source distribution is uniform without any conditioning on flattening ranks. The proof combines linked extension-field eigenmatrices, a submodule sieve under the joint law of a matrix and its inverse, and recovery from the kernels of singular original flattenings. Partial traces of matrix products provide a factorization-free algorithm in large characteristic. Complementary results give explicit positive source fractions in smaller dimensions, including a \(1/q+O(q^{-2})\) family with deterministic recovery. The algorithms invert the coefficient-uniform square-tensor group action with the stated success probabilities. A deterministic exhaustive fallback gives total correctness and a polynomial running-time bound with high probability; no polynomial expected running time is claimed.

Assuming the polynomial-time hardness of a variant of the short integer solution (SIS) problem, we show the existence of sequential and memory-hard functions. Such an assumption postulates the hardness of a problem against polynomial-time algorithms, regardless of their memory and depth. Yet, we show that this assumption implies that $\mathsf{P} \neq \mathsf{NC}$, that $\mathsf{P} \neq \mathsf{L}$, and that the $\mathsf{NC}$ hierarchy is proper, i.e., that $\mathsf{NC}^1 \subsetneq \mathsf{NC}^2\subsetneq \mathsf{NC}^3 \dots$ Our main technical tool is a new variant of homomorphic computation over lattice encodings, which does not impose a bound on the circuit depth and is not based on bootstrapping.