What are good combinations of public key algorithms or primitives for long term security?

Question

There has been talk in literature about doing multiple encryption with different block ciphers or stream ciphers several times before, and the benefits and risks of such efforts. There may be hidden assumptions or weaknesses in designs of symmetric cipher algorithms, or perhaps they have been deliberately sabotaged by a hidden weakness by the design team, while on the other hand implementing multiple symmetric cipher algorithms introduces more ways that the code can go wrong and potential security problems in the implementation itself.

Focus on multiple symmetric ciphers to me strikes me as a misplaced concern, considering that the hardness assumption for symmetric ciphers seems largely based on the hardness of searching the keyspace. While its possible that there are breaks in one modern symmetric cipher that doesn't break another, it is starting to seem less likely.

Public key cryptography however relies on many different hardness assumptions, and so it seems strange to me that there hasn't been an effort to come up with protocols for multiple encryption with algorithms that have different hardness assumptions. The RSA problem is broken by factoring the modulus, elliptic curve cryptography is broken by discrete log, lattice based cryptography is broken by solving the shortest vector problem, and so on. And it seems all hidden subgroup problems for finite Abelian groups are broken in quantum computers (discrete log and factoring) and some groups that are 'close' to Abelian groups are also broken on quantum computers (factoring in quaternion groups for example.)

If we were to build a protocol or implementation that relied on multiple cryptographic primitives or algorithms for key exchange and signing, which would be appropriate for such a scheme? Obviously some algorithms are more compute intensive than others, and some users would prefer more performance over security so we might want to rank them in terms of performance and a guess on the hardness.

I have in mind creating certificates that are grounded in multiple hardness assumptions, so if one link in the chain is broken, the whole scheme doesn't fall apart.

Answer 1

For the signatures, hash-based signatures provide a nice solution to your problem: You can use so called hash combiners to instantiate the signature. These are functions that construct a hash function given two or more hash functions and preserve certain properties as long as at least one of the hash function has this property. For example the concatenation combiner: $C_{H_1,H_2}^{\|}(M) = (H_1(M)\|H_2(M))$

preserves collision resistance and second preimage resistance.

If you use hash functions based on different design principles, e.g. SWIFFT as one that has certain security guarantees steaming from the hardness of lattice problems and one classically constructed one like SHA-3, you can achieve good redundancy.

The big advantage is, that you do not have to implement two different schemes but only one: You would have to implement two different hash functions for message compression anyway but in addition you would also have to implement two "fixed length" signature schemes for multiple signatures.

Answer 2

I haven't heard of much work on this, but really choose any two that are based on assumptions that are independent of each other. Two candidates come to mind: ECC and lattice-based methods. These are based on assumptions that have nothing known in common (dlog vs. LWE).

Additionally, one of the reasons many people are interested in lattice-based methods is that we currently don't get any speedup for breaking the underlying problems with a quantum computer. Therefore, if someone gave you a quantum computer, you could not break these methods with current knowledge.