Include FHE as an instantiation of private computation

[eriktaubeneck]

I'll note that I have seen research proposals for doing complicated stuff using FHE, so it's plausible that we might see something in this space at some point. I'm not sure that I'm up for learning lattices though.

Originally posted by @martinthomson in #14 (comment)

[eriktaubeneck]

I thought about including FHE, though I left it out for 2 reasons:

1. it's not clear to me how it could actually work in this setting (typically the party that encrypts is the one that also decrypts, which is difficult in a setting with distributed clients)
2. I wanted to focus on the specific constructions (instantiations?) that have been proposed thus far.

It's also not obvious (at this point) that TEEs require two entities.

Originally posted by @eriktaubeneck in #14 (comment)

[eriktaubeneck]

One design for FHE is to have the record collector (or someone they contract) perform the aggregation using ciphertext. Then a trusted entity decrypts the output.

As for TEEs being multi-party, I found the comments by Nigel here (relayed by you as it happens) very helpful in articulating the high-level constraints. Nigel's two parties are the client and the TEE operator, but as we've observed, this introduces a problem of scale that pushes toward the coordinator-based design described here.

Originally posted by @martinthomson in #14 (comment)

[eriktaubeneck]

Ok, that works for me.

I've been turning over the multi-party idea (wrt this and other parts), and I realized the constraint I've been circling around is the idea that we likely want 2 (or more) parties who are known up front and can be trusted to reach some conditions (typically non-collusion.) This was my concern with the single coordinator model, as one of the parties is the report collector, who is not known up front. I additionally wasn't sure if the client/user would be considered one of these parties, but maybe that point is moot due to the scale.

I'm fine with this addition, and will work in the known up front part elsewhere.

Originally posted by @eriktaubeneck in #14 (comment)

[eriktaubeneck]

I want to be a little pedantic here about how we define things. When we talk about assumption related to security, these assumptions are cryptographic hardness assumptions (mathematical problems that have been studied for a long time) for MPC and assumptions for isolation, which come in so many different forms such as isolation at hardware level or software level).

I think the number of parties and the assumption of non-collusion is a different type of assumption. This is more about the architecture and the trust assumptions we want to make. Once we have chosen this architecture the question is how we define a protocol/technology that achieves our goal within this architecture and trust assumptions. In this sense I would like to distinguish these assumptions for the adversarial and trust model from the assumptions that underly the security properties of the protocols that are already assuming the chosen trust model.

I agree with Erik that TEEs do not require multiple parties and actually that's the main way they are used - one party computes and we assume this party cannot peek in the computation. For the TEEs are not MPC, they are obfuscation - this a cryptographic primitive which has been defined and studies extensively (many impossibility results there), and has exactly the properties that TEEs aim to achieve.

I am a bit unsure about putting FHE and MPC as different objects - MPC is the much broader notion, FHE can be viewed as a specific tool that give you an MPC protocol with minimal interaction, one party can do the computation on the encrypted data and then you need to have distributed decryption.

Originally posted by @marianapr in #14 (comment)

[eriktaubeneck]

@marianapr agreed that the number of parties/non-collusion is a different type of assumption than the architecture and trust assumptions, and I can take another pass to try and call these two assumptions out distinctly. That said, this PR is attempting to suggest that those assumptions don't need to be made in the standard or threat model, but rather by the implementors (web platform vendors.)

Originally posted by @eriktaubeneck in #14 (comment)

[eriktaubeneck]

I moved this all over into a new issue as it's an important conversation and I'm not convinced it's fully resolved.