This question is similar to “What primitives are needed to generically implement public-key cryptography?”, but with a more applied/contingent focus:

  • That question asked about what's theoretically required, to which the Accepted answer is “we have no [necessary and sufficient] primitive… for public-key encryption”

    • (contrasted with symmetric cryptosystems, for which a necessary and sufficient primitive has been identified: a one-way function)
  • This question asks, not about the identically-correct N&S primitive in the platonic limit, which clearly has not been identified (if a decisive choice even exists), but about what known categories of primitives we have identified so far (that are not widely accepted as being irreconcilably broken)

So: what is the taxonomy of public-key cryptographic schemes?

That is, cryptographic schemes that can do at least one of the following:

  1. Convert an authenticated (but not confidential) communication channel into a confidential one

    • RSA Encryption

    • Curve25519+EDCH

  2. Leverage an authenticated (but not necessarily confidential) communication channel available at time $t$ to authenticate communications at time $t'$

    • RSA Signatures
    • Merkle trees

My current understanding is that all primitives that yield these abilities can be grouped together something like this:

  • Number-theoretic

    • Based on the difficulty of factoring large numbers

      • RSA
    • Based on the difficulty of inverting a group operation

      • Based on the difficulty of finding the discrete-logarithm

        • …over elliptic curves:

        • Pallier

      • ElGamal

      • Based on lattices, …

        • hic sunt dracones
  • Based on "any" one-way function:

    • Merkle trees

    • One-time signatures

Is there any current survey, overview, book, etc. giving such a "taxonomy of public-key cryptosystems" that includes all the systems mentioned above as well as at least one lattice-based system?


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.