| Abstract: |
| Central in computational complexity and cryptography is the notion of oneway functions: finite maps that are easy to compute but hard to invert. Levin recently extended this concept to functions on the reals - infinite bit-sequences - using computability and algorithmic randomness. He asked whether computable oneway real functions exist, and whether they can satisfy properties that are desirable in cryptography, such as collision-resistance. In this talk I will present answers to some of these questions and additional results on probabilistic hardness of inversion for real functions. I will then proceed to explore variations of this concept and focus on characterizing the unsolvability of inverting effective real functions. I will conclude with several open questions and connections between this and several topics in computability and algorithmic randomness.
This is joint work with Mingyang Wang and Xiaoyan Zhang based on the
preprints:
http://arxiv.org/abs/2406.15817
http://arxiv.org/abs/2501.02604
https://arxiv.org/abs/2412.07592 |
|