3
$\begingroup$

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:

Improve this question
$\endgroup$
7
  • 1
    $\begingroup$ 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. $\;$ $\endgroup$
    – user991
    Commented Jun 24, 2014 at 8:13
  • $\begingroup$ @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. $\endgroup$
    – CodesInChaos
    Commented Jun 24, 2014 at 8:30
  • $\begingroup$ @CodesInChaos : $\:$ However, that doesn't help me figure out how much time verification takes. $\hspace{.69 in}$ $\endgroup$
    – user991
    Commented Jun 24, 2014 at 9:02
  • $\begingroup$ @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. $\endgroup$
    – CodesInChaos
    Commented Jun 24, 2014 at 9:17
  • $\begingroup$ @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. $\endgroup$
    – Bardi Harborow
    Commented Jun 24, 2014 at 10:35

4 Answers 4

Reset to default
2
$\begingroup$

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.

Improve this answer
$\endgroup$
9
  • $\begingroup$ You said earlier that you could do it in less that 1000 bytes? This seems worse than this. $\endgroup$
    – Bardi Harborow
    Commented Jun 25, 2014 at 2:32
  • 1
    $\begingroup$ I said that, and that's what I did. $\:$ That link uses a significantly larger iteration count. $\hspace{1.33 in}$ $\endgroup$
    – user991
    Commented Jun 25, 2014 at 2:49
  • 1
    $\begingroup$ 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\;$. $\;\;\;\;$ $\endgroup$
    – user991
    Commented Jun 25, 2014 at 3:22
  • 1
    $\begingroup$ My suggestion is from some reference I no longer remember to Winternitz signatures; this paper seems like a more modern reference. $\;$ $\endgroup$
    – user991
    Commented Jun 25, 2014 at 3:23
  • 1
    $\begingroup$ Isn't the security level of 128 bit hashes just 64 bits since the Grover reduces the pre-image resitance? $\endgroup$
    – CodesInChaos
    Commented Jun 25, 2014 at 13:09
1
$\begingroup$

The most compact stateless post-quantum digital signature scheme currently under consideration by NIST would be Falcon. The next closest contestant is Dilithium.

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ That is, of course, not true; some of the signature methods listed in NIST SP 800-208 have rather shorter signature+public key sizes. $\endgroup$
    – poncho
    Commented Nov 21, 2020 at 3:23
  • $\begingroup$ Edited, I should refer to stateless ones. $\endgroup$
    – DannyNiu
    Commented Nov 21, 2020 at 8:55
0
$\begingroup$

The Winternitz OTS or a variant of it like SPHICS+ is your best bet.

This paper gives more detail on W-OTS.

It works similar to the Lamport scheme but each public/private key pair is a chain of 2^n hashes, that are good to sign n bits of a message digest. If you place these keys into a merkle tree structure then you have a public key of a single hash. This is quite a good simple explanation of the scheme.

You have a trade-off between computation in key generation/verification, key size, and signature size.

Assuming a 128 bit hash like the other answer, your signature 16 hashes in respect of each byte in the message hash, and 3 hashes of authorisation nodes (i think) for the merkle tree. You may also need some sort of checksum depending on the setup. But roughly (assuming per byte signature) you reduce the signature size by 8. The signature would be around 2500 bits.

The more modern versions (eg.SPHINCS+) use various merkle trees to allow a public key to sign more than one message, and as a form of checksum.

Improve this answer
$\endgroup$
0
$\begingroup$

As I know, isogeny-based cryptography and multivariate-based cryptography are known to have the smallest public keys and signature sizes, respectively. However, I don't have exact data one the sum. I've seen papers describing isogeny-based signatures with less-than-1000-bits public keys and signature sizes with sign and verification time of milliseconds. For instance, take a look at this one.

On the other hand, Rainbow, which is a multivariate-based signature scheme, has made it through to the third round of NIST post quantum contest, and thus, can be used with less concern about security. It says it has a 66-byte signature and is efficiently-computable.

Improve this answer
$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.