Installation error: The server requested authentication method unknown to the client

Hi,

I’m trying to install NextCloud 13.0.5 on my website.
This is not my own server, but just a hosted website, i.e. I cannot install other packages or e.g. restart the mysql server.
So, the error is the following:
“Error while trying to create admin user: Failed to connect to the database:
An exception occured in driver: SQLSTATE[HY000] [2054]
The server requested authentication method unknown to the client”

mysql version is 5.5.47 (via select version(); )
The variable old_passwords is set to OFF.
This happens both with php 7.0 and php 5.6.

All solutions I could find in the internet involved changing the mysql configuration and restarting the server. Because I am using just a hosted website, I cannot do this.

What is going wrong here ?
Is there a way I can fix this ?

Any hints how to get it working ?

Thanks
Alex