I personally am only aware of basic examples of public key cryptography and I haven't studied cryptography yet. I'm curious if there are circumstances in cryptography where using problem instances from graph theory are preferred to number theory, when building challenges.

(Side question: is number theory generally preferred because the data is more concise and the primitives might be faster in implementation?)


Number theory (along with neighboring "algebraic" areas like lattices and group theory) gets used for public-key crypto because the problems for which we know distributions on instances that (a) are hard and (b) have trapdoors are most naturally stated algebraically. This stands in contrast to the symmetric key setting: a much wider range of natural candidates for one-way functions (which don't require trapdoors) exist.

I imagine one can turn algebraic problems into graph-theoretic ones via the reductions which prove NP-completeness. But those transformations just make the representations more cumbersome -- they don't obviously provide any security advantages.

The eprint paper linked to by Sasho Nikolov in the comments is a good place to look for one of the very few combinatorial alternatives.

| cite | improve this answer | |

Your Answer

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

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