Is there anything such as an encrypted Turing machine? More precisely, is there any (encryption) system such that given:

  • a Turing machine: T
  • a public/private key pair

there exists a Turing machine T' (or something Turing machine like) where the tape, states and so on are encrypted using (this method together with the) the public key and such that if, both T and T' are let run for the same number of steps, the state and tape of T' decrypted with the private key equals the state and tape of T.

ie. is there some encryption where one can apply basic operations on the encrypted data?...


closed as too broad by otus, e-sushi Aug 27 '16 at 13:33

Please edit the question to limit it to a specific problem with enough detail to identify an adequate answer. Avoid asking multiple distinct questions at once. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • 2
    $\begingroup$ Yes. We are happy to help you learn all about them on this site as you have questions. That said, this site is not a replacement for your own internet searching. $\endgroup$ – mikeazo Aug 25 '16 at 23:22

Yes. ​ It's called Fully Homomorphic Encryption.

  • $\begingroup$ I keep reading papers about this, and as a guy who makes ASICs, I've never seen a good way to actually make something. I saw a machine that did a whole bunch of ADDs on encrypted data using the IDEA cipher, and the lattice encryption is mathematically nice, but it's impractical from the power perspective. Do you know of anyone who has built something? I generally read the IEEE papers, but perhaps someone closer to the field of cryptography might have a reference for an actual machine that has been built. $\endgroup$ – b degnan Aug 26 '16 at 15:18
  • 1
    $\begingroup$ No. ​ They're still not practical. ​ (in terms of doing anything that couldn't be done more easily another way. ​ If I remember right, a paper I read a few years ago said they were at 30 seconds per gate on a standard computer.) ​ ​ ​ ​ $\endgroup$ – user991 Aug 26 '16 at 15:26

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