For a given private key $d$, random $k$ and message hash $h$ is it possible that there exists a different set of $d$, $k$ and $h$ which produces the same signature using $\text{secp256k1}$ curve?
There are a number of signature schemes on small domains based on bilinear pairings which do not use random oracles. Examples are the Boneh-Boyen schemes and an interesting one from Okamoto which allows for blind, and partially blind signatures.
However all of them use some variant of the Strong ...
Unpredictable? Why unpredictable? Use a random key. Keep it secret. then encrypt 1,2,3,4,5,6,7.... All unique and up to some point they are unpredictable.
@fgrieu now you can use the LFSR library to draw easily :)
@JBis Isn't clear? AES is a family of permutations like any block cipher. With a key, you select a permutation from the family. Now for each encryption, you have a unique 128-bit. Since breaking AES is not possible then predicting the next is not possible, unless you encrypt so much value and the observer stores them, then the unpredictability decreases.
The problem the 128-bit may not fit to your 10 digit.
@JBis and probably they use getrandom() syscall and check their database, if exist call getrandom() again..., otherwise use the random.
@JBis i think you need more digits/bits in the id. with 128 the likelyhood of collision is negligible, and you could also reserve some bits for a counter - that would guarantee no collisions
@JBis another idea: choose a prime p near 10^10, choose a generator g for its multiplicative group (it's easier than it sounds) and use g^i (mod p) for the i-th id
The Side Channel
The Side Channel