Computable one-way functions on the reals

Abstract

One-way functions are the functions that are easy to compute but hard to invert. In terms of oracle Turing machines, we can formalize the notion of computable functions from reals to reals, and define it to be one-way if computable functions almost everywhere fails to invert it. We show that there is a total randomness-preserving surjective one-way function. We then observe that a computable function “being total”, “being injective” and “being one-way” is incompatible, and study if we can weaken these conditions to make them compatible.

Links and resources

• slide pdf

Relevant contents

• article - Computable one-way functions on the reals