Why is information "lost" when it got into a black hole? The black hole information loss paradox is the paradox that information can not be lost, but is lost when it got into a black hole.
But I do not see why it is lost at all.
I see it is no longer accessible, but that is different from being lost. 
I assume information is something local, that a bit is inside a finite volume of spacetime. Also, I assume a black hole is something local, it is inside a finite volume of spacetime.
It seems to me that information is merely "elsewhere" in some sense, but that does not mean it does no longer exist. I understand that lost means "no longer located in the universe". But how does it cease to be in the universe? Do we know, or at least assume it is "destroyed" in some way related to the black hole, or even in some specific way? 
 A: You are correct. Information is not lost when it gets into the black hole, it appears to be lost when that black hole subsequently evaporates via the Hawking radiation. If that radiation is fully thermal, then it cannot contain any of the information from the inside of the black hole, so when there is no black hole left one can ask, where did the information go?
For an informal overview of the paradox and its proposed solutions, have a look at this blogpost. Though it is more than 10 years old, it is a good place to start.
A: The full black hole information paradox is a paradox that involves not just classical physics but also the semiclassical physics of black hole evaporation. But this question is posed completely in the language of classical physics, so it has a classical answer. Once information (say in the form of particles) enters the event horizon of a black hole, it can exist for only a finite proper time before it hits the singularity. In the context of classical GR, all we can really say is that hitting the singularity means that the information is destroyed. Even if you dive in to the black hole in an effort to retrieve the information, you will only succeed if you do it soon enough.
A: In classical physics, there is no black hole information loss paradox: the information is lost, and that's all there is to it. No paradox. (See Ben Crowell's answer.)
The famous "black hole information loss paradox" comes from considering the behavior of quantum fields in the background spacetime of a black hole formed by a collapsing star. That analysis gives us a compelling reason to believe that a black hole eventually evaporates due to Hawking radiation. After it evaporates, presumably nothing is left — no event horizon, no singularity. 
The problem is to explain how the information about everything that fell into the black hole gets back out by the time the black hole is done evaporating. The seemingly-obvious answer is that it comes back out gradually via the Hawking radiation, just like information that was written on a piece of paper and then burned would be encoded (in a practically useless scrambled form) in the light, smoke, and atmospheric molecular motions that are produced by the burning process.
Presumably the information eventually does come back out (in scrambled form) via the radiation, but the challenge is to explain how that happens. The naive analogy with a burning piece of paper doesn't work, at least not as far as we can tell using the standard approximation that was used to derive Hawking radiation in the first place. Luboš Motl's answer to the question
Why isn't black hole information loss this easy (am I missing something basic)?
addresses this very briefly, and several reviews on arxiv.org address it in more depth. One example is [1], which says:

conventional physics implies the Hawking effect to differ fundamentally from familiar thermal emission from hot objects like stars or burning wood. 

The difference (explained more carefully in [1]) is related to the fact that when we burn a piece of wood or paper, the original information ends up being stored in subtle correlations across the resulting light, smoke, atmospheric molecular motions, and so on; but for a black hole, because of the way Hawking radiation works, Hawking-radiation modes that were emitted at different times cannot be correlated with each other in that way, at least not within the approximation that is normally used to derive the radiation in the first place. (The Appendix offers a few comments about that approximation.) 
The black hole information paradox is especially paradoxical because the aforementioned approximation is expected to be adequate during most of the black hole's lifetime, but in the final moments when the approximation is expected to fail, there isn't enough of the black hole left to restore the necessary correlations. In one author's words [2]:

The black hole information paradox forces us into a strange situation: we must find a way to break the semiclassical approximation in a domain where no quantum gravity effects would normally be expected.

Like any paradox, this one will presumably be resolved after we learn how to formulate the problem properly. As noted in the Appendix, this requires using a theory of quantum gravity (but see the Edit at the end), and it is still an active area of current research.

 Appendix: The approximation used to derive Hawking radiation 
Hawking derived Hawking radiation using an approximation that considers the behavior of quantum fields in a prescribed spacetime background. (Most modern reviews derive it essentially the same way.) The prescribed background corresponds to the black hole formed by a collapsing star. This approximation violates the "conservation of energy," because the spacetime background affects the behavior of the quantum fields (leading to Hawking radiation), but the quantum fields don't affect the spacetime background. In particular, the black hole doesn't actually evaporate in this approximation, even though it does radiate. This is acknowledged in [3]:

Hawking's original derivation... considered a quantum scalar field propagating on a fixed [aka prescribed], but dynamic, background space-time corresponding to the formation of a four-dimensional Schwarzschild black hole by the gravitational collapse of matter in asymptotically flat space. 

