Post-Quantum Primitives' Object Sizes

Question

1. Alternative Cryptographic Primitives

For quite a while, I've been thinking is it possible to "craft" a cryptographic primitive (like ECC) suitable for the purposes of post-quantum cryptography, and today (2017-05-20) I've came to the following conclusion:

There are two classes of primitives that may be used to construct cryptographic protocol:

• Groups: whose elements are equipped with addition with each other, and multiplication only with scalars.

• Rings: whose elements are equipped with addition and multiplication with them selves.

The first kind would almost certainly be vulnerable to cryptanalysis by Shor's Algorithm, because they'd most likely be cyclic.

And most primitives of the second kind would be representable with a matrix, since they're probably going to be linear. And this is exactly where we're progressing with lattice-base crypto.

2. CryptoPrimitive Size-Security Efficiency and My Question

Take ECC for example, an ECDSA signature of 192-bit security has 384*2 = 768-bit signature, therefore, it has an size-security ratio of about 4:1.

However, take the currently (2017-05-20) most efficient signature scheme BLISS, instantiated using the procedure described by Rebeca Staffas, we have a 128-bit security instance (512-A) with a signature size of about 6471 bits, that's a size-security ratio of about 50:1.

Yet, BLISS is the composition of several primitives - from sampling bimodal discrete Gaussian, to using Huffman or Arithmetic Coding.

This got me wonder, and this is my question: Is there a single primitive that offers the best post-quantum size-security efficiency, or we don't get to enjoy one such in a post-quantum world anymore?

Answer 1

TL;DR

Don't look for a primitive that provides the best communication efficiency. Instead, look for ones that are rich with desirable features.

Asker's confession

As the OP, I've always had a compulsive frustration that we don't get to enjoy the `perfection' and elegance that elliptic curve primitives used to provide in pre-quantum public-key cryptography. ECC operations are efficient compared to RSA; have actual exponential keysize-security relation; and quite a few other nice properties.

However, ECC isn't always a silver bullet. It requires generating system parameters in complicated ways; and certain parameters must be verifiably secure and sound - which isn't easy to achieve.

Symmetric-key analogy

It should be noted, that constructing secure and efficient primitives in symmetric-key cryptography, is no less noble an art than that in public-key cryptography.

Some blockciphers may require larger and more complex key schedule; some hash functions may require larger internal states, or more pre-computed constants, or both; some AEAD construct may run fast on some systems, but very slow on others.

Why answer my own question

The way the question requests an answer can't be say isn't "too broad" - it really is a bit too broad because I think it's quite deep.

I'd like to answer myself in a way that can inspire thinking instead of pointing people to a mis-predicted future.

What we really should look for

1. Communication / object size efficiency.
2. Computation efficiency / performance.
3. Interoperability.
4. Ability to be implemented correctly.
5. Ability to be implemented cost-efficient.

etc.

All these factors must be balanced.