{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,24]],"date-time":"2026-04-24T11:38:00Z","timestamp":1777030680976,"version":"3.51.4"},"reference-count":18,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2008,7,1]],"date-time":"2008-07-01T00:00:00Z","timestamp":1214870400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Inf. Syst. Secur."],"published-print":{"date-parts":[[2008,7]]},"abstract":"<jats:p>\n            Cryptanalytic time-memory trade-offs have been studied for 25 years and have benefited from several improvements since the original work of Hellman. The ensuing variants definitely improve the original trade-off but their real impact has never been evaluated in practice. We fill this lack by analyzing the\n            <jats:italic>perfect<\/jats:italic>\n            form of classic tables, distinguished point-based tables, and rainbow tables. We especially provide a thorough analysis of the latter variant, whose performances have never been formally calculated yet. Our analysis leads to the concept of a\n            <jats:italic>characteristic<\/jats:italic>\n            that enables to measure the intrinsic quality of a trade-off. We finally introduce a new technique based on\n            <jats:italic>checkpoints<\/jats:italic>\n            that still reduces the cryptanalysis time by ruling out false alarms probabilistically. Our analysis yields the exact gain of this approach and establishes its efficiency when applied on rainbow tables.\n          <\/jats:p>","DOI":"10.1145\/1380564.1380565","type":"journal-article","created":{"date-parts":[[2008,8,5]],"date-time":"2008-08-05T13:35:10Z","timestamp":1217943310000},"page":"1-22","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":50,"title":["Characterization and Improvement of Time-Memory Trade-Off Based on Perfect Tables"],"prefix":"10.1145","volume":"11","author":[{"given":"Gildas","family":"Avoine","sequence":"first","affiliation":[{"name":"Universit\u00e9 Catholique de Louvain (UCL)"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Pascal","family":"Junod","sequence":"additional","affiliation":[{"name":"Nagravision SA (Kudelski Group)"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Philippe","family":"Oechslin","sequence":"additional","affiliation":[{"name":"Objectif S\u00e9curit\u00e9"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2008,7]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1007\/11596219_15"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/11818175_1"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.5555\/2180540.2180551"},{"key":"e_1_2_1_4_1","volume-title":"Proceedings of Advances in Cryptology -- 7th International Conference on the Theory and Application of Cryptology and Information Security (ASIACRYPT'01)","volume":"2248","author":"Biryukov A."},{"key":"e_1_2_1_5_1","volume-title":"Proceedings of the Fast Software Encryption -- 7th International Workshop (FSE'00)","volume":"1978","author":"Biryukov A."},{"key":"e_1_2_1_6_1","volume-title":"Proceedings of the 19th Symposium on Information Theory in the Benelux, P. de With and M. van der Schaar-Mitrea, Eds","author":"Borst J."},{"key":"e_1_2_1_7_1","volume-title":"Cryptography and Data Security","author":"Denning D."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/103418.103473"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539795280512"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1980.1056220"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/11593447_19"},{"key":"e_1_2_1_12_1","unstructured":"Kim I. and Matsumoto T. 1999. Achieving higher success probability in time-memory trade-off cryptanalysis without increasing memory size. IEICE Transactions on Communications\/Electronics\/Information and Systems E82-A 1 (January) 123--129.]]  Kim I. and Matsumoto T. 1999. Achieving higher success probability in time-memory trade-off cryptanalysis without increasing memory size. IEICE Transactions on Communications\/Electronics\/Information and Systems E82-A 1 (January) 123--129.]]"},{"key":"e_1_2_1_13_1","unstructured":"Kusuda K. and Matsumoto T. 1996. Optimization of time-memory trade-off cryptanalysis and its application to DES FEAL-32 and Skipjack. IEICE Trans. Fundamentals E79-A 1 (January) 35--48.]]  Kusuda K. and Matsumoto T. 1996. Optimization of time-memory trade-off cryptanalysis and its application to DES FEAL-32 and Skipjack. IEICE Trans. Fundamentals E79-A 1 (January) 35--48.]]"},{"key":"e_1_2_1_14_1","volume-title":"Proceedings of the Workshop on Special Purpose Hardware for Attacking Cryptographic Systems (SHARCS'05)","author":"Mentens N."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-45146-4_36"},{"key":"e_1_2_1_16_1","volume-title":"Proceedings of Advances in Cryptology -- Workshop on the Theory and Application of Cryptographic Techniques (EUROCRYPT'89)","volume":"434","author":"Quisquater J.-J."},{"key":"e_1_2_1_17_1","volume-title":"Proceedings of the Workshop on Cryptographic Hardware and Embedded Systems (CHES'02)","volume":"2523","author":"Standaert F. c.-X."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/PL00003816"}],"container-title":["ACM Transactions on Information and System Security"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1380564.1380565","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1380564.1380565","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T13:57:45Z","timestamp":1750255065000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1380564.1380565"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,7]]},"references-count":18,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2008,7]]}},"alternative-id":["10.1145\/1380564.1380565"],"URL":"https:\/\/doi.org\/10.1145\/1380564.1380565","relation":{},"ISSN":["1094-9224","1557-7406"],"issn-type":[{"value":"1094-9224","type":"print"},{"value":"1557-7406","type":"electronic"}],"subject":[],"published":{"date-parts":[[2008,7]]},"assertion":[{"value":"2006-06-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2007-11-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2008-07-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}