DETAILED ACTION
This action is written in response to the application filed 2/7/23. The present application, filed on or after March 16, 2013, is being examined under the first inventor to file provisions of the AIA .
Double Patenting
The nonstatutory double patenting rejection is based on a judicially created doctrine grounded in public policy (a policy reflected in the statute) so as to prevent the unjustified or improper timewise extension of the “right to exclude” granted by a patent and to prevent possible harassment by multiple assignees. A nonstatutory double patenting rejection is appropriate where the conflicting claims are not identical, but at least one examined application claim is not patentably distinct from the reference claim(s) because the examined application claim is either anticipated by, or would have been obvious over, the reference claim(s). See, eg, In re Berg, 140 F.3d 1428, 46 USPQ2d 1226 (Fed. Cir. 1998).
A timely filed terminal disclaimer in compliance with 37 CFR 1.321(c) or 1.321(d) may be used to overcome an actual or provisional rejection based on nonstatutory double patenting provided the reference application or patent either is shown to be commonly owned with the examined application, or claims an invention made as a result of activities undertaken within the scope of a joint research agreement. See MPEP § 717.02 for applications subject to examination under the first inventor to file provisions of the AIA as explained in MPEP § 2159. A terminal disclaimer must be signed in compliance with 37 CFR 1.321(b).
The filing of a terminal disclaimer by itself is not a complete reply to a nonstatutory double patenting (NSDP) rejection. A complete reply requires that the terminal disclaimer be accompanied by a reply requesting reconsideration of the prior Office action. Even where the NSDP rejection is provisional the reply must be complete. See MPEP § 804, subsection I.B.1. For a reply to a non-final Office action, see 37 CFR 1.111(a). For a reply to final Office action, see 37 CFR 1.113(c). A request for reconsideration while not provided for in 37 CFR 1.113(c) may be filed after final for consideration. See MPEP §§ 706.07(e) and 714.13.
The USPTO Internet website contains terminal disclaimer forms which may be used. Please visit www.uspto.gov/patent/patents-forms. The actual filing date of the application in which the form is filed determines what form (e.g., PTO/SB/25, PTO/SB/26, PTO/AIA /25, or PTO/AIA /26) should be used. A web-based eTerminal Disclaimer may be filled out completely online using web-screens. An eTerminal Disclaimer that meets all requirements is auto-processed and approved immediately upon submission. For more information about eTerminal Disclaimers, refer to www.uspto.gov/patents/apply/applying-online/eterminal-disclaimer.
Claims 1-6 and 8-10 are provisionally rejected on the ground of nonstatutory double patenting as being unpatentable over the corresponding claims of copending application 18/088042. Although the claims at issue are not identical, they are not patentably distinct from each other for the reasons outlined in the table below. This is a provisional rejection because the claims of the copending application have not been patented.
This application – 18/106555
Copending application 18/088042
1. A computer-implemented method for modifying a variable string in a document and generating a required hash value, wherein the document comprises the variable string and a fixed string, the method comprising:
1. A method for determining an encryption key in a key space for encrypting a plain text to a corresponding encrypted ciphertext, the method comprising:
- constructing a Hamiltonian based on the variable string;
- constructing a Hamiltonian based on the encrypted ciphertext;
- encoding the variable string into a quantum circuit;
- encoding the key space into a quantum circuit;
- generating in a hash function generator a hash value from the fixed string and the output of the quantum circuit;
- encrypting the plain text using the quantum circuit to obtain a superposition of ciphertexts;
[The Examiner notes that a hash function is one way to encrypt / encode data.]
- determining an overlap between the generated hash value and a true hash value; and
- measuring the superposition of ciphertexts and determining an overlap between the measured superposition of ciphertexts and the encrypted ciphertext;
Note: The claims in the ‘042 application pertain to encryption breaking, instead of hash breaking in the instant application. However, the Preston reference shows that analogous techniques can be used to address both problems. See citations infra in prior art mapping for claim 1.
- on reaching a zero overlap value, determining the variable string, otherwise optimising parameters of the quantum circuit.
- on reaching a pre-determined overlap value, collapsing the key space to determine the encryption key, otherwise adjusting parameters of the quantum circuit; and
wherein the measuring the superposition of ciphertexts is performed at a measurement element in the key space by quantum state tomography, wherein the step of adjusting the parameters of the circuit comprises using a classical optimization algorithm.
As illustrated in the table above, every limitation in this application has a corresponding equivalent or more specific limitation in the ‘042 application, with the exception of the application to hash functions, which the Examiner addresses above.
At the time of filing, it would have been obvious to a person of ordinary skill to apply the techniques of the ‘042 claim to hash function breaking because there is considerable overlap in the two problems: both are black-box functions can be addressed by quantum optimization algorithms. See eg Preston, p. 1, background:“Grover’s algorithm can reverse a black-box function implemented as a quantum oracle in O(√N) iterations with O(log2 N) qubits, with N being the number of possible input combinations to the function [1]. In this context, the quantum oracle phase flips a target qubit when the desired output is produced (e.g., when the password is correct). Grover’s algorithm searches for the input(s) that cause the phase flip to occur.”
Independent claim 8 recites an analogous system.
The correspondence in dependent claims is illustrated in the table below.
This application – 18/106555
Copending application 18/088042
2. The method of claim 1, wherein the step of optimising the parameters of the circuit comprises using a classical optimization algorithm.
[from claim 1]
wherein the measuring the superposition of ciphertexts is performed at a measurement element in the key space by quantum state tomography, wherein the step of adjusting the parameters of the circuit comprises using a classical optimization algorithm.
3. The method of claim 2, wherein the classical optimization algorithm is a gradient descent method.
3. The method of claim 1,wherein the classical optimization algorithm is a gradient descent method.
4. The method of claim 1, wherein the encoding of the variable string into the quantum circuit is one of encoding into a parameterized quantum circuit or a tensor network.
4. The method of claim 1, wherein the encoding of the key space into the circuit is one of encoding into a parameterized quantum circuit or a tensor network.
5. The method of claim 1, wherein the constructing of the Hamiltonian comprises creating a graph with a plurality of nodes representing the bits of the variable string.
5. The method of claim 1, wherein the constructing of the Hamiltonian comprises creating a graph with a plurality of nodes representing the bits of the encrypted ciphertext.
6. The method of claim 5, wherein the graph is a 3-regular graph.
6. The method of claim 5, wherein the graph is a 3-regular graph.
As illustrated in the table above, every claim limitation in this application has a corresponding equivalent limitation in the ‘042 application.
Claim Rejections - 35 USC § 103
The following is a quotation of 35 U.S.C. 103(a) which forms the basis for all obviousness rejections set forth in this Office action:
(a) A patent may not be obtained though the invention is not identically disclosed or described as set forth in section 102 of this title, if the differences between the subject matter sought to be patented and the prior art are such that the subject matter as a whole would have been obvious at the time the invention was made to a person having ordinary skill in the art to which said subject matter pertains. Patentability shall not be negatived by the manner in which the invention was made.
The following are the references relied upon in the rejections below:
Wang (Wang Z G, Wei S J, Long G-L, et al. Variational quantum attacks threaten advanced encryption standard based symmetric cryptography. Sci China Inf Sci, 2022, 65(10): 200503. Cited by Applicant in IDS dated 10/31/23.)
Preston (Preston, Richard H. "Applying Grover's algorithm to hash functions: a software perspective." IEEE transactions on quantum engineering 3 (2023): 1-10. Published online 10 January 2023.)
Sobti (Sobti, Rajeev, and Ganesan Geetha. "Cryptographic hash functions: a review." International Journal of Computer Science Issues (IJCSI) 9, no. 2 (2012): 461.)
Claims 1-6 and 8-10 are rejected under 35 U.S.C. 103 as being unpatentable over Wang and Preston.
Regarding claims 1 and 8, Wang discloses a computer-implemented method (and an analogous system) for modifying a variable string in a document and generating a required hash value, wherein the document comprises the variable string and a fixed string, the method comprising:
- constructing a Hamiltonian based on the variable string;
P. 2, sec. 3, “The main idea of our VQAA is shown in Figure 2. Based on a pair of known ciphertext and plaintext, the associated Hamiltonian is designed, whose ground state is the ciphertext. The parameterized quantum circuit gives a linear combination of all possible keys.”
Figure 2 (reproduced below).
PNG
media_image1.png
566
1224
media_image1.png
Greyscale
- encoding the variable string into a quantum circuit;
P. 2, sec. 3, “Secondly, the key space is encoded into an adjustable quantum state by a parameterized quantum circuit which is also known as ansatz.”
- generating in a … function generator a … value from the fixed string and the output of the quantum circuit;
P. 2, sec. 3, “Next, the output of the parameterized quantum circuit is used as a key to encrypt the known plaintext based on the S-DES, and then the superposition of ciphertexts is obtained.”
- determining an overlap between the generated … value and a true … value; and
P. 2, sec. 3, “Finally, we measure the superposition of ciphertexts and forward the result to the classical optimization algorithm.”
- on reaching a zero overlap value, determining the variable string, otherwise optimising parameters of the quantum circuit.
P. 2, sec. 3, “By using the optimization algorithm, we adjust the input parameters of the parameterized quantum circuit to arrange for the superposition ciphertext state to have a considerable overlap with the known ciphertext. When the result of measurement is the known ciphertext, the key space also collapses to the required key state.”
Preston discloses the following further limitation which Wang does not disclose:
- generating in a hash function generator a hash value from the fixed string and the output of the quantum circuit;
P. 1, introduction, “Consider the following scenario. On a certain banking website, customers log in by entering their username and password. Before being sent to the server for authentication, the password is salted (random data is appended) and then passed through a cryptographic hash function.1Suppose an attacker gains access to the plaintext hash and salt. Assuming an ideal hash function, the only way to recover the original password is with guess-and-check, a.k.a. brute force. For an eight-character password consisting of random characters, the attacker would have to check approximately 264 = 1.8 × 1019 combinations. At a rate of 1 billion checks per second, it would take on average 292 years to find the password, at which point it is probably useless.But what if the attacker had access to a powerful quantum computer? With Grover’s algorithm, the password could be found directly in √ 264 = 4.3 × 109 iterations [1].” (Emphasis added.)
See also p. 1, sec. 1, “2) Apply H to each input qubit”.
In summary, Wang is directed to using quantum computing techniques to breaking encryption, whereas Preston is directed to using quantum techniques to breaking hash functions. At the time of filing, it would have been obvious to a person of ordinary skill to apply the techniques disclosed by Wang to the problem of breaking hash functions (as described throughout Preston) because there is considerable overlap in the two problems: both are black-box functions can be addressed by quantum optimization algorithms. See eg Preston, p. 1, background:
“Grover’s algorithm can reverse a black-box function implemented as a quantum oracle in O(√N) iterations with O(log2 N) qubits, with N being the number of possible input combinations to the function [1]. In this context, the quantum oracle phase flips a target qubit when the desired output is produced (e.g., when the password is correct). Grover’s algorithm searches for the input(s) that cause the phase flip to occur.”
Regarding independent claim 8, the above mapping of claim 1 applies equally to this claim. Its further limitation “at least one input/out device for inputting the document” is inherent in the Wang disclosure.
Regarding claim 2, Wang discloses the following further limitation wherein the step of optimising the parameters of the circuit comprises using a classical optimization algorithm.
P. 2, sec. 3, “We now demonstrate how to carry out a quantum attack on the S-DES using the VQAA as an example. The plaintext and ciphertext are represented by 8-bit quantum states. Firstly, we construct the Hamiltonian whose ground state corresponds to the ciphertext. The detailed construction of the Hamiltonian is assumed to be given. Secondly, the key space is encoded into an adjustable quantum state by a parameterized quantum circuit which is also known as ansatz. Next, the output of the parameterized quantum circuit is used as a key to encrypt the known plaintext based on the S-DES, and then the superposition of ciphertexts is obtained. Finally, we measure the superposition of ciphertexts and forward the result to the classical optimization algorithm.” (Emphasis added.)
Regarding claim 3, Wang discloses the following further limitation wherein the classical optimization algorithm is a gradient descent method.
P. 6, sec. 3.3, “We use two methods to optimize the parameters, namely the gradient descent method and the Nelder-Mead (N-M) method”. (Emphasis added.)
Regarding claim 4, Wang discloses the following further limitation wherein the encoding of the variable string into the quantum circuit is one of encoding into a parameterized quantum circuit or a tensor network.
P. 2, “In our design, the parameterized quantum circuit (PQC) operates on the key space, and the cost function is designed according to the known ciphertext.”.
Regarding claim 5, Wang discloses the following further limitation wherein the constructing of the Hamiltonian comprises creating a graph with a plurality of nodes representing the bits of the variable string.
P. 3, sec. 3.1, “In order to encode the known ciphertext into a Hamiltonian ground state, we use each bit as a node to construct regular graphs. For an 8-node network, we can construct an n-regular (n = 1, 2, . . . , 7) graph. The value of the i-th node is denoted by V (i), which is the value of the i-th bit.” (Emphasis added.)
P. 4, “Because a large ratio implies that the gradient changes rapidly in the vicinity of the minimum value, the optimization path tends to lean more toward the neighborhood of the minimum. The simulations in Appendix B prove our prediction. The optimization works best when n = 3. The 3-regular graph we use is shown in Figure 3.” (Emphasis added.)
Regarding claim 6, Wang discloses the following further limitation wherein the graph is a 3-regular graph.
P. 4, “Because a large ratio implies that the gradient changes rapidly in the vicinity of the minimum value, the optimization path tends to lean more toward the neighborhood of the minimum. The simulations in Appendix B prove our prediction. The optimization works best when n = 3. The 3-regular graph we use is shown in Figure 3.” (Emphasis added.)
Regarding claim 9, Wang discloses the following further limitation wherein the quantum circuit is implemented as one of a quantum annealer or a quantum gate computer.
P. 5, fig. 4, illustrating a quantum gate computer.
PNG
media_image2.png
396
1098
media_image2.png
Greyscale
Regarding claim 10, Wang discloses the following further limitation wherein the quantum circuit is implemented in a quantum computer or simulated in a classical computer.
P. 5, fig. 4 (reproduced supra) illustrating a quantum gate computer.
P. 6, describing classic simulations.
Claim 7 is rejected under 35 U.S.C. 103 as being unpatentable over Wang, Preston and Sobti.
Regarding claim 7, Sobti discloses the following further limitation which neither Wang/Preston discloses wherein the determining is carried out by calculating the Hamming distance between the generated hash value and the true hash value.
P. 467, sec. 5.3.1, describing using “hamming distance” for evaluating collision / near collision for hash functions.
At the time of filing, it would have been obvious to a person of ordinary skill to apply the technique disclosed by Sobti for using Hamming distance to compare hash outputs to the combined system of Wang/Preston because the former is a widely-used metric for performing such evaluations, providing for optimization of hash-breaking functions. (See eg discussion of hash breaking in Sobti at p. 466, sec. 5.3.) All three disclosures pertain to cryptography.
Additional Relevant Prior Art
The following references were identified by the Examiner as being relevant to the disclosed invention, but are not relied upon in any particular prior art rejection:
Sadeghi discloses a survey of broken hashing algorithms, including quantum attacks (see p. 3, second col.). (Sadeghi-Nasab, Alireza, and Vahid Rafe. "A Comprehensive Review on Broken Hashing Algorithms." Undated. 11 pages.)
Conclusion
Any inquiry concerning this communication or earlier communications from the examiner should be directed to Vincent Gonzales whose telephone number is (571) 270-3837. The examiner can normally be reached on Monday-Friday 7 a.m. to 4 p.m. MT. If attempts to reach the examiner by telephone are unsuccessful, the examiner’s supervisor, Miranda Huang, can be reached at (571) 270-7092.
Information regarding the status of an application may be obtained from the USPTO Patent Center. Unpublished application information in Patent Center is available to registered users. To file and manage patent submissions in Patent Center, visit: https://patentcenter.uspto.gov.
/Vincent Gonzales/Primary Examiner, Art Unit 2124