Systems and methods for compromise resilient and compact authentication for digital forensics

Abstract

A new compromise-resilient and compact cryptographic tool is provided that ensures a breach-resilient authentication and integrity of system measurements in computer systems. The described methods are forward-secure digital signatures with signature and partial public key aggregation capabilities. The methods reduce the total space overhead of signature and public key storage. The methods offer a high space efficiency for systems who has relatively low state transitions, wherein the same message is continuously signed and then followed by different messages.

Claims

1. A method comprising: receiving a plurality of messages, wherein each message is associated with a time period from a set of time periods; receiving a plurality of public key and private key pairs, wherein each pair is associated with a time period from the set of time periods; for each message of the plurality of messages: using the private key for the message to generate an aggregate signature for the message based on the message and an aggregate signature of a previous message of the plurality of messages; and generating an aggregate public key for the message using the public key associated with the message and an aggregate public key associated with the previous message; providing the aggregate public key and aggregate signature of a last message of the plurality of messages; and authenticating at least one message of the plurality of messages using the provided aggregate public key and aggregate signature.

2. The method of claim 1, wherein at least some of the messages of the plurality of messages are the same.

3. The method of claim 1, wherein the aggregate signatures are generated using a BLS signature scheme.

4. The method of claim 1, wherein the aggregate signatures are generated using an ETA signature scheme.

5. The method of claim 1, wherein the aggregate public keys and aggregate signatures are combined for a plurality of different sets of time periods using an MMM generic digital signature scheme.

6. A system comprising: at least one processor; and a tangible computer readable medium storing instructions that when executed by the at least one processor cause the at least one processor to: receive a plurality of images, wherein each image is associated with a time period from a set of time periods; receive a plurality of public key and private key pairs, wherein each pair is associated with a time period from the set of time periods; for each image of the plurality of images: use the private key for the message to generate an aggregate signature for the image based on the image and an aggregate signature of a previous image of the plurality of images; and generate an aggregate public key for the image using the public key associated with the image and an aggregate public key associated with the previous image; provide the aggregate public key and aggregate signature of a last image of the plurality of images; and authenticate at least one image of the plurality of images using the provided aggregate public key and aggregate signature.

7. The system of claim 6, wherein at least some of the images of the plurality of images are the same.

8. The system of claim 6, wherein the aggregate signatures are generated using a BLS signature scheme.

9. The system method of claim 6, wherein the aggregate signatures are generated using an ETA signature scheme.

10. The system of claim 6, wherein the aggregate public keys and aggregate signatures are combined for a plurality of different sets of time periods using an MMM generic digital signature scheme.

11. A non-transitory computer-readable medium comprising instructions that, when executed by at least one processor, cause the at least one processor to: receive a plurality of messages, wherein each message is associated with a time period from a set of time periods; receive a plurality of public key and private key pairs, wherein each pair is associated with a time period from the set of time periods; for each message of the plurality of messages: use the private key for the message to generate an aggregate signature for the message based on the message and an aggregate signature of a previous message of the plurality of messages; and generate an aggregate public key for the message using the public key associated with the message and an aggregate public key associated with the previous message; and authenticate at least one message of the plurality of messages using the aggregate public key and aggregate signature associated with a last message of the plurality of messages.

12. The computer-readable medium of claim 11, wherein at least some of the messages of the plurality of messages are the same.

13. The computer-readable medium of claim 11, wherein the aggregate signatures are generated using a BLS signature scheme.

14. The computer-readable medium of claim 11, wherein the aggregate signatures are generated using an ETA signature scheme.

15. The computer-readable medium of claim 11, wherein the aggregate public keys and aggregate signatures are combined for a plurality of different sets of time periods using an MMM generic digital signature scheme.

16. The computer-readable medium of claim 11, wherein the messages are one or more of bank records, images, or videos.

Description

BRIEF DESCRIPTION OF THE DRAWINGS

(1) The components in the drawings are not necessarily to scale relative to each other. Like reference numerals designate corresponding parts throughout the several views.

(2) FIG. 1 is an illustration of an example environment for providing aggregate signatures;

(3) FIG. 2 is an illustration of an example method for generating an aggregate signature and an aggregate public key for a message; and

(4) FIG. 3 illustrates an example computing device.

DETAILED DESCRIPTION

(5) Unless defined otherwise, all technical and scientific terms used herein have the same meaning as commonly understood by one of ordinary skill in the art. Methods and materials similar or equivalent to those described herein can be used in the practice or testing of the present disclosure. While implementations will be described within a cloud-based contact center, it will become evident to those skilled in the art that the implementations are not limited thereto.

(6) The basic notations used herein are as follows: operators | | and |x|=log.sub.2 x denote the concatenation and the bit length of variable x, respectively.

(7) $x\stackrel{\$}{\leftarrow }S$
means variable x is randomly and uniformly selected from set S. For any integer l, (x.sub.0 . . . x.sub.l) means

