We prove several results relating injective one-way functions, timebounded conditional Kolmogorov complexity, and time-bounded conditional entropy. The idea is to use an expected value approach of the time-bounded Kolmogorov complexity.

We prove a separation result: based on the concept of time-bounded Kolmogorov complexity, we find an interval in which every function f is a necessarily weak but not a strong one-way function.

We propose an individual approach to injective one-way functions based on Kolmogorov complexity, defining Kolmogorov one-way functions and prove some relationships between the new proposal and the classical definition of one-way functions. We explore how Kolmogorov one-way functions are related with the conjecture of polynomial time symmetry of information.

Finally, we relate our definitions and results with two forms of time-bounded entropy.

Work based on:

L. Antunes, A. Matos, A. Pinto, A. Souto and A. Teixeira, One-Way Functions Using Algorithmic and Classical Information Theories, Theory of Computing Systems, 52(1):162-178 Springer Verlag, 2013.