Injective one-way functions on the reals: existence of a partial computable one-way injection under Levin's definition

Levin (2022–2024) extended the notion of one-way function to computable functions acting on infinite binary sequences ('reals'), requiring a positive-measure domain, preservation of Martin-Löf randomness, and the absence of any partial computable randomized inversion. Barmpalias and Zhang (2024; Information and Computation 2025) proved that total computable one-way surjections exist, but every known construction is a non-injective selective permutation of input bits, and total computable injections provably admit computable inverses. The paper and both of its follow-ups (2025, 2026) explicitly leave open the injective case: does a partial computable injection satisfying Levin's definition exist? No construction and no impossibility proof is known — only sharp partial results on both sides — so the question, precisely formulated, remains open.

Background

In classical computational complexity, a one-way function is a map on finite binary strings that is easy to compute but hard to invert on typical inputs, even with random advice; whether such functions exist is a central open problem and the standard foundation of complexity-based cryptography, since nearly all of it is equivalent to their existence. Levin asked what remains of this notion when computation has no time bounds and acts on infinite objects: he proposed a definition of a one-way function on the reals within his work on the foundations of set theory, and asked whether such functions exist.

Here 'the reals' means Cantor space $2^ω$ , the set of all infinite binary sequences $x(0)x(1)\ldots$ , equipped with Lebesgue measure $μ$ ; the cylinder $⟦τ⟧$ is the set of reals extending the finite string $τ$ , and $μ(⟦τ⟧)=2^{-|τ|}$ . A partial computable function $f:\subseteq 2^ω → 2^ω$ is one computed by a Turing machine that transforms approximations of any real in its domain into approximations of its value; such functions are exactly the effectively continuous partial maps, and their domains are effectively approximable ( $Π^0_2$ ) classes. A real is Martin-Löf random if it lies in no effectively null set, and $∅′$ denotes the halting problem, the paradigmatic non-computable set of natural numbers.

Definition (Levin, 2022–2024; cf. Barmpalias–Zhang, Definition 3.1). A partial computable $f:\subseteq 2^ω → 2^ω$ is one-way if: (a) its domain has positive measure and $f$ is random-preserving, meaning it maps Martin-Löf random reals in its domain to Martin-Löf random reals — a condition equivalent to the uniform measure bound $μ(f^{-1}(⟦τ⟧)) = O(μ(⟦τ⟧))$ ; and (b) no partial computable randomized procedure inverts it: for every partial computable $g:\subseteq 2^ω × 2^ω → 2^ω$ , writing $y⊕r$ for the join interleaving two reals, the set of joins $y⊕r$ such that $g(y,r)$ converges and $f(g(y,r)) = y$ has measure zero. Probability is thus taken over the range $f(2^ω)$ together with a random advice real $r$ , mirroring average-case inversion in the discrete setting.

Barmpalias and Zhang answered Levin's existence question positively: there is a total computable one-way surjection, and every randomized continuous inversion of it computes $∅′$ . All known constructions — theirs and the subsequent ones — are selective permutations of input bits: maps of the form $f(x⊕z) = h_z(x)⊕z$ where $h_z$ copies selected positions of $x$ into the output, the selection being driven by enumerations of $∅′$ ; the hard-to-recover information is precisely which positions of the input are used or skipped. On this template the function is necessarily many-to-one.

Injectivity — the analogue of the classical one-way-permutation question — resists every known technique, for a structural reason: the unique path through a computable tree that has exactly one path is itself computable, so any total computable map admits a partial computable inversion on the set of range points having a unique preimage (Theorem 3.6 of the source paper). Consequently no total computable injection is one-way, and every total computable one-way function is almost nowhere injective (the set of range points with a unique preimage is null). The state of the art is two-to-one (at most two preimages per range point): total computable random-preserving surjections exist that are almost everywhere effectively invertible yet all of whose inversions compute $∅′$ , or that no partial procedure failing to compute $∅′$ inverts with probability one. Partial computable injections that are hard to invert do exist, but only with null domains, which condition (a) excludes. Moreover, under randomness preservation injective maps are provably easier to invert than the known total one-way functions: no partial computable injection remains one-way relative to any oracle $w$ all of whose random reals are $∅′$ -random, while total one-way functions remain one-way relative to every oracle that does not compute $∅′$ . Whether these obstructions are inherent, or an artifact of the selective-permutation template, is exactly what is open.

Problem Statement

Does there exist a partial computable injection $f:\subseteq 2^ω → 2^ω$ that is one-way in Levin's sense? Concretely: either exhibit a partial computable $f$ , injective on its domain, whose domain has positive Lebesgue measure, that is random-preserving (equivalently, $μ(f^{-1}(⟦τ⟧)) = O(2^{-|τ|})$ uniformly in the finite binary string $τ$ ), and such that for every partial computable $g:\subseteq 2^ω × 2^ω → 2^ω$ the set of joins $y⊕r$ such that $g(y,r)$ converges and $f(g(y,r)) = y$ has measure zero; or prove that no such $f$ exists, i.e. that every partial computable, random-preserving injection with positive-measure domain admits a partial computable randomized inversion of positive measure. The total computable case is already settled negatively (every total computable injection has a total computable inverse), so the question concerns exactly the partial case. This is the existence question for one-way injections on the reals left open by Barmpalias–Zhang (2025) and reiterated in their 2026 collision-resistant hash-shuffles follow-up.

References

George Barmpalias, Xiaoyan Zhang. Computable one-way functions on the reals. Information and Computation, 2025. DOI: 10.1016/j.ic.2025.105327; arXiv:2406.15817, https://arxiv.org/abs/2406.15817
Leonid A. Levin. Set Theory in the Foundation of Math; Internal Classes and External Sets (earlier versions titled 'Zermelo-Fraenkel Axioms, Internal Classes, External Sets'). arXiv:2209.07497 (v23, 2026), https://arxiv.org/abs/2209.07497
George Barmpalias, Mingyang Wang, Xiaoyan Zhang. Complexity of inversion of functions on the reals. Mathematical Structures in Computer Science, 2025. DOI: 10.1017/S0960129525100224; arXiv:2412.07592, https://arxiv.org/abs/2412.07592
George Barmpalias, Xiaoyan Zhang. Collision-resistant hash-shuffles on the reals. Information and Computation, 2026. DOI: 10.1016/j.ic.2026.105426; arXiv:2501.02604, https://arxiv.org/abs/2501.02604