(8) $\left(x_0\stackrel{\$}{\leftarrow }S,.Math.,x_l\stackrel{\$}{\leftarrow }S\right).$
|S| denotes the cardinality of set S. The set of binary strings of any finite length is denoted as {0, 1}*. The set of items q.sub.i for i=0, . . . , l−1 is denoted by {q.sub.i}.sub.i=0.sup.l−1. Log x means log.sub.2 x.

(9) The maximum number of time periods for the base schemes is denoted as t. j: 1≤j≤t is the current sampling index (also called a period or epoch). m.sub.j is jth message sampled (collected) from the system readings. i: 1≤i≤j is the last index of the last sampled distinct message denoted as M. j′: 1≤j′≤j is the initial index at which the first instance of M.sub.i is sampled. h.sub.i.sup.j,j′: is the aggregate public key whose corresponding private keys (x.sub.j′ . . . x.sub.j) are used to compute aggregate signature σ.sub.j′,j on message M.sub.i∥j′ that is continuously sampled and remains the same during periods (j′,j). st.sub.j+1=(i,j−1,j′,{right arrow over (M)},{right arrow over (PK)}) is the state vector that maintains indexes, a message vector including distinct messages collected and a public key vector including their corresponding public keys until jth period. ({right arrow over (M.sub.i)},{right arrow over (PK.sub.i)}) denotes ith elements of the message and public key vectors, respectively. σ.sub.i,t is the aggregate signature on messages sampled during t periods.

(10) The CORE.sub.Base,t.sup.BLS scheme uses BLS signature with a hash chain strategy. However, as discussed before, the scheme offers partial public key aggregation, high space efficiency (with respect to total size of signatures, private and public keys) for extensions via MMM, and computational efficiency compared to a straightforward use of these building blocks towards obtaining an efficient single-signer forward-secure and aggregate signature scheme. The relevant notation used for this BLS based scheme is as follows: a bilinear pairing e: G.sub.0×G.sub.1.fwdarw.G.sub.T. The pairing is efficiently computable, non-degenerate, and all three groups have prime order q. g.sub.0 and g.sub.1 are denoted as generators of groups G.sub.0 and G.sub.1, respectively.

(11) In the scheme a hash function H.sub.0: M.fwdarw.G.sub.1 may be used. Another suitable hash function is H: {0, 1}*.fwdarw.{0, 1}.sup.d where d is a small fixed integer (e.g., SHA-256). H.sub.1:Z.sub.q*.fwdarw.Z.sub.q*, H.sub.2: {0, 1}*.fwdarw.Z.sub.q*, and H.sub.2: {0, 1}.sup.k —.fwdarw.{0, 1}.sup.k are also distinct cryptographic hash functions that may be used. All these hash functions may be treated as a random oracle.

(12) The CORE.sub.Base,t.sup.ETA scheme uses ETA signature as a building block. ETA is a signer efficient t-time digital signature scheme, which is based on Schnorr digital signature. ETA has O(K) public key size and it offers neither forward security nor signature or partial key aggregation. In CORE.sub.Base,t.sup.ETA, ETA is transformed into a t-time forward-secure and aggregate signature with partial public key aggregation capability. The relevant notation used for the ETA based scheme is as follows: q and p>q are large primes such that q|(p−1). a is a generator of the subgroup G of order q in .sub.p*.

(13) A signature scheme may consist of three algorithms SGN=(Kg,Sig,Ver) which are defined as follows. (sk,PK)←SGN.Math.Kg(1.sup.K): Given the security parameter K, it outputs the private and public key pair (sk,PK).Math.σ SGN.Math.Kg(m,sk): Given the message m and the signer's private key sk, the algorithm outputs the signature σ. b SGN.Math.Ver(m,b,PK): Given a message-signature pair (m,σ), and a public key PK, the algorithm outputs b.

(14) The MMM generic digital signature scheme can transform any digital signature scheme into a forward secure signature with a practically unbounded signing capability. The performance of this transformation depends on efficiency of the base signature scheme. The MMM signature is used to extend the t-time signatures into digital signatures with a practically unbounded signing capability. Since the t-time single-signer forward-secure and aggregate signatures offer both signature and partial public key aggregation, they minimize the total size of private, public key and signature space. Hence, they serve as an ideal building block to be extended via MMM. The MMM scheme is composed of the sum product composition algorithm (referred to as the Σ algorithm).

(15) Remark: The schemes are presented in standard form; however, they can be efficiently implemented with Elliptic Curves (EC) that offer significant space and computational advantages.

(16) The details of proposed schemes are presented as below. As described above, the base schemes are strictly t-time signatures, which compute no more or less than t signatures. Hence, if verification is done before t items have been sampled, a sealing function may be called by setting variable c=1. This creates a sealing message marking the time stamp of the final message and its index. The signer then generates all private keys from its current index to t, aggregates them, and the signs the sealing message with this aggregated private key. The signer then generates the corresponding public key for this aggregated private key, updates the list, and finalizes the t-time signature generation.

