Are there any public key cryptographic systems whose hardness assumptions don't involve number theoretic problems?
$\begingroup$
$\endgroup$
7
-
$\begingroup$ Does the LWE count as a number theoretic problem? $\endgroup$– Hilder Vitor Lima PereiraCommented Jun 27, 2016 at 16:28
-
$\begingroup$ 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. $\endgroup$– Elliot GorokhovskyCommented Jun 27, 2016 at 16:30
-
$\begingroup$ How about McEliece? It's hardness is based on decoding a general linear code. $\endgroup$– mikeazoCommented Jun 27, 2016 at 16:37
-
$\begingroup$ That would certainly count. $\endgroup$– Elliot GorokhovskyCommented Jun 27, 2016 at 16:38
-
3$\begingroup$ @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) $\endgroup$– CodesInChaosCommented Jun 27, 2016 at 21:13
|
Show 2 more comments
4 Answers
$\begingroup$
$\endgroup$
0
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.
$\begingroup$
$\endgroup$
5
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)
-
1$\begingroup$ Hash signatures are the only signatures I'd trust for long term security since they only involve unstructured crypto. $\endgroup$ Commented Jun 27, 2016 at 17:12
-
1$\begingroup$ @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... $\endgroup$– ponchoCommented Jun 27, 2016 at 17:28
-
$\begingroup$ hmm... @CodesInChaos I wonder why bitcoin didn't choose HBS then? Considering it's supposed to be secure essentially forever. $\endgroup$ Commented Jun 27, 2016 at 20:05
-
2$\begingroup$ @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. $\endgroup$ Commented Jun 27, 2016 at 21:09
-
1$\begingroup$ @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 $\endgroup$– ponchoCommented Jun 27, 2016 at 21:19
$\begingroup$
$\endgroup$
3
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).
-
2$\begingroup$ 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. $\endgroup$– ponchoCommented Jun 28, 2016 at 17:05
-
$\begingroup$ All the bitcoin miners together compute 2^80 SHA-256 invocations in less than a week. $\endgroup$ Commented Jun 28, 2016 at 17:10
-
$\begingroup$ 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) $\endgroup$– FoonCommented Jun 28, 2016 at 19:34
$\begingroup$
$\endgroup$
1
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.
-
$\begingroup$ 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. $\endgroup$ Commented Jun 28, 2016 at 16:43