Patent Description:
A hash function is any function that can be used to map data of arbitrary size to fixed-size values. The values returned by the hash function are called hash values, hash codes, digests, or simply hashes. The hash functions and their associated hash tables are used in data storage and retrieval applications to reduce the amount of storage size, but also to ensure data integrity and authentication of messages.

Data integrity is the maintenance of, and the assurance of, data accuracy and consistency and is an aspect that needs to be considered in the design, implementation, and usage of any system that stores, processes, or retrieves data. The overall intent of a method, such as a hash function, for data integrity is to ensure that the data is recorded or stored exactly as intended and, upon later retrieval of the stored data, ensure the retrieved stored data is the same as when the data was originally stored. The hash function used for data integrity aims to prevent unintended (or unintentional) changes to information in the data stored.

Any unintended changes to the stored data as the result of a storage, retrieval or processing operation, including malicious intent, unauthorized access, unexpected hardware failure, and human error, is failure of data integrity. These unintended changes can be as benign as a single pixel in an image appearing with a different color than was originally recorded to the loss of vacation pictures or data from a business-critical database.

There are several reports about methods for breaking hash functions. For example, Laurent and Perrin presented a paper "SHA-<NUM> is a shamble" at the USENIX Security Conference in <NUM>. The paper is available at https://eprint. org/<NUM>/<NUM>. pdf (accessed on <NUM> November <NUM>). The reports about the methods for breaking hash functions are often presented in the context of the implications for security and consistency of data.

<NPL>, describes a variational quantum attack algorithm (VQAA) for classical advanced encryption standard (AES)-like symmetric cryptography, exemplified by the simplified-data encryption standard (S-DES).

<NPL> describes a secure one-way hash function built from DES.

<NPL>, provides a comparison between classical Tensor Networks and Tensor Network-inspired quantum circuits in the context of Machine Learning on simulated LHC data.

<CIT>, describes a method and system provided for optimizing parameters of a parametrized quantum Circuit (PQC) using machine learning to train a flexible initializer for arbitrarily-sized parametrized quantum circuits.

The following prior art documents are also of relevance:.

There are, however, cases in which it is desired to modify the stored data from which the hash function was generated but to maintain the original generated hash value. This has not been possible in the art, but the advent of quantum computing suggests that this may be practical in the future.

The application of quantum computing offers the potential to overcome this challenge using optimization algorithms. Currently we are in the noisy intermediate-scale quantum (NISQ) era at which real-life quantum computing systems are characterized by a number of restrictions, such as a low number of qubits, low fidelity, and shallow quantum circuits. Under these restrictions, various classical-quantum hybrid algorithms have been proposed, including the variational quantum algorithm (VQA) and the Quantum Approximate Optimization Algorithm (QAOA). VQA and QAOA quantum-classical hybrid algorithms have been found to have significant advantages in solving combinatorial optimization and Hamiltonian ground state problems.

This document will describe a computer-implemented method to attack hash functions and to generate a hash value from a modified document.

The method and system described in this document enables part of the data in a document, such as a variable string, to be modified in the document but still produce the same hash value when passed to a hash function generator.

The method for modifying the variable string in a document and generating a required hash value will now be outlined. The document comprises both the variable string and a fixed string. The term "string" is used in this context to indicate a sequence of characters in the document. The method comprises constructing a Hamiltonian based on the variable string and then encoding the variable string into a quantum circuit comprising a plurality of qubits. A hash function generator generates a hash value from the fixed string and the output of the quantum circuit. A measurement device measures a superposition of the variable string by a quantum state tomography implemented individually for the plurality of the qubits. Then an overlap is determined between the generated hash value and a true hash value. On reaching a zero-overlap (or a substantially zero overlap) value, the parameters of the quantum circuit are determined for the variable string, otherwise optimizing the parameters of the quantum circuit.

The step of optimising the parameters of the circuit uses a classical optimization algorithm, such as, but not limited to, a gradient descent method.

The encoding of the variable string into the quantum circuit is one of encoding into a parameterized quantum circuit or a tensor network and the constructing of the Hamiltonian comprises creating a graph with a plurality of nodes representing the bits of the variable string.

