Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It only takes a minute to sign up.
Sign up to join this community
Symmetric encryption schemes such as AES have known security levels equal to their key sizes (i.e. breaking an encryption with an $n$ bit key needs about $2^n$ work steps). Elliptic curve encryption gets halfway towards optimal: its security is half the size of the public key.
Are there any public key encryption schemes known which have security level equal to size of public key? If not, do any do better than ECC?
For any cryptosystem based on finite cyclic groups, no, since the baby-step-giant-step algorithm has a complexity of O(sqrt(n)) and works for any finite cyclic group
I am skeptical that there will ever be a public key system that has the property you are seeking. Of course it would be possible to wrap a public key system up inside a symmetrical system to get that effect. For example, I could use 4096 bit RSA key which I protect with a 56 bit DES key, thus giving the system the strength of that, weaker, 56 bit symmetrical key. But leaving such things aside, I think that public keys will always be "special" in that their size in bits is not a direct representation of their strength in bits.
Not just any number can be a secret key. So even if the worst case for the attacker who has to just randomly guess at candidate secret keys, they can rule out a large number of things before they have to start guessing.
To understand why I'm skeptical, it is important to understand why strength == keysize works for symmetrical systems. Only then can we look at what is different about public key systems.
Alice picks, completely at random, a 128-bit key, k for AES. If AES isn't broken, Oscar's best hope is to simply guess k. (Actually, Oscar's best hope is to not attack Alice's key at all and instead try to get the message before it's encrypted or after it is decrypted or something else altogether.) If Alice used a cryptographically appropriate random number generator to pick k then k will be any one of 2^128 numbers, each with equal probability.
We are assuming through all of this (and this is a very fair assumption) that Oscar has a way of testing a key that will tell him whether or not he has the right one. In order to be sure of finding Alice's key, k, Oscar would need to make at most 2^128 guesses. On average, he only needs to check about half of those, so it is 2^127 guesses.
This works out that way because any candidate guess is as like (well, actually unlikely) to be the right one as any other. There is nothing to prefer certain guesses to others.
There is also no way (if everything else is designed properly) to get any information about k from looking at the encrypted traffic. There also should be no way to get any information about the key even if you know what some encrypted messages decrypt to. And finally (and this has been a really hot topic in practical cryptographic implementations), there should be no way to get any information about the key even if Oscar can get Alice to decrypt messages that he creates. In sort, a properly designed symmetrical system reveals absolutely no information about the key other than the fact that it is, say a 128 bits long.
So that has all been a long winded way of driving home the point that Oscar's best attack is to just guess at keys and any 128-bit number is as likely as another other.
Public keys are nothing like symmetrical keys. We've got the public key, p and the secret key, s. Alice picks a secret key, s, and calculates p based on s. She then publishes p. It is crucial that p is calculated from s. For these systems to work, there has to be a special mathematical relationship between p and s. For RSA s can be a pair of really big prime numbers and p can be something like the product of those two primes. (For the rest of this discussion I'm going to pretend that p is the product of the two primes, that this isn't quite how RSA really works.)
As you probably know, Alice can solve problems using s that cannot be done with knowledge of p alone, but p can be used to create such problems and p can be used to verify that the problems have been successfully solved.
The strength of the system depends on (among other things) that it be hard to compute s from p.
The analogy, I suppose, of a brute force attack on an RSA public modulus (to discover the primes) would be to take primes at random that are about the appropriate size (so half as many bits as p) and see if they divide p evenly. So here you see that a brute force attack involves far far fewer guesses than the size of p. If p is 2048 bit number, then the factors of p will each be around 1024 bit numbers.
Furthermore, not every 1024 bit number is prime; only about 1 in 300 of them are prime. (I'll say 1 out of every 256 so make rounding easier in my next step.) So for a brute force attack on a 2048 bit public key, Oscar "only" has to make 2^1016 guesses.
Now that is an awful lot of guesses, and would be more than sufficient. If this were the best way to discover s, then you would only need RSA keys about about 280 bits to get 128 bit security. But of course, this is an incredibly stupid way of attacking RSA.
However, there are two points from that simple example.
Either one of these mean that in terms of just blind guessing (brute force) the number of guesses necessary will be substantially shorter than the actual size of the public key.
There are ways to try to go from p to s that are better than just doing that kind of random guessing. In the case of RSA, there are much better ways. In terms of the discrete logarithm problem in integer fields (for Diffie-Hellmen public key stuff), there are much better ways than brute force guessing to discover the private keys as well. Indeed, if the private key isn't chosen with considerable care there are enormous shortcuts that Oscar can take.
The best we can hope for is where guessing is the best strategy, but it will still be guessing in a limited domain. It won't be every possible number the size of the public key. Even though ECC and DH are based on the discrete logarithm problem (DLP), they are the DLP in different fields, and ECC is holding up remarkably well.
I don't know if we have theorems that prove that ECC will continue to hold up. It isn't perfectly at this "best case", but so far it seems to be close to that.
I really recommend the book Understanding Cryptography by Christof Paar and Jan Pelzl. Chapters 8 and 9 do an outstanding job of explaining ECC and the kinds of attacks that might exist against it. The book is written well enough that it can genuinely be used for self study.
"Key size" or "number of bits" isn't the best way to measure security. Those are intermediate numbers. The true question at the heart of the matter is "how long can I expect method X to keep my secrets safe?" From there, we walk backwards to determine what adjustments or parameters we can change while using that particular method, we look at what attackers are capable of today, how attacks have changed so far since the discovery of the method, and estimate what the attackers might be capable of throughout the future. Each of those security methods is unique. Determining the useful life of any of these algorithms involves a lot of predicting the future, and is by no means a linear curve.
Current estimates of determining algorithm strength have come by comparing attack efforts. An experimenter determines the amount of computational work required to break x-bit RSA, and the amount of work required to brute force 56-bit DES. If it takes $10^{70}$ (a made-up-for-this-example number) CPU clock cycles to crack both DES and 512-bit RSA, then they could claim 512-bit RSA offers the equivalent to 56 bit security (they aren't, this is just a made-up example.)
But that's only one test at one point in time. Tomorrow, advances in differential cryptography could reduce the attack on DES from $2^{56}$ effort to $2^{40}$ effort. Or a novel advance in factoring could reduce the attack on RSA from $2^{56}$ to $2^{30}$. A quantum computer with Shor's algorithm could even reduce RSA to a solvable problem. We simply don't know what the future holds for any algorithm.
So as far as "optimal key size" goes, don't aim for "number of bits". Aim instead for "I need 30 years of protection, what might give that to me today?"
In public-key encryption, the public key can be seen as description of an instance of a mathematical problem that we assume to be intractable plus some additional information in most cases. The secret key is something that allows a user to solve this very instance of the problem efficiently. So, the public key size solely depends on the information needed to describe the problem. It is obvious that the best security we can hope to achieve depends on the entropy of the secret key, as this determines the complexity of a generic brute-force attack.
I am not aware of any results like for a certain hardness of a problem, the description has to be bigger than $x$. However, you might find some results in this direction in literature on complexity theory. So far, for all schemes I know the description of a problem instance is much bigger than the hint that allows to solve it, i.e. the secret key.
