{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,27]],"date-time":"2026-02-27T23:54:32Z","timestamp":1772236472028,"version":"3.50.1"},"reference-count":47,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2023,12,12]],"date-time":"2023-12-12T00:00:00Z","timestamp":1702339200000},"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. Priv. Secur."],"published-print":{"date-parts":[[2024,2,29]]},"abstract":"<jats:p>\n            Logging is a key mechanism in the security of computer systems. Beyond supporting important forward security properties, it is critical that logging withstands both failures and intentional tampering to prevent subtle attacks leaving the system in an inconsistent state with inconclusive evidence. We propose new techniques combining forward security with crash recovery for secure log data storage. As the support of specifically forward integrity and the online nature of logging prevent the use of conventional coding, we propose and analyze a coding scheme resolving these unique design constraints. Specifically, our coding enables forward integrity, online encoding, and most importantly a constant number of operations per encoding. It adds a new log item by \ud835\uddb7\ud835\uddae\ud835\uddb1 ing it to\n            <jats:italic>k<\/jats:italic>\n            cells of a table. If up to a certain threshold of cells is modified by the adversary, or lost due to a crash, we still guarantee recovery of all stored log items. The main advantage of the coding scheme is its efficiency and compatibility with forward integrity. The key contribution of the paper is the use of spectral graph theory techniques to prove that\n            <jats:italic>k<\/jats:italic>\n            is constant in the number\n            <jats:italic>n<\/jats:italic>\n            of all log items ever stored and small in practice, e.g.,\n            <jats:italic>k<\/jats:italic>\n            = 5. Moreover, we prove that to cope with up to\n            <jats:inline-formula content-type=\"math\/tex\">\n              <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(\\sqrt {n}\\)<\/jats:tex-math>\n            <\/jats:inline-formula>\n            modified or lost log items, storage expansion is constant in\n            <jats:italic>n<\/jats:italic>\n            and small in practice. For\n            <jats:italic>k<\/jats:italic>\n            = 5, the size of the table is only 12% more than the simple concatenation of all\n            <jats:italic>n<\/jats:italic>\n            items. We propose and evaluate original techniques to scale the computation cost of recovery to several GBytes of security logs. We instantiate our scheme into an abstract data structure which allows to either detect adversarial modifications to log items or treat modifications like data loss in a system crash. The data structure can recover lost log items, thereby effectively reverting adversarial modifications.\n          <\/jats:p>","DOI":"10.1145\/3631524","type":"journal-article","created":{"date-parts":[[2023,11,3]],"date-time":"2023-11-03T20:07:29Z","timestamp":1699042049000},"page":"1-28","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["Forward Security with Crash Recovery for Secure Logs"],"prefix":"10.1145","volume":"27","author":[{"ORCID":"https:\/\/orcid.org\/0009-0008-2791-1564","authenticated-orcid":false,"given":"Erik-Oliver","family":"Blass","sequence":"first","affiliation":[{"name":"Airbus, Germany, Germany"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5876-2874","authenticated-orcid":false,"given":"Guevara","family":"Noubir","sequence":"additional","affiliation":[{"name":"Northeastern University, USA, USA"}]}],"member":"320","published-online":{"date-parts":[[2023,12,12]]},"reference":[{"key":"e_1_3_1_2_2","first-page":"1791","volume-title":"43rd IEEE Symposium on Security and Privacy, SP 2022, San Francisco, CA, USA, May 22-26, 2022","author":"Ahmad A.","year":"2022","unstructured":"A. Ahmad, S. Lee, and M. Peinado. 2022. HARDLOG: Practical tamper-proof system auditing using a novel audit device. In 43rd IEEE Symposium on Security and Privacy, SP 2022, San Francisco, CA, USA, May 22-26, 2022. IEEE, 1791\u20131807."},{"issue":"2","key":"e_1_3_1_3_2","doi-asserted-by":"crossref","first-page":"281","DOI":"10.1007\/s00145-009-9040-7","article-title":"Security against covert adversaries: Efficient protocols for realistic adversaries","volume":"23","author":"Aumann Y.","year":"2010","unstructured":"Y. Aumann and Y. Lindell. 2010. Security against covert adversaries: Efficient protocols for realistic adversaries. Journal of Cryptology 23, 2 (2010), 281\u2013343. ISSN 0933-2790.","journal-title":"Journal of Cryptology"},{"key":"e_1_3_1_4_2","volume-title":"International Symposium on Foundations & Practice of Security","author":"Avizheh S.","year":"2019","unstructured":"S. Avizheh, R. Safavi-Naini, and S. Li. 2019. Secure logging with security against adaptive crash attack. In International Symposium on Foundations & Practice of Security. Toulouse, France. https:\/\/arxiv.org\/abs\/1910.14169"},{"key":"e_1_3_1_5_2","volume-title":"Forward Integrity for Secure Audit Logs","author":"Bellare M.","year":"1997","unstructured":"M. Bellare and B. S. Yee. 1997. Forward Integrity for Secure Audit Logs. Technical Report. UC San Diego."},{"key":"e_1_3_1_6_2","first-page":"1","volume-title":"Topics in Cryptology - CT-RSA 2003, The Cryptographers\u2019 Track at the RSA Conference 2003, San Francisco, CA, USA, April 13-17, 2003, Proceedings","author":"Bellare M.","year":"2003","unstructured":"M. Bellare and B. S. Yee. 2003. Forward-security in private-key cryptography. In Topics in Cryptology - CT-RSA 2003, The Cryptographers\u2019 Track at the RSA Conference 2003, San Francisco, CA, USA, April 13-17, 2003, Proceedings. 1\u201318."},{"key":"e_1_3_1_7_2","first-page":"1","volume-title":"Conference on Communications and Network Security","author":"Blass E.-O.","year":"2017","unstructured":"E.-O. Blass and G. Noubir. 2017. Secure logging with crash tolerance. In Conference on Communications and Network Security. Las Vegas, USA, 1\u201310."},{"key":"e_1_3_1_8_2","unstructured":"E.-O. Blass and G. Noubir. 2022. Source code for experiments. (2022). https:\/\/github.com\/dalmayr777\/secure-logging"},{"key":"e_1_3_1_9_2","first-page":"46","volume-title":"RAID","author":"Bowers K. D.","year":"2014","unstructured":"K. D. Bowers, C. Hart, A. Juels, and N. Triandopoulos. 2014. PillarBox: Combating next-generation malware with fast forward-secure logging. In RAID. 46\u201367."},{"issue":"1","key":"e_1_3_1_10_2","doi-asserted-by":"crossref","first-page":"49","DOI":"10.1002\/(SICI)1098-2418(199608\/09)9:1\/2<49::AID-RSA3>3.0.CO;2-B","article-title":"Dependent sets of constant weight vectors in  \\(GF(q)\\)","volume":"9","author":"Calkin N. J.","year":"1996","unstructured":"N. J. Calkin. 1996. Dependent sets of constant weight vectors in \\(GF(q)\\) . Random Struct. Algorithms 9, 1-2 (1996), 49\u201353.","journal-title":"Random Struct. Algorithms"},{"issue":"3","key":"e_1_3_1_11_2","doi-asserted-by":"crossref","first-page":"263","DOI":"10.1017\/S0963548397003040","article-title":"Dependent sets of constant weight binary vectors","volume":"6","author":"Calkin N. J.","year":"1997","unstructured":"N. J. Calkin. 1997. Dependent sets of constant weight binary vectors. Combinatorics, Probability & Computing 6, 3 (1997), 263\u2013271.","journal-title":"Combinatorics, Probability & Computing"},{"issue":"3","key":"e_1_3_1_12_2","doi-asserted-by":"crossref","first-page":"251","DOI":"10.1016\/S0747-7171(08)80013-2","article-title":"Matrix multiplication via arithmetic progressions","volume":"9","author":"Coppersmith D.","year":"1990","unstructured":"D. Coppersmith and S. Winograd. 1990. Matrix multiplication via arithmetic progressions. J. Symb. Comput. 9, 3 (1990), 251\u2013280.","journal-title":"J. Symb. Comput."},{"key":"e_1_3_1_13_2","volume-title":"Elements of Information Theory (Wiley Series in Telecommunications and Signal Processing)","author":"Cover T. M.","year":"2006","unstructured":"T. M. Cover and J. A. Thomas. 2006. Elements of Information Theory (Wiley Series in Telecommunications and Signal Processing). Wiley-Interscience."},{"key":"e_1_3_1_14_2","first-page":"385","volume-title":"ICALP","author":"Dietzfelbinger M.","year":"2008","unstructured":"M. Dietzfelbinger and R. Pagh. 2008. Succinct data structures for retrieval and approximate membership (extended abstract). In ICALP. 385\u2013396."},{"key":"e_1_3_1_15_2","first-page":"17","volume-title":"Publication of the Mathematical Institute of the Hungarian Academy of Sciences","author":"Erd\u0151s P.","year":"1960","unstructured":"P. Erd\u0151s and A. R\u00e9nyi. 1960. On the evolution of random graphs. In Publication of the Mathematical Institute of the Hungarian Academy of Sciences. 17\u201361."},{"key":"e_1_3_1_16_2","volume-title":"Parameterized Complexity Theory","author":"Flum J.","year":"2006","unstructured":"J. Flum and M. Grohe. 2006. Parameterized Complexity Theory. Springer."},{"issue":"1","key":"e_1_3_1_17_2","doi-asserted-by":"crossref","first-page":"21","DOI":"10.1109\/TIT.1962.1057683","article-title":"Low-density parity-check codes","volume":"8","author":"Gallager R. G.","year":"1962","unstructured":"R. G. Gallager. 1962. Low-density parity-check codes. IRE Trans. Information Theory 8, 1 (1962), 21\u201328.","journal-title":"IRE Trans. Information Theory"},{"key":"e_1_3_1_18_2","first-page":"792","volume-title":"Allerton Conference on Communication, Control, and Computing","author":"Goodrich M. T.","year":"2011","unstructured":"M. T. Goodrich and M. Mitzenmacher. 2011. Invertible Bloom lookup tables. In Allerton Conference on Communication, Control, and Computing. Monticello, USA, 792\u2013799."},{"key":"e_1_3_1_19_2","first-page":"183","volume-title":"CT-RSA (LNCS)","author":"Hartung G.","year":"2016","unstructured":"G. Hartung. 2016. Secure audit logs with verifiable excerpts. In CT-RSA (LNCS), Vol. 9610. 183\u2013199."},{"key":"e_1_3_1_20_2","first-page":"2389","volume-title":"31st USENIX Security Symposium (USENIX Security 22)","author":"Hoang V. T.","year":"2022","unstructured":"V. T. Hoang, C. Wu, and X. Yuan. 2022. Faster yet safer: Logging system via fixed-key blockcipher. In 31st USENIX Security Symposium (USENIX Security 22). USENIX Association, Boston, MA, 2389\u20132406."},{"key":"e_1_3_1_21_2","first-page":"203","volume-title":"Australasian Symposium on Grid Computing and e-Research","author":"Holt J. E.","year":"2006","unstructured":"J. E. Holt. 2006. Logcrypt: forward security and public verification for secure audit logs. In Australasian Symposium on Grid Computing and e-Research. 203\u2013211."},{"key":"e_1_3_1_22_2","first-page":"19","volume-title":"AsiaCCS","author":"Karande V.","year":"2017","unstructured":"V. Karande, E. Bauman, Z. Lin, and L. Khan. 2017. SGX-Log: Securing system logs with SGX. In AsiaCCS. ACM, 19\u201330."},{"key":"e_1_3_1_23_2","doi-asserted-by":"crossref","first-page":"223","DOI":"10.1145\/945445.945467","volume-title":"19th ACM Symposium on Operating Systems Principles, Bolton Landing, NY, USA","author":"King Samuel T.","year":"2003","unstructured":"Samuel T. King and Peter M. Chen. 2003. Backtracking intrusions. In 19th ACM Symposium on Operating Systems Principles, Bolton Landing, NY, USA. 223\u2013236."},{"key":"e_1_3_1_24_2","volume-title":"Error Control Coding, Second Edition","author":"Lin S.","year":"2004","unstructured":"S. Lin and D. J. Costello. 2004. Error Control Coding, Second Edition. Prentice-Hall, Inc., USA."},{"key":"e_1_3_1_25_2","unstructured":"Linux Kernel Documentation. 2020. \/proc\/sys\/vm\/dirty_expire_centisecs. (2020). Standard value is 30 sec on kernel 5.8 64 bit https:\/\/www.kernel.org\/doc\/Documentation\/sysctl\/vm.txt"},{"key":"e_1_3_1_26_2","doi-asserted-by":"publisher","DOI":"10.17487\/RFC3164"},{"key":"e_1_3_1_27_2","volume-title":"IEEE Annual Symposium on Foundations of Computer Science","author":"Luby M.","year":"2002","unstructured":"M. Luby. 2002. LT codes. In IEEE Annual Symposium on Foundations of Computer Science."},{"issue":"1","key":"e_1_3_1_28_2","article-title":"A new approach to secure logging","volume":"5","author":"Ma D.","year":"2009","unstructured":"D. Ma and G. Tsudik. 2009. A new approach to secure logging. ACM Transactions on Storage 5, 1 (2009). ISSN: 1553-3077.","journal-title":"ACM Transactions on Storage"},{"key":"e_1_3_1_29_2","first-page":"111","volume-title":"ESORICS","author":"Marson G. A.","year":"2013","unstructured":"G. A. Marson and B. Poettering. 2013. Practical secure logging: Seekable sequential key generators. In ESORICS. 111\u2013128."},{"key":"e_1_3_1_30_2","first-page":"37","volume-title":"ESORICS","author":"Marson G. A.","year":"2014","unstructured":"G. A. Marson and B. Poettering. 2014. Even more practical secure logging: Tree-based seekable sequential key generators. In ESORICS. 37\u201354."},{"key":"e_1_3_1_31_2","volume-title":"NDSS","author":"Paccagnella R.","year":"2020","unstructured":"R. Paccagnella, P. Datta, W. Ul Hassan, A. Bates, C. W. Fletcher, A. Miller, and D. Tian. 2020. Custos: Practical tamper-evident auditing of operating systems using trusted execution. In NDSS. The Internet Society."},{"key":"e_1_3_1_32_2","first-page":"1551","volume-title":"Conference on Computer and Communications Security","author":"Paccagnella R.","year":"2020","unstructured":"R. Paccagnella, K. Liao, D. Tian, and A. Bates. 2020. Logging to the danger zone: Race condition attacks and defenses on system audit frameworks. In Conference on Computer and Communications Security. 1551\u20131574."},{"issue":"4","key":"e_1_3_1_33_2","doi-asserted-by":"crossref","first-page":"185","DOI":"10.1016\/j.ipl.2013.11.015","article-title":"Improving the performance of invertible Bloom lookup tables","volume":"114","author":"Pontarelli S.","year":"2014","unstructured":"S. Pontarelli, P. Reviriego, and M. Mitzenmacher. 2014. Improving the performance of invertible Bloom lookup tables. Inf. Process. Lett. 114, 4 (2014), 185\u2013191.","journal-title":"Inf. Process. Lett."},{"key":"e_1_3_1_34_2","first-page":"622","volume-title":"ESORICS (LNCS)","author":"Pulls T.","year":"2015","unstructured":"T. Pulls and R. Peeters. 2015. Balloon: A forward-secure append-only persistent authenticated data structure. In ESORICS (LNCS), Vol. 9327. 622\u2013641."},{"key":"e_1_3_1_35_2","first-page":"159","volume-title":"RANDOM\u201998 (LNCS)","author":"Raab M.","year":"1998","unstructured":"M. Raab and A. Steger. 1998. Balls into bins \u2013 a simple and tight analysis. In RANDOM\u201998 (LNCS), Vol. 1518. 159\u2013170."},{"issue":"2","key":"e_1_3_1_36_2","doi-asserted-by":"crossref","first-page":"638","DOI":"10.1109\/18.910579","article-title":"Efficient encoding of low-density parity-check codes","volume":"47","author":"Richardson T. J.","year":"2001","unstructured":"T. J. Richardson and R. L. Urbanke. 2001. Efficient encoding of low-density parity-check codes. IEEE Transactions on Information Theory 47, 2 (Feb. 2001), 638\u2013656.","journal-title":"IEEE Transactions on Information Theory"},{"key":"e_1_3_1_37_2","first-page":"348","volume-title":"Proceedings of FSE","author":"Rogaway P.","year":"2004","unstructured":"P. Rogaway. 2004. Nonce-based symmetric encryption. In Proceedings of FSE. Delhi, India, 348\u2013359. ISBN 3-540-22171-9."},{"issue":"2","key":"e_1_3_1_38_2","doi-asserted-by":"crossref","first-page":"159","DOI":"10.1145\/317087.317089","article-title":"Secure audit logs to support computer forensics","volume":"2","author":"Schneier B.","year":"1999","unstructured":"B. Schneier and J. Kelsey. 1999. Secure audit logs to support computer forensics. ACM Transactions on Information and System Security 2, 2 (1999), 159\u2013176.","journal-title":"ACM Transactions on Information and System Security"},{"key":"e_1_3_1_39_2","first-page":"262","volume-title":"IEEE Symposium on Security and Privacy, Oakland, California, USA","author":"Seiden K. F.","year":"1990","unstructured":"K. F. Seiden and J. P. Melanson. 1990. The auditing facility for a VMM security kernel. In IEEE Symposium on Security and Privacy, Oakland, California, USA. IEEE Computer Society, 262\u2013277."},{"issue":"3","key":"e_1_3_1_40_2","doi-asserted-by":"crossref","first-page":"379","DOI":"10.1002\/j.1538-7305.1948.tb01338.x","article-title":"A mathematical theory of communication","volume":"27","author":"Shannon C. E.","year":"1948","unstructured":"C. E. Shannon. 1948. A mathematical theory of communication. The Bell System Technical Journal 27, 3 (July 1948), 379\u2013423.","journal-title":"The Bell System Technical Journal"},{"key":"e_1_3_1_41_2","series-title":"Coding, Cryptography and Combinatorics","first-page":"85","volume-title":"LDPC Codes: An Introduction","author":"Shokrollahi A.","year":"2004","unstructured":"A. Shokrollahi. 2004. LDPC Codes: An Introduction. Coding, Cryptography and Combinatorics, Vol. 23. Birkh\u00e4user, 85\u2013110. ISBN 978-3-0348-9602-3."},{"issue":"6","key":"e_1_3_1_42_2","doi-asserted-by":"crossref","first-page":"2551","DOI":"10.1109\/TIT.2006.874390","article-title":"Raptor codes","volume":"52","author":"Shokrollahi A.","year":"2006","unstructured":"A. Shokrollahi. 2006. Raptor codes. IEEE Transactions on Information Theory 52, 6 (2006), 2551\u20132567.","journal-title":"IEEE Transactions on Information Theory"},{"issue":"4","key":"e_1_3_1_43_2","doi-asserted-by":"crossref","first-page":"354","DOI":"10.1007\/BF02165411","article-title":"Gaussian elimination is not optimal","volume":"13","author":"Strassen V.","year":"1969","unstructured":"V. Strassen. 1969. Gaussian elimination is not optimal. Numer. Math. 13, 4 (1969), 354\u2013356.","journal-title":"Numer. Math."},{"key":"e_1_3_1_44_2","unstructured":"Stephan van Schaik Alex Seto Thomas Yurek Adam Batori Bader AlBassam Christina Garman Daniel Genkin Andrew Miller Eyal Ronen and Yuval Yarom. 2022. SoK: SGX.Fail: How stuff get exposed. https:\/\/sgx.fail"},{"issue":"1","key":"e_1_3_1_45_2","doi-asserted-by":"crossref","first-page":"54","DOI":"10.1109\/TIT.1986.1057137","article-title":"Solving sparse linear equations over finite fields","volume":"32","author":"Wiedemann D.","year":"1986","unstructured":"D. Wiedemann. 1986. Solving sparse linear equations over finite fields. IEEE Transactions on Information Theory 32, 1 (January 1986), 54\u201362.","journal-title":"IEEE Transactions on Information Theory"},{"key":"e_1_3_1_46_2","unstructured":"XEN. 2023. (Incomplete) list of security flaws in XEN allowing to break out of VM. (2023). https:\/\/xenbits.xen.org\/xsa\/advisory-148.html https:\/\/xenbits.xen.org\/xsa\/advisory-182.html https:\/\/xenbits.xen.org\/xsa\/advisory-212.html https:\/\/xenbits.xen.org\/xsa\/advisory-213.html https:\/\/xenbits.xen.org\/xsa\/advisory-214.html https:\/\/xenbits.xen.org\/xsa\/advisory-215.html"},{"issue":"2","key":"e_1_3_1_47_2","first-page":"9","article-title":"BAF and FI-BAF: Efficient and publicly verifiable cryptographic schemes for secure logging in resource-constrained systems","volume":"15","author":"Yavuz A. A.","year":"2012","unstructured":"A. A. Yavuz, P. Ning, and M. K. Reiter. 2012. BAF and FI-BAF: Efficient and publicly verifiable cryptographic schemes for secure logging in resource-constrained systems. Transactions on Information System Security 15, 2 (2012), 9. ISSN 1094-9224.","journal-title":"Transactions on Information System Security"},{"key":"e_1_3_1_48_2","doi-asserted-by":"crossref","first-page":"148","DOI":"10.1007\/978-3-642-32946-3_12","volume-title":"Financial Cryptography and Data Security (LNCS)","author":"Yavuz A. A.","year":"2012","unstructured":"A. A. Yavuz, P. Ning, and M. K. Reiter. 2012. Efficient, compromise resilient and append-only cryptographic schemes for secure audit logging. In Financial Cryptography and Data Security (LNCS), Vol. 7397. 148\u2013163."}],"container-title":["ACM Transactions on Privacy and Security"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3631524","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3631524","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T00:03:53Z","timestamp":1750291433000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3631524"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,12,12]]},"references-count":47,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2024,2,29]]}},"alternative-id":["10.1145\/3631524"],"URL":"https:\/\/doi.org\/10.1145\/3631524","relation":{},"ISSN":["2471-2566","2471-2574"],"issn-type":[{"value":"2471-2566","type":"print"},{"value":"2471-2574","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,12,12]]},"assertion":[{"value":"2022-10-19","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-10-18","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-12-12","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}