So then the original Picasso is known to be original because it was signed by its creator, whose key is known? How is that key verified initially?
It gets more complicated later: experts assess the credibility of the painting by examining the ownership history, if available, the signature on the painting, the quality of the work, chemical properties of the pigments and canvas, etc. They sometimes get it wrong, though (cf. Beltracchi!). It's more a probability that a work is genuine, rather than a 100% certainty.