In trying to understand the significance of the black hole information paradox: regardless of what happens to information inside a black hole; how come it cannot, in principle, be reconstructed by observing the totality of information outside the black hole?
I.e. by asking what is now missing in the universe, and what imprint did it leave?
(I've seen versions of this question posed before, notably here, but the answer given seems a bit ambiguous to me.)
I'll first give an anecdote exemplifying the issue, and later I'll give the problem in more technical terms. I'm doing it like this because I'm not sure of what pieces of Physics you are acquainted with.
Let us suppose that, at some point in time, apart from the black hole and Hawking radiation there are only two things in the Universe: a blue ball and a red ball. At some time they collide and the red ball ends up falling into the black hole. The blue ball bounced off and moved far away. Due to the initial conditions of the balls and the way they hit each other, it had enough energy to escape from the black hole at least until it evaporates completely.
Once the black hole evaporates, what is the state of the Universe? One has the Hawking radiation, which keeps no information, and the blue ball. From this alone, there is no way of knowing there ever was a red ball. Hawking radiation won't come out red (a black hole is completely determined only by its mass, charge, and angular momentum) and one won't be able to distinguish whether the blue ball was moving around freely since the beginning or if it bounced off something. In this sense, one does not have enough information to reconstruct what happened in the past.
A way of thinking about the problem is that by trying to observe what is lacking, there is more than one possibility. Even if you were able to determine there was another ball (perhaps the blue ball would have crossed the black hole if it was moving forever), you'd have no way of determining the other ball was red rather than green, because all of the information that the black hole could possibly imprint on the Hawking radiation is its mass, charge, and angular momentum. Anything else is destroyed in the process.
OP pointed out in the comments that for "redness" to make sense, light needs to exist, and hence one could hunt down the red photons scattered by the ball. I agree, but that is a failure of my anecdote, not of the argument for information loss. I think a way around it could be to say the ball is red on the inside, so the photons that hit it can't really escape, but I'll try to give another example.
This time, let us think only about the star that collapses to the black hole. There is no need for anything else, but it's perfectly fine if other things exist. The star collapses, the black hole forms, it radiates, evaporates, and vanishes. After all of this has happened, I ask you: was the star made of matter or antimatter?
The difference is pretty much on the baryon number of the star. This quantity is not associated with any long range interactions (charge is associated with electromagnetism, for example, but baryon number isn't associated with anything) and hence one can't detect it outside of the black hole. Once the black hole evaporates, it will leave no clue on whether the star that originated it was made of matter or antimatter. Hence, we have information loss.
Let me point in advance that it might happen that I'm missing some detail of this anecdote, but the mathematical argument is way more solid. It has a very clear interpretation and issue with no margin for doubt, but it is particularly difficult to replicate it without diving into too much math. In the real case, there is information that will leave no imprint behind.
In physical terms, one starts with a quantum field in some pure state $\rho$ across spacetime. However, the Hilbert space can be split in $\mathcal{H}_{\text{BH}} \otimes \mathcal{H}_{\text{out}}$, representing the black hole and the outside world. What is available to an outside observer is given by $$\rho_{\text{out}} = \mathrm{Tr}_{\text{BH}}[\rho],$$ which is a mixed state (it is a thermal state at the Hawking temperature). Once the black hole evaporates, all that is left of $\rho$ is $\rho_{\text{out}}$, meaning a pure state evolved to a mixed state. Hence, there is loss of quantum coherence.
There is no information lost. Only the material particles inside the hole which the information is about.
A bike fall in the hole. The complete state of the bike, from entering until evaporation, is entangled with the virtual particle states just above the horizon. All positions and momenta get entangled, like quantum numbers.
The strong curvature pulls the negative energy solutions and positive energy solutions of the virtual particles away from each other. The negative energy particles annihilate their positive energy counterparts inside, while the positive energy particles annihilate each other and send the inside information in photonic form into the universe.
So, the hole is gone and the information flows into the universe. There is a direct, unitary link to the particles that resided in the hole.
If you fall in, the information of your last state is radiated away in the blink of an eye. Seen from faraway on the outside it takes many years.
This information is not present in the universe surrounding the hole as you imagine. There is no way you could calculate the last state of the bike, i.e., when it falls in. You would know it's missing but to calculate the last positions and momenta you have to take its whole history into consideration, which amounts to a substantial part of the universe including yourself. And that's impossible. If you measured all positions and momenta of the bike before falling in, on a safe height above the hole, you would expect to calculate and project its state into the future. So, in that case, wasn't the information projected into the surroundings? Well, knowing how a particle behaves exactly is different information. It's not information that would affect the universe around the hole so you could still see the bike by looking at the hole.
