A vectorial Boolean function takes multi-bit input and produces a multi-bit output. According to the input parameters, a vectorial Boolean function can be linear or non-linear. Non-linear vectorial Boolean functions have high importance in information theory and cryptology. Finding a linear approximation of a non-linear vectorial Boolean function is of high significance in these areas. Assuming that the quantum access to a vectorial Boolean function is provided, we present a quantum computing approach which can find the best linear approximation of the non-linear vectorial Boolean functions. The presented quantum approach is exponentially better than any known solution on the factors of querying the function, quantum circuit depth and memory requirements.
A vectorial Boolean function takes multi-bit input and produces a multi-bit output. According to the input parameters, a vectorial Boolean function can be linear or non-linear. Non-linear vectorial Boolean functions have high importance in information theory and cryptology. Finding a linear approximation of a non-linear vectorial Boolean function is of high significance in these areas. Assuming that the quantum access to a vectorial Boolean function is provided, we present a quantum computing approach which can find the best linear approximation of the non-linear vectorial Boolean functions. The presented quantum approach is exponentially better than any known solution on the factors of querying the function, quantum circuit depth and memory requirements.
Linear cryptanalysis, a Known-Plaintext Attack, for symmetric block cipher works by constructing linear approximations of the non-linear components of the cipher. The only component which introduces non-linearity in the symmetric block cipher is an S-box. Using classical computing algorithms, the best known solution to find a linear approximation of a non-linear function, in this case an S-box, requires queries to the S-box and time-complexity, where is the input size of the S-box and is the output size. In this paper, a quantum algorithm is presented which can produce best linear approximations of a non-linear S-box using only queries to S-box with time-complexity. The proposed algorithm shows a significant improvement over the classical algorithm. Correctness proof of the proposed quantum algorithm is presented along with an example.
Non-linearity of a Boolean function indicates how far it is from any linear function. Despite there being several strong results about identifying a linear function and distinguishing one from a sufficiently non-linear function, we found a surprising lack of work on computing the non-linearity of a function. The non-linearity is related to the Walsh coefficient with the largest absolute value; however, the naive attempt of picking the maximum after constructing a Walsh spectrum requires Θ (2 n ) queries to an n -bit function. We improve the scenario by designing highly efficient quantum and randomised algorithms to approximate the non-linearity allowing additive error, denoted λ, with query complexities that depend polynomially on λ. We prove lower bounds to show that these are not very far from the optimal ones. The number of queries made by our randomised algorithm is linear in n , already an exponential improvement, and the number of queries made by our quantum algorithm is surprisingly independent of n . Our randomised algorithm uses a Goldreich-Levin style of navigating all Walsh coefficients and our quantum algorithm uses a clever combination of Deutsch-Jozsa, amplitude amplification and amplitude estimation to improve upon the existing quantum versions of the Goldreich-Levin technique.
We consider the quantum query model for computing Boolean functions. The definition of the function is known, but a black box contains the input X = (x1, x2, ..., xn). Black box can be accessed by querying xivalues. The goal is to develop an algorithm, which would compute the function value for arbitrary input using as few queries to the black box as possible. We present two different quantum query algorithms for computing the basic Boolean function - logical AND of two bits. Both algorithms use only one query to determine the function value. Correct answer probability for the first algorithm is 80%, but for the second algorithm it is 90%. To compute this function with the same probability in the classical model, two queries are necessary. We analyze algorithms implementation differences and propose a way to extend the first algorithm to compute AND of two functions.
In cryptography, techniques and tools developed in the subfield of linear cryptanalysis have previously successfully been used to allow attackers to break many sophisticated cryptographic ciphers. Since these linear cryptanalytic techniques require exploitable linear approximations to relate the input and output of vectorial Boolean functions, e.g., the plaintext, ciphertext, and key of the cryptographic function, finding these approximations is essential. For this purpose, the Correlation Extraction Algorithm (CEA), which leverages the emerging field of quantum computing, appears promising. However, there has been no comprehensive analysis of the CEA regarding finding an exploitable linear approximation for linear cryptanalysis. In this paper, we conduct a thorough theoretical analysis of the CEA. We aim to investigate its potential in finding a linear approximation with prescribed statistical characteristics. To support our theoretical work, we also present the results of a small empirical study based on a computer simulation. The analysis in this paper shows that an approach that uses the CEA to find exploitable linear approximations has an asymptotic advantage, reducing a linear factor to a logarithmic one in terms of time complexity, and an exponential advantage in terms of space complexity compared to a classical approach that uses the fast Walsh transform. Furthermore, we show that in specific scenarios, CEA can exponentially reduce the search space for exploitable linear approximations in terms of the number of input bits of the cipher. Neglecting the unresolved issue of efficiently checking the property of linear approximations measured by the CEA, our results indicate that the CEA can support the linear cryptanalysis of vectorial Boolean functions with relatively few (e.g., n≤32) output bits.
In this work, we prove the strongest known lower bounds for QAC0, allowing polynomially many gates and ancillae. Our main results show that:
(1) Depth-3 QAC0 circuits cannot compute PARITY, and require Ω(exp(n)) gates to compute MAJORITY.
(2) Depth-2 circuits cannot approximate high-influence Boolean functions (e.g., PARITY) with non-negligible advantage, regardless of size.
We develop new classical simulation techniques for QAC0 to obtain our depth-3 bounds. In these results, we relax the output requirement of the quantum circuit to a single bit, making our depth 2 approximation bound stronger than the previous best bound of Rosenthal (2021). This also enables us to draw natural comparisons with classical AC0 circuits, which can compute PARITY exactly in depth 2 (exp size). Our techniques further suggest that, for boolean total functions, constant-depth quantum circuits do not necessarily provide more power than their classical counterparts. Our third result shows that depth 2 QAC0 circuits, regardless of size, cannot exactly synthesize an n-target nekomata state (a state whose synthesis is directly related to the computation of PARITY). This complements the depth 2 exponential size upper bound of Rosenthal (2021) for approximating nekomatas (which is used as a sub-circuit in the only known constant depth PARITY upper bound). Finally, we argue that approximating PARITY in QAC0, with significantly better than 1/poly(n) advantage on average, is just as hard as computing it exactly. Thus, extending our techniques to higher depths would also rule out approximate circuits for PARITY and related problems
A quantum algorithm to determine approximations of linear structures of Boolean functions is presented and analysed. Similar results have already been published (see Simon's algorithm) but only for some promise versions of the problem, and it has been shown that no exponential quantum speedup can be obtained for the general (no promise) version of the problem. In this paper, no additional promise assumptions are made. The approach presented is based on the method used in the Bernstein–Vazirani algorithm to identify linear Boolean functions and on ideas from Simon's period finding algorithm. A proper combination of these two approaches results here to a polynomial-time approximation to the linear structures set. Specifically, we show how the accuracy of the approximation with high probability changes according to the running time of the algorithm. Moreover, we show that the time required for the linear structure determine problem with high success probability is related to so called relative differential uniformityδfof a Boolean functionf. Smaller differential uniformity is, shorter time is needed.