LIGHT WEIGHT AUTHENTICATION AND SECRET RETRIEVAL

• US 20100042842A1
• Filed: 08/12/2008
• Published: 02/18/2010
• Est. Priority Date: 08/12/2008
• Status: Active Grant

• Current Assignee: Industrial Technology Research Institute
• Original Assignee: Industrial Technology Research Institute
• Inventors: Chang, Sheng-Ming, Wang, Chi-Wei, Huang, Shih-I, Shieh, Shiuh-Pyng
• Granted Patent: US 8,595,504 B2
• Time in Patent Office: Days
• US Class Current: 713/176
• CPC Class Codes: G06F 16/2365 Ensuring data consistency and integrity
• CPC Class Codes: H04L 2209/805 Lightweight hardware, e.g. radio-frequency identification [RFID] or sensor
• CPC Class Codes: H04L 9/3236 using cryptographic hash functions
• CPC Class Codes: H04L 9/3247 involving digital signatures

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.

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

generating, in the sink device, a signature for the message, wherein the signature comprises a sub-private key and an authentication path associated with the sub-private key in a hash tree, wherein the hash tree is constructed during the generation of the sub-public keys.

2. The method of claim 1, wherein the hash tree is a first hash tree, the method further comprising:

transmitting the public key, the message and the signature from the sink device to a tag device; and

verifying, in the tag device, the signature by constructing a second hash tree using the sub-private key and the authentication path.

3. The method of claim 2, the method further comprising:

storing, in the tag device, the message if the signature is verified.

4. The method of claim 3, wherein the signature is a first signature, the sub-private key is a first sub-private key, and the authentication path is a first authentication path, the method further comprising:

generating, in the sink device, a search message for searching the message stored in the tag device; and

generating, in the sink device, a second signature for the search message, wherein the second signature comprises a second sub-private key and a second authentication path associated with the second sub-private key in a third hash tree, wherein the third hash tree is constructed during the generation of the sub-public keys.

5. The method of claim 4, the method further comprising:

transmitting the search message and the second signature from the sink device to the tag device; and

verifying, in the tag device, the second signature by constructing a fourth hash tree using the second sub-private key and the second authentication path.

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 a sub-private key and an authentication path associated with the sub-private key in a hash tree, wherein the hash tree is constructed during the generation of the sub-public keys; and

transmitting the public key, the message and the signature from the sink device to the tag device,

wherein the sub-private keys are generated by a pseudorandom generator.

7. The method of claim 6, wherein the generation of the public key comprises:

hashing the sub-private keys;

constructing a plurality of hash trees, wherein each of the hash trees comprises a plurality of leaf nodes, a root node, and a plurality of intermediate nodes between the leaf nodes and the root node, wherein the leaf nodes are the hashed sub-private keys; and

selecting each of root nodes of the hash trees as the sub-public keys.

8. The method of claim 7, wherein the quantity of the sub-private keys are t and the quantity of the hash trees is d, wherein a height of each of the hash trees is equal to (ln t−

ln d).

9. The method of claim 8, wherein the generation of the signature for the message in the sink device further 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;

selecting the sub-private key by using k1 as an index;

selecting the authentication path associated with the sub-private key, wherein the authentication path does not comprise the root node of the hash tree.

10. The method of claim 9, wherein the hash tree is a first hash tree, the sub-private key is a first sub-private key, and the authentication path is a first authentication path;

and

wherein the generation of the signature for the message in the sink device further comprising;

selecting a second sub-private key in a second hash tree; and

selecting a second authentication path associated with the second sub-private key.

11. The method of claim 9, wherein the hash value is a first hash value, and wherein the verification of the signature in the tag device further comprises:

generating a second hash value by computing the message;

splitting the second hash value into m piece(s), wherein one value of the m piece(s) is m1;

selecting a sub-public key in the public key by using ml as an index; and

verifying the sub-public key.

