Papers for

cryptography system designers

Papers whose findings have a practical use for this group, as judged from the abstract. Open a paper to read what it means in practice.

Reed-Solomon codes can have unexpectedly large lists of close codewords

Combinatorial limitations of list-decoding Reed-Solomon codes

Abstract: For infinitely many rates $R \in (0,1)$, we show that full-length Reed-Solomon codes over fields of low characteristic can contain super-polynomially many codewords in a Hamming ball of radius just exceeding the Johnson radius. Over prime fields, we exhibit full-length Reed-Solomon codes of constant rate $R$ with polynomially many codewords in a Hamming ball of relative radius bounded strictly below $1-R$. This refutes a recent conjecture that, over prime fields, list sizes below capacity are always bounded by a constant. Together, these results demonstrate that certain restrictions in recent works on explicit Reed-Solomon codes achieving list-decoding capacity, related to the choice of field or evaluation points or to the list-size guarantee, are inherent.

Thu 5 NovInformation TheoryComputational Complexity
The gist
Reed-Solomon codes are methods used to detect and correct errors in data. The authors found that for some types of these codes, surprisingly many alternative codewords can be very close to one another, breaking a previous assumption. This means that decoding methods expecting only a few close possibilities must be adjusted. Their findings show inherent limits on how these codes can be used for error correction in certain cases.
Open → 2611.07607v1

New tensor method sharpens upper bound on matrix multiplication speed

Semidirect sums of tensors and the matrix multiplication exponent

Abstract: This note is an exposition of the recent preprints from OpenAI that establish the bound $ω\leq 9/4$ on the matrix multiplication exponent. We argue that the heart of these preprints is a new technique, which we formulate as the untwisting lemma for semidirect sums of tensors. This gives a generally applicable method for analyzing tensors. We also discuss further consequences of this method, as well as the relation between the OpenAI proof and previous work.

Tue 3 NovComputational ComplexityData Structures and Algorithms
The gist
Multiplying large matrices quickly is a fundamental problem in computing, and researchers measure speed by an exponent called omega (ω). The OpenAI preprints improved this exponent to 2.25, meaning potentially faster matrix multiplication. This paper explains the key technique behind that improvement—a new way to analyze tensors using something called the untwisting lemma for semidirect sums. The authors also relate this method to earlier work and suggest it could help analyze other complex mathematical objects.
Open → 2611.04175v1

Full-rank lossless expanders yield better quantum error-correcting codes

Full-Rank Constructions of Explicit Lossless Expanders and Good Small-Set qLTCs

Abstract: We construct explicit two-sided lossless expanders whose binary adjacency matrices have full rank, and use them to obtain explicit asymptotically good quantum LDPC codes whose specified X- and Z-check matrices have full row rank and satisfy small-set soundness, or confinement, on a linear range. Our lossless expanders are a variant of those of Hsieh, Lubotzky, Mohanty, Reiner, and Zhang, with a free action of a finite 2-group. Under such an action, injectivity and surjectivity of the adjacency matrix are detected on a fixed-size matrix indexed by vertex orbits. Adding a sparse factor to the gadget at the middle vertices of a single type then enforces full rank, with a controlled loss in expansion. To obtain the 2-group action, we observe that reducing the generators of the Lubotzky-Phillips-Sarnak Ramanujan graphs modulo powers of 2, instead of modulo an odd prime, gives Ramanujan Cayley graphs on finite 2-groups. This construction may be of independent interest. Plugging two such expanders into the balanced product of Lin and Hsieh gives the quantum codes, since full rank of the input graphs is inherited by the check matrices. Our construction supplies the code family sought by Hong, Guo, and Lucas. Applying their analysis, within their framework and under their dynamical assumptions, gives quantum memories whose free-energy density is analytic at every positive temperature and whose guaranteed lifetime is $exp(Ω(N))$ at sufficiently low fixed positive temperature, where N is the blocklength. This improves the previously guaranteed stretched-exponential timescale.

