1
$\begingroup$

I would like to have a function $F(x, rnd)$, where $rnd$ is a fresh random value, such that it is hard, given $x_0$ and $x_1$, to distinguish $F(x_0, rnd)$ from $F(x_1, rnd)$, EDIT: but the values should be different, i.e., I should be able to recompute the value from $x_0$ and $rnd$ and see that it is the correct value.

I can do this with an asymmetric encryption function that has the IND-CPA property, but in my case, I do not need decryption. Thus, I thought about using a hash function, and my first simple idea was to simple concatenating the randomness, $H(x || rnd)$, but I'm not sure that this is sufficient.

I have looked into keyed hash functions, but I don't really want to use a key, just a random value. I did not really find a "randomized hash function" that would have a property comparable to IND-CPA.

Do I want something else, like a pseudorandom function, for my case? Can I construct one from a hash function?

Thank You for your help.

$\endgroup$
  • 1
    $\begingroup$ I tried to guess what you really wanted in my answer below, but note that in the current formulation of your question, any constant function $F:x\mapsto c$ would work, hence there must be some additional requirement that you omitted; in this case, you should add it to your question. $\endgroup$ – Geoffroy Couteau Apr 5 '18 at 20:34
0
$\begingroup$

Not only is your idea of using $H(x|| r)$ sufficient, it will even in general provide unconditional security, if $H$ satisfies some regularity property, which is (roughly) that the size of the preimage of $H$ with a given prefix $x$ is always approximately of the same size.

To reformulate your question, you are asking whether $H(x || r)$ leads to a hiding commitment scheme, i.e., a scheme com for which it is infeasible to distinguish com$(x_0)$ from com$(x_1)$ given $x_0$ and $x_1$.

If you use any standard hash function which maps long strings to shorter string, observe that there will be in general many preimages to any given output of the hash functions. This means that given a hash value $h$ and strings $x_0$ and $x_1$, there will almost always exist values $r_0,r_1$ such that $H(x_0|| r_0) = H(x_1||r_1) = h$ (and the number of such values should be essentially the same for $x_0$ and $x_1$). This means that it is impossible to find out whether $h$ was obtained by hashing $x_0$ or $x_1$, even if the adversary is computationally unbounded.

If you want more formal details, an improved variant of this scheme was studied in this paper (where they show that their scheme is also binding - i.e., you cannot change your mind about $x$ if you later reveal the input you've fed to the hash function - and obtain a perfectly hiding commitment scheme without even having to assume that $H$ is regular).

$\endgroup$
  • $\begingroup$ Thank you for your answer! I had heard about commitment schemes, and you mentioning them in this context makes a lot of sense. Yes, I would agree your reformulation makes sense. Also, I do want the "binding" part as well, this is what was missing in my question. Thanks for the link to the paper, I will look at it. $\endgroup$ – Sven Hammann Apr 6 '18 at 13:23

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.