Using public-key signature instead of having API key I am designing an application that will need an API key. At first I believed that generating a long, random token would be secure enough (say 32 chars string that includes 0-9, a-z and A-Z), and then I could store it or its hash on the server-side for authenticating clients. But after Googling some HN threads I found that sending API keys in HTTP headers might leak if HTTP request logs have been leaked at some time in the future, and then the attackers could very easily use the keys to impersonate the clients. 

Then I looked at the AWS model, which I have always wondered how it actually works. AWS doesn't just give you an API key, it gives you a couple of tokens, probably like a private-public key pair and the client's HMACs, some request-specific string (HTTP method, HTTP path, timestamp, etc...), and then the server simply authenticates the client by checking the signature with the public key.

Now, if this public-key signature is truly much more secure than the usual API key, I want to know whether my implementation is secure enough:


When the user registers, the server generates a ed25519 or curve25519 key pair, the server gives the user the private key as an API key and the server stores the public key.
When the user sends a request that needs to be authenticated, he computes the current timestamp and then signs it with libsodium's  crypto_sign() and sends the signature in an HTTP header.
When the server authenticates the user by simply verifying the signature using libsodium's crypto_sign_open()


In that way, the user never has to send a static API key that might get stored and leaked in some log's store in the future. Additionally, the server should check the timestamp in order to verify it is not an old one that might be involved in some weird replay attack. Also, I am assuming that the server is using HTTPS with TLSv1.2 at least.

I feel that I am right, but I also understand that I should not invent my own security. I just need your recommendation of this type of public-key signature authentication
Using public key cryptography instead of a long-term shared secret is slightly more complicated but has major advantages. One of them being that the server doesn't learn the secret key. This protects against accidental leaks, but also insider threats.

If this is an option, you can use client TLS certificates. Most HTTP client libraries support this, but web server often have limited support for this. Namely, they support ACLs based on the presence (or not) of a certificate, but that's pretty much all they do. And it's not always possible to retrieve client information from web applications.

The scheme you describe (the server sends something that the client has to sign) works. However, you shouldn't use a time stamp, which would be vulnerable to replay attacks, but a nonce.