DETAILED ACTION
This communication is responsive to the application # 18/916,605 filed on October 15, 2024. Claims 1-30 are pending and are directed toward a QUANTUM-SAFE DIGITAL SIGNATURE METHOD AND SYSTEM.
Notice of Pre-AIA or AIA Status
The present application, filed on or after March 16, 2013, is being examined under the first inventor to file provisions of the AIA . In the event the determination of the status of the application as subject to AIA 35 U.S.C. 102 and 103 (or as subject to pre-AIA 35 U.S.C. 102 and 103) is incorrect, any correction of the statutory basis for the rejection will not be considered a new ground of rejection if the prior art relied upon, and the rationale supporting the rejection, would be the same under either status.
Claims interpretation
Claims recite a mathematical concept determined to recite a mathematical concept because the claims explicitly recite a mathematical formula or calculation.
The analysis of eligibility based on example 41 for subject matter eligible under the 2019 PEG is provided:
Step
Analysis
1: Statutory Category?
Yes. The claim recites a series of steps and, therefore, is a process.
2A - Prong 1: Judicial Exception Recited?
Yes. The claim recites a mathematical formula or calculation that is used for verifying authenticity of digital cryptographic communications received from a sending device over a data network. Thus, the claim recites a mathematical concept determined to recite a mathematical concept because the claim explicitly recites a mathematical formula or calculation.
2A - Prong 2: Integrated into a Practical Application?
Yes. The combination of additional elements in the claim integrates the exception into a practical application. In particular, the combination of additional elements uses the mathematical formulas and calculations in a specific manner that sufficiently limits the use of the mathematical concepts to the practical application of transmitting the ciphertext word signal to a computer terminal over a communication channel. Thus, the mathematical concepts are integrated into a process that secures private network communications.
Conclusion: Claims are eligible.
Claim Rejections - 35 USC § 112
The following is a quotation of 35 U.S.C. 112(d):
(d) REFERENCE IN DEPENDENT FORMS.—Subject to subsection (e), a claim in dependent form shall contain a reference to a claim previously set forth and then specify a further limitation of the subject matter claimed. A claim in dependent form shall be construed to incorporate by reference all the limitations of the claim to which it refers.
The following is a quotation of pre-AIA 35 U.S.C. 112, fourth paragraph:
Subject to the following paragraph [i.e., the fifth paragraph of pre-AIA 35 U.S.C. 112], a claim in dependent form shall contain a reference to a claim previously set forth and then specify a further limitation of the subject matter claimed. A claim in dependent form shall be construed to incorporate by reference all the limitations of the claim to which it refers.
Claim 20 is rejected under 35 U.S.C. 112(d) because it has the same scope as Claim 12, as the limitation “variable a is arbitrarily selected” may be any variable in the finite field GFp.
Claim Rejections - 35 USC § 103
The following is a quotation of 35 U.S.C. 103 which forms the basis for all obviousness rejections set forth in this Office action:
A patent for a claimed invention may not be obtained, notwithstanding that the claimed invention is not identically disclosed as set forth in section 102, if the differences between the claimed invention and the prior art are such that the claimed invention as a whole would have been obvious before the effective filing date of the claimed invention to a person having ordinary skill in the art to which the claimed invention pertains. Patentability shall not be negated by the manner in which the invention was made.
Claims 1-24 and 27-30 are rejected under 35 U.S.C. 103 as being unpatentable over Kuang et al., (A new quantum‑safe multivariate polynomial public key digital signature algorithm, Scientific Reports | (2022) 12:13168, August 01, 2022, 21 pages), in view of Doroz (Accelerating Fully Homomorphic Encryption in Hardware, IEEE, VOL. 64, NO. 6, JUNE 2015, pages 1509-1521), hereinafter referred to as Kuang and Doroz.
As per claim 1, Kuang teaches a method of operating a computing apparatus for verifying authenticity of digital cryptographic communications received from a sending device over a data network (MPPK/DS is a digital signature and verification scheme that uses public keys. Kuang, page 3), the method comprising:
receiving a signed message from the sending device, the signed message including (i) a digital asset represented by an integer x0 and (ii) a signature, the signature including data elements represented by integers F and H (A digital signature scheme is specified by a pair of algorithms. There are two parties: a signer and a verifier. To sign a message μ , the signer uses a signing private key s and an algorithm Ss() to create a message-digital signature pair (μ, t) = Ss(μ) . the signer sends the pair (μ, t) . Kuang, page 4);
obtaining a public key associated with a private key that is unknown to the computing apparatus, the public key including data elements represented by integers sp, sq, pij′, qij′, μij and vij, i=0 to n+λ, j=1 to m, with λ, n and m being predetermined integers stored in a memory of the computing apparatus (Upon reception of a message-digital signature pair (μ′, t′) , the verifier uses a public key v, corresponding to s, and a signature verifying algorithm Vv() to evaluate if t′ is a matching digital signature for μ . Kuang, page 4);
verifying, based on the signature, the public key and the digital asset, whether a validation equation holds true (When there is a match, the evaluation Vv(μ′) returns (μ′,VALID) , otherwise it yields (μ′, INVALID). Kuang, page 4), Kuang teaches MPPK (Equations 10 and 11, Kuang, page 5 ), but does teach reduction, Doroz however teaches wherein the validation equation comprises:
∑i=0n+λUij(H)x0i=∑i=0n+λVij(F)x0i,j=1tom,where Uij(H)=Hp′ij-sp⌊Hμij/R⌋modp Vij(F)=Fq′ij-sq⌊Fvij/R⌋modp; (Modular reduction. We may use Barrett Modular Reduction (BMR) algorithm [17] to compute r x ðmod MÞ as following:
In the equation b is the radix and other parameters are k ¼ logbM þ 1 and m ¼ bb2k=Mc. According to [17] r has the following equality: r < 3M. Therefore; after evaluating r, first we check if it is negative and perform r ¼ r þ bkþ1 and later we subtractM from r whileM < r. Doroz, page 3)
wherein p is a predetermined integer stored in the memory of the computing apparatus and wherein R is predetermined power of 2 stored in the memory of the computing apparatus (In Barrett Reduction, the result is evaluated using two large integer multiplications and a few subtractions. The values m and M are stored in NTT form to avoid conversion costs. Selecting b ¼ 264 simplifies the arithmetic. Doroz, page 6);
Kuang in view of Doroz are analogous art to the claimed invention, because they are from a similar field of endeavor of systems, components and methodologies for providing secure communication between computer systems. It would have been obvious to a person of ordinary skill in the art before the effective filing date of the claimed invention to modify Kuang in view of Doroz. This would have been desirable because Claimed formulas are the same, and transformed by Barrett reduction.
Kuang in view of Doroz further teaches in case the validation equation holds true for all values of j=1 to m, concluding that the signature was derived from the digital asset and the private key, whereby the signature is considered authentic (Signature verifying algorithm. All arithmetic is done modulo ϕ(p) , unless specified otherwise. Upon receiving a message (or the hash of a message) μ and a corresponding signature (A, B, C, D, E) from a signer, the verifier applies the signature verifying algorithm using the signer’s public key v. Kuang, page 6);
outputting on a network or storing in the memory of the computing apparatus an indication that the signature is considered authentic (Given a message μ , a public key v and corresponding private key s we have Vv(Ss(μ)) = (m,VALID). Kuang, page 6).
As per claim 2, Kuang in view of Doroz teaches the method of claim 1, in case the validation equation does not holds true for at least one value of j=1 to m, concluding that the signature was not derived from the digital asset and the private key, whereby the signature is considered forged (otherwise it yields (μ, INVALID). Kuang, page 6).
As per claim 3, Kuang in view of Doroz teaches the method of claim 1, carried out for each digital asset forming a segment of a hashed original message (Upon receiving a message (or the hash of a message) μ and a corresponding signature (A, B, C, D, E) from a signer, the verifier applies the signature verifying algorithm using the signer’s public key v. Kuang, page 6).
As per claim 4, Kuang in view of Doroz teaches the method of claim 1, wherein the predetermined integer p is selected to be a prime number (Moreover, by using a clever choice of prime p associated with a finite field Fp that has form p = 2xq + 1 , where q is a large prime, and special choice of the coefficients of the publicly available polynomials, we make it hard for an attacker to find private key components modulo ϕ(p) , and exponentially difficult to lift the solutions found modulo q and 2x to the ring Z/ϕ(p)Z. Kuang, page 1).
As per claim 5, Kuang in view of Doroz teaches the method of claim 1, wherein R is a base for a Barrett reduction algorithm and μij and vij are Barrett parameters (reduction operations, such as bx=bk_1c and x mod bkþ1, are accomplished by loading from different memory address. For division, bits are read from bk_1 to most significant bit and for modular arithmetic, bits are read from least significant to bkþ1. Doroz, page 7).
Kuang in view of Doroz are analogous art to the claimed invention, because they are from a similar field of endeavor of systems, components and methodologies for providing secure communication between computer systems. It would have been obvious to a person of ordinary skill in the art before the effective filing date of the claimed invention to modify Kuang in view of Doroz. This would have been desirable because The values m and M are stored in NTT form to avoid conversion costs. Selecting b ¼ 264 simplifies the arithmetic (Doroz, page 6).
As per claim 6, Kuang in view of Doroz teaches the method of claim 5, wherein R=2K, where K>>log2n or K>>lS.( In the equation b is the radix and other parameters are k ¼ logbM þ 1 and m ¼ bb2k=Mc. According to [17] r has the following equality: r < 3M. Therefore; after evaluating r, first we check if it is negative and perform r ¼ r þ bkþ1 and later we subtractM from r whileM < r. Doroz, page 3)
Kuang in view of Doroz are analogous art to the claimed invention, because they are from a similar field of endeavor of systems, components and methodologies for providing secure communication between computer systems. It would have been obvious to a person of ordinary skill in the art before the effective filing date of the claimed invention to modify Kuang in view of Doroz. This would have been desirable because The values m and M are stored in NTT form to avoid conversion costs. Selecting b ¼ 264 simplifies the arithmetic (Doroz, page 6).
As per claim 7, Kuang in view of Doroz teaches the method of claim 1, wherein the signed message further includes the public key (MPPK/DS has its own public-key and private-key operations. A key generation algorithm produces a private key and a corresponding public key. Doroz, page 4).
As per claim 8, Kuang in view of Doroz teaches the method of claim 1, further comprising obtaining the public key over the data network from the sending device (Upon receiving a message (or the hash of a message) μ and a corresponding signature (A, B, C, D, E) from a signer, the verifier applies the signature verifying algorithm using the signer’s public key v. Doroz, page 4).
As per claim 9, Kuang in view of Doroz teaches the method of claim 1, further comprising obtaining the public key over the data network from a key generation computer (Key generation can also be addressed explicitly. Hence, MPPK/DS comprises three algorithms: key generation, signing and signature verifying. They are respectively described in "Key generation algorithm", "Signing algorithm" and "Signature verifying algorithm". Doroz, page 4).
Claims 10-23 have limitations similar to those treated in the above rejection, and are met by the references as discussed above, and are rejected for the same reasons of obviousness as used above.
As per claim 24, Kuang in view of Doroz teaches A process for operating a computing apparatus to generate a private-public key pair, the private key for use in a signing process for creating a signed message from a digital asset, the signed message including the digital asset and a signature, and the public key for use in a verification process for authenticating the signature based on the public key, the signature and the digital asset (Key generation algorithm. MPPK/DS has its own public-key and private-key operations. A key generation algorithm produces a private key and a corresponding public key. Said algorithm is described in this subsection. The algorithm has the following security parameters, Kuang, page 4), the process comprising: a) selecting coefficients of a multivariate base polynomial B(x0, x1, . . . , xm) of order n for x0, where n and m are selected integers stored in the memory of the computing apparatus; b) selecting polynomials f(·) and h(·) of degree λ, where λ is a selected integer stored in the memory of the computing apparatus; c) constructing a pair of polynomials, p(x0, x1, . . . , xm) and q(x0, x1, . . . , xm), by multiplying the base polynomial B(x0, x1, . . . , xm) with the polynomials f(·) and h(·), respectively:
p(x0,x1,...,xm)=B(x0,x1,...,xm)f(x0)=∑j=1mpj(x0)xj q(x0,x1,...,xm)=B(x0,x1,...,xm)h(x0)=∑j=1mqj(x0)xj wherepj(x0)=∑i=0n+λpijx0iandqj(x0)=∑i=0n+λqijx0i
such that pij and qij are defined as follows: pij=∑s+t=ifsbtj qij=∑s+t=ihsbtj
d) selecting two co-prime pairs (sp, Rp) and (sq, Rq)
e) computing the following: Pij=Rp pij mod Sp Qij=Rq qij mod Sq
f) creating the private key as including the following data elements: the coefficients of the polynomial f(·)
the coefficients of the polynomial h(·) sp, sq, Rp and Rq
g) composing the public key as including the following data elements: sp=βSpmodp sq=βSqmodp p′ij=βPijmodp q′ij=βQijmodp μij=⌊RPijSp⌋ vij=⌊RQijSq⌋
where: R is a power of 2, and β is arbitrarily selected over the finite field GF(p) (Formulas 1-11, Kuang, pages 4-5).
Claims 27-30 have limitations similar to those treated in the above rejection, and are met by the references as discussed above, and are rejected for the same reasons of obviousness as used above.
Allowable Subject Matter
Claims 25 and 26 are indicated as allowable over prior art.
The following is a statement of reasons for the indication of allowable subject matter:
None of the cited prior art references teaches “wherein Sp and Sq are selected to have a bit length ls>=2*log2p+log2[m(n+λ+1)]” in combination with other limitations
As allowable subject matter has been indicated, applicant's reply must either comply with all formal requirements or specifically traverse each requirement not complied with. See 37 CFR 1.111(b) and MPEP § 707.07(a).
Pertinent Prior Art
The prior art made of record and not relied upon is considered pertinent to applicant's disclosure:
NPL:
Kuang et al. (HOMOMORPHIC POLYNOMIAL PUBLIC KEY CRYPTOGRAPHY FOR QUANTUM-SECURE DIGITAL SIGNATURE, arXiv:submit/5236764 [cs.CR] 15 Nov 2023, 16 pages) the authors introduce an extension of the Barrett reduction algorithm;
Ding (Multivariate Public Key Cryptography, Feb. 22 2016, 152 pages) Teaches Multivariate Signature schemes;
Perepechaenko et al. (Quantum Encrypted Communication between Two IBMQ Systems Using Quantum Permutation Pad, IEEE, 2022, 7 pages) Teaches early functional implementation of the Kuang and Barbeau’s Quantum Permutation Pad (QPP) algorithm on the IBMQ physical quantum computers;
Conclusion
Any inquiry concerning this communication or earlier communications from the examiner should be directed to OLEG KORSAK whose telephone number is (571)270-1938. The examiner can normally be reached on 5:00 AM- 4:00 PM.
If attempts to reach the examiner by telephone are unsuccessful, the examiner’s supervisor, Rupal Dharia can be reached on (571) 272-3880. The fax phone number for the organization where this application or proceeding is assigned is 571-273-8300.
Information regarding the status of an application may be obtained from the Patent Application Information Retrieval (PAIR) system. Status information for published applications may be obtained from either Private PAIR or Public PAIR. Status information for unpublished applications is available through Private PAIR only. For more information about the PAIR system, see http://pair-direct.uspto.gov. Should you have questions on access to the Private PAIR system, contact the Electronic Business Center (EBC) at 866-217-9197 (toll-free). If you would like assistance from a USPTO Customer Service Representative or access to the automated information system, call 800-786-9199 (IN USA OR CANADA) or 571-272-1000.
/OLEG KORSAK/
Primary Examiner, Art Unit 2492
Prosecution Insights