(17) The signature generation and verification algorithms of CORE.sub.Base,t.sup.ETA are described in Algorithm 1, Algorithm 2 and Algorithm 3, respectively. Key generation, signature generation and verification algorithms of CORE.sub.Base,t.sup.ETA are described in Algorithm 4, Algorithm 5 and Algorithm 6, respectively. The Σ algorithm of the MMM scheme is described in Algorithm 7. The full CORE schemes, which can sign practically unbounded number of messages, can be obtained by extending them into t.sup.n time period with iterative product composition.

(18) TABLE-US-00001 Algorithm 1 Key Generation Algorithm for Basic CORE Scheme with BLS for t time periods (sk.sub.1, PK) ← CORE.Math.Kg(1.sup.κ,t): The private/public key pair for t time periods are computed as follows. 1: $x_1\stackrel{\$}{⟵}{Z}_q^{*}$ 2: h.sub.i ← g.sub.1.sup.x.sup.i ∈ G.sub.1 for i = 1, . . . ,t, where x.sub.i+1 ← H(x.sub.i), 3: ${\mathrm{sk}}_1⟵x_1,\mathrm{PK}=\left(H\left(\underset{i=1}{\overset{t}{.Math.}}{h}_i\in G_1\right)\right).$

(19) TABLE-US-00002 Algorithm 2 Signature Generation Algorithm for Basic CORE Scheme with BLS for t time periods (sk.sub.j, <st.sub.j, σ.sub.1,j>) ← CORE.sub.Base,t.sup.BLS.Math.Sig(sk.sub.j, σ.sub.1,j−1, m.sub.j, st.sub.j, c): The initialization condition for the signutare generation algorithm is (i = j = j′ = 1, c = 0, ), m.sub.1 = M.sub.1, h.sub.1.sup.0,1 = σ.sub.1,0 = 1 and ({right arrow over (M)}, {right arrow over (PK)}, st.sub.1) are empty. Given the message m.sub.j sampled at jth time period, continue as follow: 1: if j > t then return the final output (sk.sub.j = ⊥, <st.sub.j, σ.sub.1,t>) and exit. 2: else if c = 1 then 3:  i = 1 + 1. 4:  M.sub.i ← “seal||timestamp||j||t”. 5:  $x_{j,t}⟵\underset{l=j}{\overset{t}{.Math.}}H\left(x_l\right),\mathrm{where}{x}_{l+1}⟵H\left(x_l\right).$ 6:  σ.sub.i,t ← H.sub.0(M.sub.i||j′ + 1).sup.x.sup.j,t ϵ G.sub.0, σ.sub.1,t ← σ.sub.1, j−1 .Math. σ.sub.j,t ϵ G.sub.0. 7:  h.sub.i.sup.j,t ← g.sub.1.sup.x.sup.j,t ϵ G.sub.1. 8:  Delete (x.sub.j, . . . , x.sub.t, x.sub.j,t, σ.sub.1,j−1, σ.sub.j,t). 9:  Add(h.sub.i.sup.j−1,j′, h.sub.i.sup.j,t) and (M.sub.i.sup.j−1, j′, M.sub.i.sup.j,t = M.sub.i||j′ + 1) to {right arrow over (PK)}.sub.i and {right arrow over (M)}.sub.i, respectively. 10:  j ← t + 1 and update st.sub.j+1 = (<i, j − 1, j′>, {right arrow over (M)}, {right arrow over (PK)})). 11:  return the final output (sk.sub.j = ⊥, <st.sub.j, σ.sub.1,t>) and exit. 12: else if m.sub.j ≠ M.sub.i then 13:  Add h.sub.i.sup.j−1, j′ and M.sub.i.sup.j−1, j′ = M.sub.i||j′ to {right arrow over (PK)}.sub.i and {right arrow over (M)}.sub.i, respec- tively, and update st.sub.j+1 = (<i, j − 1, j′>, {right arrow over (M)}, {right arrow over (PK)}). 14:  j′ ← j. 15:  i ← i + 1. 16:  M.sub.i ← m.sub.j. 17:  σ.sub.j ← H.sub.0(M.sub.i||j′).sup.xj ϵ G.sub.0. 18:  h.sub.i.sup.j,j′ ← h.sub.j. 19: else 20:  σ.sub.j ← H.sub.0(M.sub.i||j′).sup.x.sup.j ϵ G.sub.0. 21:  h.sub.i.sup.j,j′ ← h.sub.i.sup.j−1,j′ .Math. h.sub.j, delete h.sub.i.sup.j−1,j′ and h.sub.j. 22: σ.sub.1,j ← σ.sub.1,j−1 .Math. σ.sub.j ϵ G.sub.0, delete σ.sub.1,j−1 and σ.sub.j. 23: x.sub.j+1 ← H(x.sub.j), delete x.sub.j and sk.sub.j+1 ← x.sub.j+1. 24: h.sub.j+1 ← g.sub.1.sup.x.sup.i+1 ϵ G.sub.1. 25: j ← j + 1. 26: if j > t then add h.sub.i.sup.j−1,j′ and M.sub.i.sup.j−1,j′ = M.sub.i||j′ to {right arrow over (PK)}.sub.i and {right arrow over (M)}.sub.i. respectively, update st.sub.j = (<i,j − 1, j′>, {right arrow over (M)}, {right arrow over (PK)}) return the final output as (sk.sub.j = ⊥, <st.sub.j, σ.sub.1,t>) and exit. 27: return intermediate output (sk.sub.j, <st.sub.j, σ.sub.1,j>).

