Technically speaking, it’s impossible to prove the security of any encryption algorithm. As long as it’s unknown whether P is equivalent to NP, we have no idea of the problems that encryption algorithms depend on for their security can be solved in ways we just haven’t found yet. This can be disconcerting to some because it literally means the only way to “prove” a new encryption algorithm is secure is by gathering a lot of evidence from people who have tried to break it that supports the idea that is is, in fact, hard to break.
But what if an encryption algorithm depended on something other than the difficulty of factoring for security? Let’s assume, for example, that there is a massively large key space that is accessible through a key generator, and that every attack vector on algorithm X that uses keys from this key space degrades into a key space search. In this case, the most efficient way of breaking algorithm X would be the attack vector that narrows the key space search to the smallest possible subset of keys. If the original key space is large enough, searching through this subset will, in theory, still be an incredibly large problem. Even if you reduce a 64-digit number down to a 32-digit number of keys to search through, and even if you can check a billion keys per second, it will take longer than the age of the universe to crack algorithm X.
The problem of proving the security of algorithm X then becomes one of showing that all attack vectors degrade into a key space search. If such a feat is possible, it would mean that no attack vector can possibly take advantage of anything else about the algorithm to mount an effective brute force attack. In other words, if all attack vectors degrade into a key space search, then no attack vector exists which depends on any other problem. If this is the case, and if the key space is sufficiently large, a proof of the security of the algorithm may be possible.
Breaking such an algorithm for a single key would likely require far more time than the age of the universe. From an application-agnostic point of view, this is essentially the holy grail of encryption algorithms. However, other aspects of encryption need to be considered. For example, is it a public key or symmetric key algorithm? Public key algorithms usually depend on the difficulty of factoring large numbers for their security, as is the case with RSA encryption. Symmetric key encryption, on the other hand, may well be able to support such an algorithm as algorithm X.
I am currently working on a paper that specifies and explores the properties of a potential algorithm X. From our calculations so far, it actually would take longer than the age of the universe to brute-force decrypt a message created by this algorithm, assuming, of course, that the key is sufficiently large (at least 16-bytes in this case).
The question we have at this point is whether it is possible to show that every possible attack vector degrades into a key space search. So far, it seems like that is the case, especially when you consider the fact that an attacker is incredibly unlikely to have any of the unencrypted message. Assuming, however, that the attacker does have some of the original message, all attack vectors we have identified that would take advantage of this still degrade into key space searches, though the size of the key space is virtually impossible to calculate for such a case. In other words, under even extremely precarious assumptions, all attack vectors we’ve identified degrade into a key space search at some point.
Our algorithm X may well be one of the most secure encryption algorithms at the moment. What, then, do we do with it?