DETAILED ACTION
The present application, filed on or after March 16, 2013, is being examined under the first inventor to file provisions of the AIA .
This application currently names joint inventors. In considering patentability of the claims the examiner presumes that the subject matter of the various claims was commonly owned as of the effective filing date of the claimed invention(s) absent any evidence to the contrary. Applicant is advised of the obligation under 37 CFR 1.56 to point out the inventor and effective filing dates of each claim that was not commonly owned as of the effective filing date of the later invention in order for the examiner to consider the applicability of 35 U.S.C. 102(b)(2)(C) for any potential 35 U.S.C. 102(a)(2) prior art against the later 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 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-14 are rejected in the Instant Application.
Status of claims
Claims 1-5, 8, 10-12, 16-20 have been amended
Claims 1-20 are pending in the instant application
Claims 1-20 are rejected in the instant application
Response to Arguments
Applicant’s arguments with respect to claims 1-20 have been considered but are not persuasive. Please see examiners comments below:
Applicants’ arguments:
Fundamentally, Misoczki and the present application are concerned with very different
problems, and solve these problems in very different ways. The present application is concerned
with how to generate, in a particular device, a hash-based signature that comprises multiple
signature values, each generated using hash functions that are iteratively applied depending on an
input message or check sum. Even more particularly, the application is concerned with
generating this signature in a way that is resistant to side-channel attacks, and addresses that
problem by at least partially mixing up the order in which the multiple signature values of the signature are generated. Misoczki, on the other hand, is concerned with providing a signature
verification scheme for use by a group of devices, in a way that allows the signatures to be
properly verified while maintaining the privacy of the signing devices. Misoczki accomplishes
this by distributing the leaf nodes of a Merkle tree structure among the members of the group in a
random fashion. Misoczki is simply not concerned with the order in which multiple signature
value of a single hash-based signature are generated in a given device.
Claim 2 applicant argues Misoczki does not teach signature order
Claim 3 applicant argues specification teaches WOTS scheme provides additional security against side-channel attacks – and that Misocki does not teach applying WOTS scheme at least one more time than necessary.
Claim 4 similar argument to claim 3 above that Misoczki does not teach WOTS scheme.
Claim 5 similar argument to claim 3 and 4 above, states the Misoczki does not address the number of times a hash function is iterated when generating signatures. Claim 6 depends on 5 and uses same rationale.
Claim 8 argues examiners intended use is in error and claims 9 and 10 depend on claim 8 same rationale.
Examiners response:
Examiner respectfully disagrees applicant discusses nuances such as resiliency against side-channel attacks – however the claims provide a broad set up that is clearly taught by Misoczki. Applicant utilizes a very narrowed argument to highlight and discuss broad claim language. This can be easily overcome by bringing in details aligning with the arguments into the claims from the specification. Examiner maintains his rejection.
Claim 2: Examiner again respectfully disagrees, applicant here again utilizes a narrowed argument for a broad limitation. Misoczki teaches permutation of cryptographic hashes and the order of the leaf nodes. Further ¶0049 teaches the group member device 102 may execute a method 700 for generating cryptographic signatures. Examiner maintains his rejection.
Claim 3: Examiner again disagrees with the applicant here at Misoczki teaches multi-time signature schemes utilizing WOTS – the limitations require nothing further.
Claim 4: Examiner again disagrees see arguments above (¶0019)
Claim 5: ¶0045 clearly teaches number of signatures required. Examiner maintains his rejection. Claim 6 is rejected on similar rationale.
Claim 8: Examiner again respectfully disagrees, the claim iteratively applying hash function ‘is protected from side-channel attacks’ asides a generator function and one-time keys being seed and applying keys does not state how side-channel protection is achieved. Examiner clearly highlights ¶0045 of Masoczki teaching secret key seeds and generating cryptographic keys serving hash values. Examiner maintains his rejection.
USC 101 rejections is maintained, simply changing terminology from device to apparatus does not provide structure to the apparatus. Examiner suggests adding a processor and memory.
Examiner kindly suggests prior to filing a response, the applicant set up a formal interview with the examiner such that details about specific limitations can be clarified inventive concept clearly defined.
Claim Rejections - 35 USC § 101
35 U.S.C. 101 reads as follows:
Whoever invents or discovers any new and useful process, machine, manufacture, or composition of matter, or any new and useful improvement thereof, may obtain a patent therefor, subject to the conditions and requirements of this title.
Claims 11-13 are rejected under 35 U.S.C. 101 because the claimed invention is directed to non-statutory subject matter.
As per claim 11, the language is drawn to a computer program which is neither executed by a computer, nor stored on a physical structure. Examiner suggests adding a processor and memory to clarify the apparatus is a physical device.
Claims not specifically mentioned are rejected by virtue of dependency and because they do not obviate the above-recited deficiencies.
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.
(a)(2) the claimed invention was described in a patent issued under section 151, or in an application for patent published or deemed published under section 122(b), in which the patent or application, as the case may be, names another inventor and was effectively filed before the effective filing date of the claimed invention.
Claims 1-14 rejected under 35 U.S.C. 102(a)(1) as being anticipated by Misoczki et al. (US20170230182A1) hereinafter Misoczki.
Regarding claim 1. Misoczki teaches a method for generating a Hash-based signature based on a Wintermitz one-time signature scheme, wherein the signature comprises several signature values that are determined via Hash-functions that are iteratively applied depending on a message and/or checksum (abstract include a group member device to generate a signature of a message using a cryptographic key assigned to the group member device by a group manager and determine an authentication path that indicates a plurality of cryptographic hashes necessary to compute a group public key of a group associated with a plurality of group member devices..¶0019 see Merkle signature scheme construction turns a one-time signature (OTS) scheme, such as Winternitz OTS scheme, into a multi-time signature scheme), comprising the step:
generating the signature values at least partially in a mixed order, which is determined based on at least one of the following: a predefined or deterministic pattern, a pseudo-random pattern, a random pattern (¶0069 see to generate the set of cryptographic keys comprises to generate the set of cryptographic keys based on a random seed value ¶0040 see the mixed set of leaf nodes 906, the group manager 106 may build a Merkle tree 1000 of height l+b (e.g., b layers higher than a Merkle tree used for standard single-signer signatures) ).
Regarding claim 2. Misoczki teaches the method according to claim 1, wherein the method comprises temporarily storing the mixed order in order to restore the order of the signature values before they are further processed (¶0048 see the group manager 106 may permute the original order of the leaf nodes 906 or, more specifically, of the cryptographic hashes. For example, in block 610, the group manager 106 may permute the order of the leaf nodes 906 by applying a cryptographic block cipher to the leaf nodes 906, the cryptographic hashes, and/or the cryptographic keys generated by the group member devices 102).
Regarding claim 3. Misoczki teaches the method of claim 1, wherein the method comprises, for at least one of the Signature values, applying the Hash function at least one more time than necessary according to the Winternitz one-time signature scheme (¶0019 see Merkle signature scheme construction turns a one-time signature (OTS) scheme, such as Winternitz OTS scheme, into a multi-time signature scheme. An OTS scheme includes a private key, sk, used to sign and a public key, pk, used to verify the signature and are limited in that a single private key is only used to sign one message since multiple uses of the same private key may compromise the security of the scheme. As such, Merkle schemes utilize a tree to authenticate an exponential number of OTS public keys, which binds an exponentially high number of OTS public keys to a single multi-time public key, PK.).
Regarding claim 4. The method of claim 3, wherein the method comprises, for at least one signature value, iterating the Hash function as many times as necessary to reach the corresponding public key value (¶0037 see initially indicative of a cryptographic hash of a corresponding public cryptographic key generated by each of the group member device 102. Depending on the particular embodiment, each of the group member devices 102 generates the cryptographic hashes for, or is otherwise associated with or responsible for, one or more of the leaf nodes 906 of the Merkle tree 900. Further, it should be appreciated that the number of intermediary nodes in the Merkle tree 900 may vary depending on the number of leaf nodes 906 and therefore the height, h, of the corresponding tree structure. As such, the system 100 may include any number of intermediary nodes 904 and leaf nodes 906 depending on the particular embodiment).
Regarding claim 5. Misoczki teaches the method of claim 3, wherein the method comprises, for at least one of the signature values, applying the Hash function an additional number ai times, wherein at is larger than the number of times required to determine the signature value according to the Winternitz one-time signature scheme and smaller than or equal to the number of tires necessary to reach the public key value (¶0045 see the group member device 102 may generate the cryptographic keys based on a random seed value. For example, in some embodiments, in order to generate the cryptographic keys, each group member device 102, Si, samples a random seed, ki, serving as the secret key. From ki, the group member device 102 may generate a set/sequence of secret keys ski j=PRNGj(ki), using a secure pseudorandom number generator, where j runs from 1 to the number of signatures expected to be issued ¶0019 see Merkle schemes utilize a tree to authenticate an exponential number of OTS public keys, which binds an exponentially high number of OTS public keys to a single multi-time public key, PK. In the illustrative embodiment, the number of key is exponential in the height of the tree but still relatively small as such keys/signatures must be computed. Further, a signature generated with the set of OTS private keys may be validated with a single public key (i.e., the Merkle public key, PK)), wherein ai is determined based on at least one of the following:
- deterministic scheme, a predefined scheme, a pseudo-random scheme, a random scheme (¶0045 see the group member device 102 may generate the cryptographic keys based on a random seed value).
Regarding claim 6. Misoczki teaches the method of claim 5, wherein different numbers ai are used for different signature values (¶0045 see From ki, the group member device 102 may generate a set/sequence of secret keys ski j=PRNGj(ki), using a secure pseudorandom number generator, where j runs from 1 to the number of signatures expected to be issued. It should be appreciated that the number of signatures issued per group member device 102).
Regarding claim 7. Misoczki teaches the method according of claim 1, further comprising:
for at least one of the signature values, applying the Hash function at least one more time than required according to the Winternitz one-time signature scheme, wherein the signature value is based on the checksum (¶0019 see Merkle signature scheme construction turns a one-time signature (OTS) scheme, such as Winternitz OTS scheme, into a multi-time signature scheme. An OTS scheme includes a private key, sk, used to sign and a public key, pk, used to verify the signature and are limited in that a single private key is only used to sign one message since multiple uses of the same private key may compromise the security of the scheme. As such, Merkle schemes utilize a tree to authenticate an exponential number of OTS public keys, which binds an exponentially high number of OTS public keys to a single multi-time public key, PK and ¶0021 see each of the group member devices 102 generates at least one cryptographic key pair including a public cryptographic key and a private cryptographic key and generates cryptographic hash of each public cryptographic key (see, for example, nodes 906 of FIGS. 9-10). The cryptographic hashes, public cryptographic keys, and/or other identifying information may be transmitted to the group manager 106, which may reassign such data to the group member devices 102 (e.g., via a randomized permutation)).
Regarding claim 8. Misoczki teaches the method of claim 1, wherein a generator function that determines one-time keys based on a secret SEED, wherein such one-time keys are the basis for iteratively applying the Hash function, is protected from side-channel attacks (¶0045 see group member device 102 may generate the cryptographic keys based on a random seed value. For example, in some embodiments, in order to generate the cryptographic keys, each group member device 102, Si, samples a random seed, ki, serving as the secret key. From ki, the group member device 102 may generate a set/sequence of secret keys ski j=PRNGj(ki), using a secure pseudorandom number generator [random seed is the secret as one-time keys and protected from side-channel attack is an intended use]).
Regarding claim 9. Misoczki teaches the method of claim 8, wherein method comprises processing the one-time keys at least partially in a mixed order, which is determined based on at least one of the following: a predefined or deterministic pattern, a pseudo-random pattern, a random pattern (¶0045 see generate the cryptographic keys, each group member device 102, Si, samples a random seed, ki, serving as the secret key. From ki, the group member device 102 may generate a set/sequence of secret keys ski j=PRNGj(ki), using a secure pseudorandom number generator, where j runs from 1 to the number of signatures expected to be issued).
Regarding claim 10. Misoczki teaches the method of claim 8, wherein the Hash function is a cryptographically hardened Hash function (¶0021 see devices 102 generates at least one cryptographic key pair including a public cryptographic key and a private cryptographic key and generates cryptographic hash of each public cryptographic key).
Regarding claim 11. Misoczki teaches an apparatus for generating a Hash-based signature based on a Winternitz one-time signature scheme, wherein the signature comprises several signature values (SIG[N1], .., SG[N32]), which are determined via Hash-functions that are iteratively applied depending on a message and/or checksum (abstract include a group member device to generate a signature of a message using a cryptographic key assigned to the group member device by a group manager and determine an authentication path that indicates a plurality of cryptographic hashes necessary to compute a group public key of a group associated with a plurality of group member devices..¶0019 see Merkle signature scheme construction turns a one-time signature (OTS) scheme, such as Winternitz OTS scheme, into a multi-time signature scheme), wherein the apparatus is arranged to:
generate the signature values at least partially in a mixed order, which is determined based on at least one of the following: a predefined or deterministic pattern, a pseudo-random pattern, a random pattern (¶0069 see to generate the set of cryptographic keys comprises to generate the set of cryptographic keys based on a random seed value ¶0040 see the mixed set of leaf nodes 906, the group manager 106 may build a Merkle tree 1000 of height l+b (e.g., b layers higher than a Merkle tree used for standard single-signer signatures) ).
Regarding claim 12. Misoczki teaches the apparatus according to claim 11, wherein the apparatus is a cryptographic device or a device that is arranged to conduct at least one cryptographic function, in particular to generate the Hash-based signature (¶0021 see group member devices 102 generates at least one cryptographic key pair including a public cryptographic key and a private cryptographic key and generates cryptographic hash of each public cryptographic key (see, for example, nodes 906 of FIGS. 9-10). The cryptographic hashes, public cryptographic keys, and/or other identifying information may be transmitted to the group manager).
Regarding claim 13. Misoczki teaches the apparatus according to claim 11, wherein said apparatus is a security device comprising at least one of the following:
an integrated circuit, a hardware security module, a trusted platform module, a crypto unit, a FPGA, a processing unit, a controller, a smartcard (¶0041 see security co-processor and processor of the cryptography module ).
Regarding claim 14. Misoczki teaches a non-transitory computer-readable medium comprising, stored thereupon, a computer program product directly loadable into a memory of a digital processing device, the computer program product comprising software code portions for performing the steps of the method of claim 1 (¶0015 see non-transitory machine readable storage medium and further see claim 1 above).
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 nonprovisional extension fee (37 CFR 1.17(a)) 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.
References are cited not only for their quoted language but for all that they teach.
Any inquiry concerning this communication or earlier communications from the examiner should be directed to Atta Khan whose telephone number is 571-270-7364. The examiner can normally be reached on M-F 09:00-6:00.
If attempts to reach the examiner by telephone are unsuccessful, the examiner’s supervisor, Vivek Srivastava can be reached on (571) 272-7304. 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.
/ATTA KHAN/
Examiner, Art Unit 2449