(20) TABLE-US-00003 Algorithm 3 Signature Verification Algorithm for Basic CORE Scheme with BLS for t time periods $b\leftarrow {\mathrm{CORE}}_{\mathrm{Base},t}^{\mathrm{BLS}}.Math.\mathrm{Ver}\left(\mathrm{st}=\left(.Math.i,j-1,j^{\prime }.Math.,\stackrel{.fwdarw.}{M}\stackrel{.fwdarw.}{\mathrm{PK}}\right),{\sigma }_{i,j},\mathrm{PK}\right):$ 1: if 1 ≤ j′ ≤ i ≤ j ≠ t then return b = 0. 2: else if $H\left(\underset{l=1}{\overset{i}{.Math.}}{\stackrel{.fwdarw.}{\mathrm{PK}}}_l\right)\ne \mathrm{PK}$ then return b = 0 3: else if $e\left(g_1,{\sigma }_1,t\right)\ne \underset{l=1}{\overset{i}{.Math.}}e\left({\stackrel{.fwdarw.}{\mathrm{PK}}}_l,H_0\left({\stackrel{.fwdarw.}{M}}_l\right)\right)$ then return b = 0 4: else return b = 1.

(21) TABLE-US-00004 Algorithm 4 Key Generation Algorithm for Basic CORE Scheme with modified ETA for t time periods (sk.sub.1, PK) ← CORE.sub.Base,t.sup.ETA.Math.Kg(1.sup.κ, t): the private/public key pair for t time periods are computed as follows. 1: Generate (y.sub.1, h.sub.1, <q, p, α>) as in ETA key generation step 1 (which is identical to Schnorr signature key generation algo- rithm), where 0$y_1\stackrel{\$}{⟵}{Z}_Q^{*}\mathrm{and}{h}_1⟵a^{y_1}\mathrm{mod}p.$ 2: $r_1\stackrel{\$}{⟵}{Z}_Q^{*}.$ 3: $R_{1,}t⟵\underset{i=1}{\overset{t}{.Math.}}{\alpha }^{r_i}\mathrm{mod}p,\mathrm{where}{r}_{i+1}⟵H_1\left(r_i\right).$ 4: $h_{1,t}⟵\underset{i=t}{\overset{t}{.Math.}}{\alpha }^{y_i}\mathrm{mod}p,\mathrm{where}{y}_{i+1}⟵H_1\left(y_i\right).$ 5: $x_1\stackrel{\$}{⟵}{\left\{0,1\right\}}^K.$ 6: sk.sub.1 ← (y.sub.1, r.sub.1, x.sub.1), PK = (R′ = H.sub.1(R.sub.1,t), Y′ = H.sub.1(h1,t)).

