10
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Karolina Sołtys Nov 6 '10 at 9:50
  • $\begingroup$ @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? $\endgroup$ – M.S. Dousti Nov 6 '10 at 10:46
  • $\begingroup$ 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. $\endgroup$ – Karolina Sołtys Nov 6 '10 at 13:43
  • $\begingroup$ Maybe this question will help with ideas: cstheory.stackexchange.com/questions/1378 $\endgroup$ – Matt Groff Nov 8 '10 at 7:20
  • $\begingroup$ @Matt: Thanks. In that question, the condition "easy to compute but hard to invert" is not with respect to poly-time bounded machines. $\endgroup$ – M.S. Dousti Nov 8 '10 at 9:57
14
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Thanks Alon for your excellent answer. Off-topic: I'm very happy to see you here. I love your book & papers on concurrent zero-knowledge! $\endgroup$ – M.S. Dousti Nov 10 '10 at 14:09
  • $\begingroup$ Thans, Sadeq. Glad to hear that you like it :-) $\endgroup$ – Alon Rosen Nov 12 '10 at 10:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.