Idea: correction words for truncated weights

[cjpatton]

The FLP is run on the encoded measurement, which in general is longer than the truncated measurement. In some cases it might be much longer, e.g., for the Sum circuit, the encoded measurement is several field elements, while the truncated measurement is just one.

The encoded measurement is only needed when we verify the FLP. Suppose we modified Mastic as follows:

1. Include shares of the encoded measurement, i.e., flp.encode(weight), in the input shares.
2. Instead of setting beta to be the encoded measurement share, set beta to be the truncated measurement, i.e., beta = flp.truncate(flp.encode(weight)).
3. Extend the path consistency check to make sure the left and right children of the root sum up to the encoded measurement.

[jimouris]

How about:

1. vidpf.gen takes both beta and beta_truncated and sets beta at level 0, and beta_truncated at all other levels.
2. vidpf.eval:
   • level > 0: normal path checks (this would now check beta_truncated though)
   • level = 0: truncate beta to get beta_truncated and then perform the check.

[cjpatton]

I think that works. I believe we'll need to invoke flp.truncate() from vidpf.eval() in order to compute the path checks correctly. Alternatively, we could just pass beta to gen() and have it call flp.truncate() as well, which would be a little simpler.

It's sad that this means vidpf is no longer "black box" in the sense that its functionality depends on the details of flp. It would be nice if we could avoid this.

I wonder if we could do something like this: include shares of beta in the VDAF input shares and pass beta_trucnated to gen() and eval()? We would need to connect these somehow to make sure the beta in the input shares is consistent with the payload of the VIDPF output.

[jimouris]

I wonder if we could do something like this: include shares of beta in the VDAF input shares and pass beta_trucnated to gen() and eval()? We would need to connect these somehow to make sure the beta in the input shares is consistent with the payload of the VIDPF output.

Just to rephrase, the VIDPF beta will be the truncated one (at all levels) and then the VDAF will be responsible for checking if truncate(beta) is equal to the truncated beta from VIDPF at level 0?

Theoretically, this could work and keep VIDPF as a black box but we need to be sure we cannot find beta and beta' such that truncate(beta) == truncate(beta'). I guess this is important to be able to guarantee regardless of which of the two options we choose.

[cjpatton]

Excellent point. I think this property ought to hold for all weight types we're considering so far.

[jimouris]

Almost done but I ran into an issue. In prep_init we have access to both beta_share (from input share) and truncated_beta_share (from VIDPF) but these are shares, not the whole values. So how can we check that truncate(beta) == truncated_beta? Given access only to shares it won't work (e.g., truncate(beta_share) != truncated_beta_share).

[cjpatton]

Hmmmm yeah you're right. I don't think that quite works.

[cjpatton]

I'm not sure we should closet his -- It seems like we can't make this black box, but I think it might still worth doing.

[cjpatton]

(I'd like to keep this open until I've had time to think it through.)

[cjpatton]

The idea of #109 is to apply VIDPF to the truncated weight and FLP to the untruncated weight. We would "link" them by incorporating the untruncated weight into the payload check.

This would allow for the following "attack": a client can modify a report by "resharing" the FLP weight shares, and the aggregators would accept the modified report. This isn't an attack against our current definition of robustness (ia.cr/2023/130), as the aggregators would still compute the same output shares. However, we're worried this could constitute an attack in the higher level protocol.

Our current approach isn't vulnerable to this attack because the sharing of the weight is determined by the VIDPF.