<p>Boaz Barak addressed this in a <a href="http://windowsontheory.org/2013/10/07/structure-vs-combinatorics-in-computational-complexity/">blog post</a></p>

<p>My takeaway from his post (roughly speaking) is that we only know how to design cryptographic primitives using computational problems that have some amount of structure, which we exploit. With no structure, we don't know what to do.  With too much structure, the problem becomes efficiently computable (thus useless for cryptographic purposes). It seems that the amount of structure has to be just right.</p>

CC BY-SA 3.0
2014-11-05T08:27:08.180Z
Reading that article, I thought of another possible reason that factoring pairs of large primes remains the method of choice for public key cryptography: it's *really* difficult to find a replacement. The number of mathematicians who understand any given alternative is small, which (1) limits the number of people who can propose alternatives and (2) limits the number of people who can credibly analyze proposals to determine whether they're workable. Primes may not work forever, but they work for now, so inertia keeps them in use.
Steve
CC BY-SA 3.0
2014-10-31T19:15:10.583Z
2014-10-31T19:15:10.583Z
Tyson Williams
<p>All of what I am going to say is well-known (all the links are to Wikipedia), but here it goes:</p>

<ol>
<li><p>The approach used in RSA using pairs of primes can also be applied in a more general framework of cyclic groups, notably the <a href="http://en.wikipedia.org/wiki/Diffie%E2%80%93Hellman_key_exchange" rel="nofollow">Diffie-Helmann</a> protocol that generalizes $\left(\mathbb{Z}/pq\mathbb{Z}\right)^{\times}$ to an arbitrary group, notably <a href="http://en.wikipedia.org/wiki/Elliptic_curve_cryptography" rel="nofollow">elliptic curves</a> which are less susceptible to the attacks that work on integers. Other group structures <a href="http://en.wikipedia.org/wiki/Non-commutative_cryptography" rel="nofollow">have been considered</a> which may be non-commutative but none are in widespread use AFAIK.</p></li>
<li><p>There are other approaches to cryptography, notably <a href="http://en.wikipedia.org/wiki/Lattice-based_cryptography" rel="nofollow">lattice-based cryptography</a> that rely on certain hard problems on lattices (finding points with small norm on the lattice, for example) to implement public-key cryptography. Interestingly, some of these systems are <em>provably hard</em>, i.e. can be broken if <em>and only if</em> the corresponding hard problem in lattice theory can be solved. This is in contrast with, say RSA which <a href="http://en.wikipedia.org/wiki/RSA_problem" rel="nofollow">does not offer the same guarentee</a>. Note that the lattice based approach is conjectured to <em>not</em> be NP-hard (but seems harder than integer factoring for now).</p></li>
<li><p>There is a seperate concern to key sharing, namely <em>secret revealing</em>, which has very interesting complexity theory properties. I don't know the details, but the theory of <a href="http://en.wikipedia.org/wiki/Zero-knowledge_proof" rel="nofollow">zero-knowledge protocols</a> allows Alice to reveal to Bob <em>her knowledge</em> of a secret which is NP hard to compute (Graph Hamiltonian) without revealing the secret <em>itself</em> (the path in this case).</p></li>
</ol>

<p>Finally, you might want to check the page on <a href="http://en.wikipedia.org/wiki/Post-quantum_cryptography" rel="nofollow">post-quantum cryptography</a> to see some alternative approaches to public-key cryptosystems that rely on hard problems.</p>

CC BY-SA 3.0
2014-10-31T20:19:03.253Z
2014-11-26T18:59:56.760Z
2014-11-26T18:59:56.760Z
cody
<p>Most current cryptography methods depend on the difficulty of factoring numbers that are the product of two large prime numbers. As I understand it, that is difficult only as long as the method used to generate the large primes cannot be used as a shortcut to factoring the resulting composite number (and that factoring large numbers itself is difficult).</p>

