2
$\begingroup$

We have a lot of cryptographic primitives now, and many methods of deriving one type of scheme from another. There are even some like the Merkle signature scheme, which uses a hash function to derive a signature scheme, two types which are not closely related.

So now I wonder, what is the smallest set of cryptographic primitives we can start with, and derive schemes to fill all our other needs? We would need hashing, block cipher, authentication, signatures, key exchange, etc. It shouldn't rely on some convenient properties of the primitive, so even if it was swapped out with a secure oracle, the derivation methods should still work. These primitives should each fit one role (ex. hash function) and not be some magic all in one function used to cheat the security proof. I think it'd be hard to reason about possible primitives and derivation methods that haven't been discovered yet, so an answer based on only existing primitives and derivation methods will be okay.

This isn't a concern right now, since all the dedicated primitives and key sizes in use now are secure for the foreseeable future. However, considering that any break in a cryptosystem could be catastrophic, we may want to design a cryptosystem with as few entry points as possible, and part of that is having as few underlying primitives as possible. Another valid concern is that existing versatile schemes may be broken by quantum computers or other threats not present today, and we may be forced to use specialized primitives. It would be helpful then to know what small set of primitives we could depend on.


Though not quite an answer to this, if we wanted to minimize entry points today, I think we can already get it down to 2, making use of families that share a security reduction.

  • Keccak would be used for all symmetric schemes. There is already the hash function SHA-3, and the authenticated encryption schemes Ketje and Keyak. Others like stream ciphers and pseudorandom generators can be created based on the same sponge construction.
  • ECC would be used for all asymmetric schemes. All the primitives in the family reduce to the elliptic curve discrete logarithm problem. I think we could specify a curve like Curve25519, but I'm not sure if all the primitives can use the same curve.

So why wouldn't I take this as an answer? These two families rely on specific properties of the primitive aside from their security. A secure oracle in either of their place wouldn't have such nice properties, and we wouldn't be able to derive other schemes from it in the same way. If we treated the sponge and the curve group as the primitives instead, then we aren't meeting the requirement that each primitive has one role - neither the sponge or the curve group fits a role on their own.


It took me a while to write this, there are probably some mistakes in the writing. Please don't be distracted and focus on the actual question.


Just wanted to clarify, this isn't some convoluted cryptography challenge, I really do care about the answer and think it has consequences for future cryptography, the restrictions are there for the same reason as in other math problems, not because cheating is bad but because we want a useful result.

$\endgroup$
  • 1
    $\begingroup$ "all our needs" is ill-defined. You seem to take it to mean "all the constructions I know about", but do you (or does anyone) know all of them? $\endgroup$ – fkraiem Sep 4 '18 at 7:25
  • $\begingroup$ I would say all the types in common use already but that's also very broad. I don't think I can list all those. There's a lot of variants within a type too, just from what I can recall right now, encryption has choice of block cipher, stream cipher, asymmetric variants, hash can be fixed length, variable length, stream, signature can be regular, one time, ring, group, threshold, etc. Most of those can be easily derived from another. I think if you'll see it in TLS or somewhere else visible, it's common enough for here. $\endgroup$ – EPICI Sep 4 '18 at 14:44
  • $\begingroup$ What is a "secure oracle" in regards to ECC? $\endgroup$ – Ella Rose Sep 4 '18 at 14:55
  • $\begingroup$ The secure oracle is just whatever component you want to assume is secure in your security proof, a black box that does that one thing, or set of related things, but doesn't have any other nice properties like using a group. ECC wouldn't use any since it already has its own security reductions to ECDL. You can substitute all the primitives with their own oracles - signature oracle, key exchange oracle, etc. - you would lose all the nice properties of ECC but also be able to assume the security since you're using oracles. $\endgroup$ – EPICI Sep 4 '18 at 15:13
  • $\begingroup$ @EPICI Interestingly, it seems like Curve25519 could not be used for any ECC application, according to a footnote in this answer. That doesn't necessarily mean no curve could... $\endgroup$ – forest Dec 9 '18 at 7:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.