[Math] Running ‘Encrypted Code’ on a Computer

algorithmscomputer sciencecryptography

Alice released a new version of her software for removing red-eye from pictures. However, she wants to protect her secret algorithm from disassemblers and such while still letting her customers remove red-eye from pictures.

She looks at standard encryption:

  1. A message is encrypted with a key and sent across the wire
  2. If some nefarious onlooker is dropping eaves on the network, all he gets is a garbled mess of bits.
  3. When it arrives, it's decrypted by someone. There are a variety of ways to distribute keys, etc. but the person you send your message to should be able to decrypt it somehow in all of them.

And wonders if something like this might be possible:

  1. The user wants to remove red-eye from his family photo. He 'encrypts' the image with a key of some sort.
  2. The software contains an 'encrypted algorithm' that operates only on 'encrypted data'. If you try to disassemble it and see what it's doing, it's like trying to read encrypted bits – it's garbled and you get no information from it.
  3. When the image is done, the client 'decrypts' his image. You might signal that the image is done by seeing if a bit is set somewhere, by trying to decrypt it every iteration and seeing if this is valid, or even having the last instruction in the 'encrypted' data-space decrypt it into regular data again.

You can probably think of a few variations: Maybe the client has to request a public key from a website somewhere and then ask Alice's website to decrypt it with her private key. But the important properties are that

  1. An onlooker can only determine the state of the image at 2 times: Before we request red-eye removal, and after the algorithm is done removing it.
  2. All the computation has to be done client-side. Sure, Alice could expose a web service somewhere that removes red-eye in images for you if you provide your product key, but that's not what I'm asking.
  3. Red-eye removal was just an example; you should be able to transform any sufficiently general type of algorithm into one of these special 'encrypted algorithms.'

My questions are: Does this concept already exist, and if so are there any standard references? Is there some technical flaw that I didn't consider? Surely if it worked like I described then it would be used for copy-protection in software(even though 'locking' an entire piece of software is very different from locking a theoretical algorithm).

Thank you for your time,

— Michael Burge

Best Answer

Look up "Homomorphic encryption".

Related Question