DETAILED ACTION
Response to Amendment
This action is in response to amendment filed May 22, 2026 for the application # 18/916,605 filed on October 15, 2024. Claims 1-19, 21-32 are pending and are directed toward a QUANTUM-SAFE DIGITAL SIGNATURE METHOD AND SYSTEM.
Any claim objection/rejection not repeated below is withdrawn due to Applicant's amendment.
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.
Response to Arguments
Applicant’s arguments with regards to claims 1-19, 21-32 have been fully considered, but they are not persuasive.
In regards to 3.3 arguments, if Applicant considers formulas to be not just an illustrative material, but essential part of the claims, it is requested to put their position on record so that Examiner could reconsider the claims interpretations in view of 35 U.S.C. §101.
In regards to “linear vs. exponential” it should be noted that logarithmic transformation provides means to both forms of representation to be equivalent.
In regards to 3.2 arguments, Examiner stated that “they are from a similar field of endeavor of systems, components and methodologies for providing secure communication between computer systems.” It is not clear which reference Applicant considers to be not related to secure communication between computer systems. Clearly Doroz is pertinent, because his disclosure helps to achieve the claimed method by implementing teachings of Kuang by hardware acceleration of Doroz.
Conclusion: Examiner maintains rejections of Claims 1-19, 21-24 and 27-30. New claims 31 and 32 are indicated as allowable as they contain the limitations of previously allowable claims 25 and 26.
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-19, 21-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-19 and 21-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, 26, 31, and 32 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).
Conclusion
THIS ACTION IS MADE FINAL. Applicant is reminded of the extension of time policy as set forth in 37 CFR 1.136(a).
A shortened statutory period for reply to this final action is set to expire THREE MONTHS from the mailing date of this action. In the event a first reply is filed within TWO MONTHS of the mailing date of this final action and the advisory action is not mailed until after the end of the THREE-MONTH shortened statutory period, then the shortened statutory period will expire on the date the advisory action is mailed, and any extension fee pursuant to 37 CFR 1.136(a) will be calculated from the mailing date of the advisory action. In no event, however, will the statutory period for reply expire later than SIX MONTHS from the mailing date of this final action.
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.
Examiner interviews are available via telephone, in-person, and video conferencing using a USPTO supplied web-based collaboration tool. To schedule an interview, applicant is encouraged to use the USPTO Automated Interview Request (AIR) at http://www.uspto.gov/interviewpractice.
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 https://ppair-my.uspto.gov/pair/PrivatePair. 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