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.

Improve this question
$\endgroup$
6
  • $\begingroup$ Is a proof in the random oracle model sufficient? If so, the proofs seem pretty simple. $\endgroup$
    – mikeazo
    Jun 28, 2016 at 13:12
  • $\begingroup$ @mikeazo Yes, please. I can start with that. $\endgroup$
    – user153465
    Jun 28, 2016 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, 2016 at 13:54
  • $\begingroup$ @mikeazo Let me make the output of h(.) of size 80-bit everywhere. $\endgroup$
    – user153465
    Jun 28, 2016 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, 2016 at 14:39

1 Answer 1

Reset to default
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')$.

Improve this answer
$\endgroup$
4
  • $\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, 2016 at 9:23
  • $\begingroup$ Sure, we can choose any element $r \in \mathbb{F}_p$ and this inequality holds. $\endgroup$
    – puzzlepalace
    Jun 29, 2016 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, 2016 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, 2016 at 3:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.