3
$\begingroup$

Consider a function $$f: \{0,1\}^n \rightarrow \{0,1\}^{poly(n)} $$

with the following properties:

  • hard to invert, i.e. given $f(x)$, hard to find $x$
  • hard to find a collision, i.e given $f(x)$, hard to find $x'$, such that $f(x') = f(x)$
  • indistinguishable from a random number i.e given $f(x)$ and $y \stackrel{R}{\leftarrow} \{0,1\}^{|f(x)|}$, hard to distinguish w.p. $>1/2$

So, what is the generic name for this type of functions?

(I could model them as them as ideal hash functions, if i did not have the requirement of $|f(x)| = poly(x)$, but with that requirement, is there a 'expansion function' for hashes? or Does PRGs have pre-image resistant property? or OWFs that satisfy the property of indistinguishability?)

| improve this question | |
$\endgroup$
  • $\begingroup$ Maybe you should elaborate, what you mean with $poly(n)$. Either I don't understand it, or it simply makes no sense. $\endgroup$ – tylo Feb 10 '15 at 11:33
  • $\begingroup$ Does $poly(n)$ need to be significantly larger than $n$? $\:$ (as opposed to that merely being allowed $\hspace{-0.04 in}$) $\hspace{.52 in}$ $\endgroup$ – user991 Feb 10 '15 at 11:50
  • $\begingroup$ @tylo By $poly(n)$, i.e. polynomial in the length of $n$ I mean upper bounded by $c_1 n^{c_2}$, where $c_1$ and $c_2$ are constants. $\endgroup$ – Subhayan Feb 10 '15 at 16:03
1
$\begingroup$

I presume you are referring to hardcore, one-way functions (OWF's) with polynomial span?

There have been a flurry of publications in the past 12 months relating to these functions and their implied possibility or practicability. The challenge with hardcore predicates has been in achieving polynomial span...

Bellare

"The original conjecture by Goldreich and Levin only provided a hardcore predicate, meaning span one, and by extension logarithmic span."

Bellare gave a construction achieving polynomial hardcore predicate span for any OWF (injective or not) with polynomially bounded pre-image size (PPS), along with an added assumption of input obfuscation (iO). Garg countered with an example of an arbitrary (?) OWF which does not yield hardcore bits, either with or without auxilliary inputs. So in summary, there are competing claims as to the plausibility of OWF's with auxilliary input obfuscation.

If you are thinking more along the lines of iterative permutations or perfect hashing functions, you may find the specific characteristics of your definition are more completely addressed in an outline of my own algorithm, via my website:

  • unitambo.files.wordpress.com/2014/05/one-way-function1.pdf
    (A more polished paper is pending.)

So, in answer to your question. The correct-est term I guess, would be; polynomial span, one-way functions with auxilliary input obfuscation.

| improve this answer | |
$\endgroup$

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.