The NIST is currently trying to select new standards for post-quantum cryptography. The two main categories for the candidates are "Public-key Encryption and Key-establishment Algorithms" and "Digital Signature Algorithms".

The signature algorithms are based on public-key encryption algorithms. Thus, why to separate these two categories ? Is it a matter of implementation, or of performance maybe ?


2 Answers 2


The question's statement

The signature algorithms are based on public-key encryption algorithms

goes straight against accepted wisdom. Which is that signature and public-key encryption are separate beasts, and we know no way to build¹ the former from the later, or vice versa (while keeping the same key generation procedure, or efficiently; see comments).

This explains the two categories “Public-key Encryption and Key-establishment Algorithms” and “Digital Signature Algorithms”.

¹ Sure, we can build both kinds from trapdoor permutations. The standard examples are RSA signature like RSASSA-PSS and RSA encryption like RSAES-OAEP, both built from the textbook RSA trapdoor permutation of $[0,n)$ per $x\mapsto x^e\bmod n$. But there are many other useful constructions of signature and public-key encryption.

  • $\begingroup$ We do know how to generically construct signatures from PKE. Just not particularly efficiently. $\endgroup$
    – Maeher
    Commented Jun 26, 2022 at 14:26
  • $\begingroup$ @Maeher : is that with the same public/private key pair, or rebuild from scratch the way we can build hashes, then (kinda) signature ? $\endgroup$
    – fgrieu
    Commented Jun 26, 2022 at 15:47
  • $\begingroup$ No, not at all. It would be a Rube Goldbergesque construction using the key generation procedure as a OWF and building a signature scheme from that. (Crucially this does involve CRHF which we have basically no idea how to construct from general assumptions) This isn't useful, but it's in contrast to the other direction, where not even such a construction is known. $\endgroup$
    – Maeher
    Commented Jun 26, 2022 at 17:24

Like fgrieu said, not all public-key algorithms are based on bijective trapdoor permutations.

If the standardization effort looked for a general-purpose bijective permutation, then we may very probably miss some special-purpose constructs that're more efficient when designed specifically for PKE/KEM or DSS.

I mean, designing something that fits the need of both functions may make the result significantly less efficient.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.