The determining of the overlap is carried out by calculating the Hamming distance between the generated hash value and the true hash value.

A system for modifying a variable string in a document and generating a required hash value is also disclosed. The system comprises at least one input/out device for inputting the document, at least one quantum circuit with a plurality of qubits for encoding the variable string, a hash function generator for creating hash values from an output of the at least one quantum circuit, a measurement device for measurement a superposition of the variable string by a quantum state tomography implemented individually for the plurality of the qubits, a comparator for comparing the created hash values with a true hash value, and at least one optimization element for adjusting the parameters of the quantum circuit.

The quantum circuit is implemented as one of a quantum annealer or a quantum gate computer and can be is implemented in a quantum computer or simulated in a classical computer.

The invention will now be described on the basis of the drawings. It will be understood that the embodiments and aspects of the invention described herein are only examples and do not limit the protective scope of the claims in any way. The invention is defined by the claims and their equivalents. It will be understood that features of one aspect or embodiment of the invention can be combined with a feature of a different aspect or aspects and/or embodiments of the invention.

<FIG> shows an overview of a typical hybrid classical-quantum system which can be used for performing the method set out in this document. <FIG> shows an overview of a computing system <NUM> for implementing the method of this document. The computing system <NUM> is, for example, a hybrid quantum and classical system and comprises, in an example, a (classical) central processing unit <NUM> which is connected to a data storage unit <NUM> (i.e., one or more memory devices), and a plurality of input/output devices <NUM>. The input/output devices <NUM> enable input of one or more images and an output of a result for the one or more of the images.

A graphics processing unit <NUM> for processing vector calculations and a field programmable gate array (FGPA) <NUM> for control logic that can also be connected to the central processing unit <NUM>. A quantum processor <NUM> (also termed quantum accelerator) is connected to the classical central processing unit <NUM>. In an alternative embodiment, the quantum processor <NUM> is emulated on a classical processor.

In one implementation of the computing system <NUM>, the quantum processor <NUM> is a gate-based quantum processor. Alternatively, the quantum processor <NUM> could be a quantum annealing processor. It is also possible to use a quantum processor <NUM> which is a quantum annealing system. The computing system <NUM> is connected to a computer network <NUM>, such as the Internet. It will be appreciated that the computing system <NUM> of <FIG> is merely exemplary and other units or elements may be present in the computing system <NUM>. It will also be appreciated that there may be many input/output (I/O) devices <NUM> located at multiple locations and that there may be a plurality of data storage units <NUM> also located at multiple locations. The many I/O devices <NUM> and data storage units <NUM> are connected by the computer network <NUM>.

The method is illustrated in <FIG> and will now be described. The method starts in step S200. A document <NUM> has two components: a fixed string <NUM> with a set of data, such as a sequence of characters or set of pixels, which do not need to be changed and a variable string <NUM> with a set of data which needs to be changed. One example of the variable string could be correction of data or the replacement of a signature on the document <NUM>.

In a first step S210, the document <NUM> with both the fixed string <NUM> and the variable string <NUM> is input into the system <NUM> through one (or more) of the input/output devices <NUM> and, in step S220, a Hamiltonian is constructed whose ground state corresponds to the variable string <NUM>. The construction of the Hamiltonian is outlined below.

The variable string <NUM> is encoded in step S220 into an adjustable quantum state by a quantum circuit which is in this case a parameterized quantum circuit (PQC) <NUM> (which is also known as an ansatz). PQC output <NUM> of the parameterized quantum circuit <NUM> is a superposition of values and read out in step S230 by a measurement device <NUM> and passed in step S240 as an input to a hash function generator <NUM> in the (classical) central processing unit <NUM>. The hash function generator <NUM> is not limited to particular hash functions. Non-limiting examples of hash functions include folding, division hashing, multiplicative hashing as well as other known hashing functions and indeed customized hash functions combining several known hash functions.

