1
$\begingroup$

Function $f$ is a length shortening function. It reduces to log of size of input, i.e $|f(x)|/\log(|x|) \leq$ $a\ positive\ constant$. Is this a one way function?

Edit: $f$ is any function. Unknown definition, only constraint on the ratio being constant for all $x$

$\endgroup$
  • 1
    $\begingroup$ Can you provide us with your definition of "one way function"? $\endgroup$ – mikeazo Sep 22 '17 at 17:32
  • $\begingroup$ The definition of one-way function is the strict one-way function. That it is easy to compute, hard to invert (the probability that a valid pre-image is found is negligible). $\endgroup$ – crypto_geek Sep 22 '17 at 18:49
1
$\begingroup$

While the current answer to your question is technically correct, it does not really answer your issue, and the comment added by its author is incorrect: one can prove, in fact, that any function $f$ satisfying the requirements that you give cannot be one-way.

Let $f$ be a function such that for all $x$ in its domain, $|f(x)|/\log(|x|) \leq c$, where $c$ is some fixed constant. Consider the following trivial inversion algorithm for $f$: on any input $y$, it returns $x'$, where $x'$ is a fixed input to $f$, initially drawn uniformly at random from the domain of $f$.

I claim that this algorithm inverts $f$ on random inputs with non-negligible probability. Here is a sketch of the proof: let $D$ be the domain of $f$, and $I$ be its image. It is easy to see that, on a random choice of a pair of inputs $(x_0,x_1)$ from $D^2$, the probability of $f(x_0) = f(x_1)$ is bounded below by $1/|I|$ (that is, one over the number of elements in $I$).

Consider a challenger that picks a random $x\in D$, computes $y\gets f(x)$, and sends $y$; the goal is to find a valid preimage of $y$ with non-negligible probability. By my previous remark, as $x'$ was picked at random over $D$, the probability that $f(x') = y$ is at least $1/|I|$. Let $n$ be the maximum size of an element in $D$ (we can think of $n$ as the security parameter); then, all elements in $I$ have size bounded by $c\cdot\log n$. Therefore, the number of elements in $I$ is bounded above by $2^{c\log n} = n^c$, which implies that $1/|I| = 1/n^c$ is non-negligible, hence our inverter succeeds with non-negligible probability, implying that $f$ cannot be one-way.

EDIT: let me elaborate a bit on the following statement: the probability of having $f(x) = f(x')$, when drawing $(x,x')$ at random from the domain of $f$, is bounded above by $1/|I|$. Let $t = |I|$; let us consider an enumeration $\{y_1, \ldots, y_t\}$ of the elements of $I$ in any fixed order. Let $p_i$ be the probability that $f(x)=y_i$ over a random choice of $x$. Then, over random independent choices of $(x,x')$ from $D$, we have

$\mathsf{Pr}[f(x)=f(x')] = \sum_{i=1}^t \mathsf{Pr}[f(x)=y_i]\cdot \mathsf{Pr}[f(x')=y_i\text{ }|\text{ } f(x)=y_i]$

$= \sum_{i=1}^t \mathsf{Pr}[f(x)=y_i]\cdot \mathsf{Pr}[f(x')=y_i]$ as the events are independent

$= \sum_{i=1}^t p_i^2$. We now that the sum of squares of the $p_i$, subject to the constraint $\sum_i p_i = 1$, is minimized when the $p_i$ are all equal, id est $\forall i, p_i = 1/t$. Therefore,

$\sum_{i=1}^t p_i^2 \leq \sum_{i=1}^t 1/t^2 = 1/t$, which gives the desired bound.

$\endgroup$
  • $\begingroup$ Can you elaborate on why the probability is bounded below by (size of range)^{-1}? $\endgroup$ – crypto_geek Sep 24 '17 at 1:01
  • $\begingroup$ I'm not sure using the input size rather than output size for security paramater is a reasonable definition. Defining the other way was the basis of my comment. $\endgroup$ – Meir Maor Sep 24 '17 at 3:07
  • $\begingroup$ Quite on the contrary, using the input size as the security parameter is the standard definition. A polynomial time algorithm runs by definition in time polynomial in its input size. Inversion algorithms in the formal definition of OWF are given the security parameter (in unary) as input; the reason for this choice is exactly that you want it to run in time polynomial in the size of the inputs to the OWF, not only in time polynomial in the size of its outputs (although they are inputs to the inverter), see e.g. Wikipedia. @Anirudh Narayan: I'll elaborate when I have a few minuts :) $\endgroup$ – Geoffroy Couteau Sep 24 '17 at 7:20
  • $\begingroup$ @AnirudhNarayan: I edited my post to answer your request :) $\endgroup$ – Geoffroy Couteau Sep 24 '17 at 9:51
2
$\begingroup$

F(x) = 1 matches your requirement and obviously isn't one way. It is trivial to find a pre image for this function as any value is a pre image of 1. One way function doesn't mean it's hard to find the original value. It means it's hard to find any pre image which leads to the requested output value. Finding the original value of a compression function is obviously impossible to do with high confidence if the original data is chosen uniformly. This for information reasons regardless of computing power.

$\endgroup$
  • $\begingroup$ What if $f$ is any arbitrary function such that the ratio is the same constant for all $x$? $\endgroup$ – crypto_geek Sep 22 '17 at 18:55
  • $\begingroup$ If f is an arbitrary function, it may or may not be one way. I gave an example of a simple construction which isn't one way. Thus disproving the proposed claim that all compression functions are one way. I can not providing an example in the other direction of a proveably one way function as the existence of such functions is an open question. $\endgroup$ – Meir Maor Sep 23 '17 at 4:09
  • $\begingroup$ Yes I agree. This is correct. I was hoping for a proof of impossibility, if that is the case, in the general sense. $\endgroup$ – crypto_geek Sep 24 '17 at 0:36

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.