SYSTEM AND METHOD FOR AN ELECTRONIC SIGNATURE FOR QUICK AND EFFICIENT DATA AUTHENTICATION

• US 20110083015A1
• Filed: 10/05/2009
• Published: 04/07/2011
• Est. Priority Date: 10/05/2009
• Status: Abandoned Application

• Current Assignee: Eidgenossiche Technische Hochschule Zurich
• Original Assignee: Eidgenossiche Technische Hochschule Zurich
• Inventors: Meier, Remo
• Application Number:
  US12/573,596
• Publication Number:
  US 20110083015A1
• Time in Patent Office: Days
• US Class Current: 713/176
• CPC Class Codes: H04L 9/3236 using cryptographic hash functions
• CPC Class Codes: H04L 9/3247 involving digital signatures
• CPC Class Codes: H04L 9/50 using hash chains, e.g. blockchains or hash trees

Abstract

System and method for generating an electronic signature to authenticate data includes generating a private and a public key using the last value in a hash chain formed from the private key as a starting point, signing a message m, using a distinct set of hash chains using a second secure hash value of the message m and a counter c, selecting a block offset using the hash value of the selected chains, the message m, and the counter c, generating the signature from the selected seals and the counter. The electronic signature validity is verified by synchronizing a verification unit with a source of a signed message, computing expected chains by hashing the signed message m and a counter c with a first hash function, computing a set of expected block offsets by hashing the signed message m, counter c, and computed chains with a second hash function.

Claims

1. A method for generating an electronic signature to authenticate data, the method comprising the steps of:

generating, by a private key generation subunit, a private key comprised of uniformly random chosen values;

creating, by a public key generation unit, a public key using a last value in a hash chain formed from using a first secure hash function H;

{0,1}^q→

{0,1} with security parameter q and the private key values as starting points, wherein the hash chain has l blocks each of a size b, and the hash chain has a length of bl+1 blocks;

encoding, by a signing unit, a message m, wherein the encoding includes the steps of;

selecting, by a chain selection unit, a distinct set of hash chains using a second secure hash value of the message m and a counter c, wherein the second secure hash function is denoted by H_{{1, . . . , n}}<sup>λ

,distinct</sup>, wherein λ

is the number of chains in the set;

selecting, by an offset selection unit, a block offset for each selected hash chain by adding the selected chains, the message m, and the counter c in a third hash function denoted by H_{{1, . . . b}}<sup>λ

-1</sup> (m, c, c₁, . . . , c_λ

);

creating the electronic signature s_c1,uc1,p1, . . . , s<sub>cλ

,ucλ

,pλ</sub>

of the message m, by a signature generator, wherein {c₁, . . . , cλ

} represents the selected chains, {p₁, . . . , p_λ

} represents the block offsets and {u_c1, . . . , u_cλ

} represents indices of the blocks.

2. The method of claim 1, further including the steps of:

summing the block offsets; and

if the block offset sum does note equal ½

λ

(1+b), increasing the value of counter c by 1 and repeating the encoding step.

3. The method of claim 1, further including the steps of:

decreasing, by the signature generator, the indices {u_c1, . . . , u_cλ

}; and

if any of the selected chains have been used and no further blocks remain, repeating the generating a private key and creating a public key steps;

otherwise, continue creating the electronic signature.

4. A method for verifying a validity of an electronic signature, the method comprising the steps of:

weakly synchronizing a verification unit with a source of a signed message by receiving a seal in the electronic signature from the source or a trusted third party;

computing, by a verifying unit, a set of expected chains by hashing the signed message m and a counter c with a first hash function denoted H_{{1, . . . , n}}<sup>λ

distinct</sup> (m, c);

computing, by a verifying unit, a set of expected block offsets by hashing the signed message m, the counter c, and the computed chains {c₁, . . . c_λ

} with a second hash function denoted H_{{1, . . . b}}<sup>λ

-1</sup> (m, c, c₁, . . . , c_λ

);

determining the validity of the electronic signature.

5. The method of claim 4, wherein the determining step includes the steps of

matching the chains in the signature to the expected chains, and the expected block offsets computed from hashing the signed message;

and

ascertaining whether the chains in the electronic signature have been used in a prior electronic signature.

6. The method of claim 4, wherein if the received seal is received from an untrusted third party, the method further includes the step of performing the synchronizing of the verification unit only if the received seal is time stamped and signed by the source of the signed message.

7. A system for generating an electronic signature to authenticate data, the system comprising:

a private key generation subunit configured to generate a private key comprised of uniformly random chosen values;

a public key generation unit configured to generate a public key using a last value in a hash chain formed from using a first secure hash function H;

{0,1}^q→

{0,1} with security parameter q and the private key value as starting points, wherein the hash chain has l blocks each of a size b, and the hash chain has a length of bl+1 blocks;

a signing unit configured to encode a message m, wherein the signing unit includes;

a chain selection unit configured to select a distinct set of hash chains using a second secure hash value of the message m and a counter c, wherein the second secure hash function is denoted by H_{{1, . . . , n}}<sup>λ

,distinct</sup>, wherein λ

is the number of chains in the set;

an offset selection unit configured to select a block offset for each selected hash chain by adding the selected chains, the message m, and the counter c in a third hash function denoted by H_{{1, . . . , b}}<sup>λ

-1</sup> (m, c, c₁, . . . , c_λ

); and

a signature generator configured to create an electronic signature s_c1,uc1,p1, . . . , s<sub>cλ

,ucλ

,pλ</sub>

of the message m, wherein {c₁, . . . , cλ

} represents the selected chains, {p₁, . . . , p_λ

} represents the block offsets and {u_c1, . . . , u_cλ

} represents indices of the blocks.

8. The system of claim 7, wherein the signing unit is further configured to sum the block offsets, and if the block offset sum does note equal ½

λ

(1+b), to increase the value of counter c by 1.

9. The system of claim 7, wherein the signature generator is further configured to decrease the indices {u_c1, . . . , u_cλ

}; and

if any of the selected chains have been used and no further blocks remain, to generate an updated private key and create an updated public key.

10. The system of claim 7, further including:

a verification unit configured to be weakly synchronized with a source of a signed message, wherein the synchronization is done with a seal in an electronic signature received from the source or a trusted third party;

a verifying unit configured to compute a set of expected chains by hashing the signed message m and a counter c with the second secure hash function;

a verifying unit configured to compute a set of expected block offsets by hashing the signed message m, the counter c, and the computed chains {c₁, . . . c_λ

} with the third hash function; and

the verification unit further configured to determine the validity of the electronic signature.

11. The system of claim 10, wherein the verification unit is further configured to match the chains in the signature to the expected chains, and the expected block offsets computed from hashing the signed message, and to ascertain whether the chains in the electronic signature have been used in a prior electronic signature.

12. The system of claim 10, wherein the verification unit is further configured, if the received seal is received from an untrusted third party, to synchronize only if the received seal is time stamped and signed by the source of the signed message.