Light weight authentication and secret retrieval
First Claim
Patent Images
1. A method for authenticating a message in a network, the method comprising:
- generating, in a sink device, a private key and a public key, wherein the private key comprises a plurality of sub-private keys and the public key comprises a plurality of sub-public keys, the generation of the public key comprising;
hashing the sub-private keys;
constructing a plurality of hash trees, the hash trees comprising a plurality of leaf nodes, root nodes, and intermediate nodes between the leaf nodes and the root nodes, wherein the leaf nodes are the hashed sub-private keys; and
selecting the root nodes of the hash trees as the sub-public keys; and
generating, in the sink device, a signature for the message, wherein the signature comprises one of the sub-private keys and an authentication path associated with the one of the sub-private keys in a first one of the hash trees, and the generation of the signature comprises;
hashing the message into a hash value;
splitting the hash value into k piece(s), wherein one value of the k piece(s) is k1;
using k1 as an index to select the one of the sub-private keys; and
using the one of the sub-private keys to select the authentication path.
1 Assignment
0 Petitions
Accused Products
Abstract
A method for authenticating a message in a network is provided. The method includes a step of generating, in a sink device, a private key and a public key. The private key includes a plurality of sub-private keys. The method further includes a step of generating, in the sink device, a signature for the message. The signature includes a sub-private key and an authentication path associated with the sub-private key in a hash tree. The hash tree is constructed during the generation of the sub-public keys.
-
Citations
23 Claims
-
1. A method for authenticating a message in a network, the method comprising:
-
generating, in a sink device, a private key and a public key, wherein the private key comprises a plurality of sub-private keys and the public key comprises a plurality of sub-public keys, the generation of the public key comprising; hashing the sub-private keys; constructing a plurality of hash trees, the hash trees comprising a plurality of leaf nodes, root nodes, and intermediate nodes between the leaf nodes and the root nodes, wherein the leaf nodes are the hashed sub-private keys; and selecting the root nodes of the hash trees as the sub-public keys; and generating, in the sink device, a signature for the message, wherein the signature comprises one of the sub-private keys and an authentication path associated with the one of the sub-private keys in a first one of the hash trees, and the generation of the signature comprises; hashing the message into a hash value; splitting the hash value into k piece(s), wherein one value of the k piece(s) is k1; using k1 as an index to select the one of the sub-private keys; and using the one of the sub-private keys to select the authentication path. - View Dependent Claims (2, 3, 4, 5)
-
-
6. In an authentication system, a method for a tag device to verify a message from a sink device, wherein the sink device has a computation capability greater than the tag device, the method comprising:
-
generating, in the sink device, a private key and a public key, wherein the private key comprises a plurality of sub-private keys and the public key comprises a plurality of sub-public keys; storing, in the sink device, the private key; generating, in the sink device, a signature for the message, wherein the signature comprises one of the sub-private keys and an authentication path associated with the one of the sub-private keys in a hash tree, the hash tree being constructed during the generation of the sub-public keys, and wherein the generation of the signature comprises; hashing the message into a hash value; splitting the hash value into k piece(s), wherein one value of the k piece(s) is k1; using k1 as an index to select the one of the sub-private keys; and using the one of the sub-private keys to select the authentication path; and transmitting the public key, the message, and the signature from the sink device to the tag device, wherein the generation of the public key comprises; hashing the sub-private keys; constructing a plurality of hash trees, the hash trees comprises a plurality of leaf nodes, root nodes, and intermediate nodes between the leaf nodes and the root node, wherein the leaf nodes are the hashed sub-private keys; and selecting root nodes of the hash trees as the sub-public keys. - View Dependent Claims (7, 8, 9)
-
-
10. A method for uploading a message from a sink device into a tag device, wherein the sink device has a computation capability greater than the tag device, the method comprising:
-
generating, in the sink device, a private key, wherein the private key comprises a plurality of sub-private keys; hashing the sub-private keys; generating a public key by constructing a plurality of hash trees having root nodes, using the hashed sub-private keys as leaf nodes, wherein the root nodes of the hash trees are selected as the sub-public keys that form the public key; encrypting the message into an encrypted message; generating a signature for the encrypted message in the sink device by; hashing the message into a hash value; splitting the hash value into k piece(s), wherein one value of the k piece(s) is k1; using k1 as an index to select one of the sub-private keys; and selecting an authentication path associated with the one of the sub-private keys; and transmitting the encrypted message and the signature to the tag device. - View Dependent Claims (11, 12, 13)
-
-
14. A method for a sink device to search an encrypted message stored in a tag device without decryption of the encrypted message, the sink device having a computation capability greater than the tag device, the method comprising:
-
hashing, in the sink device, a message to be a first hash value; hashing, in the sink device, a secret to be a second hash value, wherein the secret is shared between the sink device and the tag device; hashing, in the sink device, an index message to be a third hash value, wherein the index message is associated with the message; encrypting, in the sink device, the message by an operation of exclusive disjunction over the message, the first hash value, and the second hash value, and encrypting the index message by an operation of exclusive disjunction over the index message, the second hash value, and the third hash value; generating, in the sink device, a first signature for the encrypted message and the encrypted index message; and storing, in the tag device, the encrypted message and the encrypted index message. - View Dependent Claims (15, 16, 17)
-
-
18. A system comprising:
-
a sink device; and a tag device, the sink device comprising; a memory for storing instructions and data; and a processor coupled to the memory, the processor operable to execute instructions stored in the memory for; generating a private key and a public key, wherein the private key comprises a plurality of sub-private keys and the public key comprises a plurality of sub-public keys, the generation of the public key comprising; hashing the sub-private keys; constructing a plurality of hash trees, the hash trees comprising a plurality of leaf nodes, a root node, and intermediate nodes between the leaf nodes and the root node, wherein the leaf nodes are the hashed sub-private keys; and selecting the root nodes of the hash trees as the sub-public keys; generating a signature for a message, wherein the signature comprises one of the sub-private keys and an authentication path associated with the one of the sub-private keys in one of the hash trees, and wherein the generation of the signature comprises; hashing the message into a hash value; splitting the hash value into k piece(s), wherein one value of the k piece(s) is k1; using k1 as an index to select the one of the sub-private keys; and using the one of the sub-private keys to select the authentication path; and transmitting the public key, the message and the signature from the sink device to the tag device. - View Dependent Claims (19)
-
-
20. A system for uploading a message in a network, the system comprising:
- a sink device and a tag device, the sink device comprising;
a memory for storing instructions and data; and a processor coupled to the memory, the processor operable to execute instructions stored in the memory for; generating a private key, wherein the private key comprises a plurality of sub-private keys; hashing the sub-private keys; generating a public key by constructing a plurality of hash trees having root nodes, using the hashed sub-private keys as leaf nodes, wherein the root nodes of the hash trees are selected as the sub-public keys constituting the public key; encrypting the message into an encrypted message; generating a signature for the encrypted message by; hashing the message into a hash value; splitting the hash value into k piece(s), wherein one value of the k piece(s) is k1; using k1 as an index to select one of the sub-private keys; and selecting an authentication path associated with the one of the sub-private keys; and transmitting the encrypted message and the signature to the tag device. - View Dependent Claims (21)
- a sink device and a tag device, the sink device comprising;
-
22. A system for searching an encrypted message within a network without decryption of the encrypted message, the system comprising:
-
a tag device; and a sink device, the sink device comprising; a first memory for storing instructions and data; and a first processor coupled to the first memory, the first processor operable to execute instructions stored in the first memory for; hashing a message to be a first hash value; hashing a secret to be a second hash value, wherein the secret is shared between the sink device and the tag device; hashing an index message to be a third hash value, wherein the index message is associated with the message; encrypting the message by an operation of exclusive disjunction over the message, the first hash value, and the second hash value, and encrypting the index message by an operation of exclusive disjunction over the index message, the second hash value, and the third hash value; generating a first signature for the encrypted message and the encrypted index message; transmitting the encrypted message, the encrypted index message, and the first signature to the tag device; generating a search message by an operation of exclusive disjunction over the index message and the third hash value; generating a second signature for the search message in the sink device; and transmitting the search message and the second signature to the tag node. - View Dependent Claims (23)
-
Specification