<p>It looks like mathematicians find better shortcuts from time to time, and encryption systems have to be upgraded periodically as a result. (There's also the possibility that quantum computing will eventually make factorization a much easier problem, but that's not going to catch anyone by surprise if the technology catches up with the theory.)</p>

<p>Some other problems are proven to be difficult. Two examples that come to mind are variations on the knapsack problem, and the traveling salesman problem.</p>

<p>I know that Merkle–Hellman has been broken, that Nasako–Murakami remains secure, and that knapsack problems may be resistant to quantum computing. (Thanks, Wikipedia.) I found nothing about using the traveling salesman problem for cryptography.</p>

<p>So, why do pairs of large primes seem to rule cryptography?</p>

<ul>
<li>Is it simply because the it is currently easy to generate pairs of large primes that are easy to multiply but difficult to factor?</li>
<li>Is it because factoring pairs of large primes is proven to be difficult to a predictable degree that is good enough?</li>
<li>Are pairs of large primes useful in a way other than difficulty, such as the property of working for both encryption and cryptographic signing?</li>
<li>Is the problem of generating problem sets for each of the other problem types that are difficult enough for the cryptographic purpose itself too difficult to be practical?</li>
<li>Are the properties of other problem types insufficiently studied to be trusted?</li>
<li>Other.</li>
</ul>

