System and method for generating one-time data signatures

• US 10,511,447 B1
• Filed: 09/26/2018
• Issued: 12/17/2019
• Est. Priority Date: 09/26/2018
• Status: Active Grant

• Current Assignee: Guardtime SA
• Original Assignee: Guardtime SA
• Inventors: Lakk, Henri
• Primary Examiner(s): Jamshidi, Ghodrat
• Application Number:
  US16/143,244
• Time in Patent Office: 447 Days
• CPC Class Codes: H04L 9/006 involving public key infrastructure [PKI] trust models network architecture or network communication protocol for supporting authentication of entities using certificates in a packet data network H04L63/0823
• CPC Class Codes: H04L 9/0869 involving random numbers or seeds
• CPC Class Codes: H04L 9/30 Public key, i.e. encryption algorithm being computationally infeasible to invert or user's encryption keys not requiring secrecy
• CPC Class Codes: H04L 9/3239 involving non-keyed hash functions, e.g. modification detection codes [MDCs], MD5, SHA or RIPEMD
• CPC Class Codes: H04L 9/3247 involving digital signatures
• CPC Class Codes: H04L 9/3297 involving time stamps, e.g. generation of time stamps
• CPC Class Codes: H04L 9/50 using hash chains, e.g. blockchains or hash trees

Abstract

A digital signature is created for a data set based on a group of one-time secret keys. Revealable, representative values of the secret keys are computed, for example by cryptographic hashing, and an authentication code vector is also formed having elements that cryptographically combine each secret key with a randomizing function of the data set. The vector is timestamped and signed at a signing time. Bits of a binary representation of the signing time are used to select which of the secret values are included in a selected key vector. A signature of the digital data is then compiled to include the set of authentication code values, the signature of the authentication code vector, and the selected key vector. The secret keys thereby become unusable after the signing time.

Claims

1. A method for verifying the authenticity of a digital data set D comprising:

selecting a plurality T of secret values;

for each secret value, computing a representative value as the output of a randomizing function;

computing a public key from the representative values;

computing a document function value of the digital data set;

compiling a set of T authentication code values by computing each authentication code value as an at least pseudo-randomizing functional combination of the document function value and a respective one of the secret values;

timestamping the set of T authentication code values at a signing time t said timestamping being synchronized with physical time, and compiling a time vector having elements corresponding to binary bits of a digital representation of the signing time;

digitally signing the set of authentication code values at the signing time t to yield a first signature;

compiling a selected key vector having a plurality of elements, each element being a respective one of the secret values when the corresponding respective element of the time vector has a first binary value; and

forming a signature of the digital data set to include the set of authentication code values, the first signature, and the selected key vector.

2. The method of claim 1, further comprising setting each element of the selected key vector for which the respective element of the time vector has a second binary value to be the corresponding representative value of the respective secret value.

3. The method of claim 2, in which the step of computing the public key comprises computing the public key as a root of a binary hash tree having leaf values formed from the secret values for which the respective element of the time vector has the first binary value and the representative values for which the respective element of the time vector has the second binary value.

4. The method of claim 1, in which the step of computing the public key comprises computing the public key as an aggregation of the representative values.

5. The method of claim 4, in which the step of computing the public key comprises computing the public key as a single hash function having the representative values as input parameters.

6. The method of claim 1, in which the step of digitally signing the authentication code values first signature comprises submitting the authentication code values as an input to a hash tree infrastructure system that has a plurality of digital input values, said first signature including values enabling recomputation upward through the hash tree infrastructure to a root hash value at a calendar period that corresponds to the signing time t, such that the first signature also acts as a timestamp for the set of authentication code values.

7. The method of claim 1, further comprising generating the secret values from a common seed value.