3 ms·

Also you cannot do queries on the encrypted db without being able to observe the results. E.g. if you are able to initiate a query on a fraction of the data, yo

Also you cannot do queries on the encrypted db without being able to observe the results. E.g. if you are able to initiate a query on a fraction of the data, you already have access to that fraction of the data. And you cannot initiate a meaningful query if you are a server-side observer. Of course, active adversaries could give wrong results (wrong pieces of the index) back, we didn't quite consider yet which problems that could cause.

roymurdock 11y ago
Is there a reason that you did not cite Enigma in your list of notable works? They solve the adversary problem by splitting tasks among a network of nodes that post their intermediate work to a blockchain where it can be verified for accuracy: Very recently, Baum et al. developed a publicly auditable secure MPC system that ensures correctness, even when all computing nodes are covertly malicious, or all but a single node are actively malicious [18]. Their state-of-the-art results are based on a variation of SPDZ (pronounced speedz) [19] and depend on a public append-only bulletin board, which stores the trail of each computation. This allows any auditing party to check the output is correct by comparing it to the public ledger’s trail of proofs. Our system uses the blockchain as the bulletin board, thus our overall security is reduced to that of the hosting blockchain. I'm not a db or crypto expert, but this seems like a promising solution to the active adversary problem if you have an honest, healthy blockchain that is incentivized correctly.
- michwill 11y ago
  Yeah, actually that is true. Enigma worths mentioning as one of MPC references. Looks like Enigma would have challenges in many practical environments (mainly because it involves a lot of small interactions between nodes, so should be affected by latency). So, it's more like a way to build "Etherium of private computations". But, as you pointed out, it can have good clues how to solve the problem of active adversaries!
teraflop 11y ago
> And you cannot initiate a meaningful query if you are a server-side observer. But that's only true if you consider the database in isolation. It's a very bad assumption to make when using it as a component of a larger system! Let's say you build a social networking service which uses ZeroDB to store its data; I'm an attacker who has access to the database server. There are all kinds of ways I can gain indirect control over the requests that users make to the service. What if I convince two different users to open a web page containing something like "<img src='https://supersecuresocialnetwork.com/friend-list.jsp'>" https://supersecuresocialnetwork.com/friend-list.jsp'>"? I've just triggered an operation that will cause the app servers to request tree nodes corresponding to those users' accounts, and those of their friends, at predictable times. I can correlate the requests and determine with some level of confidence whether the users are mutual friends, all without being able to see a single byte of plaintext. If the service is publicly available and I can register my own accounts, that opens up another huge category of attacks. My point is that you're making an awful lot of assumptions about what strategy an attacker will use. If you don't have provable security against an entire class of attacks (e.g. cryptographic properties like IND-CPA) then the burden is on you to be more imaginative than whoever is trying to compromise your system.

roymurdock 11y ago

Is there a reason that you did not cite Enigma in your list of notable works? They solve the adversary problem by splitting tasks among a network of nodes that post their intermediate work to a blockchain where it can be verified for accuracy: Very recently, Baum et al. developed a publicly auditable secure MPC system that ensures correctness, even when all computing nodes are covertly malicious, or all but a single node are actively malicious [18]. Their state-of-the-art results are based on a variation of SPDZ (pronounced speedz) [19] and depend on a public append-only bulletin board, which stores the trail of each computation. This allows any auditing party to check the output is correct by comparing it to the public ledger’s trail of proofs. Our system uses the blockchain as the bulletin board, thus our overall security is reduced to that of the hosting blockchain. I'm not a db or crypto expert, but this seems like a promising solution to the active adversary problem if you have an honest, healthy blockchain that is incentivized correctly.

michwill 11y ago
Yeah, actually that is true. Enigma worths mentioning as one of MPC references. Looks like Enigma would have challenges in many practical environments (mainly because it involves a lot of small interactions between nodes, so should be affected by latency). So, it's more like a way to build "Etherium of private computations". But, as you pointed out, it can have good clues how to solve the problem of active adversaries!

teraflop 11y ago

> And you cannot initiate a meaningful query if you are a server-side observer. But that's only true if you consider the database in isolation. It's a very bad assumption to make when using it as a component of a larger system! Let's say you build a social networking service which uses ZeroDB to store its data; I'm an attacker who has access to the database server. There are all kinds of ways I can gain indirect control over the requests that users make to the service. What if I convince two different users to open a web page containing something like "<img src='https://supersecuresocialnetwork.com/friend-list.jsp'>" https://supersecuresocialnetwork.com/friend-list.jsp'>"? I've just triggered an operation that will cause the app servers to request tree nodes corresponding to those users' accounts, and those of their friends, at predictable times. I can correlate the requests and determine with some level of confidence whether the users are mutual friends, all without being able to see a single byte of plaintext. If the service is publicly available and I can register my own accounts, that opens up another huge category of attacks. My point is that you're making an awful lot of assumptions about what strategy an attacker will use. If you don't have provable security against an entire class of attacks (e.g. cryptographic properties like IND-CPA) then the burden is on you to be more imaginative than whoever is trying to compromise your system.