{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,24]],"date-time":"2026-01-24T04:50:46Z","timestamp":1769230246383,"version":"3.49.0"},"reference-count":37,"publisher":"Association for Computing Machinery (ACM)","issue":"5","license":[{"start":{"date-parts":[[2019,9,19]],"date-time":"2019-09-19T00:00:00Z","timestamp":1568851200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"ANR","award":["RaCAF ANR-15-CE40-0016-01"],"award-info":[{"award-number":["RaCAF ANR-15-CE40-0016-01"]}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["1811729"],"award-info":[{"award-number":["1811729"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2019,10,31]]},"abstract":"<jats:p>\n            We show that the mutual information, in the sense of Kolmogorov complexity, of any pair of strings\n            <jats:italic>x<\/jats:italic>\n            and\n            <jats:italic>y<\/jats:italic>\n            is equal, up to logarithmic precision, to the length of the longest shared secret key that two parties\u2014one having\n            <jats:italic>x<\/jats:italic>\n            and the complexity profile of the pair and the other one having\n            <jats:italic>y<\/jats:italic>\n            and the complexity profile of the pair\u2014can establish via a probabilistic protocol with interaction on a public channel. For \u2113 &gt; 2, the longest shared secret that can be established from a tuple of strings (\n            <jats:italic>x<\/jats:italic>\n            <jats:sub>1<\/jats:sub>\n            , \u2026,\n            <jats:italic>x<\/jats:italic>\n            <jats:sub>\u2113<\/jats:sub>\n            ) by \u2113 parties\u2014each one having one component of the tuple and the complexity profile of the tuple\u2014is equal, up to logarithmic precision, to the complexity of the tuple minus the minimum communication necessary for distributing the tuple to all parties. We establish the communication complexity of secret key agreement protocols that produce a secret key of maximal length for protocols with public randomness. We also show that if the communication complexity drops below the established threshold, then only very short secret keys can be obtained.\n          <\/jats:p>","DOI":"10.1145\/3356867","type":"journal-article","created":{"date-parts":[[2019,9,19]],"date-time":"2019-09-19T15:32:43Z","timestamp":1568907163000},"page":"1-42","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":9,"title":["An Operational Characterization of Mutual Information in Algorithmic Information Theory"],"prefix":"10.1145","volume":"66","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-7723-7880","authenticated-orcid":false,"given":"Andrei","family":"Romashchenko","sequence":"first","affiliation":[{"name":"LIRMM, Univ Montpellier, CNRS, Montpellier, France"}]},{"given":"Marius","family":"Zimand","sequence":"additional","affiliation":[{"name":"Towson University, Towson, USA"}]}],"member":"320","published-online":{"date-parts":[[2019,9,19]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1109\/18.243431"},{"key":"e_1_2_1_2_1","volume-title":"Proceedings of the International Conference on Information Theoretic Security (ICITS\u201910)","author":"Antunes Luis","year":"2010","unstructured":"Luis Antunes , Sophie Laplante , Alexandre Pinto , and Liliana Salvador . 2010 . Cryptographic security of individual instances . In Proceedings of the International Conference on Information Theoretic Security (ICITS\u201910) . 195--210. Luis Antunes, Sophie Laplante, Alexandre Pinto, and Liliana Salvador. 2010. Cryptographic security of individual instances. In Proceedings of the International Conference on Information Theoretic Security (ICITS\u201910). 195--210."},{"key":"e_1_2_1_3_1","volume-title":"Optimal probabilistic polynomial time compression and the Slepian-Wolf theorem: Tighter version and simple proofs. Retrieved from: arXiv preprint arXiv:1802.00750","author":"Bauwens Bruno","year":"2018","unstructured":"Bruno Bauwens . 2018. Optimal probabilistic polynomial time compression and the Slepian-Wolf theorem: Tighter version and simple proofs. Retrieved from: arXiv preprint arXiv:1802.00750 ( 2018 ). Bruno Bauwens. 2018. Optimal probabilistic polynomial time compression and the Slepian-Wolf theorem: Tighter version and simple proofs. Retrieved from: arXiv preprint arXiv:1802.00750 (2018)."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2014.32"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1137\/0217014"},{"key":"e_1_2_1_6_1","first-page":"124","article-title":"Entropy and the complexity of the trajectories of a dynamic system","volume":"44","author":"Brudno A. A.","year":"1982","unstructured":"A. A. Brudno . 1982 . Entropy and the complexity of the trajectories of a dynamic system . Trudy Moskov. Matemat. Obsh. 44 (1982), 124 -- 149 . A. A. Brudno. 1982. Entropy and the complexity of the trajectories of a dynamic system. Trudy Moskov. Matemat. Obsh. 44 (1982), 124--149.","journal-title":"Trudy Moskov. Matemat. Obsh."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/321356.321363"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/JPROC.2015.2458316"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(01)00032-9"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1978.1055892"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2004.838380"},{"key":"e_1_2_1_12_1","first-page":"149","article-title":"Common information is far less than mutual information","volume":"2","author":"G\u00e1cs Peter","year":"1973","unstructured":"Peter G\u00e1cs and J\u00e1nos K\u00f6rner . 1973 . Common information is far less than mutual information . Prob. Contr. Inf. Theor. 2 , 2 (1973), 149 -- 162 . Peter G\u00e1cs and J\u00e1nos K\u00f6rner. 1973. Common information is far less than mutual information. Prob. Contr. Inf. Theor. 2, 2 (1973), 149--162.","journal-title":"Prob. Contr. Inf. Theor."},{"key":"e_1_2_1_13_1","volume-title":"Proceedings of the 29th Symposium on Theoretical Aspects of Computer Science (STACS\u201912)","volume":"14","author":"Goldwasser Shafi","year":"2012","unstructured":"Shafi Goldwasser . 2012 . Pseudo-deterministic algorithms . In Proceedings of the 29th Symposium on Theoretical Aspects of Computer Science (STACS\u201912) , Vol. 14 . LIPIcs, 29--29. Shafi Goldwasser. 2012. Pseudo-deterministic algorithms. In Proceedings of the 29th Symposium on Theoretical Aspects of Computer Science (STACS\u201912), Vol. 14. LIPIcs, 29--29."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2010.74"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/2936015"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0893-9659(03)90105-4"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2013.2274614"},{"key":"e_1_2_1_18_1","volume-title":"Conditional information inequalities and combinatorial applications. Retrieved from: arXiv preprint arXiv:1501.04867","author":"Kaced Tarik","year":"2015","unstructured":"Tarik Kaced , Andrei Romashchenko , and Nikolay Vereshchagin . 2015. Conditional information inequalities and combinatorial applications. Retrieved from: arXiv preprint arXiv:1501.04867 ( 2015 ). Tarik Kaced, Andrei Romashchenko, and Nikolay Vereshchagin. 2015. Conditional information inequalities and combinatorial applications. Retrieved from: arXiv preprint arXiv:1501.04867 (2015)."},{"key":"e_1_2_1_19_1","first-page":"1","article-title":"Three approaches to the quantitative definition of information","volume":"1","author":"Kolmogorov Andrei Nikolaevich","year":"1965","unstructured":"Andrei Nikolaevich Kolmogorov . 1965 . Three approaches to the quantitative definition of information . Prob. Inform. Transmiss. 1 , 1 (1965), 1 -- 7 . Andrei Nikolaevich Kolmogorov. 1965. Three approaches to the quantitative definition of information. Prob. Inform. Transmiss. 1, 1 (1965), 1--7.","journal-title":"Prob. Inform. Transmiss."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.5555\/146395.146399"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1109\/18.256484"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(98)00070-X"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1134\/S0032946010010059"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-011-9321-z"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2002.1824"},{"key":"e_1_2_1_27_1","volume-title":"Common information revisited. Retrieved from: arXiv preprint arXiv:1104.3207","author":"Razenshteyn Ilya","year":"2011","unstructured":"Ilya Razenshteyn . 2011. Common information revisited. Retrieved from: arXiv preprint arXiv:1104.3207 ( 2011 ). Ilya Razenshteyn. 2011. Common information revisited. Retrieved from: arXiv preprint arXiv:1104.3207 (2011)."},{"key":"e_1_2_1_28_1","first-page":"3","article-title":"Pairs of words with nonmaterializable mutual information","volume":"36","author":"Romashchenko Andrei","year":"2000","unstructured":"Andrei Romashchenko . 2000 . Pairs of words with nonmaterializable mutual information . Prob. Inform. Transmiss. 36 , 1 (2000), 3 -- 20 . Andrei Romashchenko. 2000. Pairs of words with nonmaterializable mutual information. Prob. Inform. Transmiss. 36, 1 (2000), 3--20.","journal-title":"Prob. Inform. Transmiss."},{"key":"e_1_2_1_29_1","first-page":"67","article-title":"Recent developments in explicit constructions of extractors","volume":"77","author":"Shaltiel Ronen","year":"2002","unstructured":"Ronen Shaltiel . 2002 . Recent developments in explicit constructions of extractors . Bull. EATCS 77 , 67 -- 95 (2002), 10. Ronen Shaltiel. 2002. Recent developments in explicit constructions of extractors. Bull. EATCS 77, 67--95 (2002), 10.","journal-title":"Bull. EATCS"},{"key":"e_1_2_1_30_1","volume-title":"Kolmogorov Complexity and Algorithmic Randomness","author":"Shen Alexander","unstructured":"Alexander Shen , Vladimir Uspensky , and Nikolay Vereshchagin . 2017. Kolmogorov Complexity and Algorithmic Randomness . American Mathematical Society . Alexander Shen, Vladimir Uspensky, and Nikolay Vereshchagin. 2017. Kolmogorov Complexity and Algorithmic Randomness. American Mathematical Society."},{"key":"e_1_2_1_31_1","first-page":"295","article-title":"The concept of (&alpha;, \u03b2)-stochasticity in the Kolmogorov sense, and its properties","volume":"28","author":"Shen Alexander Kh.","year":"1983","unstructured":"Alexander Kh. Shen . 1983 . The concept of (&alpha;, \u03b2)-stochasticity in the Kolmogorov sense, and its properties . Soviet Math. Dokl. 28 , 1 (1983), 295 -- 299 . Alexander Kh. Shen. 1983. The concept of (&alpha;, \u03b2)-stochasticity in the Kolmogorov sense, and its properties. Soviet Math. Dokl. 28, 1 (1983), 295--299.","journal-title":"Soviet Math. Dokl."},{"key":"e_1_2_1_32_1","first-page":"09","volume-title":"Proceedings of the 18th ACM-SIAM Symposium on Discrete Algorithms 7","author":"Smith Adam D.","year":"2007","unstructured":"Adam D. Smith . 2007 . Scrambling adversarial errors using few random bits, optimal information reconciliation, and better private codes . In Proceedings of the 18th ACM-SIAM Symposium on Discrete Algorithms 7 , 09 (2007), 395--404. Adam D. Smith. 2007. Scrambling adversarial errors using few random bits, optimal information reconciliation, and better private codes. In Proceedings of the 18th ACM-SIAM Symposium on Discrete Algorithms 7, 09 (2007), 395--404."},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(64)90131-7"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2013.2264355"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1561\/0400000010"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1002\/j.1538-7305.1975.tb02040.x"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/3055399.3055421"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1070\/RM1970v025n06ABEH001269"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3356867","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3356867","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3356867","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T23:22:56Z","timestamp":1750202576000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3356867"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,9,19]]},"references-count":37,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2019,10,31]]}},"alternative-id":["10.1145\/3356867"],"URL":"https:\/\/doi.org\/10.1145\/3356867","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,9,19]]},"assertion":[{"value":"2018-08-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-08-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-09-19","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}