Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

In this paper the term "simultaneously hardcore" is defined as:

"We say that a block of bits of $x$ are simultaneously hard-core for a one-way function $f(x)$, if given $f(x)$ they cannot be distinguished from a random string of the same length."

Could somebody give me an example of something that is simultaneously hardcore and something that is not?

Also, what does it mean to be hardcore vs. simultaneously hardcore ? Is it possible to be hardcore but not at the same time?

This terminology is quite confusing and I would really appreciate it if somebody could break it down to concrete, simple examples.

share|improve this question
add comment

1 Answer 1

up vote 3 down vote accepted

Hard-core bits are related to one-way functions.

For some intuition on what hard-core bits are, consider a one-way function $f$. SInce it's a one-way function, it's hard to invert: that is, if I select a random $x$ in the function's domain and give you $f(x)$, you cannot find a $x'$ such that $f(x) = f(x')$ with non-negligible probability in probabilistic polynomial time (this is the definition of a one-way function).

So, intuitively, there is "something" about $x$ that is hidden from you in $f(x)$. If you knew everything about $x$ from $f(x)$, you would know what $x$ was. So, there is something that $f$ hides about its input. That something is a "hard-core predicate".

A hard-core predicate is itself a function. Let's say we have a hard-core predicate for $f$ called $\mathsf{hc}$. Since it's a predicate, $\mathsf{hc}$ returns exactly one bit. So, given $f(x)$, you cannot determine the value of $\mathsf{hc}(x)$ with non-negligible probability (over $1/2$, which you can always get by guessing) in probabilistic polynomial time. In essence, $\mathsf{hc}(x)$ represents something about $x$ that you do not know given $f(x)$ — that is, $\mathsf{hc}$ is a bit related to the input that $f$ hides from you. Another way of looking at it is that $\mathsf{hc}(x)$ is indistinguishable from random (in PPT and all that business). To see this, consider if you were given $f(x)$ and $\mathsf{hc}(x)$. Since you cannot compute $\mathsf{hc}(x)$ from $f(x)$, by definition, you should not be able to distinguish it from a random bit.

Note that a hard-core predicate is a single bit. Instead of a single bit, the paper wishes to talk about multiple different bits each being hard-core simultaneously. So, simultaneously-hardcore bits are a natural extension of hard-core predicates into strings that are multiple bits in length. To be explicit, let $h$ be a hard-core function for $f$. Then, given $f(x)$ for a random $x$ in $f$'s domain, an adversary cannot compute $h(x)$ in PPT. The paper you've linked frames $h$ as being indistinguishable from random, which is equivalent.

share|improve this answer
    
This was very helpful. Thank you. Do you know of any examples of either h(x) or hc(x) ? I would really like to see examples of how these functions looks like. I'm really curious to know what makes them so special. –  user1068636 Sep 19 '13 at 1:38
    
@user1068636: Actually, I've just spotted this answer by Thomas Pornin which goes into more depth, including some examples. –  Reid Sep 19 '13 at 1:43
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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