Alice, Bob, and Penthesilea: mutually suspicious code and data owners

I'm wondering what is known, if anything, about safe interactions between mutually suspicious data and code owners. Here's an Alice and Bob story abou it:

Alice has some data she wishes to keep confidential. Bob has some code which he wishes to keep confidential. Alice is willing to pay Bob for the right to use his code to operate on her data in some way. I'll assume that Alice assumes that Bob's code actually does the Right Thing, and doesn't leak Alice's data in any way. However, Alice doesn't want Bob to have general access to her data, and Bob doesn't want Alice to have general access to his code.

The conventional solutions are for Bob to compile or otherwise obfuscate his code, and then provide it to Alice under a grave and perilous license, or for Alice to upload her data to Bob's system and constrain him by a similarly grave and perilous contract. However, in modern times neither Alice nor Bob may wish the responsibility of owning and running the computers that the application of Bob's code to Alice's data may require.

So they turn to Penthesilea, who will rent out lots of computers to either Alice or Bob at very reasonable prices. However, Penthesilea is not interested in accepting any grave and perilous legal documents, and disclaims all liability for Bad Things happening. What can Alice and Bob do in order to keep each's confidential material safe from the other and (so far as possible) from Penthesilea as well?

Thoughts and (especially) references to related work would be greatly appreciated.

Update: changed "Alice's code" to "Alice's data"

If Penthesilea were running

If Penthesilea were running a capability platform, they could each submit their code with proper confinement to ensure that Bob cannot leak Alice's data, and Alice cannot access Bob's code. They would both have to trust the platform on which the code runs.

Otherwise, Bob could operate on Alice's encrypted data via homomorphic encryption, without Alice ever disclosing what she had.

By naasking at Thu, 2016-06-30 02:20 | login or register to post comments

Tar(1)s and Tymes Forever

As I heard the story, KeyKOS was inspired specifically by actual mutually suspicious code and data owners who were customers of Tymshare in the 1970's.

_{(sorry for the title; if we start with greek mythological references, I'll continue with bad puns about misusing big iron)}

By Dave at Fri, 2016-07-29 14:27 | login or register to post comments

It's possible if very carefully constructed, but impractical

There are relatively few operations that homomorphic encryption can enable doing on encrypted data.

You can set things up in such a way that a few carefully constructed operations can be done in terms of encrypted data only - but it's always terribly inefficient. I can't think of a single case in which operations on encrypted data have ever taken less than hundreds of times the CPU that similar operations on unencrypted data would take.

And I can't think of any general-purpose programming language that's ever had an implementation that can compile to operate on encrypted data; programming such systems for particular logical operations is usually worked out from first principles. You start with (for example) a list of the operations you want and then work backward from it to figure out what your encrypted numeric representation will have to be.

By Ray Dillinger at Tue, 2016-07-05 17:59 | login or register to post comments

No free lunch

You have to pay for strong security properties. Homorphic encryption seems further along than you imply though, supporting addition and multiplication operations, which accounts for most operations on basic data types, ie. integers, pointers, arrays. That can get you pretty far.

The conclusion of the paper I linked also suggests that efficiency has increased significantly in recent years too, so if the problem warrants it, it's probably worth further investigation.

By naasking at Wed, 2016-07-06 01:14 | login or register to post comments

Fixed size

You mention variable-sized datatypes but homomorphic schemes encode elements by projecting them onto group elements: the group has to be chosen first so it is a fixed size. Variable-sized data could be handled by padding it out to the group size but performance does not scale linearly in the size of the group.

In terms of practicality, the largest example that I'm aware of is executing AES. In native code this takes a couple of hundred clock cycles (or 3 cycles per round on x86 with acceleration). Using a homomorphic scheme it takes a number of days to execute. It has not yet reached the point where it is approaching practical applications.

By Andrew Moss at Wed, 2016-07-06 06:14 | login or register to post comments

Last I knew....

You're right that I'm not aware of any developments in the last couple of years.

The last time I knew what you could do with homomorphic encryption, there was a family of representations where you could get multiplication and addition - very slowly - and another, mutually exclusive family of representations you could get binary operations like AND, OR, NOT - that took more time per bit of operand width than the multiplication/addition.

To do anything complex like AES, of course, you have to do both, so you have to encode fixed-size math in terms of pure binary operations, and it gets even slower.

By Ray Dillinger at Wed, 2016-07-06 19:55 | login or register to post comments

I don't get the Penthesilea reference

Can someone explain it to me? How does wishing death upon oneself equate to being the middleman for Alice and Bob? Other than the fact we all know Alice and Bob are really, really horrible people who can't be trusted and therefore make terrible friends!

Regards,
Z-Bo
P.S. - I have no friends named Alice and Bob, and neither should you! ;-)

By Z-Bo at Thu, 2016-07-07 12:55 | login or register to post comments

* Penthesilea was Queen of the Amazons

By johnwcowan at Fri, 2016-07-15 19:26 | login or register to post comments

Lambda the Ultimate

User login

Navigation