Mon 2 NovComputational ComplexityData Structures and Algorithms
The gist
Building reliable quantum computers requires error-correcting codes that can detect and fix mistakes. The authors construct special mathematical graphs whose connections have a property called full rank, which helps improve the design of these codes. Their approach leads to quantum codes that perform well and last longer while keeping error checks effective on small parts of the data. This work also provides new kinds of graphs that may interest mathematicians working in network design. The resulting quantum memories show better predicted stability at low temperatures than previous constructions.
Open → 2611.02963v1

Donoho Starks uncertainty principles limit approximate supports for k Hadamard operators

On approximate support versions of Donoho--Stark uncertainty principles for $k$-Hadamard operators

Abstract: In this paper we present results related to Donoho--Stark type uncertainty principles that were proved in the article "The uncertainty principle: variations on a theme" by Wigderson and Wigderson for $k$-Hadamard operators in the finite-dimensional setting. Namely, the authors showed that Donoho-Stark principles can be generalized to versions for approximate supports with respect to norms $\ell^{p}$ for $p=1$ and $p=2$. In the second case they assumed the so-called speciality condition, namely that a suitable matrix satisfies $A^{*}A = kI$. First we show that such theorems cannot be generalized to $p>1$ if matrices are not special $k$-Hadamard. Next we prove Donoho-Stark type principle for special $k$-Hadamard operators for $\ell^{p}$ norms within the range $1\leq p\leq 2$. Finally, we show that such theorems are false for $p>2$ even in the presence of the speciality condition.

Fri 30 OctInformation Theory
The gist
This paper looks at mathematical rules called uncertainty principles, which say you can’t know too much about certain pairs of properties in signals at once. The authors focus on versions that allow some approximation, working with special matrices called k-Hadamard operators. They find these rules hold for some ranges of mathematical measures but fail outside those ranges, clarifying exactly when such approximations are possible. Their results pinpoint limitations and conditions for these uncertainty principles in a finite setting.
Open → 2610.41902v1

Limits on code length from algebraic geometry over large fields

Length Bounds for MDS Algebraic Geometry Codes of Arbitrary Positive Genus

Abstract: We study the length of maximum distance separable algebraic geometry codes from curves of arbitrary positive genus. For fixed genus, we prove that the asymptotic ratio of the length to the field size is at most $1/2$ when both the dimension and the codimension grow faster than the logarithm of the field size. We also give explicit bounds under logarithmic dimension conditions. The bounds hold in every characteristic and are uniform in the curve and the evaluation set. The proof combines character sums on the Jacobian with an estimate for sums of distinct points.

Thu 29 OctInformation Theory
The gist
Some special kinds of error-correcting codes come from shapes called algebraic curves. These codes can correct many mistakes, but the authors found limits on how long these codes can be compared to the size of the system they work over. Specifically, when certain size measures get large, the code length can’t be more than half the size of the underlying setting. The authors provide mathematical bounds that apply broadly to these codes regardless of details.
Open → 2610.39434v1

Binary code structure explains all 64 I Ching hexagrams

Extremal diagonal-coherent binary codes: shortened Hamming cores, deep holes, and the 64 I-Ching hexagrams

Abstract: Each of the 64 hexagrams of the I-Ching, or Book of Changes, is a stack of six Yin-Yang lines and is therefore a binary vector of length 6; the eight hexagrams formed by repeating a single trigram span a doubled-trigram subspace $Δ$. We ask which binary $[6,3,3]$ codes are compatible with this trigram structure. We show that a $[6,3,3]$ code meets $Δ$ in at most four codewords, that the four are then forced to be the doubled trigrams Earth, Fire, Wind and Lake, and that exactly two codes attain this bound: the shortened Hamming code $\mathcal C_A$ and its dual. Since $\mathcal C_A$ has covering radius 2, its eight codewords, their radius-one balls, and its eight deep holes together reconstruct all 64 hexagrams. In general, we call a binary code of length $2m$ with $d \ge 3$ diagonal-coherent if it contains the half of the diagonal subspace $\{(u,u)\}$ coming from even-weight vectors $u$ -- the largest part of that subspace a single-error-correcting code can contain -- and extremal if its dimension is as large as possible. For $m\ge2$ and $r=\lceil\log_2(2m+1)\rceil$, we determine the number $N(m)$ of extremal diagonal-coherent codes with parameters $[\,2m,\ 2m-r,\ \ge3\,]$, show that diagonal coherence entails no loss of redundancy, and determine their minimum distances. We also put these codes in a normal form, determine their hulls, and show that each has covering radius $2$ with exactly $2^r-1-2m$ deep-hole cosets. Finally we propose three open problems.

