Is there a public key encryption scheme with optimal key size? 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?
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.

Short statement of why I'm skeptical

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.

Symmetrical strength.

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.

Brute forcing symmetric keys

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

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.

Brute forcing private key

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.


The secret key is (often) much smaller than the public key.
Not any number can be the secret key.


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.

Don't brute force

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

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.

Resources

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.