Can a former employer withhold proof of credentials I obtained while working for them?

As a general rule, Qualifications are bound to the individual. As mentioned in the comments - If the certifications were provided and managed by a 3rd party, then you should be able to contact said 3rd party and get copies.

I've had to do this with my Microsoft certifications when I have changed companies: As I have to use my MS ID that the Certs are bound to pretty much only when I change jobs, by which time I've forgotten everything.

You may need to provide some identity documentation to prove it is you in order to get copies, but that shouldn't be a big issue (normally just photo ID is fine)

As for the Company withholding - I feel this is a bit of a petty move on behalf of the company, there may be recourse available via the 3rd party (e.g. you want to make sure they aren't holding onto the physical copies to try and commit Fraud) - you could raise your concern with the certification authority that you are worried that by holding onto your certs, that they will attempt to backfill your position with someone who isn't qualified and use your certs to pretend they are.

However - if that is true, that would be a civil matter or a matter to be negotiated between the 3rd party and the company.