Suppose we only have to use factoring as trapdoor function and we are disallowed to use other trapdoors, are there applications currently deployed which cannot be done?


1 Answer 1


Certainly factoring allows you the big workhorse applications (key encapsulation, digital signatures and (with a little imagination) key agreement). As we look for more functionality, factoring does not always seem to be enough.

Full homomorphic encryption does not seem to be possible (though RSA is multiplicatively homomorphic and Paillier is log-homomorphic). Identifier-based encryption with factoring is shockingly inefficient, and I've not seen a serious proposal for extending it to hierarchical encryption or attribute based encryption. Other pairing-based constructions such as broadcast encryption can be done with factoring, but not nearly as efficiently. Likewise, although zero knowledge proofs of factorisation exists, people have not been able to extend them into the range of functionality of SNARKs and STARKs.

It should also be noted that (satirical submissions aside) factorisation does not represent a secure solution for anything if an adversary has access to a cryptanalytically relevant quantum computer.

  • $\begingroup$ I don't see what "log-homomorphic" is in the case of Paillier. $\endgroup$
    – fgrieu
    Mar 12, 2022 at 18:34
  • $\begingroup$ @daniels if factoring can do everything discrete log can and vice versa then why prefer one over the other? $\endgroup$
    – Turbo
    Mar 12, 2022 at 18:45
  • $\begingroup$ @frgieu In Paillier multiplication in the ciphertext group corresponds to addition in the plaintext group and so this sometimes referred to a log-homomorphic. $\endgroup$
    – Daniel S
    Mar 12, 2022 at 19:00
  • 1
    $\begingroup$ @turbo Principally for reasons of efficiency of computation, bandwidth or simplicity of implementation. For example, because discrete logarithm keys are simpler to produce, forward secrecy is easier for discrete logarithm constructs. Conversely the simplicity of RSA signatures means that some implementations favours them. $\endgroup$
    – Daniel S
    Mar 12, 2022 at 19:02

Your Answer

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

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