MAC-based validation is broken because it uses semi-honest reveal protocol

[akoshelev]

As part of validation process, accumulators run the check zero protocol, implemented here.

This protocol supports semi-honest security only because it runs the semi-honest reveal, so an active adversary can cheat and send a broken share to its peer and make it think that rv == ZERO.

We should close that gap and use malicious reveal instead

[andyleiserson]

I'm not sure that even a malicious reveal is sufficient. I pushed a test case (using the new support for simulating malicious behavior) in #1205. With our current implementation, a malicious helper is not limited to choosing share values for a reveal operation based on shares received from other helpers during the reveal -- the malicious helper can choose the share value it sends in the r * v multiply that precedes the reveal based on shares received from other helpers as part of the reveal operation (because helpers running ahead of each other is restricted only by data dependencies, i.e., helpers can generally get up to two steps ahead).

The r * v multiply is semi-honest, but (1) that's what the paper specifies, (2) it's not clear how to use a malicious multiply here since this is part of the verification step of the malicious protocol (i.e. a "chicken and egg" problem).

I think we need some kind of synchronization within the check zero protocol to prevent this. Although I'm nervous about other places that there could be similar problems.

There is an additional difference in our implementation vs. the paper. In the paper, check-zero uses an "open" operation, which in addition to what we're contemplating for the malicious reveal, sends all the revealed values to the other two helpers so it's guaranteed that if any helper aborts, they all abort. (Currently, only two out of three helpers in the test case report that the zero check passes, but that's unrelated to the question of verifying the revealed values match -- the helper that reports the zero check failure is H1, the malicious helper, because its copy of Sh3 isn't updated to match the tampered value it sent to H3.)