System and method for digital signatures and authentication

• US 8,291,229 B2
• Filed: 12/16/2008
• Issued: 10/16/2012
• Est. Priority Date: 01/17/2008
• Status: Expired due to Fees

• Current Assignee: Hitachi, Ltd.
• Original Assignee: Hitachi, Ltd.
• Inventors: Vuillaume, Camille, Okeya, Katsuyuki, Dahmen, Erik
• Primary Examiner(s): Chea, Philip
• Assistant Examiner(s): Traore, Fatoumata
• Application Number:
  US12/335,683
• Publication Number:
  US 20090187766A1
• Time in Patent Office: 1,400 Days
• Field of Search: None
• US Class Current: 713/176
• CPC Class Codes: G06F 21/33 using certificates
• CPC Class Codes: G06F 21/34 involving the use of external additional devices, e.g. dongles or smart cards
• CPC Class Codes: H04L 2209/30 Compression, e.g. Merkle-Damgard construction
• CPC Class Codes: H04L 2209/805 Lightweight hardware, e.g. radio-frequency identification [RFID] or sensor
• CPC Class Codes: H04L 63/0853 using an additional device, e.g. smartcard, SIM or a different communication terminal cryptographic mechanisms or cryptographic arrangements for entity authentication involving additional secure or trusted devices H04L9/3234
• CPC Class Codes: H04L 9/3226 using a predetermined code, e.g. password, passphrase or PIN network architectures or network communication protocols for supporting authentication of entities using passwords in a packet data network H04L63/083
• CPC Class Codes: H04L 9/3247 involving digital signatures
• CPC Class Codes: H04L 9/3271 using challenge-response
• CPC Class Codes: H04L 9/50 using hash chains, e.g. blockchains or hash trees

Abstract

A system and method for authentication and digital signatures on memory-only supports, comprising a read-once memory unit storing secret arrays, whose contents are destroyed upon reading, a standard memory unit storing encrypted arrays, tree data authenticating the encrypted arrays to one single public key, and a certificate of the public key issued by a certificate authority. The memory support sends its public key and certificate to a verifier, receives a challenge which is signed by elements from secret arrays in the read-once memory. The verifier system checks the authenticity of the data revealed from the read-once memory by encrypting it and comparing the result to one of the encrypted arrays, and verifies that the encrypted array authenticates to the public key using tree data. Finally, the verifier checks the authenticity of the public key using the certificate.

Claims

1. A cryptographic system for generating digital signatures, comprising:

(a) a memory configured to store secret data, encrypted data, authentication data and a public key;

(b) a receiver configured to receive an input message;

(c) a secret data extracting unit configured to extract secret data blocks from the secret data;

(d) a data block extracting unit configured to extract encrypted data blocks from the encrypted data;

(e) an authentication data block extracting unit configured to extract authentication data blocks from the authentication data;

(f) a counter unit configured to update a counter; and

(g) a sending unit configured to send a digital signature of the input message,

wherein the digital signature includes the extracted secret data blocks, the extracted encrypted data blocks and the extracted authentication data blocks,

wherein the secret data extracting unit is further configured to effect operations to;

(c-1) scan one bit of the input message,

(c-2) access a pair of secret data blocks in the secret data,

(c-3) reveal one secret data block in the pair if the bit is zero, and reveal the other secret data block in the pair if the bit is one,

(c-4) erase the pair from the secret data, and

(c-5) iterate the above operations for all bits of the input message, whereby the digital signatures include the revealed secret data blocks.

2. The system recited in claim 1, wherein the secret data is organized in a plurality of secret arrays, and the secret arrays store a plurality of secret data blocks, and the secret blocks are organized in pairs, wherein only one of the secret data blocks can be accessed in the pair and both secret data blocks are destroyed upon reading the element in the pair.

3. The system recited in claim 2, which further comprises a memory controller, wherein the memory controller erases a predetermined number of the secret data blocks upon accessing the memory.

4. The system recited in claim 3, wherein the memory includes a flash memory unit.

5. The system recited in claim 3, wherein the memory includes an EEPROM memory unit.

6. The system recited in claim 2, wherein the encrypted data is organized in a plurality of encrypted arrays, and the encrypted arrays store a plurality of encrypted data blocks, and the encrypted data blocks store the secret data blocks from the secret arrays encrypted with a cryptographic processing unit.

7. The system recited in claim 6, wherein the cryptographic processing unit is a hash function unit.

8. The system recited in claim 7, wherein the authentication data is organized in a tree storing a plurality of nodes, and leaves of the tree store a predetermined number of the encrypted data blocks further encrypted with the hash function unit, and a parent node in the tree stores a predetermined number of children nodes encrypted with the hash function unit, whereby the public key is derived from the root of the tree.

9. The system recited in claim 1, wherein the memory includes an array of fuses, wherein a predetermined number of fuses are blown upon accessing the memory.

10. The system recited in claim 1, wherein the memory includes a FeRAM memory unit.

11. A method of generating digital signatures, comprising:

(a) providing a memory configured to store secret data, encrypted data, authentication data and a public key;

(b) receiving an input message;

(c) extracting secret data blocks from the secret data;

(d) extracting encrypted data blocks from the encrypted data;

(e) extracting authentication data blocks from the authentication data;

(f) updating a counter; and

(g) sending a digital signature of the input message,

wherein the digital signature includes the extracted secret data blocks, the extracted encrypted data blocks and the extracted authentication data blocks,

wherein the extracting secret data blocks further includes operations of;

(c-1) scanning one bit of the input message,

(c-2) accessing a pair of secret data blocks in the secret data,

(c-3) revealing one secret data block in the pair if the bit is zero, and revealing the other secret data block in the pair if the bit is one,

(c-4) erasing the pair from the secret data, and

(c-5) iterating the above operations for all bits of the input message, whereby the digital signatures include the revealed secret data blocks.

12. The method recited in claim 11, wherein the extracting secret data blocks further includes:

(c-1) erasing the extracted secret data blocks, and

(c-2) for each extracted secret data block, erasing at least one other secret data block.

13. The method recited in claim 11, wherein the encrypted data is initialized by encrypting all secret data blocks from the secret data with a cryptographic encryption function.

14. The method recited in claim 13, wherein the cryptographic encryption function is a hash function.

15. The method recited in claim 14, further comprising authentication including:

(h) computing leaf nodes by hashing a predetermined number of encrypted data blocks with the hash function,

(i) computing at least one new node by hashing a predetermined number of nodes that have been computed in the previous operation,

(j) iterating operation b until one single node remains,

whereby the public key of the digital signature method is derived from the last node computed by the initialization method.