0
$\begingroup$

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?...

Improve this question
$\endgroup$
1
  • 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, 2016 at 23:22

1 Answer 1

Reset to default
1
$\begingroup$

Yes. ​ It's called Fully Homomorphic Encryption.

Improve this answer
$\endgroup$
2
  • $\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, 2016 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, 2016 at 15:26

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