<p>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 <em>distributions on instances</em> 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.</p>

<p>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. </p>

<p>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. </p>

CC BY-SA 4.0
2018-11-29T16:38:46.953Z
2018-11-29T16:38:46.953Z
Adam Smith
<p>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. </p>

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

CC BY-SA 4.0
2018-11-28T21:32:27.100Z
This may be of interest https://eprint.iacr.org/2008/335.pdf.
Sasho Nikolov
<graph-theory><soft-question><cr.crypto-security>
Cryptography protocols using graph problem instances
nish2575
# Cryptography protocols using graph problem instances

(Asked by: username_0 on 2018-11-28)

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?)

**Tags:** graph-theory, soft-question, cr.crypto-security
> **Comments:**
> **username_1**: This may be of interest https://eprint.iacr.org/2008/335.pdf.  

---

## 1 answers

### Answer by username_2 on 2018-11-29. Score: 3 | Accepted answer

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.


---