and in [4]:

As word of his calculation began to spread, Hawking published a simplified version of it in Nature... However, even at this stage Hawking was not certain of the result and so expressed the title as a question, "Black hole explosions?" He noted that the calculation ignored the change in the metric due to the particles created and to quantum fluctuations.

In reality, we expect the influence to go both ways, so that the black hole loses mass as it evaporates. We can (and Hawking did) try to account for the black hole's mass-loss in a kind of "semiclassical" approximation in which we artificially decrease the black hole's mass according to a kind of "average" amount of radiation that it has emitted so far; but that approximation is not self-consistent, as explained in a blog post by Luboš Motl [5]. 
To really understand what happens when a black hole evaporates, we need to use a theory of quantum gravity. Heuristically, if the spacetime metric is influenced by quantum fields, which can form quantum superpositions, then the spacetime metric itself will be forced into quantum superpositions (very heuristically), so we need to use a theory of quantum gravity to really understand what's happening when a black hole evaporates. This is still an active area of research today.

 Edit: I forgot about this... 
In a comment, Dvij Mankad kindly reminded me of another line of research that calls into question the assertion that we need a full theory of quantum gravity to resolve the info-loss paradox. I'm not qualified to review that recent development myself, but it is reviewed in [6]. Here's an excerpt from section 1.4.5, where "IR" (infrared) is slang for "very long wavelength phenomena":

Although I did not start this IR project with black holes in mind, as usual, all roads lead to black holes... The IR structure has important implications for the information paradox... This paradox is intertwined with the deep IR because an infinite number of soft gravitons and soft photons are produced in the process of black hole formation and evaporation. These soft particles carry information with a very low energy cost.


 References: 
[1] Marolf (2017), "The Black Hole information problem: past, present, and future," https://arxiv.org/abs/1703.02143
[2] Mathur (2012), "Black Holes and Beyond," https://arxiv.org/abs/1205.0776
[3] Kanti and Winstanley, (2014),“Hawking Radiation from Higher-Dimensional Black Holes,” https://arxiv.org/abs/1402.3952
[4] Page (2004), "Hawking Radiation and Black Hole Thermodynamics," https://arxiv.org/abs/hep-th/0409024
[5] Luboš Motl (2012), "Why "semiclassical gravity" isn't self-consistent," https://motls.blogspot.com/2012/01/why-semiclassical-gravity-isnt-self.html
[6] Strominger (2017), "Lectures on the Infrared Structure of Gravity and Gauge Theory," http://arxiv.org/abs/1703.05448
A: In layman's terms if information is considered "lost" that implies that one believes they could not reverse-engineer what exactly went in to the black hole.
Why? Because if you can figure out all of the math involved in all equations then you could take the real-time math problem that is existence and reverse calculate what has already happened which in effect would allow you to become partially aware of what will happen.
In example is a comet passes Earth it is not "random" as random is super-natural (e.g. not possible). Given enough energy, resources, technology, time, etc we could ultimately back-trace where that comet originally came from prior to entering our Solar system. So long as the prerequisites are provided at each desired step we could continue to back-trace it's origins far before the point a given object could be referenced in a singular form (e.g. decillions of atoms spread across unfathomable amounts of space which eventually formed that given comet).
Since we as a species are new-borns technologically-speaking we are utterly ignorant about how we might deconstruct the physical properties of a black hole. Does material simply stick to the outer-most point like a magnet to the surface of a refrigerator and remain in place moving only as the black hole occasionally evaporates or is the interior of a black hole like water where (what are ultimately waves) moving around or something we would currently consider exotic?
When waves are sucked in to a black hole we may want to consider if there is any meaningful (in spite of the incredibly small proportions) difference between one wave or another? The other consideration for the possibility of dynamic or "fluid" internal structure (which would complicate information being reverse-engineered) is what effects that the intense conditions may create under the various laws of existence (thermodynamics, physics) that we are not aware of in more traditional and familiar conditions? In example waves heat up as they get sucked around a black hole, does the gravity automatically negate the vibrations of the waves once they are part of the black hole? Would they be considered "almost immeasurable" by what we could now consider utterly exotic levels of technology that we millions of years from now (or other species currently) possess?
Since there is no such thing as random all things are technically predictable since existence is ultimately just a real-time math problem (that so happens to be wildly convoluted). There likely may be a point in our specicie's technological evolution where a more sophisticated problem may exist yet we are not yet aware of the phenomenon to be able to consider that given challenge.
