The article discusses the features of modeling quantum cryptanalysis algorithms on a quantum scheme. Some engineering problems of the implementation of quantum cryptanalysis algorithms are shown and an analysis of possible ways of their solution is carried out. The uniqueness of quantum computation is shown due to the ability to carry out some non-trivial quantum computation using superposition, that is, it is possible to perform a series of mathematical operations, each of which operates with all stored data at the same time. The article discusses an algorithm for a quantum computer, which must initialize this vector in some specified form (depending on the model of the quantum computer). At each step of the algorithm, this vector is modified by a unitary matrix, which is determined by the physics of the device. It is proposed to consider the universal quantum gate as the quantum equivalent of the classical Boolean function from the universal set, which is a gate, and, acting on a qubit or their various combinations, can imitate the action of any other quantum gate. In the study of quantum algorithms, polynomial-time algorithms are found in problems for which no classical polynomial algorithms are known for their solution. For the required protection of quantum systems from decoherence errors and other quantum noise, methods of quantum error correction (QEC) have become widespread.
Distinguish between symmetric and asymmetric (public key) encryption algorithms. Symmetric encryption algorithms, for example, AES or RC6, are considered sufficiently strong if they are not known to crack them faster than brute force. The brute-force complexity (for an attack with a known ciphertext) can be estimated as O (2k), where k is the key length in bits. Considering that back in 2002, using the amateur network of distributed computing distributed.net, the possibility of cracking a 64-bit key by brute force was demonstrated, now the key length is considered to be 128 bits, and the maximum key length supported by the most symmetric crypto algorithms is 256 bits.
For asymmetric crypto algorithms, cryptanalysis methods are known that work much faster than full search. Because of this, asymmetric crypto algorithms have a key length much longer than symmetric ones. The most commonly used algorithm is RSA, based on the computational complexity of the problem of factorizing integers, and El-Gamal's algorithm, based on the computational complexity of the discrete logarithm problem. In this case, versions of the El-Gamal algorithm are used for various fields, for example, over a group of points of an elliptic curve. Consider possible quantum cryptanalysis algorithms for symmetric and asymmetric encryption schemes.
Consider the features of modeling quantum cryptanalysis algorithms on a quantum scheme. Let us show the differences between the mentioned algorithms and classical algorithms (the essence of the transformation of the well-known Church-Turing thesis into the Church-Turing-Deutsch thesis). Then we will point out some engineering problems in the implementation of quantum cryptanalysis algorithms and then analyze possible ways to solve them.
The authors of [
The research [
The article [
Authors [
The authors [
The work [
The authors [
In [
In [
A quantum analog of a bit (quantum bit, or qubit) has quantum mechanical features of behavior. Almost any quantum system (with at least two states) can act as a qubit. Its state space is the Hilbert space the linear hull spanned by two (or more) basis vectors (in Dirac's notation, quantum states are written as |0⟩ and |1⟩).
The general state of a quantum system with two states can be represented by a superposition of basis states | ⟩ = |0⟩ + |1⟩, wherein | |2+| |2 = 1 (Fig. 1).
Note that a register composed of L two-level qubits can simultaneously store up to 2L numbers in a quantum superposition. Therefore, if the register is replenished with additional qubits, then the amount of stored information in the register will increase exponentially. For example, a 250-qubit register with atomic dimensions will be able to store more numbers than there are atoms in the known universe (1078). Moreover, this is an understated estimate of the amount of quantum information contained in a quantum register, since the superposition vectors are in a continuously variable proportion - each with its own phase. Even so, if we measure the state of the register, we get only one of those numbers. However, the uniqueness of quantum computation lies in the fact that it is possible to carry out some non-trivial quantum computation using superposition - you can perform a series of mathematical operations, each of which operates on all the stored data at the same time.The state of the L-qubit register can be represented by a 2L-dimensional complex vector. An algorithm for a quantum computer must initialize this vector in some specified form (depending on the model of the quantum computer). At each step of the algorithm, this vector is modified by a unitary matrix, which is determined by the physics of the device. The unitarity of the matrix guarantees its reversibility (thus, each step is reversible). After the completion of the algorithm, the 2L-dimensional complex vector stored in the register must be read from the qubit register by quantum measurement. According to the laws of quantum mechanics, the result of this measurement will be a random string of L bits (and the measurement will destroy the final state). This random string can be used in calculating the function value because (according to the model) the probability distribution of the measured bit string is skewed towards the correct function value. By repeated runs of the quantum computer and then measuring the yield, the correct value can be determined with high probability (Fig. 2).
The quantum algorithm is performed by implementing a series of sequential unitary operations. Note that for a given algorithm, operations will always be performed in the same order. There is no "IF, THEN" logical condition to varying the sequence since there is no way to read the state of the qubit before the final measurement. But there are conditional operations implemented by the СNOT gate (Figure 3).
According to D. Deutsch, the following requirements are imposed on a quantum computer. A quantum computer is a set of n qubits, for which the following operations are practically defined: 1) Each qubit can be initialized in a known state (for example, the state |0⟩. 2) Each qubit can be measured in the basis {|0⟩, |1⟩}. 3) A universal quantum gate (or set of gates) can act on any limited subset of qubits. 4) The state of the qubits does not change except through the above transformations.
This description does not touch on certain technological aspects but contains the basic ideas for constructing a quantum computer.
Note that the theoretical model of quantum computing is networked and implies a sequential effect
of logical gates on a set of qubits. Logic gates of a classical electronic computer are located on a circuit
board separately from each other; in a quantum computer, logical gates are considered as interactions
of several qubits that occur at a certain time. In this case, qubits form a certain configuration, in which
there are fundamentally more options for interaction between elements than in a classical computer. It
is also possible to develop other models of quantum computing, for example, the cellular automaton
model [
The universal quantum gate is the quantum equivalent of the classical Boolean function from the universal set and is a gate that, acting on a qubit or their various combinations, can simulate the action of any other quantum gate. In 1985, D. Deutsch showed that fairly simple quantum gates can constitute a universal set that will be sufficient to build a quantum computer. For example, a pair of one-qubit gate V(θ, φ) and two-qubit gate “CNOT”, where V(θ, φ) is a gate of arbitrary rotation of one qubit: ( , )= ( CNOT can be represented by a matrix cos ( ) − −
sin ( ) − sin ( ) cos ( ) 2 2
), 2 1 0 0 0 2 0 1 0 0 0 0 0 1 0 0 0 1
) 2 −1 ∑ | ⟩.
=0 ∑ | |
2 = 1. 2 −1 =0 and can be considered a universal set. Any unitary n × n matrix can be formed by combining two-qubit CNOT gates and rotation gates of one qubit. A description of such universal gates can be found in D. Deutsch, S. Lloyd, D.P. di Vincenzo, and A. Barenzo
A quantum algorithm is an algorithm that uses the quantum properties of an object to process a computation. You can formalize the description of quantum computing in terms of the classical computing model. For example, logical operations on bits of computer memory according to Turing of classical computation are replaced by unitary transformations acting on a fixed finite number of qubits.
In the study of quantum algorithms, it turns out to be interesting to find polynomial-time algorithms
in problems for which no classical polynomial algorithms for their solution are known. According to
researchers [
Thus, quantum computers are based on quantum registers, which are made up of quantum bits (qubits). When measuring a quantum system, a quantum bit can have such a state that the measurement can show |0 with some probability, and show |1 with some other probability.
A quantum register consisting of n quantum bits has dedicated states corresponding to n bit binary numbers from |00K0 to |11K1. The state of a quantum register is written as a linear combination of all these highlighted states:
In this case, the normalization condition is satisfied:
The ax coefficients are complex numbers. They are called the amplitudes of the corresponding states |x. denoted as ⟨ | ⟩ and is introduced in the usual way: ⟨ | ⟩ = represent different values of an n-bit word at the same time.
The state of a system consisting of n quantum bits is described by a vector of unit length in a 2ndimensional complex unitary space (the scalar product of states | ⟩ = | 1K ⟩ and | ⟩ = | 1K ⟩ ∑ . Quantum register of length n, can
To extract information from a quantum register, a measurement must be made. Any set of quantum bits can be measured. In addition, since quantum states form Euclidean space, measurements can be made on different bases. However, the measurement leads to the transition of the system to the basic state corresponding to the measurement results.
A quantum computer can perform transformations on a quantum register. A quantum transformation is a mapping of a unitary space formed by a quantum system into itself. With quantum systems, only linear unitary transformations can be performed, and any linear unitary transformation is admissible. Due to linearity, quantum transformations are completely determined by their action based on vectors.
The engineering problems of the implementation of quantum cryptanalysis algorithms include keeping the computer elements in a relatively stable (coherent) state, as well as protecting against decoherence errors. The first problem is related to the fact that, in practice, the interaction of a quantum system with the outside world leads to a loss of coherence (otherwise, its decoherence), and, consequently, to an emergency shutdown of the computer. This effect leads to a violation of the unitary nature (or, more precisely, reversibility) of the quantum steps of the computation, which will soon be after the launch of the algorithm, as a result of which it will be impossible to solve complex problems of cryptanalysis.
The point is that the fourth point of D. Deutsch's requirements to a quantum computer on the
invariability of the state of a quantum system is, in principle, physically unrealizable [
In practice, it turned out that designing a quantum system in which the loss of coherence would occur less than once in a million uses of the XOR gate turned out to be a rather difficult engineering task. According to the researchers, it remains to be seen whether the laws of physics allow finding a lower limit on the rate of loss of coherence. This problem was identified in the works of S. Garoche and J.M. Raymond, R. Landauer, C. Miguel and A. Barenzo.
Thus, periodically projecting the state of the computer through carefully selected measurements is
not sufficient by itself. Therefore, for the required protection of quantum systems from decoherence
errors and other quantum noise, methods of quantum error correction (QEC) have become widespread
[20]. For quantum systems, were first proposed and considered in the works of E. Steen and,
independently of him, A.R. Kalderbank and P. Shor [
Scientists have noted the importance of quantum error correction for error-correcting quantum computing, not only to combat noise are stored quantum information but also to compensate for “noisy” quantum gates, as well as to compensate for imperfections in quantum measurement tools. Initially, it was not clear whether network data should be ideal when using error correction techniques. P. Shor showed how to make error correction networks insensitive to errors within these networks. In other words, it turned out that such "error correction" networks cancel out more interference than they create.
The discovery of the method of quantum error correction approximately coincided with the
emergence of the associated method of “entanglement enhancement”, which also provides
interferencefree transmission of quantum states over a noisy quantum channel [
The sender and receiver accumulate qubits and then perform a parity-checked measurement: for example, the receiver XOR the received and subsequent qubits and then measures the resulting qubit. After the sender performs identical operations on their qubits, they compare the results. If the results match, then the states of more than half of the unmeasured qubits coincide with the required one by chance: |00⟩ + |11⟩. If the results do not match, the qubits are discarded.
It is required to have its technical solutions with the maximum degree of localization of production
(both end devices and components) to eliminate the risk of introducing destructive hardware and
software (undeclared capabilities, NDV) into hardware and software, and, as a consequence, access to
protected information [
Thus, The study of user awareness as an element of predicting the targets of an attack has also
practical application as a study of the dynamics of changes in the landscape of security threats [
The article was prepared based on the results of research carried out with the support of the RFBR grant (No. 20-04-60080).