3 ms·

Is there any insight why there is no PQC signature with a short signature? Is it just us failing to find one, or something more fundamental prevents a quantum

Is there any insight why there is no PQC signature with a short signature? Is it just us failing to find one, or something more fundamental prevents a quantum resistant short signature like?

some_furry 3y ago
The kind of math problems that are hard for quantum computers to break tend to produce kilobyte+ outputs at our target security levels.
adastra22 3y ago
I’m confused because there are such things. What you want here is authentication, and there are hashing modes which provide that.
- some_furry 3y ago
  They specifically asked about PQC signatures, not MACs.
  - nmadden 3y ago
    Well, there are PQC (public key) signature schemes based on hash functions, but they all have large signatures (in the multi-kB range) and other drawbacks (eg being stateful). Moving to a MAC is also not a crazy idea in a lot of deployments. You can horizontally scale an internal MAC validation service. I believe Facebook use MAC-based tokens internally (CATs).
  - adastra22 3y ago
    There are hashing modes that achieve both integrity and authentication. It usually involves prefixing the data with a server-provided secret before hashing. Only someone who knows the secret can produce such a hash, thereby providing both authentication and data integrity. Cookies are signed by the server, not the client, and only the server needs to check the signature, so there really isn’t any reason to use much more expensive asymmetric cryptography. And post-quantum security is just a bonus. In the context of cookies, authenticated hashing IS a PQC signature.
- deleted 3y ago
  [deleted]
wbl 3y ago
There is! It just takes milliseconds to verify and has questionable security
maple3142 3y ago
SQIsign is relatively small and fast to verify, but it is pretty slow to sign.
- nmadden 3y ago
  Well, SQIsign signatures are about the same size (204 bytes) than RSA-2048 (256 bytes). So ok, but most people who care about size on the wire have moved to EC sigs, which are much smaller (64 bytes). And “fast to verify” is not really true: 50ms is not fast — both RSA and Ed25519 signature verification is <0.1ms.
bawolff 3y ago
Keep in mind it took us quite a while to move to short (ECC based) public key schemes for classical crypto. Although some of that is for non-technical reasons.

Is there any insight why there is no PQC signature with a short signature? Is it just us failing to find one, or something more fundamental prevents a quantum resistant short signature like?

some_furry 3y ago

The kind of math problems that are hard for quantum computers to break tend to produce kilobyte+ outputs at our target security levels.

adastra22 3y ago

I’m confused because there are such things. What you want here is authentication, and there are hashing modes which provide that.

some_furry 3y ago
They specifically asked about PQC signatures, not MACs.
- nmadden 3y ago
  Well, there are PQC (public key) signature schemes based on hash functions, but they all have large signatures (in the multi-kB range) and other drawbacks (eg being stateful). Moving to a MAC is also not a crazy idea in a lot of deployments. You can horizontally scale an internal MAC validation service. I believe Facebook use MAC-based tokens internally (CATs).
- adastra22 3y ago
  There are hashing modes that achieve both integrity and authentication. It usually involves prefixing the data with a server-provided secret before hashing. Only someone who knows the secret can produce such a hash, thereby providing both authentication and data integrity. Cookies are signed by the server, not the client, and only the server needs to check the signature, so there really isn’t any reason to use much more expensive asymmetric cryptography. And post-quantum security is just a bonus. In the context of cookies, authenticated hashing IS a PQC signature.
deleted 3y ago
[deleted]

wbl 3y ago

There is! It just takes milliseconds to verify and has questionable security

maple3142 3y ago

SQIsign is relatively small and fast to verify, but it is pretty slow to sign.

nmadden 3y ago
Well, SQIsign signatures are about the same size (204 bytes) than RSA-2048 (256 bytes). So ok, but most people who care about size on the wire have moved to EC sigs, which are much smaller (64 bytes). And “fast to verify” is not really true: 50ms is not fast — both RSA and Ed25519 signature verification is <0.1ms.

bawolff 3y ago

Keep in mind it took us quite a while to move to short (ECC based) public key schemes for classical crypto. Although some of that is for non-technical reasons.