(22) TABLE-US-00005 Algorithm 5 Signature Generation Algorithm for Basic CORE Scheme with ETA for t time periods (sk.sub.j, <st.sub.j, σ.sub.1,j>) ← CORE.sub.Base,t.sup.ETA.Math.Sig(sk.sub.j, σ.sub.1,j−1, m.sub.j, st.sub.j, c): The initialization condition for the signature generation algorithm is (i = j = j′ = 1, c = 0,), m.sub.1 = M.sub.1, h.sub.1.sup.0,1 = 1, s.sub.1,0 = 0 and ({right arrow over (M)}, {right arrow over (PK)}, st.sub.1) are empty. The signer keeps x.sub.1 to be released as a part of final signature σ.sub.1,t, while deletes intermediate x values to save space (seed x is not used for forward secrecy and therefore cane be released but only after final signature σ.sub.1,t was computed). Given the message m.sub.j sampled at jth time period, continue as follow:  1: if j > t then return the final output (sk.sub.j = ⊥, <st.sub.j, σ.sub.1,t>) and exit.  2: else if c = 1 then  3:  x.sub.i+1 ← H.sub.3(x.sub.i).  4:  i = 1 + 1.  5:  M.sub.i ← “seal||timestamp||j||t”.  6:  $\mathrm{yj},t\leftarrow \underset{l=j}{\overset{l}{.Math.}}{H}_1\left(y_l\right)\mathrm{mod}q,\mathrm{where}{y}_{l+1}\leftarrow H_1\left(y_l\right).$  7:  $\mathrm{rj},t⟵\underset{l=j}{\overset{t}{.Math.}}{H}_1\left(r_l\right)\mathrm{mod}q,\mathrm{where}{r}_{l+1}⟵H_1\left(r_l\right).$  8:  s.sub.j,t ← r.sub.j,t − H.sub.1(M.sub.i||j + 1||x.sub.i) .Math. y.sub.j,t mod q.  9:  s.sub.1,t ← s.sub.1,j−1 + s.sub.j,t mod q. 10:  h.sub.i.sup.j,t ← α.sup.y.sup.j,t mod p. 11:  Delete (y.sub.i, . . . , y.sub.t, y.sub.j, t, r.sub.j, . . . , r.sub.t, r.sub.j,t, x.sub.i, x.sub.i+1, s.sub.j,t, s.sub.1, j−1). 12:  Add(h.sub.i.sup.j−1, j′, h.sub.i.sup.j,t) and (M.sub.i.sup.j−1, j′, M.sub.i.sup.j,t = M.sub.i||j′ + 1) to {right arrow over (PK)}.sub.i and {right arrow over (M)}.sub.i, respectively. 13:  j ← t + 1 and update st.sub.j = (<i, j − 1, j′>, {right arrow over (M)}, {right arrow over (PK)})). 14:  σ.sub.1,t ← (s.sub.1,t, x.sub.1) 15:  return the final state (sk.sub.j = ⊥, <st.sub.j, σ.sub.1,t>) and exit. 16 else if m.sub.j ≠ M.sub.i then 17:  Add h.sub.i.sup.j−1,j′ and M.sub.i.sup.j−1,j′ = M.sub.i||j′ to {right arrow over (PK)}.sub.i and {right arrow over (M)}.sub.i, repec- tively, and update st.sub.j−1 = (<i, j − 1, j′>, {right arrow over (M)}, {right arrow over (PK)}). 18:  j′ ← j. 19:  x.sub.i−1 ← x.sub.i, delete x.sub.t (to save space). 20:  i ← i + 1. 21:  M.sub.i ← m.sub.j. 22:  s.sub.j ← r.sub.j − H.sub.1(M.sub.i||j′||x.sub.i) .Math. y.sub.j mod q. 23:  h.sub.i.sup.j,j′ ← h.sub.j. 24: else 25:  s.sub.j ← r.sub.j − H.sub.1(M.sub.i||j′||x.sub.i) .Math. y mod q. 26:  h.sub.i.sup.j,j′ ← h.sub.i.sup.j−1,j′ .Math. h.sub.j, delete h.sub.i.sup.j−1, j′ and h.sub.j. 27: s.sub.1,j ← s.sub.1,j−1 + s.sub.j mod q, delete (s.sub.1, j−1, s.sub.j). 28: y.sub.j+1 ← H.sub.1(y.sub.j), delete y.sub.j. 29: r.sub.j+1 ← H.sub.1(r.sub.j), delete r.sub.j. 30: h.sub.j+1 ← α.sup.y.sup.j−1 mod p. 31: j ← j + 1. 32: if j >t then add h.sub.i.sup.j−1,j′ and M.sub.i.sup.j−1,j′ = M.sub.i||j′ to {right arrow over (PK)}.sub.i and {right arrow over (M)}.sub.i. respectively, update st.sub.j = (<i,j − 1, j′>, {right arrow over (M)}, {right arrow over (PK)}) return the final output as (sk.sub.j = ⊥, <st.sub.j, σ.sub.1,t,x.sub.1)>) and exit. 33: return intermediate output (sk.sub.j = ⊥, <st.sub.j, σ.sub.1,j =(s.sub.1,j, x.sub.i)>).

(23) TABLE-US-00006 Algorithm 6 Signature Verification Algorithm for Basic CORE Scheme with ETA for t time periods b ← CORE.sub.Base,t.sup.ETA.Math.Ver(st = (<i, j − 1, j′>, {right arrow over (M)}, {right arrow over (PK)}), σ.sub.1,j, PK): 1: if 1 ≤ j′ ≤ i ≤ j ≠ t then return b = 0. 2: else if H.sub.1(Π.sub.l=1.sup.i {right arrow over (PK)}.sub.l mod p) ≠ Y′ then return b = 0. 3: $\mathrm{else}\mathrm{if}{R}^{\prime }\ne \underset{l=1}{\overset{i}{.Math.}}{\stackrel{.fwdarw.}{\mathrm{PK}}}_l^{H_1({\stackrel{.Math.}{M}}_{l.Math.x_l)}}.Math.a^{s_l,t}\mathrm{mod}p,\mathrm{where}{x}_l+1⟵H_3\left(x_l\right)\mathrm{then}\mathrm{return}b=0.$ 4: else return b = 1.

