From hnash at mason1.gmu.edu  Thu Jul 29 20:07:19 1993
From: hnash at mason1.gmu.edu (hnash at mason1.gmu.edu)
Date: Thu, 29 Jul 93 20:07:19 PDT
Subject: TECH: encrypted computer?
Message-ID: <9307300306.AA20191@mason1.gmu.edu>


Peter Baumbach wrote:
>I don't
>want the owner to be able to decrypt the executable and run 
>that, he has to run it encrypted.

I've been thinking about this also.  I think your idea boils 
down to an encoding for software which allows execution but not 
modification.  This could be called a tamper-proof software 
encoding.  Such an encoding would have all sorts of 
applications.  For example:

- public key encryption (a public key is simply a tamper-proof 
encoding of a private encryption algorithm).  
- distribution of software with advertisements or credits 
permanently attached.  
- distribution of software that requires "fuel" consisting of 
certificates signed by the manufacturer.  
- computer viruses that utilize secret information.  

It's clear that the state variables internal to the algorithm 
must remain encrypted.  If any of the *original* state variables 
were revealed, the algorithm could be inferred from changes to 
these variables.  Therefore, tamper-proof software requires 
processing of encrypted data.  The problem would be solved by a 
computationally complete set of functions (ex: NAND) which could 
produce encrypted output from encrypted input without revealing 
decrypted input or output.  It's a simple problem, but as far as 
I know it hasn't been solved.  

I have tried to solve this problem in several different ways, 
without much success.  I found one paper entitled "Processing 
Encrypted Data" (comm. of ACM v.30 n.9 1987), which reported 
some very rudimentary results, but which commented intriguingly:

"The Department of Defense has invested considerable efforts in 
recent years in solving this problem ... but the results of this 
efforts have not been made public."


-------------- Yours Truly, ][adon Nash --------------------------------
 in founding a family or a state, or acquiring fame even, we are mortal;
 but in dealing with truth we are immortal, and need fear no change nor
 accident. --------------------------------- ][enry David Thoreau, 1850