CC BY-SA 3.0
2014-10-31T13:56:13.507Z
First, I am pretty sure elliptic curve cryptography is used in practice, though I cannot remember in which situation. Yet you're right that RSA is used a lot more than other cryptosystems. I think the reason is mainly because RSA encryption is some kind of standard for years now, with a lot a (buggy, of course!) software implementing it, and with people used to it. Other encryption systems (based for instance on elliptic curves or lattices) are sometimes usable, but it needs people to acquire them, and this takes time! Change of habits...
Bruno
CC BY-SA 3.0
2014-10-31T15:28:51.643Z
@Bruno Bitcoin for example uses elliptic curves to sign transactions.
Martin Berger
CC BY-SA 3.0
2014-11-01T07:14:20.620Z
Related: [Why hasn't there been an encryption algorithm that is based on the known NP-Hard problems?](http://cs.stackexchange.com/questions/356/why-hasnt-there-been-an-encryption-algorithm-that-is-based-on-the-known-np-hard)
Kaveh
<cr.crypto-security><primes>
Why does most cryptography depend on large prime number pairs, as opposed to other problems?
Steve
# Why does most cryptography depend on large prime number pairs, as opposed to other problems?

(Asked by: username_0 on 2014-10-31)

Most current cryptography methods depend on the difficulty of factoring numbers that are the product of two large prime numbers. As I understand it, that is difficult only as long as the method used to generate the large primes cannot be used as a shortcut to factoring the resulting composite number (and that factoring large numbers itself is difficult).

It looks like mathematicians find better shortcuts from time to time, and encryption systems have to be upgraded periodically as a result. (There's also the possibility that quantum computing will eventually make factorization a much easier problem, but that's not going to catch anyone by surprise if the technology catches up with the theory.)

Some other problems are proven to be difficult. Two examples that come to mind are variations on the knapsack problem, and the traveling salesman problem.

I know that Merkle–Hellman has been broken, that Nasako–Murakami remains secure, and that knapsack problems may be resistant to quantum computing. (Thanks, Wikipedia.) I found nothing about using the traveling salesman problem for cryptography.

So, why do pairs of large primes seem to rule cryptography?

* Is it simply because the it is currently easy to generate pairs of large primes that are easy to multiply but difficult to factor?
* Is it because factoring pairs of large primes is proven to be difficult to a predictable degree that is good enough?
* Are pairs of large primes useful in a way other than difficulty, such as the property of working for both encryption and cryptographic signing?
* Is the problem of generating problem sets for each of the other problem types that are difficult enough for the cryptographic purpose itself too difficult to be practical?
* Are the properties of other problem types insufficiently studied to be trusted?
* Other.

**Tags:** cr.crypto-security, primes

> **Comments:**
> **username_1**: First, I am pretty sure elliptic curve cryptography is used in practice, though I cannot remember in which situation. Yet you're right that RSA is used a lot more than other cryptosystems. I think the reason is mainly because RSA encryption is some kind of standard for years now, with a lot a (buggy, of course!) software implementing it, and with people used to it. Other encryption systems (based for instance on elliptic curves or lattices) are sometimes usable, but it needs people to acquire them, and this takes time! Change of habits...  
> **username_2**: @username_1 Bitcoin for example uses elliptic curves to sign transactions.  
> **username_3**: Related: [Why hasn't there been an encryption algorithm that is based on the known NP-Hard problems?](http://cs.stackexchange.com/questions/356/why-hasnt-there-been-an-encryption-algorithm-that-is-based-on-the-known-np-hard)  

---

## 2 answers

### Answer by username_4 on 2014-10-31. Score: 9

Boaz Barak addressed this in a [blog post](http://windowsontheory.org/2013/10/07/structure-vs-combinatorics-in-computational-complexity/)

My takeaway from his post (roughly speaking) is that we only know how to design cryptographic primitives using computational problems that have some amount of structure, which we exploit. With no structure, we don't know what to do. With too much structure, the problem becomes efficiently computable (thus useless for cryptographic purposes). It seems that the amount of structure has to be just right.

> **Comments:**
> **username_0**: Reading that article, I thought of another possible reason that factoring pairs of large primes remains the method of choice for public key cryptography: it's *really* difficult to find a replacement. The number of mathematicians who understand any given alternative is small, which (1) limits the number of people who can propose alternatives and (2) limits the number of people who can credibly analyze proposals to determine whether they're workable. Primes may not work forever, but they work for now, so inertia keeps them in use.  

---

### Answer by username_5 on 2014-10-31. Score: 6

All of what I am going to say is well-known (all the links are to Wikipedia), but here it goes:

1. The approach used in RSA using pairs of primes can also be applied in a more general framework of cyclic groups, notably the [Diffie-Helmann](http://en.wikipedia.org/wiki/Diffie%E2%80%93Hellman_key_exchange) protocol that generalizes $\left(\mathbb{Z}/pq\mathbb{Z}\right)^{\times}$ to an arbitrary group, notably [elliptic curves](http://en.wikipedia.org/wiki/Elliptic_curve_cryptography) which are less susceptible to the attacks that work on integers. Other group structures [have been considered](http://en.wikipedia.org/wiki/Non-commutative_cryptography) which may be non-commutative but none are in widespread use AFAIK.
2. There are other approaches to cryptography, notably [lattice-based cryptography](http://en.wikipedia.org/wiki/Lattice-based_cryptography) that rely on certain hard problems on lattices (finding points with small norm on the lattice, for example) to implement public-key cryptography. Interestingly, some of these systems are *provably hard*, i.e. can be broken if *and only if* the corresponding hard problem in lattice theory can be solved. This is in contrast with, say RSA which [does not offer the same guarentee](http://en.wikipedia.org/wiki/RSA_problem). Note that the lattice based approach is conjectured to *not* be NP-hard (but seems harder than integer factoring for now).
3. There is a seperate concern to key sharing, namely *secret revealing*, which has very interesting complexity theory properties. I don't know the details, but the theory of [zero-knowledge protocols](http://en.wikipedia.org/wiki/Zero-knowledge_proof) allows Alice to reveal to Bob *her knowledge* of a secret which is NP hard to compute (Graph Hamiltonian) without revealing the secret *itself* (the path in this case).

Finally, you might want to check the page on [post-quantum cryptography](http://en.wikipedia.org/wiki/Post-quantum_cryptography) to see some alternative approaches to public-key cryptosystems that rely on hard problems.


---

