1
$\begingroup$

We consider a finite field $\mathbb{F}_p$, where $p$ is a large prime e.g. 256-bit.

We have $b$ a fixed element of the field. We encode it as $b'=b||h(b)$, where $h(.)$ is a cryptographic hash function. Assume the output of $h(.)$ is of size 160-bit. We encode that way to distinguish the element $b'$ from a random element $r$ of the field.

So to check if the element has the above structure we do:

(1) Parse the value: $r=r'||r''$, where size of $r''$ is 160-bit.

(2) check: $h(r')\stackrel{?}=r''$


Question1: How can we show/prove that the random element only with a negligible probability can have such structure?

Question2: Can we reduce the $h(.)$ output size to 80-bit (which is not the standard hash function output size) and set $p$ as smaller prime number (e.g. 128-bit )and prove a random value can have the above structure with only negligible probability?

Citing a paper that use/prove such statement would suffice.

$\endgroup$
  • $\begingroup$ Is a proof in the random oracle model sufficient? If so, the proofs seem pretty simple. $\endgroup$ – mikeazo Jun 28 '16 at 13:12
  • $\begingroup$ @mikeazo Yes, please. I can start with that. $\endgroup$ – user153465 Jun 28 '16 at 13:13
  • $\begingroup$ I'm confused, your value $b'$ is 416 bits long. A random field element $r$ will be only 256 bits long. $\endgroup$ – mikeazo Jun 28 '16 at 13:54
  • $\begingroup$ @mikeazo Let me make the output of h(.) of size 80-bit everywhere. $\endgroup$ – user153465 Jun 28 '16 at 13:57
  • 1
    $\begingroup$ Never mind. I think I understand now. You pick some $r'$, such that $r'||h(r')$ is 256 bits. So if the output of $h$ is 160 bits, then $r'$ is 96 bits long. If the output of $h$ is 80 bits, then $r'$ is 176 bits. $\endgroup$ – mikeazo Jun 28 '16 at 14:39
1
$\begingroup$

Question1: How can we show/prove that the random element only with a negligible probability can have such structure?

If we assume the random oracle model and have $h: \{0,1\}^* \to \{0,1\}^n$ then we can state that $h(.)$ is equivalent to randomly sampling from $\{0,1\}^n$. Thus for a random element $r = r'||r''$ the probability that $r$ has the structure $r'' = h(r')$ is $\frac{1}{2^n}$ since all $2^n$ possible outputs of $h(r')$ are equally likely. Thus for $n=160$ we have a probability of $\frac{1}{2^{160}}$ which is negligible.

Question2: Can we reduce the $h(.)$ output size to 80-bit (which is not the standard hash function output size) and set $p$ as smaller prime number (e.g. 128-bit )and prove a random value can have the above structure with only negligible probability?

Sure, the same logic as above can be applied here as well, now with the case $n=80$ and a corresponding probability of $\frac{1}{2^{80}}$ which is still negligible.

Note that the size of $r'$ is not relevant to the probability of a random element having the structure $r'||h(r')$, the probability solely depends on the size of $h(r')$.

$\endgroup$
  • $\begingroup$ Thank you for the answer. I have another question, if you don't mind.: What if value $r$ is not a uniformly random element of the field. In other words, can the answer apply to the case where $r$ is a fixed value. $\endgroup$ – user153465 Jun 29 '16 at 9:23
  • $\begingroup$ Sure, we can choose any element $r \in \mathbb{F}_p$ and this inequality holds. $\endgroup$ – puzzlepalace Jun 29 '16 at 16:09
  • $\begingroup$ Do we also need to take the collision probability into account? I mean, what would happen if two elements have the same hash value. $\endgroup$ – user153465 Jul 17 '16 at 11:03
  • $\begingroup$ I fail to see how collision probability applies. Even if other elements have the same hash as $r'$ this doesn't change the probability of a randomly sampled value $r'||r''$ having $r'' = h(r')$. $\endgroup$ – puzzlepalace Jul 18 '16 at 3:26

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.