{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,12]],"date-time":"2025-10-12T03:58:35Z","timestamp":1760241515065,"version":"build-2065373602"},"reference-count":20,"publisher":"MDPI AG","issue":"2","license":[{"start":{"date-parts":[[2018,4,28]],"date-time":"2018-04-28T00:00:00Z","timestamp":1524873600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Cryptography"],"abstract":"<jats:p>We study characterizations of one-way functions in terms of time-bounded Kolmogorov complexity. As the main contribution, we propose definitions for strong and weak Kolmogorov one-way functions and show that these are equivalent to classical strong and weak one-way functions, respectively. The new definitions were motivated by the fact that the expected value approach is not able to characterize strong one-way functions as we prove in the paper.<\/jats:p>","DOI":"10.3390\/cryptography2020009","type":"journal-article","created":{"date-parts":[[2018,4,30]],"date-time":"2018-04-30T03:45:49Z","timestamp":1525059949000},"page":"9","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Kolmogorov One-Way Functions Revisited"],"prefix":"10.3390","volume":"2","author":[{"given":"Filipe","family":"Casal","sequence":"first","affiliation":[{"name":"Department Matem\u00e1tica, Instituto Superior T\u00e9cnico, Avenida Rovisco Pais 1, 1049-001 Lisboa, Portugal"},{"name":"Centro de Matem\u00e1tica, Aplica\u00e7\u00f5es Fundamentais e Investiga\u00e7\u00e3o Operacional (CMAF-CIO), Campo Grande 016, 1749-016 Lisboa, Portugal"}]},{"given":"Jo\u00e3o","family":"Rasga","sequence":"additional","affiliation":[{"name":"Department Matem\u00e1tica, Instituto Superior T\u00e9cnico, Avenida Rovisco Pais 1, 1049-001 Lisboa, Portugal"},{"name":"Centro de Matem\u00e1tica, Aplica\u00e7\u00f5es Fundamentais e Investiga\u00e7\u00e3o Operacional (CMAF-CIO), Campo Grande 016, 1749-016 Lisboa, Portugal"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8792-959X","authenticated-orcid":false,"given":"Andr\u00e9","family":"Souto","sequence":"additional","affiliation":[{"name":"Department Inform\u00e1tica, Faculdade de Ci\u00eancias, Campo Grande 016, 1749-016 Lisboa, Portugal"},{"name":"LASIGE, Faculdade de Ci\u00eancias, U Lisboa, Portugal; Campo Grande 016, 1749-016 Lisboa, Portugal"},{"name":"Instituto de Telecomunica\u00e7\u00f5es, Avenida Rovisco Pais, 1, 1049-001 Lisboa, Portugal"}]}],"member":"1968","published-online":{"date-parts":[[2018,4,28]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","unstructured":"Goldreich, O. (2001). Foundations of Cryptography, Cambridge University Press.","DOI":"10.1017\/CBO9780511546891"},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"850","DOI":"10.1137\/0213053","article-title":"How to generate cryptographically strong sequences of pseudo-random bits","volume":"13","author":"Blum","year":"1984","journal-title":"SIAM J. Comput."},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"281","DOI":"10.1137\/0217017","article-title":"A digital signature scheme secure against adaptive chosen-message attacks","volume":"17","author":"Goldwasser","year":"1988","journal-title":"SIAM J. Comput."},{"key":"ref_4","unstructured":"Impagliazzo, R., and Luby, M. (November, January 30). One-way functions are essential for complexity based cryptography. Proceedings of the Symposium on Foundations of Computer Science \u201989, Research Triangle Park, NC, USA."},{"key":"ref_5","doi-asserted-by":"crossref","unstructured":"Impagliazzo, R., Levin, L., and Luby, M. (1989, January 14\u201317). Pseudo-random generation from one-way functions. Proceedings of the Symposium on Theory of Computing \u201989 ACM, Seattle, WA, USA.","DOI":"10.1145\/73007.73009"},{"key":"ref_6","doi-asserted-by":"crossref","unstructured":"Rompel, J. (1990, January 13\u201317). One-way functions are necessary and sufficient for secure signatures. Proceedings of the Symposium on Theory of Computing \u201990 ACM, Baltimore, MD, USA.","DOI":"10.1145\/100216.100269"},{"key":"ref_7","first-page":"1","article-title":"Three approaches to the quantitative definition of information","volume":"1","author":"Kolmogorov","year":"1965","journal-title":"Probl. Inf. Transm."},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/S0019-9958(64)90223-2","article-title":"A formal theory of inductive inference, part I","volume":"7","author":"Solomonoff","year":"1964","journal-title":"Inf. Control"},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"547","DOI":"10.1145\/321356.321363","article-title":"On the length of programs for computing finite binary sequences","volume":"13","author":"Chaitin","year":"1966","journal-title":"J. ACM"},{"key":"ref_10","unstructured":"Souto, A., Teixeira, A., and Pinto, A. (2010). One-way functions using Kolmogorov complexity. Proc. of CiE, 346\u2013356."},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"162","DOI":"10.1007\/s00224-012-9418-z","article-title":"One-Way Functions Using Algorithmic and Classical Information Theories","volume":"52","author":"Antunes","year":"2013","journal-title":"Theory Comput. Syst."},{"key":"ref_12","unstructured":"Li, M., and Vit\u00e1nyi, P. (2013). An Introduction to Kolmogorov Complexity and its Applications, Springer."},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"92","DOI":"10.1023\/A:1023634616182","article-title":"The Tale of One-Way Functions","volume":"39","author":"Levin","year":"2003","journal-title":"Probl. Inf. Trans."},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"149","DOI":"10.1007\/s11128-017-1599-6","article-title":"Quantum one-way permutation over the finite field of two elements","volume":"16","year":"2017","journal-title":"Quantum Inf. Process."},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"2464","DOI":"10.1109\/18.945258","article-title":"Quantum Kolmogorov complexity based on classical descriptions","volume":"47","year":"2001","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"201","DOI":"10.1006\/jcss.2001.1765","article-title":"Quantum Kolmogorov complexity","volume":"63","author":"Berthiaume","year":"2001","journal-title":"J. Comput. Syst. Sci."},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"6859","DOI":"10.1088\/0305-4470\/34\/35\/312","article-title":"Quantum algorithmic entropy","volume":"34","year":"2001","journal-title":"J. Phys. A Math. Gen."},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"200503","DOI":"10.1103\/PhysRevLett.95.200503","article-title":"Algorithmic Complexity and Entanglement of Quantum States","volume":"95","author":"Mora","year":"2005","journal-title":"Phys. Rev. Lett."},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"763","DOI":"10.1109\/TIT.2007.913263","article-title":"Strongly Universal Quantum Turing Machines and Invariance of Kolmogorov Complexity","volume":"54","year":"2008","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1093\/logcom\/exv008","article-title":"Universality of quantum Turing machines with deterministic control","volume":"27","author":"Mateus","year":"2017","journal-title":"J. Log. Comput."}],"container-title":["Cryptography"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/2410-387X\/2\/2\/9\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T15:02:31Z","timestamp":1760194951000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/2410-387X\/2\/2\/9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,4,28]]},"references-count":20,"journal-issue":{"issue":"2","published-online":{"date-parts":[[2018,6]]}},"alternative-id":["cryptography2020009"],"URL":"https:\/\/doi.org\/10.3390\/cryptography2020009","relation":{},"ISSN":["2410-387X"],"issn-type":[{"type":"electronic","value":"2410-387X"}],"subject":[],"published":{"date-parts":[[2018,4,28]]}}}