12. 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 using the hashed sub-private keys as leaf nodes;

encrypting the message into an encrypted message;

generating a signature for the encrypted message in the sink device by selecting a sub-private key and an authentication path in a hash tree, wherein the hash tree is constructed during the generation of the public key; and

transmitting the encrypted message and the signature to the tag device.

13. The method of claim 12, further comprising verifying, in the tag device, the signature;

and storing, in the tag device, the message if the signature is verified.

14. The method of claim 12, wherein the public key comprises each of the root nodes of the hash trees and wherein the selected authentication path in the hash tree does not comprise the root node of the hash tree.

15. The method of claim 12, wherein the encryption of the message further comprises:

hashing the message to be a first hash value;

hashing a secret to be a second hash value; and

computing the message with the first hash value and the second hash value by an operation of exclusive disjunction,

wherein the secret is shared by the sink device and the tag device.

16. 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 extrusive disjunction over the message, the first hash value, and the second hash value, and encrypting the index message by an operation of extrusive 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.

17. The method of claim 16, further comprising:

generating, in the sink device, a search message by an operation of extrusive disjunction over the index message and the third hash value;

generating, in the sink device, a second signature for the search message;

transmitting the search message and the second signature to the tag node;

computing, in the tag device, the search message with the second hash value by an operation of extrusive disjunction to obtain an index verification;

comparing the index verification with the encrypted index message; and

transmitting the encrypted message from the tag device to the sink device if the index verification is equal to the encrypted index message.

18. The method of claim 17, further comprising:

generating, in the sink device, a private key, wherein the private key comprises a plurality of sub-private keys;

hashing, in the sink device, the sub-private keys;

generating, in the sink device, a public key by constructing a plurality of hash trees using the hashed sub-private keys as leaf nodes; and

storing, in the tag device, the public key.

19. The method of claim 18, wherein the second signature comprises a second sub-private key and a second authentication path in a third hash tree, the method further comprising:

verifying, in the tag device, the second signature by constructing a fourth hash tree with the second sub-private key and the second authentication path to compute a root node of the fourth hash tree, and by comparing the root node of the fourth hash tree with the public key.

20. 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;

generating a signature for the message, wherein the signature comprises a sub-private key and an authentication path associated with the sub-private key in a hash tree, wherein the hash tree is constructed during the generation of the sub-public keys; and

transmitting the public key, the message and the signature from the sink device to the tag device.

21. The system of claim 20, wherein the hash tree is a first hash tree, the memory is a first memory, and the processor is a first processor, and wherein the tag device comprises:

a second memory; and

a second processor coupled to the second memory, the second processor operable to execute instructions in the second memory for;

verifying the signature by constructing a second hash tree using the sub-private key and the authentication path.

22. 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 using the hashed sub-private keys as leaf nodes;

encrypting the message into an encrypted message;

generating a signature for the encrypted message by selecting a sub-private key and an authentication path associated with the sub-private key in a hash tree, wherein the hash tree is constructed during the generation of the public key; and

transmitting the encrypted message and the signature to the tag device.

23. The system of claim 22, wherein the selected authentication path in the hash tree does not comprise the root node of the hash tree.

24. A system for searching an encrypted message within a network without decryption of the encrypted message, the system comprising:

a sink device and a tag 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 extrusive disjunction over the message, the first hash value, and the second hash value, and encrypting the index message by an operation of extrusive 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 extrusive 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.

25. The system of claim 24, wherein the tag device comprises:

a second memory; and

a second processor coupled to the second memory, the second processor operable to execute instructions in the second memory for;

receiving the encrypted message, the encrypted index message, and the first signature;

storing the encrypted message and the encrypted index message in the second memory if the first signature is verified;

receiving the search message and the second signature;

verifying the second signature;

computing the search message and the second hash value to obtain an index verification;

comparing the index verification with the encrypted index message; and

transmitting the encrypted message to the sink device if the index verification is equal to the encrypted index message.