Alexandre Maret <amaret@infomaniak.ch> says:
[how to do trusted computation on untrusted platforms]
I'm working on a paper, it's one of the technical hurdles on the way to my Eternity DDS eternity service implementation.
rdl, less frustrated with changing from vtwm/athena to KDE, says:
I so far have been approaching it as "Type I (active)" and "Type II (passive)" attackers. In the first case, people lie about the results, in the second, they give you the correct results, but snoop on the data. (For some reason the terminology is kind of lame, but it helps to have some)
There are a bunch of mathematical/cryptographic ways of hiding data from those doing computations on it, at least for a subset of computations. I'm trying to put together a generalized computing model for this which would be turing complete if it can be, although it is not clear it can be. Some operations practically will be a lot more expensive in this model than in the conventional environment, and perhaps to a computation which would require 10 units of conventional secret CPU time, you will need 9 units of secret CPU to encode/decode the data and 41 units of public CPU time. You also need to guard against covert channels, such as the total amount of public CPU time you are requesting as a clue to what you're doing with it. I am confident type II security can be realized with at least a minor amount of performance improvement over purely secret use, assuming public time is free.
Type I security is a lot more difficult to realize in true theoretical sense, but is easier in a practical sense. A simple solution is to do the same computation on a bunch of different remote machines, and as long as they don't collude, you can just make sure they all answered the same, modulo rounding errors and stuff. This isn't the kind of provable security you can conceivably get against type II attackers, but it doesn't have any innate performance hit.
It's possible there are systems which are byzantine fault tolerant to the former kind of attack -- instinctively, you can just split up the computation in small enough pieces that you don't care if it is compromised.
I'm interested in finding a provably secure computation-checksum technique. I think there are most likely reductions for a lot of problems to things which can be verified, and again, my goal is to have a Turing-complete model of computation with this property.
[can cryptography be helpful?]
It's as much a theory of computation problem as anything else, once you have some functions through which you can carry some operations.
Most of the stuff I've done so far focuses on the graph coloring problem. I'm probably going to finish a quick version which can only deal with a subset of problems, then work on a general model.
[paper availability issues]
Yes, it will be publically available. It will be available when it's closer to done; I will send something to cypherpunks about it, and I'll put it up on the web somewhere. If it doesn't suck, and I can convince someone at LCS-CIS of this/to be a co-author/etc., I might try to get it published.
Anyone know anything very relevant to this? I've mostly just started on the research (my current exciting project has been Linux Fibre Channel and making a bloody fast, yet maybe secure, yet small cipher for an on board processor), and pointers would be useful. It isn't as hard a problem as I first thought, though. This seems like the kind of thing everyone's favorite judge-threatening tree-hugger-nose-mac-10-inserting gun-hoarding old-man-on-the-mountain would have done N years ago :) [flames, fan. gasoline. rdx...] so I'd rather not reinvent the wheel more than once or twice. Ryan (getting dangerously close to having a working Eternity DDS demo, and wondering if FC98 will be on mbone, particularly the solar eclipse, since even if he had the money to go, it's in the middle of next semester, and disappearing for a week would kind of be difficult, although not at all impossible of someone wants to pay for me to go...ahh, but there's always next year) -- Ryan Lackey rdl@mit.edu http://mit.edu/rdl/