Finite One-Way Permutation with Infinite Domain

Question

Let $\pi \colon \{0,1\}^* \to \{0,1\}^*$ be a permutation. Note that while $\pi$ acts on an infinite domain, its description might be finite. By description, I mean a program that describes $\pi$'s functionality. (As in Kolmogorov complexity.) See explanations below.

For instance, the NOT function is one such permutation:

function NOT(x)
    Let y = x
    For i=1 to |x|
        Flip the ith bit of y
    return y

$\pi_k(\cdot)$, defined below, is another case:

function pi_k(x)
    return x + k (mod 2^|x|)

My question is about a special class of permutations, called one-way permutations. Informally speaking, these are permutations which are easy to compute, but hard to invert (for a $\rm{BPP}$ machine). The mere existence of one-way permutations is a long-standing open problem in cryptography and complexity theory, yet in the remainder, we will assume that they exist.

As an example of a conjectured one-way permutation, one can consider the RSA: Let $n = pq$ be a Blum integer, and let $e = 65537$. The one-way permutation is defined by: $\pi_n(x) = x^e \bmod n$.

Note that RSA is defined over the finite domain $\mathbb{Z}_n$. In fact, to obtain an infinite domain permutation, one has to consider a family of RSA permutations $\{\pi_n\}_{n\in D}$, where $D$ is an infinite set of Blum integers. Note that $D$ is the description of the family, and by definition, it is infinite.

My question is (assuming the existence of one-way permutations):

Does there exist finite-description one-way permutations over an infinite domain?

The answer may vary: It can be positive, negative, or open (either likely to be positive, or likely to be negative).

Background

The question arose when I was reading an ASIACRYPT 2009 paper. There, the author implicitly (and in the context of some proof) assumed that such one-way permutations exist.

I'll be happy if this is indeed the case, though I couldn't find a proof.

Answer 1

The paper On constructing 1-1 One-Way Functions, by Goldreich, Levin and Nisan shows how to construct length preserving 1-1 functions with infinite domains and finite description. The hardness of inverting the functions is based on popular assumptions, such as hardness of inverting RSA or finding Discrete Logarithms.

Their construction is a twist of the straightforward idea of converting a family, $\{f_i\}_i$, of one-way functions into a single one-way function by setting $f(r,s) = f_i(x)$ where $r$ is the randomness used to pick the index $i$ and $s$ is the randomness used to select the input $x$ (given the index $i$).

The problem with the above idea is that $f(r,s)$ is not necessarily 1-1. They amend this problem by slightly modifying $f(r,s)$ and arguing that, under certain conditions on the family $\{f_i\}_i$, the new construction is indeed 1-1. They then go on to show that these conditions are satisfies by the RSA/Discrete-log based functions.