# Finite One-Way Permutation with Infinite Domain

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.

• Can't we finitely describe $D$? There exists a finite algorithm searching for a smallest Blum number bigger than some input number, so computing $\pi(x)$ could be described for example as "find the smallest Blum number $b$ bigger than $x$, then compute $\pi_b(x)$". Still, it's not obvious to me that the function you will get by glueing together some infinite number of $\pi_b$'s will necessarily be a permutation. Could you explain? – Karolina Sołtys Nov 6 '10 at 9:50
• @Karolina: Thanks for the response. I think the algorithm "find the smallest Blum number $b$ bigger than $x$, then compute $\pi_b(x)$" will necessarily exhibit extra info about $b$, such as its factorization. Therefore, such algorithm cannot be used to describe one-way permutations. Do you agree? – M.S. Dousti Nov 6 '10 at 10:46
• Ok, I think I get it - you want the finite description to describe the function in an easy to compute way. I think we could encode the "find the smallest Blum number..." part without disclosing any info about $b$ (just implement the brute-force search for $b$), but then it wouldn't be efficiently computable. – Karolina Sołtys Nov 6 '10 at 13:43
• Maybe this question will help with ideas: cstheory.stackexchange.com/questions/1378 – Matt Groff Nov 8 '10 at 7:20
• @Matt: Thanks. In that question, the condition "easy to compute but hard to invert" is not with respect to poly-time bounded machines. – M.S. Dousti Nov 8 '10 at 9:57

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.