A Harvard study just concluded that the US cannot regulate or control encryption because it is worldwide technology. The following article sees this as the number one reason why encryption is beyond control. In this blog post I will show that the problem is much more fundamental than that.
An example of regulation: It is forbidden to bring knives into the airplane
This regulation could work. Knives are objects. It is possible to define what exactly is a knife. Any object that is hard enough and has a sufficiently suitable shape for stabbing with it, would be considered a knife for the purpose of this regulation. It would even be possible to even construct a computer program that receives inputs about any object and that will determine “yes” or “no”, if it is a knife.
What exactly is a “definition”
This brings us to the core problem of regulation: It is necessary to unambiguously define all terms in the rule. If there are terms in the rule that can impossible be defined, the rule is naturally invalid and cannot be applied.
This brings us to the next question: What exactly is a “definition”?
The definition of the term X is a (predicate) function that accepts any input and unambiguously returns a “yes” or a “no” for the question whether the input is an X. We established earlier on that a definition (function) for the object “knife” would be possible.
Let’s try to produce a definition function for encryption. This is an example of what is considered to be an encryption program (“gpg”):
$ echo "hello world" | gpg --encrypt --armor -r sometest -----BEGIN PGP MESSAGE----- Version: GnuPG v1 hQEMA1+MO4r8dOqPAQgAgzmT1Q+gYncZ0FgkwN5mih3TxHMrHyygE4nSy/z0+RLE 4ljw4vlLBbfxBiFupuuNm8d/hx1MYr+jOKRRQJQ1vjTCh8EZyWhD8I6KVbenhIDD cSNWpcEXoRpbZlSYPrwSPZJ3QKfhu5TkENoYpOLdjJ2jSFyJyvVfZAu1sREQmpNd 8rPltpMltsAWRT6TUBM5S3bs5rauLzlhsXwGy2QYKAnVevmihwvz7MWZ4/b1FPo4 4Ei0WgVIjwIEc6gY/2bSAabJefqptuHtgNDXqTi0NFM3xkYi/jxeC654sh7aIPzF KWtnpPve42cENZUwtHw2s7z6NHIn4dQjxXzRhxUVXdJHAU2eLCaiVYfSOiEwK2zo RpmAAVb9p70DU095Ybrm32vf3V000IbQcusmcgWWNsxF/4DprggVE0i0VG7BAfun HHo99d7W+VA= =IQ5z -----END PGP MESSAGE-----
The gpg program takes as input any text and turns it into an alternative representation of the type that you can see above. By “decrypting” you can reverse the alternative representation back to the original one:
$ echo "-----BEGIN PGP MESSAGE----- > Version: GnuPG v1 > > hQEMA1+MO4r8dOqPAQgAgzmT1Q+gYncZ0FgkwN5mih3TxHMrHyygE4nSy/z0+RLE > 4ljw4vlLBbfxBiFupuuNm8d/hx1MYr+jOKRRQJQ1vjTCh8EZyWhD8I6KVbenhIDD > cSNWpcEXoRpbZlSYPrwSPZJ3QKfhu5TkENoYpOLdjJ2jSFyJyvVfZAu1sREQmpNd > 8rPltpMltsAWRT6TUBM5S3bs5rauLzlhsXwGy2QYKAnVevmihwvz7MWZ4/b1FPo4 > 4Ei0WgVIjwIEc6gY/2bSAabJefqptuHtgNDXqTi0NFM3xkYi/jxeC654sh7aIPzF > KWtnpPve42cENZUwtHw2s7z6NHIn4dQjxXzRhxUVXdJHAU2eLCaiVYfSOiEwK2zo > RpmAAVb9p70DU095Ybrm32vf3V000IbQcusmcgWWNsxF/4DprggVE0i0VG7BAfun > HHo99d7W+VA= > =IQ5z > -----END PGP MESSAGE----- > " | gpg --decrypt gpg: encrypted with 2048-bit RSA key, ID FC74EA8F, created 2016-02-12 "sometest <email@example.com>" hello world
In that sense, encryption consists of two functions that reverse each other. Therefore, a possible definition of encryption is that it is a program that contains two functions that can reverse each other.
Can we construct a predicate function to which we supply any program and which will return “yes” or “no” to the question whether the program is an encryption program?
The halting problem
No. Impossible. Such function cannot be constructed. Alan Turing’s 1936 mathematical proof for the halting problem shows that we cannot even construct a function that can demonstrate if a program will ultimately halt, or else run forever, let alone whether it will ultimately return a “yes” or a “no”.
Therefore, the definition function for encryption cannot be constructed. Consequently, encryption cannot be defined unambiguously.
The impossibility of second-order logic on running programs
Since functions that accept programs as input cannot determine if such the program will actually halt or produce any output at all, it is not possible to define even the most basic characteristics of a set of running programs, that is, the membership function. Example: Is a program member of the set of encryption programs? The answer is generally undefined and this is true about any possible set of running programs.
For example, can we construct a general and unambiguous function that will determine if a program is a member of the set of virus programs? No, it cannot be done.
In other words, valid classifications of programs are not possible, and therefore, the entire domain of programs cannot be defined nor regulated.
The problem of regulation on the internet
Old-world regulators may wish to transpose their methods of regulating physical objects in the physical world to virtual objects on the internet. The problem is that running programs are not physical objects at all. They are simply not of the same nature. This is a general problem. A statement about physical things and a statement about other statements are fundamentally two different things.
In the first case, you could conduct experiments to look for counterexamples for the statement. In the second case, you cannot. Statements about statements do not rest on validating experimentation but on a search for contradictions in the statement. But then again, this already assumes that the statement only uses terms that are unambiguously defined. Otherwise, a statement about statements is meaningless from the get-go.
In other words, how can you regulate encryption programs if it is impossible to define what an encryption program is?