<p>The paper <a href="http://www.wisdom.weizmann.ac.il/~oded/PS/gln.ps">On constructing 1-1 One-Way Functions</a>, 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. </p>

<p>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$). </p>

<p>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.</p>

CC BY-SA 2.5
2010-11-10T14:09:19.700Z
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**!
Sadeq Dousti
CC BY-SA 2.5
2010-11-12T10:46:24.897Z
Thans, Sadeq. Glad to hear that you like it :-)
Alon Rosen
CC BY-SA 2.5
2010-11-10T07:03:05.060Z
2010-11-10T14:04:45.070Z
2010-11-10T14:04:45.070Z
Alon Rosen
<p>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 <strong>description</strong>, I mean a program that describes $\pi$'s functionality. (As in Kolmogorov complexity.) See explanations below.</p>

<p>For instance, the NOT function is one such permutation:</p>

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

<p>$\pi_k(\cdot)$, defined below, is another case:</p>

<pre>
function pi_k(x)
    return x + k (mod 2^|x|)
</pre>

<p>My question is about a special class of permutations, called <a href="http://en.wikipedia.org/wiki/One-way_function#Related_concepts" rel="nofollow">one-way permutations</a>. Informally speaking, these are permutations which are easy to compute, but hard to invert (for a $\rm{BPP}$ machine). The mere <strong>existence</strong> 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.</p>

<p>As an example of a conjectured one-way permutation, one can consider the <a href="http://en.wikipedia.org/wiki/RSA" rel="nofollow">RSA</a>: Let $n = pq$ be a <a href="http://en.wikipedia.org/wiki/Blum_integer" rel="nofollow">Blum integer</a>, and let $e = 65537$.
The one-way permutation is defined by: 
$\pi_n(x) = x^e \bmod n$.</p>

<p>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 <strong>family</strong> 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.</p>

<p>My question is (assuming the existence of one-way permutations):</p>

<blockquote>
  <p>Does there exist <strong>finite-description</strong> one-way permutations over an <strong>infinite domain</strong>?</p>
</blockquote>

<p>The answer may vary: It can be positive, negative, or open (either <em>likely to be positive</em>, or <em>likely to be negative</em>).</p>

<h3>Background</h3>

<p>The question arose when I was reading an <a href="http://asiacrypt2009.cipher.risk.tsukuba.ac.jp/" rel="nofollow">ASIACRYPT 2009</a> paper. There, the author <strong>implicitly</strong> (and in the context of some proof) assumed that such one-way permutations exist.</p>

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

CC BY-SA 2.5
2010-11-10T07:18:40.243Z
@Sadeq: Perhaps I am missing something, but why can you not simply apply RSA (or any other public-key system) blockwise along the input? Sure this will leak an upper bound on the size of the input, but that seems unavoidable.
Joe Fitzsimons
CC BY-SA 2.5
2010-11-10T13:38:53.153Z
@Joe: Assume that 4096-bit RSA is applied on 4096-bit blocks of data. Then, there exists a polynomial-time bounded adversary that can invert this version of RSA: This is because there exists some positive $c$, such that for large enough $n$, $2^{4096} < n^c$.
Sadeq Dousti
CC BY-SA 2.5
2010-11-10T13:48:40.193Z
@Sadeq: So do you want the security to scale with the length of the input, or rather to be an independent parameter which can be adjusted. If the latter, surely you can simply vary the block size and RSA key length with the security parameter.
Joe Fitzsimons
CC BY-SA 2.5
2010-11-10T13:57:30.913Z
@Joe: As you put it, I want it to scale. In formal words, I want it to be one-way, as defined [here](http://www.nowpublishers.com/product.aspx?product=TCS&doi=0400000001&section=x1-7r2) by Goldreich.
Sadeq Dousti
CC BY-SA 2.5
2010-11-06T09:50:09.497Z
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
CC BY-SA 2.5
2010-11-06T10:46:13.030Z
@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?
Sadeq Dousti
CC BY-SA 2.5
2010-11-06T13:43:48.613Z
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
CC BY-SA 2.5
2010-11-08T07:20:30.393Z
Maybe this question will help with ideas: http://cstheory.stackexchange.com/questions/1378
Matt Groff
CC BY-SA 2.5
2010-11-08T09:57:41.880Z
@Matt: Thanks. In that question, the condition "easy to compute but hard to invert" is not with respect to poly-time bounded machines.
Sadeq Dousti
<cc.complexity-theory><co.combinatorics><cr.crypto-security><descriptive-complexity><one-way-function>
Finite One-Way Permutation with Infinite Domain
Sadeq Dousti
# Finite One-Way Permutation with Infinite Domain

(Asked by: username_0 on 2010-11-06)

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.

**Tags:** cc.complexity-theory, co.combinatorics, cr.crypto-security, descriptive-complexity, one-way-function

> **Comments:**
> **username_2**: 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?  
> **username_0**: @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?  
> **username_2**: 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.  
> **username_3**: Maybe this question will help with ideas: http://cstheory.stackexchange.com/questions/1378  
> **username_0**: @Matt: Thanks. In that question, the condition "easy to compute but hard to invert" is not with respect to poly-time bounded machines.  
> **username_1**: @Sadeq: Perhaps I am missing something, but why can you not simply apply RSA (or any other public-key system) blockwise along the input? Sure this will leak an upper bound on the size of the input, but that seems unavoidable.  
> **username_0**: @Joe: Assume that 4096-bit RSA is applied on 4096-bit blocks of data. Then, there exists a polynomial-time bounded adversary that can invert this version of RSA: This is because there exists some positive $c$, such that for large enough $n$, $2^{4096} < n^c$.  
> **username_1**: @Sadeq: So do you want the security to scale with the length of the input, or rather to be an independent parameter which can be adjusted. If the latter, surely you can simply vary the block size and RSA key length with the security parameter.  
> **username_0**: @Joe: As you put it, I want it to scale. In formal words, I want it to be one-way, as defined [here](http://www.nowpublishers.com/product.aspx?product=TCS&doi=0400000001&section=x1-7r2) by Goldreich.  

---

## 1 answers

### Answer by username_4 on 2010-11-10. Score: 14 | Accepted answer

The paper [On constructing 1-1 One-Way Functions](http://www.wisdom.weizmann.ac.il/~oded/PS/gln.ps), 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.

> **Comments:**
> **username_0**: 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**!  
> **username_4**: Thans, Sadeq. Glad to hear that you like it :-)  

---

