We propose new methodologies for the authentication of RFID tags along supply chains, exploiting tags equipped with a Physical Unclonable Function (PUF) device. Unlike state-of-the-art approaches that require sharing a large database of challenge-response pairs (CRPs), we achieve a constant amount of shared secret data, oblivious of the number of CRPs and tags to be handled. Such data can be distributed using a secure hardware token. The rest of the data can be released over an insecure one-way communication channel that can be realized by shipping storage media along with goods. We discuss the applicative scenario and perform experiments on pre-production PUF-based tags in order to assess the applicability of our approaches.