How to do rsync-like encrypted backup?

The best thing around is Duplicity. The only drawback is that it does not handle hardlinks.

Another solution is Tartarus, which can be piped through GPG and FTP/SSH directly to a backup server. It does incrementals.

Here are Tartarus instructions, in German.

I think you'll like rsyncrypto.

Use rsyncrypto to encrypt files from your plaintext directory to your encrypted directory, and decrypt files from your encrypted directory and your plaintext directory, using keys that you keep locally.

Use rsync to synchronize between your encrypted directory and the remote host.

The rsyncrypto implementation you can download now from Sourceforge not only handles changes in bytes, but also insertions and deletions.

With rsyncrypto, all encryption keys never leave the local computer.

"The remote server should preferably not even know the directory structure"

In that case, you'll want to use the --name-encrypt=map option. That makes each encrypted file name is a random string of characters, and by default all mangled file names are stored in a single directory. The true file names and folder names are stored in the (encrypted) file named "filemap".

Related: "Is there an encrypted version control system?"

In recent years, Rclone has been developed. Its motto is "rsync for cloud storage" but beyond things like S3/Azure/Google/etc. cloud storage providers, it also supports syncing between local and SSH/SFTP targets.

Any "remote" you configure, you can also add a crypt wrapper around it. This acts as the original remote, but the contents of all your files (and optionally the file names themselves) get encrypted on the client side. The algorithm is documented, and its been a generally seamless process in my experience so far.