The hash function generator <NUM> takes as its input both the set of values from the PQC output <NUM> and the fixed string <NUM> and produces in step S250 a set of hash values which can be compared with a true hash value <NUM> in a comparator <NUM>. The comparator <NUM> produces a Hamiltonian of the Hamming distances between the true hash value <NUM> and the set of hash values produced by the hash function generator <NUM>.

The Hamiltonian is forward to a classical optimization algorithm <NUM> in the classical central processing unit <NUM>. The optimization algorithm is used to adjust in step S270 the input parameters of the parameterized quantum circuit <NUM> to arrange for the output of the hash function generator <NUM> to have an overlap with the true hash value <NUM> in step S280. The overlap occurs when the Hamming distance is zero (or very close to zero). At this point, the parameters of the parameterized quantum circuit <NUM> are known and the output of the hash function generator <NUM> can be used to create from the variable string <NUM> a hash value which is the same as the true hash value <NUM> despite having a different variable string <NUM>.

An example of the implementation of the VQAA will serve to illustrate this method. The variable string <NUM> is encoded in the Hamiltonian (step S220).

As noted above, the variational process (i.e., step S270) is started to find the lowest energy of the Hamiltonian. This is done by using each bit in the variable string <NUM> as a node to construct regular graphs. It is possible, for an <NUM>-node network, to construct an n-regular (where n=<NUM>, <NUM>. ,<NUM>) graph. In practice, it is chosen that n=<NUM> (although this is not limiting of the invention and other options may be also possible). It will be appreciated that the number of nodes is not limiting of the invention.

