0
$\begingroup$

I am looking for a one way function that can generate outputs deterministically. However, revealing any of the inputs dont allow the person to generate other inputs.

E.g:
lets say we have a list of inputs: $i_{1},i_{2},i_{3},...$ that look completely random and a list of corresponding outputs: $o_{1},o_{2},o_{3},...$ that also look completely random which are each mapped by one way functions: $f_{1},f_{2},f_{3},...$
These outputs can be generated without knowing the inputs so anyone should be able to deterministically generate the outputs (perhaps by knowing a public shared data which is used in the function). But if one of these inputs is revealed, it should not reveal the other inputs.
If it is not mathematically possible, I need a proof for it.

$\endgroup$
1
$\begingroup$

"public shared data" $\:$ = $\:$ the ordered pair whose entries are
[a key for a full-domain statistically injective PRF] and [a signature verification key]

$\hspace{.04 in}f$ is an arbitrary one-way function.
For each positive integer $j$, [$o_j$ is the value of the PRF at $j\hspace{.03 in}$] and [$i_j$ is [[the signature for $o_j$] concatenated with [the string of zeros whose length equals the length of that signature]]]
and $\hspace{.04 in}f_j$ is given by
if $\hspace{.04 in}f_j$'s input has even length and its left half is a valid signature for $o_j$
and its right half is all-zero then output $o_j$ else output $\hspace{.04 in}f$ of $\hspace{.04 in}f_j$'s input.

|improve this answer|||||
$\endgroup$
  • $\begingroup$ Why should the inputs left half be all zero? You said the input is the signature for $j$? $\endgroup$ – abeikverdi Apr 23 '15 at 9:31
  • $\begingroup$ And how can someone generate the next output? He/she needs the signature of $j$. So if the key owner doesn't sign the next input $j$, the next output can not be calculated. $\endgroup$ – abeikverdi Apr 23 '15 at 9:34
  • $\begingroup$ The inputs' left half being all zero is a way to make sure that the $\hspace{.04 in}f_j$s are one-way. $\;$ $\endgroup$ – user991 Apr 23 '15 at 9:35
  • $\begingroup$ $o_j = j {}{}\;$ $\endgroup$ – user991 Apr 23 '15 at 9:35
  • $\begingroup$ umm.. interesting! but now the outputs are not random then. They are like 1,2,3,.. $\endgroup$ – abeikverdi Apr 23 '15 at 9:40

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.