What does it mean to be simultaneously hardcore?

Question

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.

Answer 1

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.