What is the quantum-resistant signature scheme with the smallest signature + pubkey? After playing cat and mouse with an number of quantum-resistant signature schemes and coming up with nothing with small enough signatures, I'm turning to Crypto.SE. I need a quantum-resistant signature scheme with the smallest $signature || publickey$ that you can find. Private key size shouldn't really matter, can't I just use a CSRNG to generate a private key from a smaller seed?

Implementations are appreciated but not totally necessary. I'm hoping to get under 1000 bytes at least. Verification time is allowed to be in milliseconds, seconds sounds a bit exessive. Signing time could be up to 10 seconds, it's not the biggest issue. Also, it's fine if it's a one-time signature.

Some interesting reading:


https://en.wikipedia.org/wiki/Lamport_signature
https://gist.github.com/karlgluck/8412807/
http://tuprints.ulb.tu-darmstadt.de/1319/2/dissertation.dahmen.pdf
Choose some 128-bit hash function, such as RIPEMD-128, and a way of randomizing it, such as this.

The private key is either 60 uniformly random 128-bit strings s00,s01,...,s58,s59

and a uniformly random short salt or a seed to regenerate those. $\:$ For each i in

{00,01,...,58,59}, vi is the result of hashing si 19 times. $\:$ The public key is the

result of randomized-hashing v00 || v01 || ... || v58 || v59 with that salt.

To sign a message, the signer chooses a longer salt uniformly at random, computes the base-20 representation of the randomized hash of the message with the longer salt, and outputs

[[the two salts] and [for each j in {00,01,...,28,29}, the result of hashing s[2*j]

[19 minus the j-th digit of the base-20 representation] times and the result of

hashing s[(2*j)+1] [the j-th digit of the base-20 representation] times].

To verify a signature, the verifier computes the base-20 representation of the randomized-hash

of the message with the longer salt, [for each j in {00,01,...,28,29}, lets v[2*j] and

v[(2*j)+1] be the result of hashing the corresponding 128-bit parts of the signature [the j-th

digit of the base-20 representation] and [19 minus the j-th digit of the base-20 representation]

times respectively], and checks that the result of randomized-hashing

v00 || v01 || ... || v58 || v59 with the shorter salt is the public key.

If the length of the salts are fixed or can be efficiently computed from the sum of their lengths, then

the length of $\; signature \hspace{.04 in} || \hspace{.04 in} public\text{_}key \;$ will be $\;\;$ 7808 bits + the sum of the lengths of the salts.