The known variable string <NUM> is encoded in the step S220 into the Hamiltonian ground state and this will now be described. Each of the eight bits of the variable string <NUM> is used as a node to construct an <NUM>-node <NUM>-regular graph. The value of the i-th node is denoted by V(i), which is the value of the i-th bit. If there is a pair of nodes (i, j) in the graph that are connected, the term wijZiZj is added into the Hamiltonian, where Z is the Pauli-Z operator, i, j ∈ {<NUM>, <NUM>,. The coefficient wij is determined by V (i) and V (j): wij = +<NUM> if V(i) = V(j), and -<NUM> otherwise. Additionally, the single-qubit terms ti Zi are added, such that ti = <NUM> if V(i) = <NUM>, and -<NUM> if V(i) = <NUM>. The resulting <NUM>-regular graph shown in <FIG>. The corresponding Hamiltonian is: <MAT>.

The cost function E(β) is the expectation value of the Hamiltonian where |β > is the superposition of the variable string <NUM>. The parameterized quantum circuit <NUM> is the ansatz shown in <FIG>. It will be appreciated, however, that other variational quantum circuits could be implemented as well without further restrictions. The exemplary implementation shown in <FIG> and described in this document requires ten parameters (β / θ) and its circuit depth is <NUM>. The initial state is prepared as the uniform superposition state. The PQC / ansatz <NUM> gives a linear combination of all possible values of the variable string.

On another implementation, the Hamiltonian is the Hamming distance between the bit strings.

The variational process starts to find the Hamiltonian with the lowest energy. This Hamiltonian with the lowest energy state is expected to contain the corresponding key. The superposition of the variable string <NUM> is measured in step S240 and the result is forwarded in step <NUM> to a classical optimization algorithm <NUM> running on a classical central processing unit <NUM> to adjust the input parameters of the quantum circuit <NUM>. This variational process (adjusting the input parameters of the quantum circuit <NUM>) continues until a zero overlap with the true hash value <NUM> is found.

In one non-limiting implementation, the classical optimization algorithm with best results is the Gradient Descent method with cut-off condition of -<NUM>, i.e., when the expectation of the Hamiltonian is less than -<NUM>, the first excited energy. GD is restarted when the norm of the gradient is lower than <NUM>, the moment in which the parameters are randomly initialized. The learning rate is set to <NUM>.

The VQAA can be improved in terms of better classical optimization algorithm, such as Adaptive Moment Estimation Algorithm (ADAM), better ansatz (less sequential ansatz to increase entanglement, in search) and better initial parameters (learning rate, cut-off condition, initial state).

In a further aspect, the method can be implemented using a quantum annealer, such as those from D-Wave, as the quantum processor <NUM>. The quantum annealer is used to generate the variational states for the qubits (note: no non-orthogonal basis in this case). The variational parameters are the couplings of the D-Wave Hamiltonian and other annealing parameters (such as, but not limited to annealing schedule, extra magnetic fields).

A further aspect is the use of non-orthogonal qubit states: Current NISQ quantum devices have a limited number of qubits (as noted above) and are therefore only able to handle a small number of qubit variables. For current variational quantum algorithms in gate-based quantum computers, one qubit of the quantum computer is typically assigned to one bit variable of the cost function. The largest gate-based quantum computer as of today, built by IBM, has <NUM> superconducting qubits. Therefore, with the current approach, it is possible to optimize the cost functions up to <NUM> bits.

Current variational quantum optimization algorithms are based on e.g., Variational Quantum Eigensolvers (VQE). This approach fits very well into NISQ devices but is very hard to scale up to those cost functions involving many bits. This is because, in the current approach, each bit variable in the cost function corresponds to one qubit in the NISQ device. The NISQ devices have a limited number of qubits, and this limited number limits the applicability to large, realistic cost functions. This is limiting in cybersecurity applications.

One idea to overcome the problem of limited number of qubits is to modify the assignment between the quantum state of each individual qubit and the corresponding variable in the cost function. The method set out above has the correspondence as follows: |<NUM>〉→<NUM>, |<NUM>〉→<NUM>. In other words, a measurement in the <NUM>/<NUM> basis provides immediately the value of the bit variable. It is possible to extend the representability of classical discrete variables using different non-orthogonal states of one qubit. In particular, p maximally orthogonal states of one qubit could represent the values of a classical variable q = <NUM>, <NUM>,. The maximally orthogonal states of one qubit correspond to Platonic solids inside of the Bloch sphere of the qubit, as illustrated in <FIG>.

Using this Bloch sphere representation, it is possible to fit much larger optimization problems in variational quantum algorithms in the NISQ devices for cybersecurity attacks. As an example, for a processor of <NUM> qubits, with <NUM> states per qubit, it would be possible to optimize cost functions of up to <NUM>,<NUM>-bit variables.

To implement an improved variational optimization algorithm such as in VQAA using the qubit states as in <FIG>, it is necessary to slightly modify the measurement at the end of the quantum circuit. In this implementation of the algorithm, instead of implementing a measurement in the computational <NUM>/<NUM> basis, a quantum state tomography is implemented individually for the qubits. Quantum state tomography is a technique that determines, via measurements, the exact individual quantum state of a qubit in the Bloch sphere. In this way, the readout of the measurements would not be <NUM>/<NUM>, but rather the quantum state of each qubit in their respective Bloch spheres, which would correspond, for each qubit, to some state as the ones in <FIG>.

Other non-orthogonal encodings can also be used, including polyhedral, discretized qubit angles and continuum optimization.

It will be further appreciated that the use of the quantum variational circuits <NUM> could be replaced by tensor networks. In this case, the variable string <NUM> is encoded into the tensor network and the values of the tensors in the tensor networks are updated using gradient descent.

The search can also be parallelized by using more than one quantum variational circuit <NUM> to search for minima.

Claim 1:
A computer-implemented method for modifying a variable string (<NUM>) in a document (<NUM>) and generating a required hash value, wherein the document (<NUM>) comprises the variable string (<NUM>) and a fixed string (<NUM>), the method comprising:
- constructing (S220) a Hamiltonian based on the variable string (<NUM>);
- encoding (S230) the variable string (<NUM>) into a quantum circuit (<NUM>) comprising a plurality of qubits;
- generating in a hash function generator (<NUM>) a hash value from the fixed string (<NUM>) and the output of the quantum circuit (<NUM>);
- measuring a superposition of the variable string (<NUM>) by a measurement device (<NUM>), wherein the measuring is implemented by a quantum state tomography individually for the plurality of the qubits;
- determining (S280) an overlap between the generated hash value and a true hash value (<NUM>); and
- on reaching a zero overlap value, determining the variable string (<NUM>), otherwise optimising (S270) parameters of the quantum circuit (<NUM>).