Remote sync without rsync

Question

My setup is as follows:

• Two Linux machines running Debian 9
• A "storage box" on the internet rented from a cloud hosting company. This box can only be accessed via the SFTP, Samba and WebDAV protocols for transferring data. I have no means of installing any software on it, since it is not a server, only a "dumb" storage device. I do not have any SSH access either.

Now, here's what I would like to do:

1. Synchronize a directory across my two Debian machines.
2. Do this incrementally, so I don't have to upload and download the entire directory structure every time.

What I've tried so far:

• rsync: Basically rsync -avz /path/to/dir/local/machine USER@remote_address.com. The problem: The remote storage box does not have rsync installed to act as a server. Therefore, the entire directory has to be parsed (and therefore transferred) every time, which is slow.

• WebDAV mount: Mounted remote directory locally using fusedav and did an rsync locally. This took too long since modify times are not preserved when uploading via fusedav so rsync has to checksum each file.

• Duplicity: Incremental backups work fine over SFTP. There is, however, no possibility to do an incremental restore over existing files. It downloads the entire directory each time.

• Borg Backup: Same issue as with duplicity, no incremental restores (that I found).

Is there any backup solution that offers incremental restore and works over SFTP? Or can I make rsync work quickly (I thought of some kind of cache, though that doesn't seem to be an option.