DETAILED ACTION
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 .
Claim Rejections - 35 USC § 102
The following is a quotation of the appropriate paragraphs of 35 U.S.C. 102 that form the basis for the rejections under this section made in this Office action:
A person shall be entitled to a patent unless –
(a)(1) the claimed invention was patented, described in a printed publication, or in public use, on sale, or otherwise available to the public before the effective filing date of the claimed invention.
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 (i.e., changing from AIA to pre-AIA ) 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 1, 3-6 and 12 are rejected under 35 U.S.C. 102(a)(1) as being anticipated by AKHMETZYANOV A, L., et al., 'On methods of shortening ElGamal-type signatures. Cryptology ePrint Archive, Paper 2021/148, 2021 (Received: 12 February 2021) hereinafter referred to as Ak.
Regarding Claim 1, Ak discloses A method for generating and verifying a digital signature, the method comprising: sharing, between a signing node (SIG) and a verifying node (VER), a message (M) in which the SIG is to issue a digital signature (S); performing, by the SIG, a first number of operations to generate the digital signature S [page 5, paragraphs 3-6] [page 7, These parameters are not independent from each other and they are strictly related to the generation time and probability of outputting the valid signature by the GenEGs.Sig procedure. Thus, they should be chosen in accordance with the generating mechanism computing power – teaches a “generating mechanism”, construed as a “signing node”] [page 8, The value of parameter t is strictly related to the signature verification time and should be chosen in accordance with the verifier's computing power – teaches a “verifier’s computing power” which indicates a verifier entity which is construed as “a verifying node”]
Regarding Claim 3, Ak discloses wherein performing the first number of operations to generate the digital signature further includes: searching, by the SIG, a digital signature featuring said redundancy P by re-signing the message M using a randomized digital signature algorithm until the redundancy P appears in the digital signature S. [page 7, paragraph 1, We generate signature until it meets certain additional conditions: the first l bits of r should match the constant vector][page 8, Vf algorithm] [page 8, paragraph 4, it can be applied to the GenEGs scheme by replacing the GenEG.Sig and GenEG.Vf calls with the corresponding GenEGs procedure calls]
Regarding Claim 4, Ak discloses wherein performing the first number of operations to generate the digital signature further includes: solving, by the SIG, a mathematical equation involving at least M and a private signature key to generate the S featuring the redundancy P. [page 7, paragraph 1, We generate signature until it meets certain additional conditions: the first l bits of r should match the constant vector] [page 8, paragraph 4, it can be applied to the GenEGs scheme by replacing the GenEG.Sig and GenEG.Vf calls with the corresponding GenEGs procedure calls]
Regarding Claim 5, Ak discloses wherein the VER is configured to recover the redundancy P to complete S’ and subsequently generate S by exhaustively searching through all possible bit values until the S value complying with the redundancy P is found, and wherein the S value is confirmed by a successful cryptographic verification of S. [pages 7, section 3.3, The idea behind the third method is to truncate the signature ( either r or s component) by t bits and search them during verification procedure]
Regarding Claim 6, Ak discloses wherein VER is configured to recover the redundancy P necessary to complete S’ and subsequently generate S by solving a mathematical equation involving the message M and a public verification key of the SIG. [page 8, Vf algorithm]
Regarding Claim 12, Ak discloses A system comprising: a signing node [page 7, These parameters are not independent from each other and they are strictly related to the generation time and probability of outputting the valid signature by the GenEGs.Sig procedure. Thus, they should be chosen in accordance with the generating mechanism computing power – teaches a “generating mechanism”, construed as a “signing node”]
comprising: one or more processors; and a memory comprising instructions which, when executed by the one or more processors, cause the one or more processors to perform operations comprising: performing several operations to generate a random number resulting in a digital signature S of a message M, [page 5, paragraphs 3-6]
wherein the digital signature S includes a redundancy P; omitting the redundancy P from S to generate a shortened signature S’; [pages 7, section 3.3, The idea behind the third method is to truncate the signature ( either r or s component) by t bits and search them during verification procedure] [page 8, Sig algorithm]
and transmitting M and S’ from the signing node to a verifying node. [Transmission of the message and signature (shortened or otherwise) from SIG to VER is an inherent part of any digital signature protocol and is thus considered to be inherent in the disclosure] [Abstract, The modified scheme provides sufficient security and acceptable (for non-interactive protocols) signing and verifying time – teaches signing and verifying. Pages 7 and 8, as referenced to above, teach a “signing node” as well as a “verifying node”]
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.
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 (i.e., changing from AIA to pre-AIA ) 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 2 and 13-16 are rejected under 35 U.S.C. 103 as being unpatentable over Ak, as applied to Claims 1 and 12, respectively, above, in view of MENEZES, A. J., et al., 'Handbook of Applied Cryptography', CRC Press, Boca Raton, 1997, ISBN-13: 978-0-84-938523-0 hereinafter referred to as Menezes.
Regarding Claim 2, Ak does not explicitly teach wherein the redundancy P is a bit-string of a form P = X|X where X represents any L-bit pattern and X|X stands for a concatenation of X to itself.
Menezes teaches wherein the redundancy P is a bit-string of a form P = X|X where X represents any L-bit pattern and X|X stands for a concatenation of X to itself. [page 29, paragraph 2, Let M' be the subset of M consisting of all strings where the first t bits are replicated in the last t positions (e.g., 1 OJ 1 OJ would be in M'for t = 3) – teaches utilizing a repeated a bit sequence to provide redundancy for similar purposes]
Before the effective filing date of the claimed invention, it would have been obvious to one with ordinary skill in the art to combine the teachings of Menezes with the disclosure of Ak. The motivation or suggestion would have been to further simplify the signature scheme. (page 29, paragraph 2)
Regarding Claim 13, Ak does not explicitly teach wherein redundancy P is any bit pattern X of size L repeated twice, with the digital signature comprising S = S’|X|X.
Menezes teaches wherein redundancy P is any bit pattern X of size L repeated twice, with the digital signature comprising S = S’|X|X. [page 29, paragraph 2, Let M' be the subset of M consisting of all strings where the first t bits are replicated in the last t positions (e.g., 1 OJ 1 OJ would be in M'for t = 3) – teaches utilizing a repeated a bit sequence to provide redundancy for similar purposes]
Before the effective filing date of the claimed invention, it would have been obvious to one with ordinary skill in the art to combine the teachings of Menezes with the disclosure of Ak. The motivation or suggestion would have been to further simplify the signature scheme. (page 29, paragraph 2)
Regarding Claim 14, Ak does not explicitly teach wherein redundancy P is any bit pattern X of size L repeated twice, with the digital signature comprising S = X|X|S’.
Menezes teaches wherein redundancy P is any bit pattern X of size L repeated twice, with the digital signature comprising S = X|X|S’. [page 29, paragraph 2, Let M' be the subset of M consisting of all strings where the first t bits are replicated in the last t positions (e.g., 1 OJ 1 OJ would be in M'for t = 3) – teaches utilizing a repeated a bit sequence to provide redundancy for similar purposes]
Before the effective filing date of the claimed invention, it would have been obvious to one with ordinary skill in the art to combine the teachings of Menezes with the disclosure of Ak. The motivation or suggestion would have been to further simplify the signature scheme. (page 29, paragraph 2)
Regarding Claim 15, Ak does not explicitly teach wherein redundancy P is any bit pattern X of size L repeated once at a beginning of S and once at an end of S, with the digital signature comprising S = X|S’|X.
Menezes teaches wherein redundancy P is any bit pattern X of size L repeated once at a beginning of S and once at an end of S, with the digital signature comprising S = X|S’|X. [page 29, paragraph 2, Let M' be the subset of M consisting of all strings where the first t bits are replicated in the last t positions (e.g., 1 OJ 1 OJ would be in M'for t = 3) – teaches utilizing a repeated a bit sequence to provide redundancy for similar purposes]
Before the effective filing date of the claimed invention, it would have been obvious to one with ordinary skill in the art to combine the teachings of Menezes with the disclosure of Ak. The motivation or suggestion would have been to further simplify the signature scheme. (page 29, paragraph 2)
Regarding Claim 16, Ak does not explicitly teach wherein the redundancy on X values appearing in S is replaced by f(X), where f is any bijective function.
Menezes teaches wherein the redundancy on X values appearing in S is replaced by f(X), where f is any bijective function. [page 29, paragraph 2, Let M' be the subset of M consisting of all strings where the first t bits are replicated in the last t positions (e.g., 1 OJ 1 OJ would be in M'for t = 3) – teaches utilizing a repeated a bit sequence to provide redundancy for similar purposes]
Before the effective filing date of the claimed invention, it would have been obvious to one with ordinary skill in the art to combine the teachings of Menezes with the disclosure of Ak. The motivation or suggestion would have been to further simplify the signature scheme. (page 29, paragraph 2)
Allowable Subject Matter
Claims 7-11 and 17-20 are objected to as being dependent upon a rejected base claim, but would be allowable if rewritten in independent form including all of the limitations of the base claim and any intervening claims.
The following is an examiner’s statement of reasons for allowance:
Regarding Claims 7 and 17, the closest prior art of record, AKHMETZYANOV A, L., et al., 'On methods of shortening ElGamal-type signatures. Cryptology ePrint Archive, Paper 2021/148, 2021 (Received: 12 February 2021) and MENEZES, A. J., et al., 'Handbook of Applied Cryptography', CRC Press, Boca Raton, 1997, ISBN-13: 978-0-84-938523-0 does not explicitly teach nor suggest in detail, wherein the mathematical equation includes a modified version of an elliptic curve digital signature algorithm (EC-DSA) algorithm, wherein public parameters of the SIG are an elliptic curve E and a prime p, as well as a generator G chosen randomly in E of some order q, and wherein a private key of the SIG is a number x chosen randomly between 1 and q-1 and the public verification key of the SIG is Y = x.G in view of other limitations of the intervening claims.
Thus the prior arts of record taking singly or in combination do not teach or suggest the above-stated limitations taking wholly in combination with all the elements of each independent claim.
Claim 8 depends on Claim 7, and Claims 9-11, depend on Claim 8. Claim 18 depends on Claim 17, and Claims 19-20 depend on Claim 18.
Therefore, Claims 7-11 and 18-20 are objected to as being dependent upon a rejected base claim, but would be allowable if rewritten in independent form including all of the limitations of the base claim and any intervening claims.
Conclusion
Any inquiry concerning this communication or earlier communications from the examiner should be directed to ANDREW J STEINLE whose telephone number is (571)272-9923. The examiner can normally be reached M-F 10am-6pm CT.
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, Eleni Shiferaw can be reached at (571) 272-3867. The fax phone number for the organization where this application or proceeding is assigned is 571-273-8300.
Information regarding the status of published or unpublished applications may be obtained from 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. Visit https://www.uspto.gov/patents/apply/patent-center for more information about Patent Center and https://www.uspto.gov/patents/docx for information about filing in DOCX format. For additional questions, contact the Electronic Business Center (EBC) at 866-217-9197 (toll-free). If you would like assistance from a USPTO Customer Service Representative, call 800-786-9199 (IN USA OR CANADA) or 571-272-1000.
/ANDREW J STEINLE/Primary Examiner, Art Unit 2497
Prosecution Insights