A Geometric Approach to Quantum Distinguishers (CRYPTO 2026)

Hello, everyone. My name is Chengyu Huang from Tsinghua University. Today, I will present our work a geometric approach to quantum distinguish. This is joint work with Jianjian Bao. In this talk, we will look at quantum distinguish from a geometric perspective and try to give a unified picture of why some attacks get exponential speedups, others only quadratic, and some get no speedup at all. Let me start with three questions that, in our opinion, keep coming back in quantum symmetric cryptanalysis. First, which primitive should be used? We have Grover, Simon, Bernstein-Vazirani, Deutsch-Jozsa, amplitude estimation, quantum walk, and many more. Choosing the right one is not always obvious. Second, how do we actually design a quantum attack? Right now, it often feels ad hoc. You take a classical distinguisher, you pick a quantum algorithm, and you hope it works. But, the cryptanalytic property should select the algorithm, not the other way around. Third, what speedup actually survived? We often say Grover gives quadratic speedup, and Simon gives exponential speedup. But, when you plug them into a real cipher, things get messy. Grover's gain varies a lot. And Simon's exponential advantage does not automatically carry over to every construction. So, algorithm choice is not attack design. And neither is a speed-up guarantee. We wanted a single template that can quantize many classical distinguishers in a systematic way. Our thesis is the following five-step pipeline. You start with a function, a cipher, a permutation, whatever you are attacking. First, you perform an exact lift into a larger linear space. Non-linear functions become linear operators on free vectors. Second, you choose a basis. The basis is what makes structure visible. Fourier basis shows linear structure. Another basis shows differential structure, and so on. Third, you make one coherent query to prepare what we call the correlation state. This is a single superposition query. Fourth, you measure in that basis. Depending on what you measure, either the support pattern or the probability mass, you get a different family of algorithms. And finally, quantum speedup depends on where the signal mass lands in that basis. If it concentrates, you get a big speedup. If it dilutes, you lose some advantage. Here is the road map for this talk. We work entirely in the Q2 model. That is, superposition queries to the oracle. First, I will explain the geometric lift, how we embed a cipher into a linear space. Then, I will introduce the correlation state and the generalized correlation extraction algorithm, along with two measurement paradigms. After that, we will look at three basis instantiations, Fourier, quasi-differential, and integral. Finally, we will discuss speedups and their limits, dilution, state preparation cost, and non-unitarity. Let us start with the geometry. The core idea of the classical geometric approach is this. You take a function on bits and you lift it to a linear map on a much larger free vector space. On the left you have the set map, the actual function, which can be highly non-linear. On the right you have its free vector extension, which is always linear. Formally, this is a monoid representation. For invertible functions like permutations, it restricts to a group representation. Every function value becomes a column in a matrix. Composition becomes matrix multiplication. And parallel composition becomes tensor products. Importantly, this is an exact representation. No approximation. Every detail of the original function is preserved. This matrix is called the pushforward operator. Let me give you a tiny example. Here is the AND function on two bits. The input basis has four states: 00, 01, 10, 11. The output basis has two states: 0 and 1. Each column corresponds to exactly one input. You can see that three inputs map to zero and one input maps to one. So, one column equals one exact function value. Now, a very important warning. Because many inputs can map to the same output, this operator is not unitary. It is a linear representation, but it is not a quantum gate. Do not confuse it with a unitary operator. Why is this useful? Because the lift preserves the structure of the cipher exactly. If you have sequential composition, round after round, in the lifted space, this becomes matrix multiplication. If you have parallel components, like an S-box layer in a brick layer cipher, this becomes a tensor product in the lifted space. Round-by-round propagation is retained exactly. Parallel components remain separable. The cipher structure survives the embedding completely. This observation helps the classical geometric approach to unify linear, differential, and integral cryptanalysis. We want to carry this over to the quantum world. Now the key conceptual point. On the left, we have the operator in standard coordinates. It looks like a big messy matrix. On the right, the same operator in a carefully chosen basis, suddenly structure becomes visible. The basis is what determines what you can see. If you choose the Fourier basis, you see linear approximations. If you choose the quasi-differential basis, you see differential probabilities. If you choose the integral basis, you see divisibility properties. Same operator, different basis, and different cryptanalytic observable. The most familiar example is the Fourier basis. The Hadamard transform diagonalizes XOR translation. When you change to the Fourier basis, the correlation matrix becomes exactly the linear approximation table. Each entry tells you the correlation between an input mask and an output mask. This is the standard object of linear cryptanalysis. So, in the geometric language, linear cryptanalysis is just what you see when you look at the pushforward operator through Fourier glasses. Now, we move to the quantum part. How do we get from geometry to an actual quantum algorithm? You start with a uniform superposition over all inputs. Then, you apply the oracle once. The result is the graph state of the function. Each input branch is paired with its corresponding output, forming a uniform superposition of input-output pairs. This is one coherent query. You do not collect many classical data points. You create a superposition that encodes the entire function at once. From here, if you apply a change of bases transformation, you turn this graph state into something whose amplitudes are exactly the entries of the correlation matrix. This brings us to the main technical tool, the generalized correlation extraction algorithm. The original CEA was introduced by Hosoyamada for multi-dimensional linear distinguish us. We generalize it to arbitrary bases. The theorem says, with one superposition query to the oracle, followed by the appropriate basis change case. You produce a state. We call it the correlation state. Whose amplitudes are proportional to the entries of the geometric correlation matrix in your chosen basis. One query, one template works for Fourier, works for quasi-differential and in principle for any basis with an efficient unitary implementation. This is the unified preparation step. Once you have the correlation state, you measure it. You get an outcome with probability equal to the squared amplitude of that basis state. From one measurement, what usable information do you get? You get support information whether a particular entry is zero or not. You get interference patterns. And you get probability weight. How much mass is on certain states? This is the raw material for two different testing paradigms. So, from the same correlation state, you can run two very different kinds of test. First, support test. You look for hidden algebraic structure. Zeros in the correlation matrix. You sample sequentially and this sample gives you an equation. CMOS algorithm PB, DJ All of these are support tests. They exploit zero correlation constraints. Second mass best or event probability test. Here you use quantum amplitude amplification or amplitude estimation to measure how much probability mass is on a good event. This is what you do for linear distinguish us differential distinguish us multidimensional linear distinguish us. You are estimating a deviation from the random oracle expectation. Same preparation template two different measurement strategies and two families of quantum algorithms. For event probability test the speed up typically follows a square root scaling. The familiar quadratic advantage. If you are looking for a rare event quantum amplitude estimation gives you roughly a square root improvement over classical sampling. This is the standard quadratic speed up you expect from Grover type algorithms. If you are measuring a small bias, you also get roughly quadratic gain. This is the regime of differential cryptanalysis, linear cryptanalysis, and similar statistical distinguish us. In our framework, they all come from the same mass testing paradigm. Now, we come to a problem, dilution. Imagine you have one informative cell in a huge state space. The correlation is real. The signal is there, but the probability mass on that cell become vanishingly small once the whole state is normalized. It is like hiding a needle in a haystack. The needle exists, but most of the state is hay. Because quantum mechanics is unitary, you cannot throw away the un- informative components. They are still there taking up amplitude. This is why some published distinguish us perform poorly. The signal gets diluted across too many basis states, and the quantum advantage vanishes. Where the signal concentrate depends on which basis you use, and each basis comes with its own concentration mechanism. For the Fourier basis, the visible object is the LAT. And you concentrate using phase oracles that restrict to specific output mask rows. For the quasi-differential basis, the visible object is the DDT. And you concentrate by restricting to a chosen plain text subset state. For the algebraic integral basis, the visible object is two added divisibility. But there is no direct unitary transform, so discussion is unnecessary. So, your choice of basis determines not only what you can see, but also which algorithm family you and where the performance bottlenecks will be. Let us look at the Fourier case first. The remedy for dilution is the phase oracle. On the left, you have all output mask rows of the LAT. Most of them are uninformative for your distinguisher. On the right, by using a phase oracle, you restrict to just one selected row, the output mask you actually care about. While other rows are suppressed, this concentrates all the amplitude onto the relevant Fourier coefficients. You go from a huge diluted state to a much smaller denser state. And this is not just a trick. We prove that this row selection ability is unique to the Fourier basis. You cannot do the same thing for other basis via a simple conjugate relation. Once you are in the Fourier basis with support testing, three famous algorithms turn out to be the same thing with different support geometries. Deutsch-Jozsa tests whether the support is concentrated entirely at zero frequency or entirely on its complement. It distinguishes constant from balanced functions. Bernstein-Vazirani has support concentrated at a single hidden mask. Simon's algorithm has support restricted to a hyperplane, the orthogonal complement of the secret period. Same Fourier preparation, same measurement paradigm, just hidden different subset geometries. This is why we say it the framework unifies them. They are all instances of zero correlation support testing on the correlation state. Now, let us switch to the quasi-differential basis, which corresponds to differential cryptanalysis. Here, the concentration mechanism is different. Instead of restricting output masks, you restrict the input by preparing a subset state. How hard is it to prepare a subset state? It depends on the structure. A singleton set is easy. Just fully X case. An affine subspace is also easy. Hadamard plus C not network. An unstructured set is costly. You need QAA or rejection sampling. For differential cryptanalysis, the set of pairs with a fixed input difference is an affine subspace. So, you can prepare it efficiently. This is exactly what a chosen plaintext attack does. Let me briefly explain the quasi-differential basis itself. Differential attacks are second order. They work on pairs of plain text. So, we have two input coordinates. The cosine differential change of basis splits these two coordinates into a difference coordinate, which is the XOR of the two inputs, and a fiber coordinate, which is essentially a Fourier coordinate on the remaining degree of freedom. The circuit to do this is quite simple. C-NOT, swap, and Hadamard gates per bit pair. What this basis reveals is the differential distribution table, but with extra phase information along the fiber. The key theorem here is if you sum the squared magnitudes over all fiber coordinates, you get exactly the DDT entry for that input-output difference pair. In other words, the total probability mass on the fiber equals the differential probability. Classically, you sample right pairs one by one. Quantumly, you prepare the subset state, and then run amplitude estimation on the good output difference. The result is a quadratic speed up over classical differential sampling. The same as Kaplan and others quantum differential attack. Now reinterpreted through the geometric lens. Now an important point. Why can we not get Simon like exponential speed up for differential attacks? Because the DDT is classically sampleable. If I pick two random plain texts and compute their cipher text difference I get one sample from the DDT distribution for the cost of two classical queries. I do not need to enumerate the whole table. The LPN by contrast is not directly classically sampleable. To get a Fourier coefficient you would need the whole codebook. That is why Simon's algorithm can give exponential speed up. It displays a structure that classically would require exponential data. So the rule of thumb is if the classical table is hard to sample you may get super quadratic or exponential gain. If the classical table is easy to sample you typically top out at quadratic gain. Finally let us talk about the integral basis or more precisely the ultrametric integral basis based on p-adic geometry. Here, we run into a mismatch. The integral basis comes from ultrametric geometry, but quantum mechanics live in complex Hilbert space with the Euclidean inner product. The columns of the integral basis change and not orthogonal. That means there is no straightforward deterministic unitary gate that implements this basis change exactly and efficiently. You can still do some things. Balanced integral properties can be detected through zero correlation details, but a general direct quantization of integral cryptanalysis is not straightforward. Whether there is a genuine quantum speedup for non-trivial integral properties remains an open question. To summarize, we have proposed a geometric framework for quantum distinguishments. A single correlation state preparation template with one coherent query unifies the port type and mass type attacks across multiple bases. The framework explains where speedups come from, why dilution kills them and how a basis specific techniques face articles for free air sub says days for quasi differential can restore the advantage. This is a theoretical bridge not a magic compiler. It gives you a design language but it does not automatically give you end-to-end attacks or free key recovery. Thank you very much for your attention. If you have any questions you can reach me by email. Thank you.