I would not rely on certificates of authenticity unless I also had a supplier audit to back it up. In my opinion, you need to conduct an (annual) audit of the supplier and determine that he is doing the same of his suppliers.
For example, if you are using a multi-layer poly packing bag or on-line sealer system, you need to have test data for the material lots to assure that the layers exist and are doing their jobs. There are standard industry tests for this (gas permeability, and so forth). If it's printed material, you also need to assure the printing is properly cured in the production process and testing is performed. You should also check that the supplier is assuring his raw material sources are giving him what they say they are. That includes the layers and the printing materials. Everything must be to the proper (food) grade and produced on equipment suited to the purpose (as Setanta suggests).
Because it's difficult to tell one multilayer product from another, you may need to rely on a third-party testing expert. There are certain unscrupulous suppliers that make changes without your approval. So, be sure your terms and conditions specify that no changes may occur without a management of change that includes your company's agreement.
I could go on and on. But, it would be a good practice to perform a what-if analysis on your supply chain first. From that, determine the most likely places where something can go wrong. Prioritize them and attack them.
Also, there are plenty of great audit schemes out there. This organization as well as IPEC have great documents and guidance for it.
I hope this helps!
Regards,
Mike