(24) TABLE-US-00007 Algorithm 7 Sum Composition (Σ) Algorithms in MMM (sk, PK) Σ.Kg(1.sup.K, r, levels, i, SGN):  1: (r.sub.0, r.sub.1)  G(r)  2: if levels = 0 then  3:  (sk.sub.0, pk.sub.0)←SGN.Kg(1.sup.K, r.sub.0)  4:  (sk.sub.1, pk.sub.1)←SGN.Kg(1.sup.K, r.sub.1)  5:  PK  H(pk.sub.0∥pk.sub.1), sk ← (sk.sub.0, r.sub.1, pk.sub.0, pk.sub.1)  6:  return (sk, PK)  7: (sk.sub.0, pk.sub.0)  Σ.Kg(1.sup.K, r.sub.0, levels − 1, i + 1, SGN)  8: (sk.sub.1, pk.sub.1)  Σ.Kg(1.sup.K, r.sub.1, levels − 1, i + 1, SGN)  9: PK ←H(pk.sub.0, pk.sub.1), sk ← (spk.sub.0, r.sub.1, pk.sub.0, pk.sub.1) 10: return (sk, PK) $\left(\sigma ,\stackrel{\_}{t}\right).Math..Math.\mathrm{Sig}\left(\stackrel{\_}{t},\mathrm{sk}=\left({\mathrm{sk}}^{\prime },r_1,{\mathrm{pk}}_0,{\mathrm{pk}}_1\right),M,\mathrm{levels},i,T,\mathrm{SGN}\right):$  1: if levels = 0 then  2:  if t < T/2 then t′   t else t′ ← t' − T/2  3:  σ′ SGN.Sig(s k′, M), σ ← <σ′, pk.sub.0, pk.sub.1>  4:  return (σ′, t′)  5: else  6:  if t < T/2 then  7:   (σ′, t′) Σ.Sig(t, sk′, t, M, levels − 1, i + 1, SGN)  8:  else t ← t−T/2  9:   (σ′, t′) ← Σ.Sig(t′, sk′, t, M, levels − 1, i + 1, SGN) 10:  (σ)  <σ′,pk.sub.0,pk.sub.1> and return (σ', t) $.Math..Math.\mathrm{Up}\left(\mathrm{sk}=.Math.{\mathrm{sk}}^{\prime },r_1,{\mathrm{pk}}_0,{\mathrm{pk}}_1.Math.,\stackrel{\_}{t},\mathrm{levels},i,\mathrm{SGN}\right):$  1: if t + 1 < T then sk′ ← SGN.UP(sk′)  2: elseif (t+1 = T) then  3:  (sk′,pk′) ← SGN.Kg(r.sub.1), r.sub.1  0, delete pk′ else sk″  ← SGN.UP(sk′)  4: if t < T/2 then  5:  Σ.Up(sk″, r.sub.1, pk.sub.0, pk.sub.1,t,levels − 1, i + 1, SGN)  6: else Σ.Up(sk″, r.sub.1, pk.sub.0, pk.sub.1,t−T/2,levels − 1, i + 1, SGN) 0$b.Math..Math.\mathrm{Ver}\left(\mathrm{pk},M,\sigma =.Math.{\sigma }^{\prime },{\mathrm{pk}}_0,{\mathrm{pk}}_1.Math.,\stackrel{\_}{t},\mathrm{levels},i,\mathrm{SGN}\right):$  1: if H(pk.sub.0 ∥ pk.sub.1) ≠ pk then return b = 0.  2: if levels = 0 then  3:  if t < T/2 then SGN.Ver(pk.sub.0, M, σ)  4:  else  SGN.Ver(pk.sub.1,M, σ)  5: else  6:  if t < T/2 then  7:   return $.Math..Math.\mathrm{Ver}({\mathrm{pk}}_0,M,\sigma =.Math.{\sigma }^{\prime },{\mathrm{pk}}_0,{\mathrm{pk}}_1.Math.,$t,  8:   levels−1, i + 1, SGN)  9:  else return $.Math..Math.\mathrm{Ver}({\mathrm{pk}}_1,M,\sigma =.Math.{\sigma }^{\prime },{\mathrm{pk}}_0,{\mathrm{pk}}_1.Math.,$   t−T/2, levels−1, i+1, SGN)

(25) FIG. 1 is an illustration of an environment 100 for authenticating messages. As shown, the environment 100 may include an authentication system 130 and a message generator 110 in communication through a network 160. While shown as separate, in some embodiments, the message generator 110 and the authentication system 130 may be implemented together using one or more computing devices such as the computing device 300 illustrated with respect to FIG. 3.

(26) The message generator 110 may generate one or more messages. Depending on the embodiment, the messages may include images or videos (e.g., images or video from a security camera), transaction records (e.g., bank records, visitor logs, phone or text records), and computer programs (e.g., operating systems, program versions, and updates).

