156:
388:
198:
33:
223:
Linked timestamping is inherently more secure than the usual, public-key signature based time-stamping. All consequential time-stamps "seal" previously issued ones - hash chain (or other authenticated dictionary in use) could be built only in one way; modifying issued time-stamps is nearly as hard as
379:
The hash functions used in the secure time-stamping schemes do not necessarily have to be collision-resistant or even one-way; secure time-stamping schemes are probably possible even in the presence of a universal collision-finding algorithm (i.e. universal and attacking program that is able to find
320:
for the number of time stamps issued during the aggregation period; it is suggested that it is probably impossible to prove the security without this explicit bound - the so-called black-box reductions will fail in this task. Considering that all known practically relevant and efficient security
244:
The common technology for guaranteeing long-term attestation value of the issued time-stamps (and digitally signed data) is periodic over-time-stamping of the time-stamp token. Because of missing key-related risks and of the plausible safety margin of the reasonably chosen hash function this
213:
some links, so that all previously issued time-stamp tokens depend on the published link and that it is practically impossible to forge the published values. By publishing widely witnessed links, the TSA creates unforgeable verification points for validating all previously issued
331:
Buldas, Laur showed in 2007 that bounded time-stamping schemes are secure in a very strong sense - they satisfy the so-called "knowledge-binding" condition. The security guarantee offered by Buldas, Saarepera in 2004 is improved by diminishing the security loss coefficient from
104:. Later modification of the issued time-stamps would invalidate this structure. The temporal order of issued time-stamps is also protected by this data structure, making backdating of the issued time-stamps impossible, even by the issuing server itself.
279:
Benaloh and de Mare constructed a one-way accumulator in 1994 and proposed its use in time-stamping. When used for aggregation, one-way accumulator requires only one constant-time computation for round membership verification.
324:
Next, in 2005 it was shown that bounded time-stamping schemes with a trusted audit party (who periodically reviews the list of all time-stamps issued during an aggregation period) can be made
283:
Surety started the first commercial linked timestamping service in
January 1995. Linking scheme is described and its security is analyzed in the following article by Haber and Sornetta.
540:
denotes binary tree depth). Current security proofs work on the assumption that there is a hard limit of the aggregation tree size, possibly enforced by the subtree length restriction.
234:
Absence of secret keys increases system trustworthiness. There are no keys to leak and hash algorithms are considered more future-proof than modular arithmetic based algorithms, e.g.
374:
518:
700:
Benaloh, Josh; de Mare, Michael (1991). "Efficient
Broadcast Time-Stamping". Technical Report 1. Clarkson University Department of Mathematics and Computer Science.
465:
439:
241:
Linked timestamping scales well - hashing is much faster than public key cryptography. There is no need for specific cryptographic hardware with its limitations.
538:
485:
413:
350:
318:
1216:
1168:
1125:
1082:
1031:
988:
947:
904:
788:
613:
554:
384:
for any hash function). This suggests that it is possible to find even stronger proofs based on some other properties of the hash functions.
328:- they remain secure in arbitrary environments (compositions with other protocols and other instances of the time-stamping protocol itself).
300:
Security proof for hash-function based time-stamping schemes was presented by Buldas, Saarepera in 2004. There is an explicit upper bound
51:
173:
For increased scalability the TSA might group time-stamping requests together which arrive within a short time-frame. These requests are
742:
Bayer, Dave; Stuart A., Haber; Wakefield Scott, Stornetta (1992). "Improving the
Efficiency And Reliability of Digital Time-Stamping".
197:
853:
69:
276:
Tree-like schemes and operating in rounds were proposed by
Benaloh and de Mare in 1991 and by Bayer, Haber and Stornetta in 1992.
565:
231:
Tampering with absolute time values could be detected by users, whose time-stamps are relatively comparable by system design.
228:. Continuity of operation is observable by users; periodic publications in widely witnessed media provide extra transparency.
1235:
245:
over-time-stamping period of hash-linked token could be an order of magnitude longer than of public-key signed token.
225:
193:
Linking creates a verifiable and ordered cryptographic link between the current and already issued time-stamp tokens.
1251:
579:(Evidence Record Syntax) encompasses hash tree and time-stamp as an integrity guarantee for long-term archiving.
124:
289:
et al. continued with further optimization and formal analysis of binary tree and threaded tree based schemes.
652:
177:
together without retaining their temporal order and then assigned the same time value. Aggregation creates a
558:
270:
163:
120:
181:
connection between all involved requests; the authenticating aggregate value will be used as input for the
1194:
1146:
1103:
1060:
1009:
925:
882:
831:
747:
701:
664:
715:
1185:
292:
Skip-list based time-stamping system was implemented in 2005; related algorithms are quite efficient.
568:
266:
86:
1199:
1151:
1108:
1065:
1014:
930:
887:
836:
752:
706:
669:
152:
The simplest linear hash chain-based time-stamping scheme is illustrated in the following diagram:
97:
Linked timestamping creates time-stamp tokens which are dependent on each other, entangled in some
1037:
953:
859:
682:
355:
262:
827:
819:
1212:
1164:
1121:
1078:
1027:
984:
943:
900:
849:
784:
609:
490:
1204:
1156:
1113:
1070:
1019:
976:
935:
892:
841:
776:
674:
601:
572:
728:
235:
444:
418:
824:
Proceedings of the 4th ACM conference on
Computer and communications security - CCS '97
768:
523:
470:
398:
381:
335:
303:
101:
387:
155:
1256:
1245:
596:
Buchmann, J.; Dahmen, E.; Szydlo, M. (2009). "Hash-based
Digital Signature Schemes".
265:
proposed in 1990 to link issued time-stamps together into linear hash-chain, using a
98:
863:
686:
1041:
971:
Blibech, K.; Gabillon, A. (2006). "A New
Timestamping Scheme Based on Skip Lists".
258:
178:
17:
1238:; includes application in time-stamping and provable security; by A. Buldas, 2011.
957:
1117:
1160:
605:
576:
395:
At the illustration above hash tree based time-stamping system works in rounds (
286:
140:
135:
116:
780:
548:
146:
112:
845:
769:"One-Way Accumulators: A Decentralized Alternative to Digital Signatures"
1074:
980:
561:) from June 2005 covers linking-based and hybrid time-stamping schemes.
1208:
1145:. Lecture Notes in Computer Science. Vol. 4784. pp. 138–150.
1102:. Lecture Notes in Computer Science. Vol. 4450. pp. 150–165.
1059:. Lecture Notes in Computer Science. Vol. 3650. pp. 359–373.
1008:. Lecture Notes in Computer Science. Vol. 3329. pp. 500–514.
924:. Lecture Notes in Computer Science. Vol. 1751. pp. 293–305.
896:
678:
1187:
Do Broken Hash
Functions Affect the Security of Time-Stamping Schemes?
1193:. Lecture Notes in Computer Science. Vol. 3989. pp. 50–65.
744:
Sequences II: Methods in
Communication, Security and Computer Science
557:
for
Financial Services, "Trusted Timestamp Management and Security" (
467:, ...), with one aggregation tree per round. Capacity of the system (
1023:
939:
42:
provides insufficient context for those unfamiliar with the subject
975:. Lecture Notes in Computer Science. Vol. 3982. p. 395.
881:. Lecture Notes in Computer Science. Vol. 1462. p. 486.
638:
386:
201:
Example newspaper publication of hash-linked time-stamping service
196:
130:
Suitable candidates for the authenticated data structure include:
775:. Lecture Notes in Computer Science. Vol. 765. p. 274.
1100:
Knowledge-Binding Commitments with Applications in Time-Stamping
805:"Surety, LLC | Protect the Integrity of Electronic Records"
111:
in some hard-to-modify and widely witnessed media, like printed
1143:
Does Secure Time-Stamping Imply Collision-Free Hash Functions?
1055:
Buldas, A.; Laud, P.; Saarepera, M. R.; Willemson, J. (2005).
26:
1236:"Series of mini-lectures about cryptographic hash functions"
321:
proofs are black-box, this negative result is quite strong.
154:
920:
Buldas, Ahto; Lipmaa, Helger; Schoenmakers, Berry (2000).
1057:
Universally Composable Time-Stamping Schemes with Audit S
804:
166:(TSA) usually performs the following distinct functions:
107:
The top of the authenticated data structure is generally
877:
Buldas, A.; Laud, P.; Lipmaa, H.; Villemson, J. (1998).
973:
Computational Science and Its Applications - ICCSA 2006
47:
571:
or standard draft about linking based time-stamping.
526:
493:
473:
447:
421:
401:
358:
338:
306:
551:
part 3 covers 'Mechanisms producing linked tokens'.
89:
where issued time-stamps are related to each other.
532:
512:
479:
459:
433:
407:
368:
344:
312:
269:hash function. The main rationale was to diminish
922:Optimally Efficient Accountable Time-Stamping
8:
1198:
1150:
1107:
1064:
1013:
929:
886:
879:Time-stamping with binary linking schemes
835:
751:
705:
668:
525:
504:
492:
472:
446:
420:
400:
359:
357:
337:
305:
70:Learn how and when to remove this message
1006:On Provably Secure Time-Stamping Schemes
588:
1004:Buldas, Ahto; Saarepera, Märt (2004).
773:Advances in Cryptology – EUROCRYPT '93
724:
713:
653:"How to time-stamp a digital document"
52:providing more context for the reader
7:
818:Haber, S.; Stornetta, W. S. (1997).
651:Haber, S.; Stornetta, W. S. (1991).
628:See ISO/IEC 18014-1:2002 Chapter 4.2
1141:Buldas, A.; Jürgenson, A. (2007).
487:) is determined by the tree size (
25:
224:finding a preimage for the used
31:
820:"Secure names for bit-strings"
767:Benaloh, J.; Mare, M. (1994).
391:Hash tree based linking scheme
1:
1184:Buldas, A.; Laur, S. (2006).
1098:Buldas, A.; Laur, S. (2007).
1118:10.1007/978-3-540-71677-8_11
746:. Springer-Verlag: 329–334.
1161:10.1007/978-3-540-75670-5_9
606:10.1007/978-3-540-88702-7_3
369:{\displaystyle {\sqrt {N}}}
226:cryptographic hash function
119:. There are no (long-term)
1273:
555:American National Standard
598:Post-Quantum Cryptography
781:10.1007/3-540-48285-7_24
559:ANSI ASC X9.95 Standard
513:{\displaystyle N=2^{l}}
164:time-stamping authority
723:Cite journal requires
534:
514:
481:
461:
435:
409:
392:
370:
346:
326:universally composable
314:
202:
159:
846:10.1145/266420.266430
657:Journal of Cryptology
535:
515:
482:
462:
436:
410:
390:
371:
347:
315:
209:The TSA periodically
200:
158:
524:
491:
471:
445:
419:
399:
356:
336:
304:
273:trust requirements.
87:trusted timestamping
1075:10.1007/11556992_26
981:10.1007/11751595_43
460:{\displaystyle t+2}
434:{\displaystyle t+1}
267:collision-resistant
83:Linked timestamping
48:improve the article
18:Linked Timestamping
1209:10.1007/11767480_4
897:10.1007/BFb0055749
679:10.1007/BF00196791
530:
510:
477:
457:
431:
405:
393:
366:
342:
310:
263:W. Scott Stornetta
203:
162:The linking-based
160:
143:(binary hash tree)
1252:Computer security
1218:978-3-540-34703-3
1170:978-3-540-75669-9
1127:978-3-540-71676-1
1084:978-3-540-31930-6
1033:978-3-540-23975-8
990:978-3-540-34075-1
949:978-3-540-66967-8
906:978-3-540-64892-5
790:978-3-540-57600-6
615:978-3-540-88701-0
533:{\displaystyle l}
480:{\displaystyle N}
408:{\displaystyle t}
364:
345:{\displaystyle N}
313:{\displaystyle N}
296:Provable security
123:in use, avoiding
80:
79:
72:
16:(Redirected from
1264:
1223:
1222:
1202:
1192:
1181:
1175:
1174:
1154:
1138:
1132:
1131:
1111:
1095:
1089:
1088:
1068:
1052:
1046:
1045:
1017:
1001:
995:
994:
968:
962:
961:
933:
917:
911:
910:
890:
874:
868:
867:
839:
815:
809:
808:
801:
795:
794:
764:
758:
757:
755:
739:
733:
732:
726:
721:
719:
711:
709:
697:
691:
690:
672:
648:
642:
637:For example see
635:
629:
626:
620:
619:
593:
539:
537:
536:
531:
519:
517:
516:
511:
509:
508:
486:
484:
483:
478:
466:
464:
463:
458:
440:
438:
437:
432:
414:
412:
411:
406:
375:
373:
372:
367:
365:
360:
351:
349:
348:
343:
319:
317:
316:
311:
127:-related risks.
75:
68:
64:
61:
55:
35:
34:
27:
21:
1272:
1271:
1267:
1266:
1265:
1263:
1262:
1261:
1242:
1241:
1232:
1227:
1226:
1219:
1200:10.1.1.690.7011
1190:
1183:
1182:
1178:
1171:
1152:10.1.1.110.4564
1140:
1139:
1135:
1128:
1109:10.1.1.102.2680
1097:
1096:
1092:
1085:
1054:
1053:
1049:
1034:
1024:10.1007/b104116
1003:
1002:
998:
991:
970:
969:
965:
950:
919:
918:
914:
907:
876:
875:
871:
856:
817:
816:
812:
803:
802:
798:
791:
766:
765:
761:
741:
740:
736:
722:
712:
699:
698:
694:
650:
649:
645:
636:
632:
627:
623:
616:
595:
594:
590:
585:
546:
522:
521:
500:
489:
488:
469:
468:
443:
442:
417:
416:
397:
396:
354:
353:
334:
333:
302:
301:
298:
256:
251:
221:
95:
76:
65:
59:
56:
45:
36:
32:
23:
22:
15:
12:
11:
5:
1270:
1268:
1260:
1259:
1254:
1244:
1243:
1240:
1239:
1231:
1230:External links
1228:
1225:
1224:
1217:
1176:
1169:
1133:
1126:
1090:
1083:
1066:10.1.1.59.2070
1047:
1032:
1015:10.1.1.65.8638
996:
989:
963:
948:
940:10.1007/b75033
931:10.1.1.40.9332
912:
905:
888:10.1.1.35.9724
869:
855:978-0897919128
854:
837:10.1.1.46.7776
810:
796:
789:
759:
753:10.1.1.46.5923
734:
725:|journal=
707:10.1.1.38.9199
692:
670:10.1.1.46.8740
643:
630:
621:
614:
600:. p. 35.
587:
586:
584:
581:
545:
542:
529:
507:
503:
499:
496:
476:
456:
453:
450:
430:
427:
424:
404:
363:
341:
309:
297:
294:
255:
252:
250:
247:
220:
217:
216:
215:
207:
195:
194:
191:
187:
186:
171:
150:
149:
144:
138:
102:data structure
94:
91:
78:
77:
60:September 2017
39:
37:
30:
24:
14:
13:
10:
9:
6:
4:
3:
2:
1269:
1258:
1255:
1253:
1250:
1249:
1247:
1237:
1234:
1233:
1229:
1220:
1214:
1210:
1206:
1201:
1196:
1189:
1188:
1180:
1177:
1172:
1166:
1162:
1158:
1153:
1148:
1144:
1137:
1134:
1129:
1123:
1119:
1115:
1110:
1105:
1101:
1094:
1091:
1086:
1080:
1076:
1072:
1067:
1062:
1058:
1051:
1048:
1043:
1039:
1035:
1029:
1025:
1021:
1016:
1011:
1007:
1000:
997:
992:
986:
982:
978:
974:
967:
964:
959:
955:
951:
945:
941:
937:
932:
927:
923:
916:
913:
908:
902:
898:
894:
889:
884:
880:
873:
870:
865:
861:
857:
851:
847:
843:
838:
833:
829:
825:
821:
814:
811:
806:
800:
797:
792:
786:
782:
778:
774:
770:
763:
760:
754:
749:
745:
738:
735:
730:
717:
708:
703:
696:
693:
688:
684:
680:
676:
671:
666:
663:(2): 99–111.
662:
658:
654:
647:
644:
640:
634:
631:
625:
622:
617:
611:
607:
603:
599:
592:
589:
582:
580:
578:
574:
570:
567:
562:
560:
556:
552:
550:
543:
541:
527:
505:
501:
497:
494:
474:
454:
451:
448:
428:
425:
422:
402:
389:
385:
383:
377:
361:
339:
329:
327:
322:
307:
295:
293:
290:
288:
284:
281:
277:
274:
272:
268:
264:
260:
253:
248:
246:
242:
239:
237:
232:
229:
227:
218:
212:
208:
205:
204:
199:
192:
189:
188:
184:
180:
179:cryptographic
176:
172:
169:
168:
167:
165:
157:
153:
148:
145:
142:
139:
137:
133:
132:
131:
128:
126:
122:
118:
114:
110:
105:
103:
100:
99:authenticated
92:
90:
88:
85:is a type of
84:
74:
71:
63:
53:
49:
43:
40:This article
38:
29:
28:
19:
1186:
1179:
1142:
1136:
1099:
1093:
1056:
1050:
1005:
999:
972:
966:
921:
915:
878:
872:
823:
813:
799:
772:
762:
743:
737:
716:cite journal
695:
660:
656:
646:
633:
624:
597:
591:
564:There is no
563:
553:
547:
394:
378:
330:
325:
323:
299:
291:
285:
282:
278:
275:
259:Stuart Haber
257:
243:
240:
233:
230:
222:
214:time-stamps.
210:
182:
174:
161:
151:
129:
121:private keys
108:
106:
96:
82:
81:
66:
57:
46:Please help
41:
826:. pp.
254:Foundations
170:Aggregation
141:Merkle tree
93:Description
1246:Categories
583:References
382:collisions
206:Publishing
185:operation.
175:aggregated
136:hash chain
117:blockchain
115:or public
1195:CiteSeerX
1147:CiteSeerX
1104:CiteSeerX
1061:CiteSeerX
1010:CiteSeerX
926:CiteSeerX
883:CiteSeerX
832:CiteSeerX
748:CiteSeerX
702:CiteSeerX
665:CiteSeerX
549:ISO 18014
544:Standards
211:publishes
147:Skip list
113:newspaper
109:published
864:14108602
687:14363020
520:, where
249:Research
219:Security
1042:1230568
639:XAdES-A
190:Linking
183:linking
134:Linear
1215:
1197:
1167:
1149:
1124:
1106:
1081:
1063:
1040:
1030:
1012:
987:
958:573442
956:
946:
928:
903:
885:
862:
852:
834:
787:
750:
704:
685:
667:
612:
575:
287:Buldas
1191:(PDF)
1038:S2CID
954:S2CID
860:S2CID
683:S2CID
1257:Time
1213:ISBN
1165:ISBN
1122:ISBN
1079:ISBN
1028:ISBN
985:ISBN
944:ISBN
901:ISBN
850:ISBN
785:ISBN
729:help
610:ISBN
577:4998
566:IETF
261:and
1205:doi
1157:doi
1114:doi
1071:doi
1020:doi
977:doi
936:doi
893:doi
842:doi
777:doi
675:doi
602:doi
573:RFC
569:RFC
352:to
271:TSA
236:RSA
125:PKI
50:by
1248::
1211:.
1203:.
1163:.
1155:.
1120:.
1112:.
1077:.
1069:.
1036:.
1026:.
1018:.
983:.
952:.
942:.
934:.
899:.
891:.
858:.
848:.
840:.
830:.
828:28
822:.
783:.
771:.
720::
718:}}
714:{{
681:.
673:.
659:.
655:.
608:.
441:,
415:,
376:.
238:.
1221:.
1207::
1173:.
1159::
1130:.
1116::
1087:.
1073::
1044:.
1022::
993:.
979::
960:.
938::
909:.
895::
866:.
844::
807:.
793:.
779::
756:.
731:)
727:(
710:.
689:.
677::
661:3
641:.
618:.
604::
528:l
506:l
502:2
498:=
495:N
475:N
455:2
452:+
449:t
429:1
426:+
423:t
403:t
362:N
340:N
308:N
73:)
67:(
62:)
58:(
54:.
44:.
20:)
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.