# Which public key cryptosystems are not based on number theory?

Are there any public key cryptographic systems whose hardness assumptions don't involve number theoretic problems?

• Does the LWE count as a number theoretic problem? – Hilder Vítor Lima Pereira Jun 27 '16 at 16:28
• From skimming that article it seems the hardness assumption is at least partially based on lattice problems, so maybe? It depends on whether the problem is hard independently of those lattice problems. – Elliot Gorokhovsky Jun 27 '16 at 16:30
• How about McEliece? It's hardness is based on decoding a general linear code. – mikeazo Jun 27 '16 at 16:37
• That would certainly count. – Elliot Gorokhovsky Jun 27 '16 at 16:38
• @D.W. Not all public key crypto is based on bijective one-way functions. Hash signatures are obviously not. And even RSA is a trapdoor function and not one-way in the sense SDL was looking for (unless you throw the private key away) – CodesInChaos Jun 27 '16 at 21:13

Yes. The McEliece cryptosystem using Binary Goppa codes has withstood cryptanalysis to date. Its hardness is based on decoding. I should note that it has been broken for certain classes of codes.

Another common example is the Merkle-Hellman knapsack cryptosystem. Unfortunately it was broken. It is likely possible to build a secure cryptosystem based on the knapsack problem. I wanted to at least mention this line of work.

In addition to McEliece (already mentioned by Mike), there's also Hash Based Signatures (such as this one); these are signature algorithms that is based only on some security assumptions of a hash function (and typical hash functions as about as far from numeric-theoretical problems as you can get)

• Hash signatures are the only signatures I'd trust for long term security since they only involve unstructured crypto. – CodesInChaos Jun 27 '16 at 17:12
• @CodesInChaos: well, yes; since every signature algorithm I've heard of starts out with "hash the message", they're trusting the hash function anyways; with Hash Based Signatures, you're not trusting anything else to be secure... – poncho Jun 27 '16 at 17:28
• hmm... @CodesInChaos I wonder why bitcoin didn't choose HBS then? Considering it's supposed to be secure essentially forever. – Elliot Gorokhovsky Jun 27 '16 at 20:05
• @RenéG Because the signatures are pretty big and size really matters for bitcoin. ECDSA needs 64 bytes. A one-time hash signature needs hundreds of bytes. A reusable stateless hash signature something like a megabyte. – CodesInChaos Jun 27 '16 at 21:09
• @CodesInChaos: "A reusable stateless hash signature something like a megabyte"; actually, Sphincs needs only 40k (not that Sphincs was known when bitcoin was designed); if you need a signature method that can generate a billion signatures per public key (and don't mind stateful), you can do it in perhaps 2k – poncho Jun 27 '16 at 21:19

This is only useful as a thought exercise, but Alice and Bob can do key exchange based only on the strength of AES or some other private cipher:

Assumptions: doing $2^{40}$ operations will take "a while" but is doable; $2^{80}$ operations is out of the realm of possibility in a century. Alice can publish arbritary amounts of information which cannot be tampered with

Alice generates $2^{40}$ AES keys (assuming each is a 128 bit key, that $2^{44}$ bytes aka 16 TB) and encrypts each with another random AES key along with a check value. She then publishes this data set with most of the key she picked (all but 40 bits) Assuming the check value is also 128 bits, we're now talking about 48 TB, so again, this is mainly only useful as a thought experiment. This takes $O(2^{40})$ steps and about the same storage.

Bob picks one of the keys at random (after downloading the whole set) and brute forces the remaining bits (which will take $O(2^{40})$ steps). Bob sends a message to Alice using the decrypted key which again has a check value. Alice then has to try all of the $2^{40}$ keys (which again takes $O(2^{40})$ steps) until she finds a key that yields the expected check value, and at that point Bob and Alice have agreed on a 128-bit AES key.

Eve would have to brute force all of the messages (which would take $O(2^{80})$ which is assumed to be reasonably secure without quantum computers).

• This is the Merkle Puzzle scheme. Alas, $O(2^{80})$ operations aren't quite as completely out of the realm of possibility as Foon would hope. – poncho Jun 28 '16 at 17:05
• All the bitcoin miners together compute 2^80 SHA-256 invocations in less than a week. – CodesInChaos Jun 28 '16 at 17:10
• Thanks for the name poncho (meant to point out that this was from my crypto textbook which I can't seem to find at the moment to cite... and to also just to provide a citation for CodesInChaos's point (or a link to an answer that includes the citation: crypto.stackexchange.com/questions/13299/… mentions that bitcoin mining at the end of 2015 was doing 2^84.7 SHA-256 per year) – Foon Jun 28 '16 at 19:34

I am currently looking at “A SAT-based Public Key Cryptography Scheme” (PDF) where it is proposed a Public Key Cryptography Scheme based in Boolean Satisfiability Problem which is NP-complete. It seems pretty interesting and the autor also provides an implementation at GitHub. The public key is a SAT formula satisfied by the private key.

• I read that paper about a year ago and I remember there were serious problems with it... I'm busy right now but give me a couple days, I'll read it again and remember what the attack was. – Elliot Gorokhovsky Jun 28 '16 at 16:43