Sat 24 OctDiscrete MathematicsInformation Theory
The gist
The paper studies a special set of binary codes that align with the ancient 64 hexagrams from the I Ching, each represented as a string of six Yin-Yang lines. The authors find two particular codes that fit a trigram pattern related to these hexagrams and show how these codes can reconstruct all 64 hexagrams along with their surrounding variations. They then explore properties of a broader family of similar binary codes, including their size, error-correcting ability, and special points called deep holes. The work also identifies some mathematical structures and poses open questions for future study.
Open → 2610.33676v1

Quantum communication proves stronger than Merlin-Arthur protocols

BQP^cc is not contained in MA^cc

Abstract: We exhibit a bipartite language with a poly-logarithmic quantum communication protocol and polynomial Merlin-Arthur communication complexity.

Sat 17 OctComputational Complexity
The gist
This work shows that there are some communication problems where quantum methods are more efficient than classical ones that rely on proofs checked in a traditional way. Specifically, the authors found a task that can be solved with very little quantum communication but requires much more communication if done with Merlin-Arthur style protocols. This suggests that quantum communication can solve some problems in ways classical approaches cannot match.
Open → 2610.24742v1

Quantum computing may improve approximation guarantees for hard problems

Quantum Approximation Complexity of Classical Optimization Problems

Abstract: Classical approximation complexity asks what solution quality can be guaranteed with polynomial-time computation. The classes APX, PTAS, and FPTAS distinguish a fixed approximation ratio, approximation to any fixed accuracy, and approximation schemes whose running time is also polynomial in inverse accuracy. Their randomized counterparts are R-APX, R-PTAS, and R-FPTAS. We define bounded-error quantum counterparts BQ-APX, BQ-PTAS, and BQ-FPTAS. Membership requires a uniform quantum algorithm that, on every input, returns a feasible classical solution achieving at least the claimed approximation ratio with probability at least 2/3. Scores (objective values) must be efficiently classically computable. Running time includes parameter selection, preparation, measurement, decoding, and repetition. Many quantum optimization methods are used heuristically, and high benchmark scores alone do not establish these guarantees. We further establish a conditional hierarchy for logarithmic, polynomial, and exponential approximation factors. Assuming NP $\subsetneq$ BQP, the quantum classes form a strict hierarchy. Problems based on prime factorization and discrete logarithms give conditional quantum-classical separations. Certified Maximum Order has an exact quantum algorithm, while any randomized polynomial-time algorithm guaranteeing at least an inverse-polynomial approximation ratio on every input would yield efficient factoring. Discrete-Logarithm Fitting has an exact quantum algorithm and a deterministic one-half approximation, but any fixed improvement over one half would give a randomized polynomial-time algorithm for the safe-prime discrete logarithm problem. Our results show, under explicit complexity assumptions, that quantum computation can improve worst-case approximation guarantees. A quantum-classical gap for common problems such as MaxCut or MaxSAT remains open.

Wed 7 OctComputational Complexity
The gist
This work studies how well quantum computers can find approximate solutions to tough optimization problems compared to classical computers. The authors define new classes that capture how good quantum algorithms can guarantee their results on any input within polynomial time. They show that, assuming some complexity theory assumptions hold, quantum algorithms can sometimes outperform classical ones for certain problems such as factoring and discrete logarithms. However, it remains unknown if this quantum advantage applies to common optimization problems like MaxCut or MaxSAT.
Open → 2610.09584v1