(27) In some embodiments, the messages 117 may be a type of file or data that does not change very much overtime. For example, messages 117 such as operating system versions may not change very much between updates. As another example, messages 117 such as daily bank account transaction logs may have days were the logs are identical due to infrequent deposits or withdrawals.

(28) Each message 117 may be associated with a time that the message 117 was generated. The message generator 110 may provide the messages 117 in the order that they are generated to the authentication system 130.

(29) The authentication system 130 may receive the messages 117 from the message generator 110 and may allow for the authentication of any message of the plurality of messages 117. As shown, the authentication system 130 includes several components including, but not limited to, a key generator 135, an aggregator 143, and an authenticator 153. More or fewer components may be supported. Each of the components of the authentication system 130 may be implemented together or separately by a computing device such as the computing device 300.

(30) The key generator 135 may generate a key pair 137 for each messages of the plurality of messages 117. Depending on the embodiment, the key generator 135 may generate the messages using the algorithm 1 or the algorithm 4 described above. Each public key pair 137 for a message 117 may include a private key and a public key. Any method for generating public and private keys may be used.

(31) The aggregator 143 may generate an aggregate signature for 147 for each message 117 of the plurality of messages 117. The aggregator 143 may generate the aggregate signature 147 for a message 117 using either the algorithm 2 or algorithm 5. Depending on the embodiment, the aggregate signature 147 for a message 117 may generated using the key pair 137 associated with the message 117 and an aggregate signature 147 generated for a previous message of the plurality of messages 117.

(32) The aggregator 143 may generate an aggregate public key 145. The aggregator may generate an aggregate public key 145 for each message 117 of the plurality of messages 117. In some embodiments, the aggregator 143 may generate an aggregate public key 143 for a message 117 using the public key of the key pair 137 associated with the message 117, and the aggregate public key 145 generated for a previous message 117. The aggregate public keys 145 and aggregate signatures for all of the messages 117 in the plurality of messages 117 may be stored by the aggregator 143.

(33) At some time, a requestor 120 may desire to authenticate one of the messages 117 in the plurality of messages. For example, the requestor 120 may be an auditor who would like to verify the authenticity of a message 117 such as a bank record. As another example, the requestor 120 may be a law enforcement officer who may want to authenticate a message 117 such as a video that may be used as evidence. The requestor may have a copy of the message 117 and the message 117 may be associated with a particular time.

(34) The requestor 120 may send a request to the authentication system 130 to authenticate the message 117. Depending on the embodiment, the request 115 may identify the time associated with the message 117 and/or may include the message 117 itself.

(35) In response to the request, the authenticator 153 may authenticate the message 117 identified in the request. The authenticator 153 may authenticate the identified message 117 using the aggregate signature 147 and the aggregate public key 145 of the last message of the plurality of messages 117. If the message 117 is authenticated, the authentication system 130 may provide an authenticated message 190 to the requestor 120. If the message 117 cannot be authenticated then the authentication system 130 may provide an indication that the message 117 of the request 115 cannot be authenticated.

(36) FIG. 2 is an illustration of an example method 100 for generating an aggregate public key and aggregate signature for a plurality of messages and for authenticating at least one message of the plurality of messages. The method 200 may be implemented by the authentication system 130 of FIG. 1.

(37) At 210, a plurality of messages is received. The plurality of messages 117 may be received by the authentication system 130. Each message 117 may be associated with a time period up until a maximum time period t. The plurality of messages 117 is not limited to messages and may include a variety of file and application types such as images, and bank account statements or statuses. Other types of files or applications may be supported. The method 200 as described may be particularly well suited for files or applications where updates are not frequent, but security is very important. For example, the images or videos generated by a security camera may not change very often, but it may be very important that a particular image or video can be authenticated.

(38) At 215, a plurality of public key and private key pairs is received. The plurality of public key and private key pairs 137 may be received by the authentication system 130. Alternatively, or additionally the key pairs 137 may have been generated by the key generator 135. The plurality of public and private key pairs 137 may be generated using the algorithm 1 or the algorithm 4 described above. The algorithm 1 and 4 may both generate t public and private key pairs 137 with one private and public key pair 137 corresponding to each time period. Any method or technique for generating public and private key pairs 137 may be used.

(39) At 220, for each message, an aggregate signature is generated. The aggregate signature 147 for a message 117 may be generated by the aggregator 143. The aggregate signature 147 for a message 117 may be generated using either the algorithm 2 or the algorithm 5 described above, the private key of the key pair 137 associated with the message 117, and the aggregate signature 147 generated for a previous message 117 of the plurality of messages 117. However, any signature aggregation method may be used. This may include potential signature schemes with post-quantum security (e.g., lattice-based scheme and coding based schemes).

(40) At 225, for each message, an aggregate public key is generated. The aggregate public key 145 may be generated by the aggregator 143. The aggregate public key 145 may be generated using the public key of the key pair 137 of the message 117 and an aggregate public key 145 generated for a previous message 117 of the plurality of messages 117. Any method for public key aggregation may be used.

