on 12-04-2013
André Souto, SQIG - Instituto de Telecomunicações
April 12, 2013, Friday, 16h15m.
Abstract: 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.
More Information..