Quantum circuit obfuscation enables verifiable quantum advantage protocols

Verifiable Quantum Advantage and Computation via Quantum Circuit Obfuscation

Abstract: We construct protocols for classically verifiable quantum advantage and classical verification of $\mathsf{BQP}$ computations using \emph{quantum indistinguishability obfuscation} (qiO). Specifically, given qiO and assuming a slightly stronger version of $\mathsf{BQP}\neq\mathsf{BPP}$, we construct a two-message quantum-advantage protocol that is efficiently and publicly verifiable. Our result can be viewed as a rigorous cryptographic foundation for the heuristic quantum advantage proposals based on \emph{peaked random circuit sampling} of Aaronson and Zhang (arXiv:2404.14493). We also construct two simple protocols for classically verifying arbitrary $\mathsf{BQP}$ computations. The first protocol is privately verifiable and assumes only the existence of qiO. This gives a rare example of a nontrivial cryptographic application of (quantum) iO that does not make additional computational hardness assumptions. The second protocol additionally assumes post-quantum one-way functions and is \emph{publicly verifiable}. To our knowledge, this is the first publicly verifiable protocol for classical verification of $\mathsf{BQP}$ computations under computational assumptions in the standard model. We show that all our results hold when qiO is assumed only for ancilla-free unitary circuits. As evidence supporting this assumption, we prove a worst-to-average-case reduction for obfuscating such circuits. This reduction extends the local-mixing framework of Canetti, Chamon, Mucciolo and Ruckenstein (TCC 2024) under quantum analogues of their assumptions.

Wed 30 SeptCryptography and Security
The gist
Showing that quantum computers can do tasks beyond classical ones is a key goal, but verifying these tasks using only classical computers is hard. The authors build protocols that let classical computers verify quantum computations under assumptions about quantum circuit obfuscation and computational hardness. Their work provides cryptographic guarantees for quantum advantage experiments and offers ways to check any quantum computation classically with either private or public verification. They also support their assumptions by proving technical results about the difficulty of obfuscating certain quantum circuits.
Open → 2609.40289v1

Noise breaks Shor's quantum factoring advantage in circuits

Resonance Breaking in Noisy Shor's Algorithm

Abstract: We argue that the exponential quantum advantage in Shor's algorithm is broken under one-layer depolarizing noise of arbitrary small error rate, by analyzing a resonance breaking phenomenon in noisy quantum circuits. First, we express the distribution of measurements on $n$-qubit strings as the superposition of the $4^n$ wave functions in the Pauli path integral. In the noiseless case, the bit-strings achieving resonant peaks guaranteed a constant rate of successful measurements to factor a large number. Secondly, when the middle layer of the quantum circuit has independent depolarizing noise of rate $λ$, for any Hamming weight $d$, we obtain corresponding measurement rate bounded by $2(1-λ)^d$ for higher frequency terms and by $O(n^d)/2^{n/2}$ for low frequency terms. The rate approaches to zero as $n$ and $d$ approaches to infinity. Resonance breaking destroys the exponential quantum advantage. Furthermore, we design a classical factoring algorithm in polynomial time $O(n^d)$ to substitute the low frequency contribution.

Tue 29 SeptComputational ComplexityInformation Theory
The gist
Shor's algorithm is a famous quantum method that can factor large numbers much faster than traditional computers. This paper shows that even a tiny amount of noise in the quantum circuit can ruin the special patterns needed for the algorithm to work well, causing its speed advantage to disappear. The authors also present a classical method that can simulate part of the algorithm under noise conditions, meaning the quantum advantage is lost. Their work suggests that noise can fundamentally limit how useful some quantum algorithms are in practice.
Open → 2609.37636v1

Quantum networks enable information-free proof verification among many parties

Zero Knowledge Proofs in Quantum Networks

