A prestashop store I host started throwing the error “Link to database cannot be established: SQLSTATE[HY000]  The server requested authentication method unknown to the client” and the site was offline. Searching the internet gave me solutions that involved a full reinstallation and then copying back previously backed up files etc etc which all seemed too complex.
the fix for me was to add a new database user via my hosts control panel and using a long complex password. I then updated the /config/settings.inc.php file to match and everything was going again. I think this was caused by an update to the mysql version my host was using. I hope this helps others.