DETAILED ACTION
This action is in response to amendments filed 7/8/2025. Claims 1-3, 6-10, 15-18 and 21-27 are pending with claims 1, 6, 15 and 21 being amended and claims 4-5, 11-14, 19-20 and 28-29 cancelled.
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 .
Priority
Acknowledgment is made of applicant's claim for foreign priority under 35 U.S.C. 119(a)-(d). The certified copy has been received.
Response to Arguments
Applicant's arguments filed 7/8/2025 have been fully considered.
Applicant's arguments with respect to amended claim 1 that Nagravision or Campagna does not teach “constricting the authenticated binary tree based on the predicted messages and probabilities of the respective predicted messages” have been fully considered but they are not persuasive (see response pages 8-10).
While Nagravision does not disclose a binary tree Nagravision teaches wherein the pre-computer data structure is constructed based on: the predicted messages and probabilities of the respective predicted messages (see Nagravision page 2 line 33 – page 3 line 5 i.e. The set of messages may instead be predetermined dynamically, that is vary over time in a predefined manner, for example so that a small set of possible values can be predicted when communication occurs, for example by consulting a reference common to the sender and transmitter. A sufficient condition on the accuracy of the prediction is that the plurality of values at the sender and transmitter have at least the transmitted value in common to enable the tag for the transmitted value to be recognised. Examples of such values may be dates, times, clock ticks, coordinates close to each other and the like)
Campagna teaches wherein determining the pre-computed data structure comprises constructing an authenticated binary tree based on the predicted messages (see Campagna paragraphs 0040-0042 i.e. After or concurrent with the generation of the Merkle tree, the system may generate 310 an authentication path from the signing key to the root node of the Merkle tree. An authentication path may refer to a collection of nodes that may be used to verify that a first node and a second node are connected nodes of a Merkle tree. For example, an authentication path may be formed from a leaf node of the Merkle tree (e.g., a leaf node corresponding to the key identifier) to the root node of the Merkle tree. An authentication path may be verified by hashing the leaf node with the first node of the authentication path, and iteratively hashing the hash outputs with the next node of the authentication path. An authentication path may be generated in accordance with techniques described above, for example, in connection with FIGS. 1-2);
It would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to modify Nagravision in view of Campagna to have used a Merkle Tree as one way to authenticate date since a Merkle Tree allows efficient and secure verification of data (see Campagna paragraph 0040-0042). Therefore, one would have been motivated to have used a Merkle Tree.
Applicant's arguments with respect to the 103 rejection of claim 26 that Nagravision in view of Campagna does not teach “an authenticated binary tree, each leaf node of the binary tree containing a hash of the concatenation of a predicted message and a nonce value” or “wherein the cryptographic proof comprises a combination of a nonce value of a leaf node corresponding to the message, and the hashes of all sibling nodes on a path between the leaf node and the root of the binary tree” have been fully considered but they are not persuasive.
Regarding B) Campagna teaches receiving a root value wherein the root value is a root value of an authenticated binary tree, each leaf node of the binary tree containing a hash of the concatenation of a predicted message and a nonce value in Campagna paragraph 0040-0043 i.e. The computer system may provide 304 a root of the Merkle tree to the service provider. In some embodiments, the root node provided may be the root of the entire Merkle tree (e.g., the public key 204 illustrated in FIG. 2), but in some embodiments, a root node of a subtree may be provided. Continuing with FIG. 2 as an illustrative example, H.sub.2,0 may be provided as the root node of the subtree having child nodes H.sub.1,0 and H.sub.1,1, and so on. Returning to FIG. 3, the system may, after providing the root node of a Merkle tree (e.g., the root of the full Merkle tree generated), receive 306 as part of a challenge a key identifier and a message … In response to the challenge, the system may provide 312 a digital signature over a message, the public signing key corresponding to the private signing key used to generate the digital signature, and the generated authentication path. In some embodiments, the proof-of-work may include the root node, one or more leaf nodes, an authentication path, the digital signature, or some combination thereof. In general, the proof-of-work may include information that may be used to verify a solution to a challenge, and may also provide an indication that the client committed non-trivial computing resources in the generation of the proof-of-work (e.g., performing a number of cryptographic hash operations to generate a Merkle tree))).
Campagna teaches wherein the cryptographic proof comprises a combination of a nonce value of a leaf node corresponding to the message, and the hashes of all sibling nodes on a path between the leaf node and the root of the binary tree in paragraph 0043 i.e. In response to the challenge, the system may provide 312 a digital signature over a message, the public signing key corresponding to the private signing key used to generate the digital signature, and the generated authentication path. In some embodiments, the proof-of-work may include the root node, one or more leaf nodes, an authentication path, the digital signature, or some combination thereof. In general, the proof-of-work may include information that may be used to verify a solution to a challenge, and may also provide an indication that the client committed non-trivial computing resources in the generation of the proof-of-work (e.g., performing a number of cryptographic hash operations to generate a Merkle tree))
It would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to modify Nagravision in view of Campagna to have used a Merkle Tree as one way to authenticate date since a Merkle Tree allows efficient and secure verification of data (see Campagna paragraph 0040-0042). Therefore, one would have been motivated to have used a Merkle Tree.
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, 3, 6-10, 15, 17-18, 21-24 and 26 are rejected under 35 U.S.C. 103 as being unpatentable over Nagravision (WO 2020/038789) in view of Campagna et al (US 2018/0183601).
With respect to claim 1 Nagravision teaches an apparatus for providing authentication information, the apparatus comprising:
one or more processors;
a memory storing instructions that when executed by the one or more processors, cause the apparatus to:
generate a plurality of predicted messages based on a known structure of the a message and/or based on a plurality of past messages having a same structure as the message (see Nagravision page 2 line 33 – page 3 line 1 i.e. The set of messages may be predefined in a fixed manner, for example a fixed set of possible control or sensor values to be transmitted. Of course, such a fixed set may change from time to time. The set of messages may instead be predetermined dynamically, that is vary over time in a predefined manner, for example so that a small set of possible values can be predicted when communication occurs, for example by consulting a reference common to the sender and transmitter and page 8 lines 14-20 i.e. The set of messages may be fixed and may correspond, for example, to a set of control commands or sensor values to be transmitted. Alternatively, the set of messages may change over time in a predictable manner, so that both sender and receiver can have a shared set of messages 220 and message tags 230, for example deriving the set using a common reference such as a common time reference. A particular example relates to clock signals in a GPS system in which GPS signals are transmitted using messages 220 and message tags 230.);
pre-compute, based on at least one of the predicted messages, a data structure for generation of cryptographic evidence for future messages (see Nagravision page 2 lines 22-29 i.e. The processor is configured to combine each message with an authentication key to generate a corresponding message tag. Generating the message tags may comprise encrypting the message with the authentication key, hashing the message with the authentication key or applying any suitable MAC algorithm using the authentication key in combination with the message, as a seed, parameter, or the like. The MAC algorithm may be CMAC, HMAC or SipHash, for example. The processor is further configured to store each computed message tag in the memory, page 8 line 6-8 i.e. With reference to Figure 2, a data structure 200 is stored in the memory 110 and comprises pairs 210 of messages 220 and message tags 230 corresponding to each message, for example a MAC computed for each message 220 and page 9 lines 15-19 i.e. As discussed above, the data structure 200 stores pairs 210 of messages 220 and message tags 230. The message tag 230 for a message 220, xi, of a set of messages {xi} is pre-computed by combining each xi with a current authentication key Kj to generate as a message tag 230 a MAC MAC_Kj(xi), using for exampie any of the MAC algorithms discussed above);
receive a true message (see Nagravision page 2 line 29 i.e. Subsequently, the processor can compare a received message tag with the stored computed message tags to identify a matching message tag, thereby validating the received message tag as one of the set);
determine a cryptographic proof for the true message based on the pre- computed data structure (see Nagravision page 2 lines 29-31 i.e. Subsequently, the processor can compare a received message tag with the stored computed message tags to identify a matching message tag, thereby validating the received message tag as one of the set and page 3 lines 27-29 i.e. Typically, each tag is stored in the memory associated with its corresponding message as a pair, so that a received message can be validated, or a message can be identified by looking up the received tag in the memory); and
transmit the true message and the cryptographic proof to at least one message destination apparatus (see Nagravision page 5 lines 19-21 i.e. The processor then causes the communications interface to transmit the retrieved message tag corresponding to the selected message, together with or without the message itself).
wherein the pre-computer data structure is constructed based on: the predicted messages and probabilities of the respective predicted messages (see Nagravision page 2 line 33 – page 3 line 5 i.e. The set of messages may instead be predetermined dynamically, that is vary over time in a predefined manner, for example so that a small set of possible values can be predicted when communication occurs, for example by consulting a reference common to the sender and transmitter. A sufficient condition on the accuracy of the prediction is that the plurality of values at the sender and transmitter have at least the transmitted value in common to enable the tag for the transmitted value to be recognised. Examples of such values may be dates, times, clock ticks, coordinates close to each other and the like)
Nagravision does not teach wherein determining the pre-computed data structure comprises constructing an authenticated binary tree based on the predicted messages; wherein the authenticated binary tree is constructed based on: the predicted messages and probabilities of the respective predicted messages
Campagna teaches wherein determining the pre-computed data structure comprises constructing an authenticated binary tree based on the predicted messages (see Campagna paragraphs 0040-0042 i.e. After or concurrent with the generation of the Merkle tree, the system may generate 310 an authentication path from the signing key to the root node of the Merkle tree. An authentication path may refer to a collection of nodes that may be used to verify that a first node and a second node are connected nodes of a Merkle tree. For example, an authentication path may be formed from a leaf node of the Merkle tree (e.g., a leaf node corresponding to the key identifier) to the root node of the Merkle tree. An authentication path may be verified by hashing the leaf node with the first node of the authentication path, and iteratively hashing the hash outputs with the next node of the authentication path. An authentication path may be generated in accordance with techniques described above, for example, in connection with FIGS. 1-2);
wherein the authenticated binary tree is constructed based on: the predicted messages and probabilities of the respective predicted messages (see Campagna paragraphs 0040-0042 i.e. After or concurrent with the generation of the Merkle tree, the system may generate 310 an authentication path from the signing key to the root node of the Merkle tree. An authentication path may refer to a collection of nodes that may be used to verify that a first node and a second node are connected nodes of a Merkle tree. For example, an authentication path may be formed from a leaf node of the Merkle tree (e.g., a leaf node corresponding to the key identifier) to the root node of the Merkle tree. An authentication path may be verified by hashing the leaf node with the first node of the authentication path, and iteratively hashing the hash outputs with the next node of the authentication path. An authentication path may be generated in accordance with techniques described above)
It would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to modify Nagravision in view of Campagna to have used a Merkle Tree as one way to authenticate date since a Merkle Tree allows efficient and secure verification of data (see Campagna paragraph 0040-0042). Therefore, one would have been motivated to have used a Merkle Tree.
With respect to claim 3 Nagravision and Campagna teaches the apparatus according to claim 1, wherein execution of the instructions by the one or more processors further causes the apparatus to determine the cryptographic proof by: comparing content of the true message to the predicted messages; selecting one of said predicted messages based on its similarity or identity to the true message; and retrieving the cryptographic proof from the pre-computed data structure using the selected one of the predicted messages (see Nagravision page 2 lines 22-31 i.e. The processor is configured to combine each message with an authentication key to generate a corresponding message tag. Generating the message tags may comprise encrypting the message with the authentication key, hashing the message with the authentication key or applying any suitable MAC algorithm using the authentication key in combination with the message, as a seed, parameter, or the like. The MAC algorithm may be CMAC, HMAC or SipHash, for example. The processor is further configured to store each computed message tag in the memory. Subsequently, the processor can compare a received message tag with the stored computed message tags to identify a matching message tag, thereby validating the received message tag as one of the set).
With respect to claim 6 Nagravision and Campagna teach the apparatus according to claim 4. Campagna further teaches wherein each leaf node of the binary tree contains a hash of a concatenation of one of the plurality of predicted messages and a nonce value (see Campagna paragraphs 0040-0042 i.e. The computer system may provide 304 a root of the Merkle tree to the service provider. In some embodiments, the root node provided may be the root of the entire Merkle tree (e.g., the public key 204 illustrated in FIG. 2), but in some embodiments, a root node of a subtree may be provided. Continuing with FIG. 2 as an illustrative example, H.sub.2,0 may be provided as the root node of the subtree having child nodes H.sub.1,0 and H.sub.1,1, and so on. Returning to FIG. 3, the system may, after providing the root node of a Merkle tree (e.g., the root of the full Merkle tree generated), receive 306 as part of a challenge a key identifier and a message. The key identifier and challenge may be provided to the system by a service provider after the service provider receives the root of the Merkle tree. In some embodiments, the key identifier may be an index position of the key that should be used to digitally sign a message. The message may include information corresponding to the user's identity (e.g., an email address) or may include information such as a nonce value which may be a counter that is incremented for each request).
With respect to claim 7 Nagravision and Campagna teach the apparatus according to claim 6. Campagna further teaches wherein execution of the instructions by the one or more processors further causes the apparatus to: determine a root value for the authenticated binary tree by iterative pairwise hashing of values of nodes of the binary tree; and share the root value with the at least one message destination (see Campagna paragraphs 0040-0042 i.e. After or concurrent with the generation of the Merkle tree, the system may generate 310 an authentication path from the signing key to the root node of the Merkle tree. An authentication path may refer to a collection of nodes that may be used to verify that a first node and a second node are connected nodes of a Merkle tree. For example, an authentication path may be formed from a leaf node of the Merkle tree (e.g., a leaf node corresponding to the key identifier) to the root node of the Merkle tree. An authentication path may be verified by hashing the leaf node with the first node of the authentication path, and iteratively hashing the hash outputs with the next node of the authentication path).
With respect to claim 8 Nagravision and Campagna teach 6 the apparatus according to claim 6. Campagna further teaches wherein execution of the instructions by the one or more processors further causes the apparatus to determine the cryptographic proof by: determining a leaf node in the binary tree that corresponds to the true message; and traversing the binary tree to retrieve hashes of siblings of nodes on a path between the corresponding leaf node and a root; wherein the cryptographic proof comprises a combination of the nonce value of the corresponding leaf node, and the hashes of all sibling nodes on the path (see Campagna paragraphs 0040-0042 i.e. After or concurrent with the generation of the Merkle tree, the system may generate 310 an authentication path from the signing key to the root node of the Merkle tree. An authentication path may refer to a collection of nodes that may be used to verify that a first node and a second node are connected nodes of a Merkle tree. For example, an authentication path may be formed from a leaf node of the Merkle tree (e.g., a leaf node corresponding to the key identifier) to the root node of the Merkle tree. An authentication path may be verified by hashing the leaf node with the first node of the authentication path, and iteratively hashing the hash outputs with the next node of the authentication path).
With respect to claim 9 Nagravision and Campagna teach the apparatus according to claim 7. Campagna further teaches wherein execution of the instructions by the one or more processors further causes the apparatus to: share the root value with a plurality of message destinations, each respective message destination being associated with a different respective symmetric key (see Campagna paragraphs 0040-0042 i.e. After or concurrent with the generation of the Merkle tree, the system may generate 310 an authentication path from the signing key to the root node of the Merkle tree. An authentication path may refer to a collection of nodes that may be used to verify that a first node and a second node are connected nodes of a Merkle tree. For example, an authentication path may be formed from a leaf node of the Merkle tree (e.g., a leaf node corresponding to the key identifier) to the root node of the Merkle tree. An authentication path may be verified by hashing the leaf node with the first node of the authentication path, and iteratively hashing the hash outputs with the next node of the authentication path).
With respect to claim 10 Nagravision teaches the apparatus according to claim 1, but does not disclose wherein execution of the instructions by the one or more processors further causes the apparatus to: initialise a series of hash chain values, the series of hash chain values comprising a final hash chain value (Co), wherein each hash chain value (Ci) corresponds to a specific transmission interval (i); and transmit the final hash chain value (Co) to at least one message destination apparatus.
Campagna teaches wherein execution of the instructions by the one or more processors further causes the apparatus to: initialise a series of hash chain values, the series of hash chain values comprising a final hash chain value (Co), wherein each hash chain value (Ci) corresponds to a specific transmission interval (i); and transmit the final hash chain value (Co) to at least one message destination apparatus (see Campagna paragraphs 0040-0042 i.e. After or concurrent with the generation of the Merkle tree, the system may generate 310 an authentication path from the signing key to the root node of the Merkle tree. An authentication path may refer to a collection of nodes that may be used to verify that a first node and a second node are connected nodes of a Merkle tree. For example, an authentication path may be formed from a leaf node of the Merkle tree (e.g., a leaf node corresponding to the key identifier) to the root node of the Merkle tree. An authentication path may be verified by hashing the leaf node with the first node of the authentication path, and iteratively hashing the hash outputs with the next node of the authentication path).
It would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to modify Nagravision in view of Campagna to have used a Merkle Tree authentication path to verify the hashing leaf node with the first node of the authentication path, and iteratively hashing the hash outputs with the next node of the authentication path authenticate date since the Merkle Tree authentication path allows efficient and secure verification of data (see Campagna paragraph 0040-0042). Therefore, one would have been motivated to have used a Merkle Tree.
With respect to claim 15 Nagravision teaches a method for providing authentication information for a message, comprising, at a message source: prior to receiving or generating the message: generating a plurality of predicted messages based on a known structure of the message and/or based on a plurality of past messages having a same structure as the message (see Nagravision page 2 line 33 – page 3 line 1 i.e. The set of messages may be predefined in a fixed manner, for example a fixed set of possible control or sensor values to be transmitted. Of course, such a fixed set may change from time to time. The set of messages may instead be predetermined dynamically, that is vary over time in a predefined manner, for example so that a small set of possible values can be predicted when communication occurs, for example by consulting a reference common to the sender and transmitter and page 8 lines 14-20 i.e. The set of messages may be fixed and may correspond, for example, to a set of control commands or sensor values to be transmitted. Alternatively, the set of messages may change over time in a predictable manner, so that both sender and receiver can have a shared set of messages 220 and message tags 230, for example deriving the set using a common reference such as a common time reference. A particular example relates to clock signals in a GPS system in which GPS signals are transmitted using messages 220 and message tags 230.); and
pre-computing, based on at least one of the predicted messages, a data structure for generation of cryptographic evidence for future messages (see Nagravision page 2 lines 22-29 i.e. The processor is configured to combine each message with an authentication key to generate a corresponding message tag. Generating the message tags may comprise encrypting the message with the authentication key, hashing the message with the authentication key or applying any suitable MAC algorithm using the authentication key in combination with the message, as a seed, parameter, or the like. The MAC algorithm may be CMAC, HMAC or SipHash, for example. The processor is further configured to store each computed message tag in the memory, page 8 line 6-8 i.e. With reference to Figure 2, a data structure 200 is stored in the memory 110 and comprises pairs 210 of messages 220 and message tags 230 corresponding to each message, for example a MAC computed for each message 220 and page 9 lines 15-19 i.e. As discussed above, the data structure 200 stores pairs 210 of messages 220 and message tags 230. The message tag 230 for a message 220, xi, of a set of messages {xi} is pre-computed by combining each xi with a current authentication key Kj to generate as a message tag 230 a MAC MAC_Kj(xi), using for exampie any of the MAC algorithms discussed above) wherein the data structure for generation of cryptographic evidence is constructed based on: the predicted messages and probabilities of the respective predicted messages (see Nagravision page 2 line 33 – page 3 line 5 i.e. The set of messages may instead be predetermined dynamically, that is vary over time in a predefined manner, for example so that a small set of possible values can be predicted when communication occurs, for example by consulting a reference common to the sender and transmitter. A sufficient condition on the accuracy of the prediction is that the plurality of values at the sender and transmitter have at least the transmitted value in common to enable the tag for the transmitted value to be recognised. Examples of such values may be dates, times, clock ticks, coordinates close to each other and the like); and
on receiving or generating the message (true message), determining a cryptographic proof for the true message based on the pre-computed data structure (see Nagravision page 2 lines 29-31 i.e. Subsequently, the processor can compare a received message tag with the stored computed message tags to identify a matching message tag, thereby validating the received message tag as one of the set and page 3 lines 27-29 i.e. Typically, each tag is stored in the memory associated with its corresponding message as a pair, so that a received message can be validated, or a message can be identified by looking up the received tag in the memory).
Nagravision does not teach wherein the data structure for generation of cryptographic evidence for future message by constructing an authenticated binary tree based on the predicted messages.
Campagna teaches wherein wherein the data structure for generation of cryptographic evidence for future message by constructing an authenticated binary tree based on the predicted messages (see Campagna paragraphs 0040-0042 i.e. After or concurrent with the generation of the Merkle tree, the system may generate 310 an authentication path from the signing key to the root node of the Merkle tree. An authentication path may refer to a collection of nodes that may be used to verify that a first node and a second node are connected nodes of a Merkle tree. For example, an authentication path may be formed from a leaf node of the Merkle tree (e.g., a leaf node corresponding to the key identifier) to the root node of the Merkle tree. An authentication path may be verified by hashing the leaf node with the first node of the authentication path, and iteratively hashing the hash outputs with the next node of the authentication path. An authentication path may be generated in accordance with techniques described above, for example, in connection with FIGS. 1-2);
wherein the authenticated binary tree is constructed based on: the predicted messages and probabilities of the respective predicted messages (see Campagna paragraphs 0040-0042 i.e. After or concurrent with the generation of the Merkle tree, the system may generate 310 an authentication path from the signing key to the root node of the Merkle tree. An authentication path may refer to a collection of nodes that may be used to verify that a first node and a second node are connected nodes of a Merkle tree. For example, an authentication path may be formed from a leaf node of the Merkle tree (e.g., a leaf node corresponding to the key identifier) to the root node of the Merkle tree. An authentication path may be verified by hashing the leaf node with the first node of the authentication path, and iteratively hashing the hash outputs with the next node of the authentication path. An authentication path may be generated in accordance with techniques described above)
It would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to modify Nagravision in view of Campagna to have used a Merkle Tree as one way to authenticate date since a Merkle Tree allows efficient and secure verification of data (see Campagna paragraph 0040-0042). Therefore, one would have been motivated to have used a Merkle Tree.
With respect to claim 17 Nagravision and Campagna teaches the method according to claim 15, wherein the plurality of predicted messages is all possible prospective messages, and wherein the pre-computed data structure is determined based on the plurality of predicted messages (see Nagravision page 2 lines 22-31 i.e. The processor is configured to combine each message with an authentication key to generate a corresponding message tag. Generating the message tags may comprise encrypting the message with the authentication key, hashing the message with the authentication key or applying any suitable MAC algorithm using the authentication key in combination with the message, as a seed, parameter, or the like. The MAC algorithm may be CMAC, HMAC or SipHash, for example. The processor is further configured to store each computed message tag in the memory. Subsequently, the processor can compare a received message tag with the stored computed message tags to identify a matching message tag, thereby validating the received message tag as one of the set).
With respect to claim 18 Nagravision and Campagna teaches the method according to claim 15, wherein the cryptographic proof is determined by: comparing content of the true message to the predicted messages; selecting one of said predicted messages based on its similarity or identity to the true message; and retrieving the cryptographic proof from the pre-computed data structure using the selected one of the predicted messages (see Nagravision page 2 lines 22-31 i.e. The processor is configured to combine each message with an authentication key to generate a corresponding message tag. Generating the message tags may comprise encrypting the message with the authentication key, hashing the message with the authentication key or applying any suitable MAC algorithm using the authentication key in combination with the message, as a seed, parameter, or the like. The MAC algorithm may be CMAC, HMAC or SipHash, for example. The processor is further configured to store each computed message tag in the memory. Subsequently, the processor can compare a received message tag with the stored computed message tags to identify a matching message tag, thereby validating the received message tag as one of the set).
With respect to claim 21 Nagravision and Campagna teach the method according to claim 19. Campagna further teaches wherein each leaf node of the binary tree contains a hash of a concatenation of one of the plurality of predicted message messages and a nonce value (see Campagna paragraphs 0040-0042 i.e. The computer system may provide 304 a root of the Merkle tree to the service provider. In some embodiments, the root node provided may be the root of the entire Merkle tree (e.g., the public key 204 illustrated in FIG. 2), but in some embodiments, a root node of a subtree may be provided. Continuing with FIG. 2 as an illustrative example, H.sub.2,0 may be provided as the root node of the subtree having child nodes H.sub.1,0 and H.sub.1,1, and so on. Returning to FIG. 3, the system may, after providing the root node of a Merkle tree (e.g., the root of the full Merkle tree generated), receive 306 as part of a challenge a key identifier and a message. The key identifier and challenge may be provided to the system by a service provider after the service provider receives the root of the Merkle tree. In some embodiments, the key identifier may be an index position of the key that should be used to digitally sign a message. The message may include information corresponding to the user's identity (e.g., an email address) or may include information such as a nonce value which may be a counter that is incremented for each request).
With respect to claim 22 Nagravision and Campagna teach the method according to claim 21. Campagna further teaches comprising: determining a root value for the authenticated binary tree by iterative pairwise hashing of values of nodes of the binary tree; and sharing the root value with at least one message destination using a symmetric key (see Campagna paragraphs 0040-0042 i.e. After or concurrent with the generation of the Merkle tree, the system may generate 310 an authentication path from the signing key to the root node of the Merkle tree. An authentication path may refer to a collection of nodes that may be used to verify that a first node and a second node are connected nodes of a Merkle tree. For example, an authentication path may be formed from a leaf node of the Merkle tree (e.g., a leaf node corresponding to the key identifier) to the root node of the Merkle tree. An authentication path may be verified by hashing the leaf node with the first node of the authentication path, and iteratively hashing the hash outputs with the next node of the authentication path).
With respect to claim 23 Nagravision and Campagna teach the method according to claim 21. Campagna further teaches wherein the cryptographic proof is determined by: determining a leaf node in the binary tree that corresponds to the true message; and traversing the binary tree to retrieve hashes of siblings of nodes on a path between the corresponding leaf node and a root; wherein the cryptographic proof comprises a combination of the nonce value of the corresponding leaf node, and the hashes of all sibling nodes on the path (see Campagna paragraphs 0040-0042 i.e. After or concurrent with the generation of the Merkle tree, the system may generate 310 an authentication path from the signing key to the root node of the Merkle tree. An authentication path may refer to a collection of nodes that may be used to verify that a first node and a second node are connected nodes of a Merkle tree. For example, an authentication path may be formed from a leaf node of the Merkle tree (e.g., a leaf node corresponding to the key identifier) to the root node of the Merkle tree. An authentication path may be verified by hashing the leaf node with the first node of the authentication path, and iteratively hashing the hash outputs with the next node of the authentication path).
With respect to claim 24 Nagravision and Campagna teach the method according to claim 22. Campagna further teaches wherein the root value is shared with a plurality of message destinations (see Campagna paragraphs 0040-0042 i.e. After or concurrent with the generation of the Merkle tree, the system may generate 310 an authentication path from the signing key to the root node of the Merkle tree. An authentication path may refer to a collection of nodes that may be used to verify that a first node and a second node are connected nodes of a Merkle tree. For example, an authentication path may be formed from a leaf node of the Merkle tree (e.g., a leaf node corresponding to the key identifier) to the root node of the Merkle tree. An authentication path may be verified by hashing the leaf node with the first node of the authentication path, and iteratively hashing the hash outputs with the next node of the authentication path).
With respect to claim 26 Nagravision teaches a method for authenticating a message from a message source, comprising:
an initialisation operation comprising receiving a symmetric key from the message source (see Nagravision page 1 lines 26-28 i.e. Message authentication can be based on digital signatures using asymmetric encryption, or on a common shared symmetric key that is used to compute a message tag, known as a Message Authentication Code (MAC));
a pre-verification operation conducted before receiving messages from the message source and comprising: receiving an HMAC (hash-based message authentication code) from the message source; and wherein the HMAC is generated by the message source, and a timestamp (see Nagravision page 2 line 23 – page 3 line 5 i.e. The processor is configured to combine each message with an authentication key to generate a corresponding message tag. Generating the message tags may comprise encrypting the message with the authentication key, hashing the message with the authentication key or applying any suitable MAC algorithm using the authentication key in combination with the message, as a seed, parameter, or the like. The MAC algorithm may be CMAC, HMAC or SipHash, for example. The processor is further configured to store each computed message tag in the memory. Subsequently, the processor can compare a received message tag with the stored computed message tags to identify a matching message tag, thereby validating the received message tag as one of the set. The set of messages may be predefined in a fixed manner, for example a fixed set of possible control or sensor values to be transmitted. Of course, such a fixed set may change from time to time. The set of messages may instead be predetermined dynamically, that is vary over time in a predefined manner, for example so that a small set of possible values can be predicted when communication occurs, for example by consulting a reference common to the sender and transmitter. A sufficient condition on the accuracy of the prediction is that the plurality of values at the sender and transmitter have at least the transmitted value in common to enable the tag for the transmitted value to be recognised. Examples of such values may be dates, times, clock ticks, coordinates close to each other and the like); verifying using the HMAC (see Nagravision page 3 lines 27-29 i.e. Typically, each tag is stored in the memory associated with its corresponding message as a pair, so that a received message can be validated, or a message can be identified by looking up the received tag in the memory); and
an authentication operation comprising: receiving, from the message source, the message and a cryptographic proof of the message (see Nagravision page 5 lines 19-21 i.e. The processor then causes the communications interface to transmit the retrieved message tag corresponding to the selected message, together with or without the message itself); and
verifying the message using the cryptographic proof (see Nagravision page 12 lines 26 – 29 i.e. At step 830 the message tag 230 is validated by a table look-up, for example as described above. If the message tag is successfully validated the corresponding message 230, if received, is of considered to be of validated authenticity or, if the message 230 is not received, is identified in the data structure 220, as described above, at step 840. Steps 830 and 840 may be combined, for example, the received message 220 may be used in a table-look up, the tag 230 retrieved and compared to the received tag 230, or the pair 210 of message 220 and tag 230 may be looked up).
Nagravision does not disclose receiving a root value, wherein the root value is a root value of an authenticated binary tree, each leaf node of the binary tree containing a hash of the concatenation of a predicted message and a nonce value; verifying the root value, if the root value is verified storing the root value; wherein the cryptographic proof comprises a combination of a nonce value of a leaf node corresponding to the message, and the hashes of all sibling nodes on a path between the leaf node and the root of the binary tree; and verifying the message by traversing the binary tree, using the cryptographic proof, to compute a verification value; and comparing the verification value to the stored root value.
Campagna teaches receiving a root value wherein the root value is a root value of an authenticated binary tree, each leaf node of the binary tree containing a hash of the concatenation of a predicted message and a nonce value (see Campagna paragraph 0040-0043 i.e. The computer system may provide 304 a root of the Merkle tree to the service provider. In some embodiments, the root node provided may be the root of the entire Merkle tree (e.g., the public key 204 illustrated in FIG. 2), but in some embodiments, a root node of a subtree may be provided. Continuing with FIG. 2 as an illustrative example, H.sub.2,0 may be provided as the root node of the subtree having child nodes H.sub.1,0 and H.sub.1,1, and so on. Returning to FIG. 3, the system may, after providing the root node of a Merkle tree (e.g., the root of the full Merkle tree generated), receive 306 as part of a challenge a key identifier and a message … In response to the challenge, the system may provide 312 a digital signature over a message, the public signing key corresponding to the private signing key used to generate the digital signature, and the generated authentication path. In some embodiments, the proof-of-work may include the root node, one or more leaf nodes, an authentication path, the digital signature, or some combination thereof. In general, the proof-of-work may include information that may be used to verify a solution to a challenge, and may also provide an indication that the client committed non-trivial computing resources in the generation of the proof-of-work (e.g., performing a number of cryptographic hash operations to generate a Merkle tree)));
verifying the root value, if the root value is verified storing the root value (see Campagna paragraph 0040 i.e. The computer system may provide 304 a root of the Merkle tree to the service provider. In some embodiments, the root node provided may be the root of the entire Merkle tree (e.g., the public key 204 illustrated in FIG. 2), but in some embodiments, a root node of a subtree may be provided. Continuing with FIG. 2 as an illustrative example, H.sub.2,0 may be provided as the root node of the subtree having child nodes H.sub.1,0 and H.sub.1,1, and so on. Returning to FIG. 3, the system may, after providing the root node of a Merkle tree (e.g., the root of the full Merkle tree generated), receive 306 as part of a challenge a key identifier and a message. The key identifier and challenge may be provided to the system by a service provider after the service provider receives the root of the Merkle tree. In some embodiments, the key identifier may be an index position of the key that should be used to digitally sign a message),
wherein the cryptographic proof comprises a combination of a nonce value of a leaf node corresponding to the message, and the hashes of all sibling nodes on a path between the leaf node and the root of the binary tree (see Campagna paragraph 0043 i.e. In response to the challenge, the system may provide 312 a digital signature over a message, the public signing key corresponding to the private signing key used to generate the digital signature, and the generated authentication path. In some embodiments, the proof-of-work may include the root node, one or more leaf nodes, an authentication path, the digital signature, or some combination thereof. In general, the proof-of-work may include information that may be used to verify a solution to a challenge, and may also provide an indication that the client committed non-trivial computing resources in the generation of the proof-of-work (e.g., performing a number of cryptographic hash operations to generate a Merkle tree))
verifying the message by traversing the binary tree, using the cryptographic proof, to compute a verification value; and comparing the verification value to the stored root value (see Campagna paragraphs 0040-0042 i.e. After or concurrent with the generation of the Merkle tree, the system may generate 310 an authentication path from the signing key to the root node of the Merkle tree. An authentication path may refer to a collection of nodes that may be used to verify that a first node and a second node are connected nodes of a Merkle tree. For example, an authentication path may be formed from a leaf node of the Merkle tree (e.g., a leaf node corresponding to the key identifier) to the root node of the Merkle tree. An authentication path may be verified by hashing the leaf node with the first node of the authentication path, and iteratively hashing the hash outputs with the next node of the authentication path. An authentication path may be generated in accordance with techniques described above, for example, in connection with FIGS. 1-2).
It would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to modify Nagravision in view of Campagna to have used a Merkle Tree as one way to authenticate date since a Merkle Tree allows efficient and secure verification of data (see Campagna paragraph 0040-0042). Therefore, one would have been motivated to have used a Merkle Tree.
Claims 2 and 16 are rejected under 35 U.S.C. 103 as being unpatentable over Nagravision (WO 2020/038789) in view of Campagna et al (US 2018/0183601) in view of Ochoa et al (US 2020/0128042).
With respect to claim 2 Nagravision and Campagna teaches the apparatus according to claim 1, but does not disclose wherein the pre- computed data structure is determined based on at least a most likely or urgent one of the predicted messages.
Ochoa teaches wherein the pre- computed data structure is determined based on at least a most likely or urgent one of the predicted messages (see Ochoa paragraph 0061-0062 i.e. The premise of identifying critical payloads 1000 is that not all packets being transmitted by nodes in the ICS need to be authenticated. It is appreciated that some packets are less important than others as their manipulation do not pose a threat to the ICS. As such, by identifying which network packets are carrying critical payloads 1000, those critical network packets can be selectively authenticated).
It would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to modify Nagravision in view of Ochoa to have selectively capturing a critical network packet that are identified based on a predefined list of critical payloads and generating a signature from the critical network packet using a signing algorithm and transmitting a combined network packet that includes the critical network packet and the signature to the address as a way to protect and authenticate critical payload packets transmitted by nodes that contain critical network packet (see Ochoa paragraph 0010 and 0061).
With respect to claim 16 Nagravision and Campagna teaches the method according to claim 15, but does not disclose wherein the pre-computed data structure is determined based on at least a most likely or urgent one of the predicted messages.
Ochoa teaches wherein the pre-computed data structure is determined based on at least a most likely or urgent one of the predicted messages (see Ochoa paragraph 0061 i.e. The premise of identifying critical payloads 1000 is that not all packets being transmitted by nodes in the ICS need to be authenticated. It is appreciated that some packets are less important than others as their manipulation do not pose a threat to the ICS. As such, by identifying which network packets are carrying critical payloads 1000, those critical network packets can be selectively authenticated).
It would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to modify Nagravision in view of Ochoa to have sel