Abstract: Zero-knowledge proofs (ZKPs) enable the verification of a statement without revealing any information beyond its validity and constitute a fundamental primitive in cryptography and information theory. However, existing constructions rely on computational assumptions and are predominantly confined to bipartite settings, leaving their information-theoretic realization in bipartite or network scenarios largely unexplored. Here we develop a framework for zero-knowledge verification based on the indistinguishability of quantum states under operational constraints. Exploiting the fundamental limitations imposed by local operations, we show that a verifier is inherently restricted from extracting information about the underlying state while retaining the ability to verify correctness. We construct explicit protocols for multiparty quantum networks that achieve information-theoretic security, ensuring that no subset of collaborating parties can gain knowledge beyond the validity of the statement, independent of their joint computational power.

Mon 28 SeptCryptography and SecuritySocial and Information Networks
The gist
Sometimes you want to prove something is true without sharing any extra details. The authors find a way to do this using quantum states in networks of multiple people, relying on physics limits instead of complex math assumptions. Their method stops anyone from learning more than just whether the statement is true, even if they work together and have unlimited computing power. This is like a magic proof where nobody learns the secret, only the fact that the secret is correct.
Open → 2609.35339v1

Improved sphere packing counts found in high dimensions 25 to 31

New lower bounds for kissing numbers in dimensions $25$--$29$ and $31$

Abstract: The kissing number in dimension $d$ is the largest number of non-overlapping congruent spheres that can simultaneously touch a central sphere of the same size. We study dimensions $25$-$31$, where the best previous constructions are based on Leech lifting from the optimal kissing configuration in dimension $24$. Our method exploits the absence of contacts between the unlifted bulk and the block consisting of lifted and auxiliary vectors. Rotating this block while keeping the bulk fixed creates room for two antipodal points in dimensions $26$, $27$, and $28$, and one point in dimension $29$. Two further modifications yield improvements in dimensions $25$ and $31$: a nonorthogonal diagonal linear deformation of the lifted block admits two antipodal points in dimension $25$, while rotating only the additional coordinates of the lifted vectors admits four nonantipodal points in dimension $31$. Together, these constructions yield the new lower bounds $τ_{25}\geq 197058$, $τ_{26}\geq 198552$, $τ_{27}\geq 200046$, $τ_{28}\geq 204522$, $τ_{29}\geq 209497$, and $τ_{31}\geq 238354$.

Fri 18 SeptInformation Theory
The gist
The kissing number problem asks how many same-sized spheres can touch one central sphere without overlapping. The paper improves known minimum counts for this problem in high dimensions from 25 to 31. The authors build on existing arrangements in dimension 24 and use geometric rotations and deformations to fit more spheres around the center. This work updates the best known lower limits on how many spheres can simultaneously touch the center sphere in these specific dimensions.
Open → 2609.21591v1

Quantum channel capacity strictly limits reliable information transfer

No information transmission through quantum channels above capacity

Abstract: We show that the capacity of a quantum channel demarcates a phase transition: while reliable transmission below capacity is always possible, any attempt to transmit information above it fails catastrophically. Specifically, we prove exponential strong converse theorems for unassisted quantum and classical communication over arbitrary finite-dimensional memoryless quantum channels. At rates beyond the respective capacity, the entanglement-generation fidelity and the success probability for classical communication decay exponentially with the number of channel uses. This rules out transmission above capacity even when one tolerates arbitrarily large errors. Our proof follows the classical Arimoto strategy, augmented by a crucial new ingredient: integral representations of Rényi information measures that lead to asymptotic continuity bounds for Rényi capacities.

Tue 8 SeptInformation Theory
The gist
This paper shows there is a clear hard limit on how much information can be reliably sent over quantum communication channels. The authors prove that sending data above this limit doesn't just get harder, but actually fails exponentially fast with more uses of the channel. This means no matter the method, you can't hope to reliably communicate above the channel’s capacity, even if you're willing to accept large errors. The proof builds on classical methods but adds new mathematical tools for understanding quantum information measures.
Open → 2609.08998v1