The entirety of physics is based on information. Physicists use information about the past or present to predict what will happen in the future or what has happened in the past. Information can be anything from a chemical formula to a velocity to a number of particles. A fundamental law of physics is that information is neither created nor destroyed - if it was, the predictions could not function, because the information they use to predict would not remain constant. The idea of Hawking radiation escaping a black hole creates the information paradox. When objects fall into black holes, their information cannot be released out into the world, because nothing can escape the event horizon of a black hole, so presumably, the information must be contained within the black hole. However, Hawking radiation establishes that black holes slowly lose mass in the form of radiation. This Hawking radiation is pure heat and is produced in the same way regardless of what falls into the black hole. Eventually, the black hole will disappear due to losing all its mass from Hawking radiation, and the information the black hole contained will disappear with it. The information could never have escaped the black hole, is not released with Hawking radiation (because the radiation is completely thermal), and is no longer in the black hole when it disappears. The only solution seems to be that the information has been destroyed, which violates the basic laws of physics - this is the information paradox.
Many theories exist to solve the information paradox. Hawking radiation is not well understood, and it's possible that the information escapes with this radiation in a way physicists just don't understand yet. Perhaps, the underlying assumption that no information can be destroyed is simply incorrect, and our understanding of physics is flawed. Many times in history have scientists been majorly wrong, and this could be one of those cases. Additionally, the concept of black holes as a wormhole to another Universe could solve the paradox, because the information could be transported and released into an alternate universe through the black hole.
[P1] Information can never be destroyed. [P2] When objects fall into a black hole, their information is contained within it. [P3] Black holes are slowly destroyed by Hawking radiation, and the information is destroyed along with them. [P4] Since the information is destroyed, but information can never be destroyed, it creates a paradox.
Rejecting the premises
[Rejecting P1] Information can be destroyed. [Rejecting P3] The information is not actually destroyed with the black holes.