Turing and Reverse - Disappearing Cryptography - page 133

build a more general model of what a virus is and how it accom-
plishes its job before you can continue. If you get a complete copy of
the context-free grammar that is carried along by a virus, you might
create a parser that would parse each file and look for something that
came from this grammar. If it was found, then a virus would be iden-
tified. This might work sometimes, but what if the virus modified
the grammar in the same way that the grammars were expanded and
contracted on page 119? The possibilities are endless.
The goal for this chapter is to capture the same theoretical im-
possibility that gives Turing machines their ability to resist attacks
by creating a cipher system that isn't just a cipher. It's a computing
machine that runs forward and backward. The data is hidden as it
runs forward and revealed as it runs backward. If this machine is
as powerful as a Turing machine, then there is at least the theoreti-
cal possibility that the information will never be revealed. Another
computer that could attack all possible machines by reversing them
could never work in all cases.

8.2.1 Reversing Gears
Many computer scientists have been studying reversible computers
for some time, but not for the purpose of hiding information. Revers-
iblemachines have a thermodynamic loophole that implies that they
might become quite useful as CPUs become more and more power-
ful. Ordinary electronic circuits waste some energy every time they
make a decision, but reversible computers don't. This wasted energy
leaves a normal chip as heat, which is why the newest and fastest
CPUs come with their own heat-conducting fins attached to the top.
Some of the fastest machines are cooled by liquid coolants that can
suck away even more heat. The build up of waste heat is a serious
problem—if it isn't removed, the CPU fails.
The original work on reversible computers was very theoretical
and hypothetical. Ed Fredkin offered a type of logic gate that would
not expend energy. [Fre82] Normal gates that take the AND of two
bits are not reversible. For instance, if

x AND y is 1 ,thenboth x and

y can be recovered because both must have been 1 .Butif x AND y

is 0 , then nothing concrete is known about either y

might be a 1 . This makes it impossible to run such a normal gate in
reverse.
The Fredkin gate, on the other hand, does not discard informa-
tion so it can be reversed. Figure 8.1 shows such a gate, and the logic
table that drives it. There are three lines going in and three lines leav-
ing. One of the incoming lines is a control line. If it is on, then the
other two lines are swapped. If it is off, then the other lines are re-

x or y .Either x or