Transcription
Hello, my name is Lars Lieber, and I will present to you the paper "Quantum Period Finding is Compression Robust." This is a joint work with Alexander Mai.
Today, only a few hundred physical qubits are available, which also have a quite high noise rate and so are not capable of executing most of the quantum algorithms known today. Moreover, we do not have access to a single logical qubit, in other words, a noise-free qubit, which would require some thousand physical qubits to be created and on which most of our theoretical quantum algorithms in the cryptographical field are built on.
However, there are many companies such as IBM, IonQ, and SCC that have announced plans to build quantum computers with a few million physical qubits and quantum computers that can simulate a few hundred logical qubits in the next 10 years. Our goal in this work is to reduce the number of logical qubits required for the class of period finding algorithms in order to use a few available logical qubits in the future more efficiently. This will lead to quantum computers being earlier, with fewer qubits, already a threat to security, and we use the time that we have to prepare for this.
We primarily study Simon's problem, which is defined as the problem to find the period $s$ given access to a two-to-one function $f$ with $f(x) = f(x \oplus s)$ for all $x$. This problem is classically hard to solve and requires at least $2^{n/2}$ queries to $f$. More precisely, we would have to find a collision in $f$ to calculate $s$ for a function that behaves like a random function. By side of the period of $s$, quantumly on the other side, this problem can be solved efficiently in polynomial time with roughly $n$ queries to $f$ and $2n$ qubits. This can be done by using Simon's algorithm.
This algorithm uses quantum access to $f$ in the circuit below to sample uniform at random $y$'s that are orthogonal to $s$. After collecting $n-1$ linear independent vectors $y$, the algorithm then calculates $s$ via Gaussian elimination from the collected vectors. Thereby, it holds that expected about $n+1$ random sampled $y$'s are sufficient to collect $n-1$ linear independent vectors. The underlying circuit requires $n$ qubits to represent the input of $f$ as well as the sample vector at the end, and additionally $n$ qubits to hold the value of $f(x)$. An example distribution of the $y$'s for $n=3$ and $s=001$ can be seen here on the right. Note that the $000$ vector contains no information about $s$. However, the amplitude of the zero vector decreased with increasing $n$.
An application of Simon's algorithm will be an attack on the famous Even Mansour cipher. The Even Mansour cipher is defined over a key $k$ and a public permutation $P$, whereby the encryption of $m$ is computed as $k \oplus P(k \oplus m)$ and is classically provably secure in the sense that any attacker requires at least $2^{n/2}$ queries to the cipher to break it with constant probability. Using Simon's algorithm with quantum access to the cipher, the key $k$ can be acquired in polynomial time. For this, a function $f$ is defined as $f(x) = E_k(x) = k \oplus P(k \oplus x)$. It is easy to see that the secret key $k$ is a period of $f$, and so the secret key can be efficiently be found via Simon's algorithm.
Let us come to our compression technique. We are hash functions. The starting point of our study was the question whether all $n$ bits of $f(x)$ are really necessary, or if the number of qubits representing $f(x)$ can be reduced, or in other words, if $f(x)$ can be compressed. Previous approaches to reduce the number of qubits required for such algorithms focused only on reducing the number of input qubits required, such as the Mosca-Eckert approach to recycle a single qubit for the input of Simon's algorithm for special cases.
Our main observation by compressing $f$ was that hashing preserves the collisions of $f$, which leads to the fact that we will in Simon's circuit still only measure vectors that are orthogonal to $s$. On the other hand, however, hashing introduced additional collisions that affect the distribution of the sampled $y$'s. Especially a bias towards the zero vector is introduced. In worst-case scenarios, this collision could introduce new periods or, for a constant hash function, could shift all probability to the zero vector.
To counteract the fact that the hash function might introduce too many bad new collisions and shift too much probability away from a complete subspace, we sample our $y$'s to different hash functions. The intuition behind this concept can be seen here on the right. The green areas represent vectors that are orthogonal to all vectors measured to a specific hash function. We see that the zero vector and the $s$ vector are contained in all these subspaces. By combining the measured vectors to the different hash functions, we can compute the intersection of the different subspaces, which only contains the zero vector and the $s$ vector.
For our proof, we used a set of universal hash functions, such as, for example, the set of the scalar products modulo 2. It is worth noting that we conjecture that the necessity of multiple hash functions is just a proof artifact and that in most cases, one single hash function is sufficient, or in other words, that with high probability, each of these subspaces already contains only the zero vector and the $s$ vector.
Our hash algorithm thereby is almost the same as the original algorithm. Again, we use a similar circuit to collect vectors $y$ orthogonal to $s$. The only difference is that the embedding of $f$ is in each iteration replaced with the embedding of a different hashed version of $f$. We have shown in our paper that we still only measure $y$'s that are orthogonal to $s$, as well as the algorithm still works with a constant factor of overhead. Additionally, we provide some examples in our paper how such hashed embeddings could be implemented, which only require roughly twice the depth of the unhashed version.
Let us consider the distribution of the $y$'s for a fixed hash function compared to the original Simon distribution. Such a distribution might look like this, for example, for our $n=3$ and $s=001$ case. Here, we already see the bias towards zero, and also that some $y$'s are no longer measurable. On the good side, however, we see again that the probability to measure a non-orthogonal vector of $y$'s remains at zero. At other distribution graphs to other hash functions, we see further that, for example, for some hash functions, the probability for some particular vector of $y$'s might even be greater than before, or that, as mentioned before, for some hash functions whose subspaces are no longer measurable. But also, which vector is affected depends on the hash function.
Taking the average distribution over all our hash functions to one bit, we see that the probability of measuring the zero vector increased only by roughly one half, and also that the probability of any other vectors decreased by only a factor of two. We also proved this observation in our paper.
Let us summarize our results. Even with only access to a hashed embedding of $f$, we sample only $y$'s that are orthogonal to $s$. Furthermore, on average over the choice of the hash function, the distribution of the vectors is preserved, except for a constant bias towards the zero vector, which means that we can use the same post-processing as before, after sorting out the zero vectors that do not provide any information about $s$ anyways. Furthermore, we expect only to require a constant factor of more measurements due to term $s$ with the hashed approach, and that in many cases, only a doubling of the circuit depth is required to implement the embedding of the hashed version of $f$. Summarized in one sentence: require only a small additional effort to solve the same problem with almost only half the qubits required.
To put this in some perspective, in the setting of Even Mansour, instead of $2n$ qubits, we require only $n+1$ qubits, with the number of measurements required increased from $n+1$ to $2n+2$. We would like to stress again that we conjecture that in most cases, a single projection onto a single bit should be sufficient. Furthermore, our hash technique can be combined with other techniques such as the Grover-meets-Simon's approach or the offline Simon technique, which also eliminates our reliance on implementations of embeddings of hashed versions of the function and greatly simplify the application of our hash technique. We show this in our paper in more detail.
To give a rough outline to this combination, to use our hash technique in this context, we only require simple implementations of our used hash function, which can be realized for our example set of hash functions with the use of a single multi-qubit gate. Additionally, we have shown that our hash technique is not limited to the Simon's algorithm but can also be applied to more general period-finding algorithms like Shor. These results have also already been used for an attack on Polyakov, the reference can be found in our paper.
To summarize our results in the light of security: quantum computers might already be a greater threat to cryptography with fewer logical qubits and though earlier than expected. Thank you for your attention.