(41) At 230, the aggregate public key and aggregate signature of a last message is provided. The aggregate public key 145 and aggregate signature 147 of the last message 117 may be provided by the authentication system 130. The aggregate public key 145 and aggregate signature 147 of the last message 117 of the plurality of messages 117 may be provided to a user or individual who wishes to authenticate any of the messages 117 of the plurality of messages 117.

(42) At 235, at least one message is authenticated using the aggregate public key and aggregate signature. The at least one message 117 may be authenticated by the authenticator 153 using one or more of the algorithms 3 and 6 described above.

(43) FIG. 3 shows an exemplary computing environment in which example embodiments and aspects may be implemented. The computing system environment is only one example of a suitable computing environment and is not intended to suggest any limitation as to the scope of use or functionality.

(44) Numerous other general purpose or special purpose computing system environments or configurations may be used. Examples of well-known computing systems, environments, and/or configurations that may be suitable for use include, but are not limited to, personal computers, servers, handheld or laptop devices, multiprocessor systems, microprocessor-based systems, network personal computers (PCs), minicomputers, mainframe computers, embedded systems, distributed computing environments that include any of the above systems or devices, and the like.

(45) Computer-executable instructions, such as program modules, being executed by a computer may be used. Generally, program modules include routines, programs, objects, components, data structures, etc. that perform particular tasks or implement particular abstract data types. Distributed computing environments may be used where tasks are performed by remote processing devices that are linked through a communications network or other data transmission medium. In a distributed computing environment, program modules and other data may be located in both local and remote computer storage media including memory storage devices.

(46) With reference to FIG. 3, an exemplary system for implementing aspects described herein includes a computing device, such as computing device 300. In its most basic configuration, computing device 300 typically includes at least one processing unit 302 and memory 304. Depending on the exact configuration and type of computing device, memory 304 may be volatile (such as random access memory (RAM)), non-volatile (such as read-only memory (ROM), flash memory, etc.), or some combination of the two. This most basic configuration is illustrated in FIG. 3 by dashed line 306.

(47) Computing device 300 may have additional features/functionality. For example, computing device 300 may include additional storage (removable and/or non-removable) including, but not limited to, magnetic or optical disks or tape. Such additional storage is illustrated in FIG. 3 by removable storage 308 and non-removable storage 310.

(48) Computing device 300 typically includes a variety of tangible computer readable media. Computer readable media can be any available tangible media that can be accessed by device 300 and includes both volatile and non-volatile media, removable and non-removable media.

(49) Tangible computer storage media include volatile and non-volatile, and removable and non-removable media implemented in any method or technology for storage of information such as computer readable instructions, data structures, program modules or other data. Memory 304, removable storage 308, and non-removable storage 310 are all examples of computer storage media. Tangible computer storage media include, but are not limited to, RAM, ROM, electrically erasable program read-only memory (EEPROM), flash memory or other memory technology, CD-ROM, digital versatile disks (DVD) or other optical storage, magnetic cassettes, magnetic tape, magnetic disk storage or other magnetic storage devices, or any other medium which can be used to store the desired information and which can be accessed by computing device 300. Any such computer storage media may be part of computing device 300.

(50) Computing device 300 may contain communications connection(s) 312 that allow the device to communicate with other devices. Computing device 300 may also have input device(s) 314 such as a keyboard, mouse, pen, voice input device, touch input device, etc. Output device(s) 316 such as a display, speakers, printer, etc. may also be included. All these devices are well known in the art and need not be discussed at length here.

(51) It should be understood that the various techniques described herein may be implemented in connection with hardware or software or, where appropriate, with a combination of both. Thus, the methods and apparatus of the presently disclosed subject matter, or certain aspects or portions thereof, may take the form of program code (i.e., instructions) embodied in tangible media, such as floppy diskettes, CD-ROMs, hard drives, or any other machine-readable storage medium wherein, when the program code is loaded into and executed by a machine, such as a computer, the machine becomes an apparatus for practicing the presently disclosed subject matter. In the case of program code execution on programmable computers, the computing device generally includes a processor, a storage medium readable by the processor (including volatile and non-volatile memory and/or storage elements), at least one input device, and at least one output device. One or more programs may implement or utilize the processes described in connection with the presently disclosed subject matter, e.g., through the use of an application programming interface (API), reusable controls, or the like. Such programs may be implemented in a high level procedural or object-oriented programming language to communicate with a computer system. However, the program(s) can be implemented in assembly or machine language, if desired. In any case, the language may be a compiled or interpreted language and it may be combined with hardware implementations.

(52) Although the subject matter has been described in language specific to structural features and/or methodological acts, it is to be understood that the subject matter defined in the appended claims is not necessarily limited to the specific features or acts described above. Rather, the specific features and acts described above are disclosed as example forms of implementing the claims.