Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
"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." — this is a flaw, I guess. In fact, I have not seen any point in those transformations. You want to protect from copying of what? –  beroal Mar 5 '11 at 20:52
add comment

2 Answers

up vote 3 down vote accepted

What you are looking for is code that works on encrypted data: see A First Glimpse of Cryptography's Holy Grail by Daniele Micciancio in Communication of the ACM 3/2010. Processing arbitrary encrypted data is an open problem. The paper is behind a pay wall but if you are at an academic institution with a computer science department, your library most likely will have it available.

share|improve this answer
1  
All I get when I click on the link is a first glimpse of the article. –  Yuval Filmus Mar 4 '11 at 19:07
1  
"the full text of this article is premium content!" They don't even give us upper-case letters for free. –  TonyK Mar 4 '11 at 19:09
    
Thank you - reading the article right now. –  Michael Burge Mar 4 '11 at 19:31
add comment

Look up "Homomorphic encryption".

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.