# 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.

-
I'm too theoretical to have an idea of what "ECDSA-type ballpark" is, but I can see a way to do it by taking up barely under 1000 bytes and requiring around 600 hash operations to verify, despite only being one-time. $\;$ –  Ricky Demer Jun 24 '14 at 8:13
@RickyDemer ECDSA sigs use 4x the security level and public keys 2x the security level. So total of public key and signature is around 100 bytes. –  CodesInChaos Jun 24 '14 at 8:30
@CodesInChaos : $\:$ However, that doesn't help me figure out how much time verification takes. $\hspace{.69 in}$ –  Ricky Demer Jun 24 '14 at 9:02
@RickyDemer eBACs lists a fast Ed25519 implementation at 170k CPU cycles. Most implementations are closer to a million CPU cycles. So 600 calls to a compression function should be in the right ballpark, probably even faster than ECC if you choose a fast hash function. –  CodesInChaos Jun 24 '14 at 9:17
@RickyDemer and @CodesInChaos: I didn't mean to be too specific. When I said: ECDSA-type ballpark, I meant in terms of milliseconds rather than seconds. –  Bardi Harborow Jun 24 '14 at 10:35

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.

-
You said earlier that you could do it in less that 1000 bytes? This seems worse than this. –  Bardi Harborow Jun 25 '14 at 2:32
I said that, and that's what I did. $\:$ That link uses a significantly larger iteration count. $\hspace{1.33 in}$ –  Ricky Demer Jun 25 '14 at 2:49
I would suggest replacing the 19s and 20s with $n$s and $(n\hspace{-0.04 in}+\hspace{-0.05 in}1)$s respectively for some positive integer $n$, replacing the 29s with the least positive integer $m$ such that $\: 2^{128} \leq (n\hspace{-0.04 in}+\hspace{-0.05 in}1)^{m+1} \;$, $\;$ and then replacing the 59s with $\:(2\hspace{-0.04 in}\cdot \hspace{-0.04 in}m)\hspace{-0.02 in}+\hspace{-0.02 in}1\;$. $\;\;\;\;$ –  Ricky Demer Jun 25 '14 at 3:22
My suggestion is from some reference I no longer remember to Winternitz signatures; this paper seems like a more modern reference. $\;$ –  Ricky Demer Jun 25 '14 at 3:23
Isn't the security level of 128 bit hashes just 64 bits since the Grover reduces the pre-image resitance? –  CodesInChaos Jun 25 '14 at 13:09